電大數(shù)據(jù)結(jié)構(gòu)本形成性考核冊(cè)作業(yè)

1、數(shù)據(jù)結(jié)構(gòu)（本）形成性考核作業(yè)冊(cè)使用說明本作業(yè)冊(cè)是中央廣播電視大學(xué)計(jì)算機(jī)科與技術(shù)專業(yè)（本科）數(shù)據(jù)結(jié)構(gòu)（本）課程形成性考核的依據(jù)，與數(shù)據(jù)結(jié)構(gòu)（本科） 教材（李偉生主編，中央電大出版社出版）配套使用。數(shù)據(jù)結(jié)構(gòu)（本）課程是中央廣播電視大學(xué)計(jì)算機(jī)科學(xué)技術(shù)專業(yè)的一門統(tǒng)設(shè)必修、學(xué)位課程， 4 學(xué)分，共 72 學(xué)時(shí)。其中實(shí)驗(yàn)24 學(xué)時(shí)，開設(shè)一學(xué)期。本課程的特點(diǎn)是綜合性、實(shí)踐性強(qiáng)，內(nèi)容抽象，在專業(yè)中具有承上啟下的作用。因此，在學(xué)習(xí)本課程時(shí)，要注意理論聯(lián)系實(shí)際，結(jié)合教學(xué)內(nèi)容進(jìn)行上機(jī)實(shí)踐，認(rèn)真完成作業(yè)和實(shí)驗(yàn)內(nèi)容。本課程的總成績(jī)按百分制記分， 其中形成性考核所占的比例為30%， 終結(jié)性考試占 70 （閉卷，答題時(shí)限為

2、 90 分鐘） 。課程總成績(jī)達(dá)到 60 分及以上者為合格，可以獲得該課程的學(xué)分。本課程的學(xué)位課程學(xué)分為 70 分，即課程總成績(jī)達(dá)到 70 分及以上者有資格申請(qǐng)專業(yè)學(xué)位。本課程共設(shè)計(jì)了 4 次形考作業(yè)，每次形考作業(yè)均包括實(shí)驗(yàn)內(nèi)容，由各地電大根據(jù)學(xué)生對(duì)作業(yè)中各種題型練習(xí)和實(shí)驗(yàn)的完成情況進(jìn)行考核。對(duì)于實(shí)驗(yàn)內(nèi)容要求按實(shí)驗(yàn)要求認(rèn)真完成，并提交實(shí)驗(yàn)報(bào)告。數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)作業(yè) 1（本部分作業(yè)覆蓋教材第1-2 章的內(nèi)容）一、單項(xiàng)選擇題1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ） 。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu).緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部機(jī)構(gòu)2下列說法中，不正確的是（ ）

3、 。A.數(shù)據(jù)元素是數(shù)據(jù)的基本單位B.數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識(shí)單位C.數(shù)據(jù)可有若干個(gè)數(shù)據(jù)元素構(gòu)成D.數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成3一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一個(gè)（ ） 。A數(shù)據(jù)項(xiàng)B .數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu) D .數(shù)據(jù)類型4數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（ ） 。A.存儲(chǔ)結(jié)構(gòu)B .物理結(jié)構(gòu)C.邏輯結(jié)構(gòu)D.物理和存儲(chǔ)結(jié)構(gòu)5下列的敘述中，不屬于算法特性的是（） 。A有窮性B .輸入性C.可行性D.可讀性6 算法分析的目的是（ ） 。A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B 研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn) D .分析算法的易懂性和文檔性7數(shù)據(jù)結(jié)構(gòu)是一門研究計(jì)算機(jī)中（ ）對(duì)象及其關(guān)

4、系的科學(xué)。A.數(shù)值運(yùn)算B .非數(shù)值運(yùn)算C.集合D.非集合）有關(guān)。8算法的時(shí)間復(fù)雜度與（A 所使用的計(jì)算機(jī)B 與計(jì)算機(jī)的操作系統(tǒng)C.與算法本身 D .與數(shù)據(jù)結(jié)構(gòu)9設(shè)有一個(gè)長(zhǎng)度為n 的順序表，要在第i 個(gè)元素之前（也就是插入元素作為新表的第 i 個(gè)元素） ，則移動(dòng)元素個(gè)數(shù)為（ ） 。A n-i+1 B n-i C n-i-1 D i10 設(shè)有一個(gè)長(zhǎng)度為 n 的順序表，要?jiǎng)h除第i 個(gè)元素移動(dòng)元素的個(gè)數(shù)為（）。A n-i+1 B n-i C n-i-1 D i11 在一個(gè)單鏈表中， p、 q 分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q 所指結(jié)點(diǎn)是 p 所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q 所指結(jié)點(diǎn)，可用語句（ ）A

5、p=q->nextB p->next=qC p->next=q nextD q->next=NULL12 在一個(gè)單鏈表中p 所指結(jié)點(diǎn)之后插入一個(gè)s 所指的結(jié)點(diǎn)時(shí)，可執(zhí)行A p->next= s; snext= p next B p->next=s next;C p=s->nexts->next=p->next; p->next=s;13 非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（）（設(shè)頭指針為head,指針 p 指向尾結(jié)點(diǎn)）A. P->next= =NULL BC P->next= =head D14 鏈表不具有的特點(diǎn)是（ ）A 可

6、隨機(jī)訪問任一元素 P= =NULL P= = headB 插入刪除不需要移動(dòng)元素C 不必事先估計(jì)存儲(chǔ)空間 D 所需空間與線性表長(zhǎng)度成正比15 帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（ ） （設(shè)頭指針為 head ） 。A head = =NULLB head->next= =NULLC head->next= =headD head!=NULL16在一個(gè)單鏈表中，p、 q 分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q 所指結(jié)點(diǎn)是 p 所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q 所指結(jié)點(diǎn)，可用語句（ ） 。A p=q->nextB p->next=qC p->next=q->nextD q-

7、>next=NULL17 在一個(gè)鏈隊(duì)中，假設(shè)f 和 r 分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（ ） 。A r=f->next;B r=r->next;C f=f->next;D f=r->next;18 在一個(gè)鏈隊(duì)中，假設(shè)f 和 r 分別為隊(duì)頭和隊(duì)尾指針，則插入 s 所指結(jié)點(diǎn)的運(yùn)算為（ ） 。A f->next=s; f=s;B r->next=s;r=s;C s->next=r;r=s;D s->next=f;f=s;19 . 一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是90，每個(gè)元素的長(zhǎng)度為2 ，則第6個(gè)元素的地址是(A. 98 B . 1

8、00 C . 102 D . 10620 .有關(guān)線性表的正確說法是()。A.每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B.線性表至少要求一個(gè)元素C.表中的元素必須按由小到大或由大到下排序D.除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼二、填空題1 .在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)結(jié)構(gòu)的線性表中，向第 i(1 i n+1)個(gè)元素之 前插入新元素時(shí)，需向后移動(dòng) 個(gè)數(shù)據(jù)元素。2 .從長(zhǎng)度為n的采用順序存儲(chǔ)結(jié)構(gòu)的線性表中刪除第i(1 i n+1)個(gè)元素，需向前移動(dòng) 個(gè)元素。3 .數(shù)據(jù)結(jié)構(gòu)按結(jié)點(diǎn)間的關(guān)系，可分為4種邏輯結(jié) 構(gòu)：、4 .數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為 或。5 .除了

9、第1個(gè)和最后一個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)和后繼 結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為 ,每個(gè)結(jié)點(diǎn)可有任意多個(gè)前驅(qū)和后繼結(jié)點(diǎn)數(shù) 的結(jié)構(gòu)為。6 . 算 法 的 5 個(gè) 重 要 特 性7 .數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為 結(jié)構(gòu)。8 .數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為 結(jié)構(gòu)。9 .數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為 結(jié)構(gòu)。10 .要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的 比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為 和。11 .在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè) s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 口 p->next=s;的操作。12 .設(shè)有一個(gè)頭指針為head的單向循環(huán)鏈

10、表，p指向鏈表中的結(jié)點(diǎn)，若 p->next= =,則 p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。13 .在一個(gè)單向鏈表中，要?jiǎng)h除 p所指結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的前 驅(qū)結(jié)點(diǎn)。則可以用操作 。14 .設(shè)有一個(gè)頭指針為 head的單向鏈表，p指向表中某一個(gè)結(jié)點(diǎn)，且有 p->next= =NULL,通過操作 就可使該單向鏈表構(gòu)造成單向循環(huán) 鏈表。15 .每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域的線性表叫 。16 .線性表具有 和 兩種存儲(chǔ)結(jié)構(gòu)。17 .數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的關(guān)系 無關(guān)，是獨(dú)立于計(jì)算機(jī)的。18 .在雙向循環(huán)鏈表的每個(gè)結(jié)點(diǎn)中包含 指針域，其中next指向它 的, prior 指向它的

11、,而頭結(jié)點(diǎn)的prior 指 向,尾結(jié)點(diǎn)的next指向。19 .單向循環(huán)鏈表是單向鏈表的一種擴(kuò)充，當(dāng)單向鏈表帶有頭結(jié)點(diǎn)時(shí)，把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為 ;當(dāng)單向鏈表不帶頭 結(jié)點(diǎn)時(shí)，則把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為指向。20 .線性鏈表的邏輯關(guān)系時(shí)通過每個(gè)結(jié)點(diǎn)指針域中的指針來表示的。其邏輯順序和物理存儲(chǔ)順序不再一致，而是一種 存儲(chǔ)結(jié)構(gòu)，又稱 為。三、問答題1 .簡(jiǎn)述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的區(qū)別與聯(lián)系，它們?nèi)绾斡绊懰惴ǖ脑O(shè)計(jì)與實(shí)現(xiàn)？2 .解釋順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)，并比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)?存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。3 .什么情況下用順序表比鏈表好？4 .頭指針、頭結(jié)點(diǎn)、第一個(gè)

12、結(jié)點(diǎn)(或稱首元結(jié)點(diǎn))的區(qū)別是什么？5 .解釋帶頭結(jié)點(diǎn)的單鏈表和不帶頭結(jié)點(diǎn)的單鏈表的區(qū)別。四、程序填空題1.下列是用尾插法建立帶頭結(jié)點(diǎn)的且有n個(gè)結(jié)點(diǎn)的單向鏈表的算法，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z句。NODE *create1(n)/*對(duì)線，性表(1,2,.,n),建立帶頭結(jié)點(diǎn)的單向鏈表 */NODE *head,*p,*q;int i;p=(NODE *)malloc(sizeof(NODE);head=p; q=p; p->next=NULL;for(i=1;i<=n;i+)p=(NODE *)malloc(sizeof(NODE);(1)；(3) ;(4) ;return(head);

13、2.下列是用頭插法建立帶頭結(jié)點(diǎn)的且有 n個(gè)結(jié)點(diǎn)的單向鏈表的算法，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z句。NODE *create2(n)/*對(duì)線卜t表(n,n-1,.,1),建立帶頭結(jié)點(diǎn)的線性鏈表*/NODE *head,*p,*q;int i;p=(NODE *)malloc(sizeof(NODE);(1) ;p->next=NULL;(2) ;for(i=1;i<=n;i+)p=(NODE *)malloc(sizeof(NODE);p->data=i;if(i=1)(3) ;else(4) ;(5) ; return(head);3.下列是在具有頭結(jié)點(diǎn)單向列表中刪除第i個(gè)結(jié)點(diǎn)，請(qǐng)?jiān)?/p>

14、空格內(nèi)填上適當(dāng)?shù)恼Z句。int delete(NODE *head,int i)找到要?jiǎng)h除結(jié)點(diǎn)的直接前驅(qū)，并使 q指向它*/int j； q=head; j=0;while(q!=NULL)&&(j<i-1)/* q=q->next; j+； if(q=NULL) return(0); (1)；(2)；free(p)； return(1); 五、完成：實(shí)驗(yàn)1線性表根據(jù)實(shí)驗(yàn)要求（見教材P201-202）認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè) 2（本部分作業(yè)覆蓋教材第3-5章的內(nèi)容）一、單項(xiàng)選擇題1 .若讓元素1, 2,3依次進(jìn)棧，則出棧順序不可能為（A.

15、 3, 2, 1 2, 1, 3C. 3, 1,2D. 1, 3, 22. 一個(gè)隊(duì)列的入隊(duì)序列是1, 2, 3, 4。則隊(duì)列的輸出序列是（A. 4, 3, 2, 1 B 1, 2, 3C. 1, 4, 3, 2 D 3, 2, 43.向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（A.先移動(dòng)棧頂指針，再存入元素.先存入元素，再移動(dòng)棧頂指針C.先后次序無關(guān)緊要4在一個(gè)棧頂指針為 top 的鏈棧中，將一個(gè)p 指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（ ） 。A top->next=p;B p->next=top->next; top->next=p;C p->next=top; top=p;D p-

16、>next=top->next; top=top->next;5 在一個(gè)棧頂指針為 top 的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)， 用 x 保存被刪結(jié)點(diǎn)的值，則執(zhí)行（ ） 。A x=top;top=top->next;B x=top->data;C top=top ->next; x=top->data;D x=top->data; top=top->next;6一般情況下，將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置（ ） 。隊(duì)列D.數(shù)組A.棧C.堆?；蜿?duì)列7表達(dá)式 a*（b+c）-d 的后綴表達(dá)式是（ abc+*d- C abc*+d- D -+*abc

17、dsq （最多元素為m）為空的條件是（）。A abcd*+- B8判斷一個(gè)順序隊(duì)列sq->rear-sq->front-1= = m0 sq->front=sq->rear+1A sq->rear-sq->front=m0BC sq->front=sq->rearD9 .判斷一個(gè)循環(huán)隊(duì)列 Q （最多元素為m）為空的條件是（）Q->front!=Q->rearA Q->front=Q->rearC Q->front=(Q->rear+1)% mD Q->front!= (Q->rear+1)%m10

18、.判斷一個(gè)循環(huán)隊(duì)列Q （最多元素為m）為空的條件是（）。A Q->front=Q->rearB Q->front!=Q->rearC Q->front=（Q->rear+1）% m0 D Q->front!= （Q->rear+1）% m011 .判斷棧S滿（元素個(gè)數(shù)最多n個(gè)）的條件是（）。A s->top=0B s->top!=0C s->top=n-1D s->top!=n-112 一個(gè)隊(duì)列的入隊(duì)順序是a,b,c,d ，則離隊(duì)的順序是（ ） 。A a,d,cb B a,b,c,d C d,c,b,a D c,b,d,a

19、13 如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)（） 。A 必須判斷棧是否滿B 判斷棧元素類型C.必須判斷棧是否空D .對(duì)棧不作任何判斷14 在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機(jī)則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個(gè)（ ）結(jié)構(gòu)。A.堆棧 B .隊(duì)列 C .數(shù)組 D .先性表15 一個(gè)遞歸算法必須包括（ ） 。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D .終止條件和迭代部分16 從一個(gè)棧頂指針為top 的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量x 保存被刪結(jié)點(diǎn)的值，則執(zhí)行（ ） 。A x=top->data; t

20、op=top->next; B x=top->data;top=top->next; x=data;C top=top->next; x=top->data; D17在一個(gè)鏈隊(duì)中，假設(shè)f 和 r 分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（ ） 。A r=f->next; B r=r->next; C f=f->next; D f=r->next;18在一個(gè)鏈隊(duì)中，假設(shè)f 和 r 分別為隊(duì)頭和隊(duì)尾指針，則插入 s 所指結(jié)點(diǎn)的運(yùn)算為（ ） 。A f->next=s; f=s;BC s->next=r;r=s;D19. 以下陳述中

21、正確的是（A.串是一種特殊的線性表C.串中元素只能是字母20設(shè)有兩個(gè)串p 和 q ，其中法稱為（ ） 。A.求子串BC 匹配D21 串是（ ）。A 不少于一個(gè)字母的序列C 不少于一個(gè)字符的序列22 串的長(zhǎng)度是指（） 。A.串中所含不同字母的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù) r->next=s;r=s; s->next=f;f=s;）。B 串的長(zhǎng)度必須大于零D 空串就是空白串q 是 p 的子串， q 在 p 中首次出現(xiàn)的位置的算連接求串長(zhǎng)B任意個(gè)字母的序列D有限個(gè)字符的序列B 串中所含字符的個(gè)數(shù)D 串中所含非空格字符的個(gè)數(shù)23 . 若串 S=“English ” ，其子串的個(gè)數(shù)是（A

22、9 B 16 C 36 D 2824下面關(guān)于串的敘述中，不正確的是（） 。A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算D.串即可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)25 串與普通的線性表相比較，它的特殊性體現(xiàn)在（ ） 。A.順序的存儲(chǔ)結(jié)構(gòu)B .鏈接的存儲(chǔ)結(jié)構(gòu)C.數(shù)據(jù)元素是一個(gè)字符D .數(shù)據(jù)元素可以任意26 空串與空格串（ ） 。A.相同 B.不相同C .可能相同 D .無法確定27 兩個(gè)字符串相等的條件是（ ） 。A 兩串的長(zhǎng)度相等B.兩串包含的字符相同C 兩串的長(zhǎng)度相等，并且兩串包含的字符相同D 兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同28 在實(shí)際應(yīng)用中， 要輸

23、入多個(gè)字符串， 且長(zhǎng)度無法預(yù)定。 則應(yīng)該采用 （）存儲(chǔ)比較合適（ ） 。A.鏈?zhǔn)?B 順序 C.堆結(jié)構(gòu) D .無法確定29 .一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)元素的存儲(chǔ)地址為100，則該數(shù)組的首地址是（）。28A 6490C 7030稀疏矩陣采用壓縮存儲(chǔ)的目的主要是（） 。A.表達(dá)變得簡(jiǎn)單B.對(duì)矩陣元素的存取變得簡(jiǎn)單C 去掉矩陣中的多余元素 D 減少不必要的存儲(chǔ)空間的開銷31 一個(gè)非空廣義表的表頭（ ）。A 不可能是原子B 只能是子表C 只能是原子D 可以是子表或原子32常對(duì)數(shù)組進(jìn)行的兩種基本操作是（） 。A.建立與刪除B.索引與、和修改C.查找和修改D.查找與索引33

24、 . 設(shè)二維數(shù)組A56 按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，已知 A00 起始地址為1000， 每個(gè)數(shù)組元素占用5 個(gè)存儲(chǔ)單元， 則元素 A44 的地址為 （） 。A 1140 B 1145 C 1120 D 112534 .設(shè)有一個(gè)20階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組 B 中（數(shù)組下標(biāo)從1 開始） ，則矩陣中元素a9,2 在一維數(shù)組 B 中的下標(biāo)是（ ） 。A 41 B 32 C 18 D 3835一個(gè)非空廣義表的表頭（） 。A.不可能是子表B .只能是子表C.只能是原子D .可以是子表或原子二、填空題1 棧是限定在表的一端進(jìn)行插入和刪除操作的線 性表， 又

25、稱 為。2 .隊(duì)列的特性是。3 .往棧中插入元素的操作方式是：先, 后。4 .刪除棧中元素的操作方式是：先, 后。5 .循環(huán)隊(duì)列隊(duì)頭指針在隊(duì)尾指針 位置，隊(duì)列是“滿”狀態(tài)6 .在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，尾指 針,當(dāng)刪除一個(gè)元素隊(duì)列時(shí)，頭指針 。7 .循環(huán)隊(duì)列的引入，目的是為了克服 。8 .向順序棧插入新元素分為三步：第一步進(jìn)行 判斷，判斷條件 是;第二步是修改 ;第三步是把新元素賦 給。同樣從順序棧刪除元素分為三步：第一步進(jìn)行 判 斷，判斷條件是。第二步是把;第三9 .假設(shè)以S和X分別表示入棧和出棧操作，則對(duì)輸入序列 a,b,c,d,e 一系歹U棧操作SSXSXSSXX

26、X后，得至J的輸出序歹U為 。10 . 一個(gè)遞歸算法必須包括 和。11 .判斷一個(gè)循環(huán)隊(duì)列LU（最多元素為 m）為空的條件是 。12 .在將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式和計(jì)算后綴表達(dá)式的算法中，都需要使用棧，對(duì)于前者，進(jìn)入棧中的元素為表達(dá)式中的 ,而對(duì)于后者，進(jìn)入棧的元素為,中綴表達(dá)式(a+b)心(f-d/c)所對(duì)應(yīng)的后綴表達(dá)式16 .向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行和h=s;操作。(結(jié)點(diǎn)的指針域?yàn)閚ext)17 .從一個(gè)棧頂指針為h的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用 x保存被刪結(jié)點(diǎn)的 值，可執(zhí)行x=h->data;和。(結(jié)點(diǎn)的指針域?yàn)閚ext)18 .在一個(gè)鏈隊(duì)中，設(shè)f和r

27、分別為隊(duì)頭和隊(duì)尾指針，則插入 s所指結(jié)點(diǎn)的操作為 和r=s;(結(jié)點(diǎn)的指針域?yàn)閚ext)19 .在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的 操作為。(結(jié)點(diǎn)的指針域?yàn)閚ext)20 .串是一種特殊的線性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都21 . 串的兩種最基本的存儲(chǔ)方式是和 022 .空串的長(zhǎng)度是 ;空格串的長(zhǎng)度是 。23 .需要壓縮存儲(chǔ)的矩陣可分為 矩陣和 矩陣兩種。24 .設(shè)廣義表L=(), (),則表頭是,表尾是, L的長(zhǎng)度是。25 .廣義表 A (a,b,c ) ,(d,e,f)的表尾為 。26 .兩個(gè)串相等的充分必要條件是 。27 .設(shè)有n階對(duì)稱矩陣A,用數(shù)組s進(jìn)行壓

28、縮存儲(chǔ)，當(dāng)i j時(shí)，A的數(shù)組元素aj相應(yīng)于數(shù)組s的數(shù)組元素的下標(biāo)為(數(shù)組元素的下標(biāo)從1開始)28 .對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的、和三項(xiàng)信息。三、問答題1 .簡(jiǎn)述棧和一般線性表的區(qū)別。2 .簡(jiǎn)述隊(duì)列和一般線性表的區(qū)別。3 .鏈棧中為何不設(shè)頭結(jié)點(diǎn)？4 .利用一個(gè)棧，則：(1)如果輸入序列由A, B, C組成，試給出全部可能的輸出序列和不可能 的輸出序列。(2)如果輸入序列由 A B, C, D組成，試給出全部可能的輸出序列和不 可能的輸出序列。5 .用S表示入棧操作，X表示出棧操作，若元素入棧順序?yàn)?234,為了得到1342出棧順序，相應(yīng)的S和X操作串是什么

29、？6 .有5個(gè)元素，其入棧次序?yàn)椋篈 B、C、D、E,在各種可能的出棧次序中，以元素C、 D最先的次序有哪幾個(gè)？7 .寫出以下運(yùn)算式的后綴算術(shù)運(yùn)算式(1) 3x2+x-1/x+5(2) (A+B)*C-D/(E+F)+G8 .在什么情況下可以用遞歸解決問題？在寫遞歸程序時(shí)應(yīng)注意什么？9 .簡(jiǎn)述廣義表和線性表的區(qū)別和聯(lián)系。四、程序填空題1.在下面空格處填寫適當(dāng)?shù)恼Z句，以使下面的循環(huán)隊(duì)列的入隊(duì)和出隊(duì)算法完整。define TRUE 1;define FALSE 0;define MAXSIZE 100;typedef charelemtype;typedef structElemtype queu

30、e MAXSIZE;int front,rear;sequeuetype;Sequeuetype Q;int encqueue(sequeuetype*Q,elemtype x)if ( ( 1JJPrintf( ''The cicular queue is full!n "); return(FALSE);else(3) return(TRUE); /*encqueue*/ elemtype del_cqueue(sequeuetype *Q)if ( (4)Printf('' The queue is empty !n")return(N

31、ULL);else(5)Return(Q-queueQ- >front);/*del_cqueue*/2.在下面空格處填寫適當(dāng)?shù)恼Z句，以使下面的鏈?zhǔn)疥?duì)列取出元素的算法完整。int write(LinkQueue *q)QueueNode *p;if (q->front=q->rear)/* 隊(duì)空 */printf( "underflow ”)；exit(0);while (q->front->next != NULL)p=q->front->next; printf("4d ,p ->data);(2) (3) ;/*隊(duì)空時(shí)，

32、頭尾指針指向頭結(jié)點(diǎn)*/五、綜合題1 .設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5 和e6依次通過S, 一個(gè)元素出棧后即進(jìn)隊(duì)列 Q,若6個(gè)元素出隊(duì)的序列是 e2,e4,e3,e6,e5,e1 ,則 棧S的容量至少應(yīng)該是多少？2 .假設(shè)用循環(huán)單鏈表實(shí)現(xiàn)循環(huán)隊(duì)列，該隊(duì)列只使用一個(gè)尾指針rear ,其相應(yīng)的存儲(chǔ)結(jié)構(gòu)和基本算法如下；(1)初始化隊(duì)列initqueue(Q):建立一個(gè)新的空隊(duì)列Q。(2)入隊(duì)列enqueue(Q,x):將元素x插入到隊(duì)列Q中。（3）出隊(duì)列delqueue（Q）:從隊(duì)列Q中退出一個(gè)元素。（4）取隊(duì)首元素gethead（Q）:返回當(dāng)前隊(duì)首元素。（5）判斷隊(duì)列

33、是否為空：emptyqueue（Q）。（6）顯示隊(duì)列中元素：dispqueue（Q）。六、完成：實(shí)驗(yàn)2棧、隊(duì)列、遞歸程序設(shè)計(jì)根據(jù)實(shí)驗(yàn)要求（見教材 P203）認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)作業(yè)3（本部分作業(yè)覆蓋教材第 6-7章的內(nèi)容）一、單項(xiàng)選擇題1 .假定一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為30,則葉子結(jié)點(diǎn)數(shù)為（）。A. 15 B . 16C .17 D . 472 .二叉樹第k層上最多有（）個(gè)結(jié)點(diǎn)。A . 2kB. 2k-1C . 2k-1D. 2k-13 .二叉樹的深度為k,則二叉樹最多有（）個(gè)結(jié)點(diǎn)。A. 2kB. 2k-1C 2k-1D. 2k-14

34、.設(shè)某一二叉樹先序遍歷為abdec,中序遍歷為 dbeac,則該二叉樹后序A . abdec B遍歷的順序是（）。.debac C . debca D . abedc5樹最適合于用來表示（A.線性結(jié)構(gòu)的數(shù)據(jù)B.順序結(jié)構(gòu)的數(shù)據(jù)C.元素之間無前驅(qū)和后繼關(guān)系的數(shù)據(jù)D.元素之間有包含和層次關(guān)系的數(shù)據(jù)6 設(shè) a,b 為一棵二叉樹的兩個(gè)結(jié)點(diǎn)， 在后續(xù)遍歷中， a 在 b 前的條件是（）A a 在 b 上方B a 在 b 下方C. a在b左方D. a在b右方7 權(quán)值為 1 ， 2 ， 6 ， 8 的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是（）A 18 B 28 C 19 D 298將含有150 個(gè)結(jié)點(diǎn)的完全二

35、叉樹從根這一層開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為 1，則編號(hào)為 69 的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為（）。A 33 B 34 C 35 D 369如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長(zhǎng)度最小，則該樹稱為（ ）。A.哈夫曼樹B.平衡二叉樹C 二叉樹D 完全二叉樹10 下列有關(guān)二叉樹的說法正確的是（）。A.二叉樹中度為0的結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)的個(gè)數(shù)加1B.二叉樹中結(jié)點(diǎn)個(gè)數(shù)必大于 0C.完全二叉樹中，任何一個(gè)結(jié)點(diǎn)的度，或者為0或者為2D.二叉樹的度是211. 在一棵度為 3 的樹中， 度為 3 的結(jié)點(diǎn)個(gè)數(shù)為 2， 度為 2 的結(jié)點(diǎn)個(gè)數(shù)為 1 ，則度為 0

36、的結(jié)點(diǎn)個(gè)數(shù)為（ ）。A 4 B 5 C 6 D 712. 在一棵度具有5 層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（ ）。A 31 B 32 C 33 D 1613. 利用 n 個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含有（ ） 個(gè)結(jié)點(diǎn)。A. n B. n+1 C. 2*n D. 2*n-114. 利用 n 個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含有（ ） 個(gè)雙支結(jié)點(diǎn)。A. n B. n-1 C. n+1 D. 2*n-115. 利用3、 6 、 8、 12 這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子的最長(zhǎng)帶權(quán)路徑長(zhǎng)度為 （ ）。A. 18 B. 16 C. 12 D. 3016在一棵樹中，（）

37、沒有前驅(qū)結(jié)點(diǎn)。A.分支結(jié)點(diǎn)B .葉結(jié)點(diǎn) C .樹根結(jié)點(diǎn)D .空結(jié)點(diǎn)17在一棵二叉樹中，若編號(hào)為i 的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（ ） 。A 2iB 2i-1 D 2i+1 C 2i+218設(shè)一棵哈夫曼樹共有n 個(gè)葉結(jié)點(diǎn)，則該樹有（ ）個(gè)非葉結(jié)點(diǎn)。A nB n-1 C n+1 D 2n19 設(shè)一棵有n 個(gè)葉結(jié)點(diǎn)的二叉樹，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2 ，則該樹共有（ ）個(gè)結(jié)點(diǎn)。A 2nB 2n-1 C 2n+1 D 2n+220一棵完全二叉樹共有5 層，且第 5 層上有六個(gè)結(jié)點(diǎn)，該樹共有（ ）個(gè)結(jié)點(diǎn)。 A 20B 21 C 23 D 3021 在一個(gè)圖 G 中，所有頂點(diǎn)的度數(shù)之和等于所有

38、邊數(shù)之和的（ ） 倍。A 1/2 B 1 C 2 D 422在一個(gè)有像圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 （ ）倍。A 鄰接矩陣表示法 B 鄰接表表示法C.逆鄰接表表示法D .鄰接表和逆鄰接表23在圖的存儲(chǔ)結(jié)構(gòu)表示中，表示形式唯一的是（）。A n B n 1 C n 1 D n/224一個(gè)具有n 個(gè)頂點(diǎn)的無向完全圖包含（ ）條邊。A n（ n 1） B n（ n 1） C n （ n 1） /2 D n （ n 1 ） /225一個(gè)具有n 個(gè)頂點(diǎn)的有向完全圖包含（ ）條邊。A n（ n 1） B n（ n 1） C n （ n 1） /2 D n （ n 1 ）/226 對(duì)于具有

39、n 個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則該矩陣的大小為）。A n B n2 C n 1 D （ n 1） 227對(duì)于一個(gè)具有n 個(gè)頂點(diǎn)和 e 條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為（ ）。A n B e C 2n D 2e28對(duì)于一個(gè)具有n 個(gè)頂點(diǎn)和 e 條邊的無向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為（ ）。A n B e C 2n D 2e29在有向圖的鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（）鄰接點(diǎn)。A 入邊B 出邊C.入邊和出邊D.不是入邊也不是出邊30在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（）鄰接點(diǎn)。.出邊.不是入邊也不是出邊.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu).散

40、列存儲(chǔ)結(jié)構(gòu)A 入邊BC.入邊和出邊D31 鄰接表是圖的一種（ ）。A 順序存儲(chǔ)結(jié)構(gòu)BC.索引存儲(chǔ)結(jié)構(gòu)D32 如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是（ ）。A 完全圖 B 連通圖 C 有回路D 一棵樹33 .下列有關(guān)圖遍歷的說法不正確的是（A.連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程B.圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征C.非連通圖不能用深度優(yōu)先搜索法D.圖的遍歷要求每一頂點(diǎn)僅被訪問一次34 .無向圖的鄰接矩陣是一個(gè)（）。A.對(duì)稱矩陣B .零矩陣 C .上三角矩陣D .對(duì)角矩陣35 .圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。A.先序B .中序

41、 C .后序 D .層次36 .已知下圖所示的一個(gè)圖，若從頂點(diǎn) Vi出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A . MMMV8V3MV6V7B . VMV4V5VV3V6V75 .在一棵樹中，每個(gè)結(jié)點(diǎn)的 或者說每個(gè)結(jié)點(diǎn)的稱為該結(jié)點(diǎn)的 ,簡(jiǎn)稱為孩子。6 . 一個(gè)結(jié)點(diǎn)稱為其后繼結(jié)點(diǎn)的 o7 .具有 的結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)，簡(jiǎn)稱為兄弟。8 .每個(gè)結(jié)點(diǎn)的所有子樹中的結(jié)點(diǎn)被稱為該結(jié)點(diǎn)的 。9 .從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的 。10 .樹的深度或高度是指 。11 . m(m 0)棵互不相交的樹的集合稱為 。12 .度為k的樹中的第i層上最多有 結(jié)點(diǎn)。13 .深度為

42、k的二叉樹最多有 結(jié)點(diǎn)。14 .在一棵二叉樹中，如果樹中的每一層都是滿的，則稱此樹 為;但如果出最后一層外，其余層都是滿的，并且最后一層 是滿的，或者是在缺少若干連續(xù)個(gè)結(jié)點(diǎn)，則稱此二叉樹 為。15 .具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度是 。16 .先序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則 進(jìn)行如下操作，訪問二叉樹的 ;先序遍歷二叉樹的 , 先序遍歷二叉樹的17 .中序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進(jìn)行如下操作，中序遍歷二叉樹的 ;訪問而叉樹的 中序遍歷二叉樹的 18 .后序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進(jìn)行如下操作，后序遍歷二

43、叉樹的;后序遍歷二叉樹的,訪問而叉樹的19 .將樹中結(jié)點(diǎn)賦上一個(gè)有著某種意義的實(shí)數(shù)，稱此實(shí)數(shù)為該結(jié)點(diǎn) 的。20 .樹的帶權(quán)路徑長(zhǎng)度為樹中所有葉子結(jié)點(diǎn) 的。21 .哈夫曼樹又稱為 ,它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有 二叉樹中帶權(quán)路徑長(zhǎng)度 WPL。22 .若以4, 5, 6, 7, 8作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路 徑長(zhǎng)度是。23 .具有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有 結(jié)點(diǎn)。24 .在圖中，任何兩個(gè)數(shù)據(jù)元素之間都可能存在關(guān)系，因此圖的數(shù)據(jù)元素之間是一種_的關(guān)系。25 .圖的鄰接矩陣表示法是用一個(gè) 來表示圖中頂點(diǎn)之間的相 鄰關(guān)系。26 .鄰接表是圖中的每個(gè)頂點(diǎn)建立一個(gè)鄰接關(guān)系的 。27 .圖的

44、遍歷是從圖的某一頂點(diǎn)出發(fā)，按照一定的搜索方法對(duì)圖中 各做一訪問的過程。28 .圖的深度優(yōu)先搜索遍歷類似于樹的 遍歷。29 .圖的廣度優(yōu)先搜索類似于樹的 遍歷。30 .具有n個(gè)頂點(diǎn)的有向圖的鄰接矩陣，其元素個(gè)數(shù)為 。31 .具有n個(gè)頂點(diǎn)的無向圖至少有 條邊，才能確保其為一個(gè)連 通圖。32 .圖常用的兩種存儲(chǔ)結(jié)構(gòu)是 和。33 . 一個(gè)AOV網(wǎng)(頂點(diǎn)活動(dòng)圖)應(yīng)該是一個(gè) 。即不應(yīng)該帶有 回路，否則回路上的所有活動(dòng)都 。34 .用鄰接矩陣存儲(chǔ)有向圖G,其第i行的所有元素之和等于頂點(diǎn)i的。35 .在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá) 。36 .在一個(gè)帶權(quán)圖中，兩頂點(diǎn)之間的最段路徑最多經(jīng)過 條邊。3

45、7 .為了實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷，其非遞歸的算法中需要使用的一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)為。三、綜合題1 .寫出如下圖所示的二叉樹的先序、中序和后序遍歷序列。f2 .已知某二叉樹的先序刎第果是:A，B, D, G, C, E, H, L, I , K, M, F和J,它的中序遍號(hào)怦D,B,A)L H,E,K,I ,M,C,F和J,請(qǐng)畫出這棵二叉樹，并寫bH該二叉樹卮續(xù)遍歷的結(jié)惠.3 .已知1媒2全二般b有 892個(gè)色，廣)(1)樹的高度葉子結(jié)點(diǎn)數(shù) 單支結(jié)點(diǎn)數(shù) 最后一個(gè)非終端結(jié)點(diǎn)的序號(hào)4給出滿足下列條件的所有二叉樹。（ 1）先序和中序相同（ 2）中序和后序相同（ 3）先序和后序相同（ 假設(shè)通信用的報(bào)文由9

46、 個(gè)字母A、B、C、D、E、F、G、H 和 I 組成，它們出現(xiàn)的頻率分別是： 10、 20、 5 、 15 、 8、 2、 3、 7 和 30。請(qǐng)請(qǐng)用這9 個(gè)字母出現(xiàn)的頻率作為權(quán)值求：（ 1）設(shè)計(jì)一棵哈夫曼樹；（ 2）計(jì)算其帶權(quán)路徑長(zhǎng)度WPL；（ 3）寫出每個(gè)字符的哈夫曼編碼。6請(qǐng)根據(jù)以下帶權(quán)有向圖G（1）給出從結(jié)點(diǎn)v1出發(fā)分別按深度優(yōu)先搜索遍歷G和廣度優(yōu)先搜索遍歷G所得的結(jié)點(diǎn)序列；（2）給出G的一個(gè)拓?fù)湫蛄?；?3）給出從結(jié)點(diǎn)v1 到結(jié)點(diǎn) v8 的最短路徑。7.已知無向圖G描述如下：G=（ V， E）V=V1， V2， V3， V4， V5E=（ V1， V2）， （ V1，V4）， （ V

47、2，V4）， （V3，V4）， （ V2，V5）， （V3，V4），（ V3，V5) (1)畫出G的圖示;(2)然后給出G的鄰接矩陣和鄰接表；(3)寫出每個(gè)頂點(diǎn)的度。8.回答下列問題：對(duì)于存儲(chǔ)結(jié)構(gòu)采用鄰接矩陣的無向圖，如何判斷下列有關(guān)問題？圖中有多少條邊？任意兩頂點(diǎn)間是否有邊相連？任意一個(gè)頂點(diǎn)的度是多少？對(duì)于存儲(chǔ)結(jié)構(gòu)采用鄰接表的有向圖，如何判斷下列有關(guān)問題？圖中有多少條邊？圖中是否存在從V到V的邊？如何求頂點(diǎn)V的入度和出度？四、程序填空題1 .下面函數(shù)的功能是返回二叉樹 BT中值為X的結(jié)點(diǎn)所在的層號(hào)，請(qǐng)?jiān)趧澯袡M線的地方填寫合適內(nèi)容。int NodeLevel(struct BinTreeNod

48、e* BT, char X)if(BT=NULL) return 0;/*空樹的層號(hào)為 0*/else if(BT->data=X) return 1; /*根結(jié)點(diǎn)的層號(hào)為 1*/* 向子樹中查找X結(jié)點(diǎn)*/else int c1=NodeLevel(BT->left,X);if(c1>=1);int c2=(2) if (3)；/若樹中不存在 X結(jié)點(diǎn)則返回0else return 0;2 .下面函數(shù)的功能是按照?qǐng)D的深度優(yōu)先搜索遍歷的方法，輸出得到該圖的生成樹中的各條邊，請(qǐng)?jiān)趧澯袡M線的地方填寫合適內(nèi)容。void dfstree(adjmatrix GA, int i, int

49、n)int j；visitedi=1;(1) if(GAij!=0 && GAij!=MaxValue && !visitedj) printf("(%d,%d)%d,",i,j,GAij);(2) 五、算法設(shè)計(jì)題1 .寫一個(gè)將一棵二叉樹復(fù)制給另一棵二叉樹的算法。2 .根據(jù)下面函數(shù)聲明編寫出求一棵二叉樹中葉子結(jié)點(diǎn)總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)BT初始指向二叉樹的根結(jié)點(diǎn)。int BTreeLeafCount(struct BTreeNode* BT);3 .已知有n個(gè)頂點(diǎn)的有向圖鄰接表，設(shè)計(jì)算法分別實(shí)現(xiàn)下列功能：(1)求出圖G中每個(gè)頂

50、點(diǎn)的出度、入度。(2)計(jì)算圖中度為0的頂點(diǎn)數(shù)。六、完成：實(shí)驗(yàn)3棧、隊(duì)列、遞歸程序設(shè)計(jì)實(shí)驗(yàn)4圖的存儲(chǔ)方式和應(yīng)用根據(jù)實(shí)驗(yàn)要求(見教材 P203)認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。數(shù)據(jù)結(jié)構(gòu)(本)課程作業(yè)(4)(本部分作業(yè)覆蓋教材第8-9章的內(nèi)容)一、單項(xiàng)選擇題1 .順序查找方法適合于存儲(chǔ)結(jié)構(gòu)為()的線性表。.索引存儲(chǔ)A.散列存儲(chǔ)C.散列存儲(chǔ)或索引存儲(chǔ) D.順序存儲(chǔ)或鏈接存儲(chǔ)2對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（）。A 以順序存儲(chǔ)方式B.以鏈接存儲(chǔ)方式C 以順序存儲(chǔ)方式 ，且數(shù)據(jù)元素有序D.以鏈接存儲(chǔ)方式，且數(shù)據(jù)元素有序3如果要求一個(gè)線性表既能較快地查找，又能動(dòng)態(tài)適應(yīng)變化要求，可以采用（ ）查找方法

51、。A.順序B.分塊C.折半D.散列4 . 對(duì)于一個(gè)線性表，若要求既能進(jìn)行較快地插入和刪除，又要求存儲(chǔ)結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系，則應(yīng)該（ ） 。A 以順序存儲(chǔ)方式B 以鏈接存儲(chǔ)方式C.以索引存儲(chǔ)方式 D .以散列存儲(chǔ)方式5 采用順序查找方法查找長(zhǎng)度為n 的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（ ） 。A nB n/2C （n+1）/2 D （n-1）/26 采用折半查找方法查找長(zhǎng)度為n 的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（ ） 。A O(n*n)O(nlog 2n)C O(n)s(log 2n)）取其值域的每個(gè)7哈希函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以（值。A.最大概率B .最小概率C

52、 .平均概率D .同等概率8有一個(gè)長(zhǎng)度為10 的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ ） 。A 29/10 B 31/10 C 26/10 D 29/99. 已知一個(gè)有序表為 11,22,33,44,55,66,77,88,99， 則順序查找元素55需要比較（ ）次。A 3 B 4 C 5 D 610. 順序查找法與二分查找法對(duì)存儲(chǔ)結(jié)構(gòu)的要求是（）。A.順序查找與二分查找均只是適用于順序表B.順序查找與二分查找均既適用于順序表，也適用于鏈表C.順序查找只是適用于順序表D.二分查找適用于順序表11. 有數(shù)據(jù) 53,30,37,12,45,24,96 ，從空二

53、叉樹開始逐個(gè)插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是（ ）。A 45,24,53,12,37,96,30B 37,24,12,30,53,45,96C 12,24,30,37,45,53,96D 30,24,12,37,45,96,5312. 對(duì)有18 個(gè)元素的有序表作二分（折半）查找，則查找A3 的比較序列的下標(biāo)可能為（ ）。A 1、 2、 39、 5、 2 、 3C 9、 5、 3 D 9、 4、 2 、 313. 對(duì)于順序存儲(chǔ)的有序表5 ， 12 ， 20， 26， 37， 42， 46 ， 50 ， 64 ，若采用折半查找，則查找元素26 的比較次數(shù)是（ ） 。A.3 B. 3 C. 4D.514. 關(guān)于哈希查找的說法正確的是（ ） 。A. 除留余數(shù)法是最好的B. 哈希函數(shù)的好壞要根據(jù)具體情況而定C