數(shù)據(jù)結(jié)構(gòu)1-10題目

數(shù)據(jù)結(jié)構(gòu)作業(yè)班級(jí)：學(xué)號(hào)：姓名：教師：

第一章：概述一．單項(xiàng)選擇。1、數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)值計(jì)算得程序設(shè)計(jì)問題中計(jì)算機(jī)的以及它們之間的和運(yùn)算等的學(xué)科。(1)A.數(shù)據(jù)元素B.計(jì)算方法C.邏輯存儲(chǔ)D.數(shù)據(jù)映像（2）A．結(jié)構(gòu)B關(guān)系C運(yùn)算D算法2、數(shù)據(jù)結(jié)構(gòu)被形式地定義為（K，R），其中K是的有限集，R是K上的有限集。（1）A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結(jié)構(gòu)（2）A.操作B.映像C.存儲(chǔ)D.關(guān)系3、線性結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)是一種的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)式一種的存儲(chǔ)結(jié)構(gòu)。A．隨機(jī)存取B.順序存取C.索引存取D.散列存取4、計(jì)算機(jī)算法指的是，它必須必備輸入，輸出和等5個(gè)特性。（1）A.計(jì)算方法B.排序方法C.解決問題的有限運(yùn)算序列D.調(diào)度方法（2）A.可執(zhí)行性、可移值性和可擴(kuò)充性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性5、線性表的邏輯順序與存儲(chǔ)順序與總是一致的，此說法。A.對(duì)B.錯(cuò)6、以下哪一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)？。A.順序表B.鏈表C.散列表D.隊(duì)列7、研究數(shù)據(jù)結(jié)構(gòu)就是研究。A．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu) 。 B．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。C．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。D．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其數(shù)據(jù)的運(yùn)算。8、邏輯結(jié)構(gòu)是指數(shù)據(jù)元素的。A．關(guān)聯(lián)方式 B．存儲(chǔ)方式 C．結(jié)構(gòu) D．?dāng)?shù)據(jù)項(xiàng)9、在以下的敘述中，正確的是。A.線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)與鏈表存儲(chǔ)結(jié)構(gòu)B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C.棧的操作方式是先進(jìn)先出D.隊(duì)列的操作方式是先進(jìn)后出10、每種數(shù)據(jù)結(jié)構(gòu)都具三個(gè)基本運(yùn)算：插入、刪除、查找，此說法。A.對(duì)B.錯(cuò)11、以下哪一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)？。A.順序表B.鏈表C.散列表D.隊(duì)列12、算法在發(fā)生非法操作時(shí)可以做出處理的特性稱為。A．正確性 B．易讀性 C．健壯性 D．高效性二、填空。1樹型結(jié)構(gòu)和圖型結(jié)構(gòu)合稱為（）。2在線性結(jié)構(gòu)中第一個(gè)結(jié)點(diǎn)（）前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有（）個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)（）后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有（）個(gè)后續(xù)結(jié)點(diǎn)。3在樹性結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有（）結(jié)點(diǎn)，其余結(jié)點(diǎn)有且只有（）個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有（）結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)可以（）。4在圖型結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以（）。5線性結(jié)構(gòu)中元素之間存在（）的關(guān)系，樹型結(jié)構(gòu)中元素之間存在（）的關(guān)系，圖型結(jié)構(gòu)中元素之間存在（）的關(guān)系。6算法的無(wú)個(gè)重要特性是（）、（）、（）、（）、（）。7下面程序的時(shí)間復(fù)雜度是（）for(i=o;i<n;i++)for(j=0;<m;j++)a[I][j]=0;8下面程序段的時(shí)間復(fù)雜度是（）i=s=0;while(s<n){i++;s+=i;}9下面程序段的時(shí)間復(fù)雜度是（）s=0;for(I=0;I<n;I++)for(j=0;j<n;j++)s+=B[i][j];sum=s;10下面程序段的時(shí)間復(fù)雜度是（）I=1;while(I<=n)I=I*3;三、分析下列用二元組形式表示的數(shù)據(jù)結(jié)構(gòu)，指出他們分別屬于何種類型的數(shù)據(jù)結(jié)構(gòu)。A=（K，R），其中：K={a，b，c，d，e，f，g，h}，R={r}，r={<a，b>，<b，c>，<c，d>，<d，e>，<e，f>，<f，g>，<g，h>}。B=（K，R），其中：K={a，b，c，d，e，f，g，h}，R={r}，r={<d，b>，<d，g>，<d，a>，<b，c>，<g，e>，<g，h>，<e，f>}。C=（K，R），其中：K={a，b，c，d，e}，R={r}，r={<a，b>，<b，c>，<c，d>，<d，e>，<e，f>，<a，d>，<c，f>}。D=（K，R），其中：K={48，25，64，57，82，36，75}，R={r1，r2}，r1={<25，36>，<36，48>，<48，57>，<57，64>，<64，75>，<75，82>}；r2={<48，25>，<48，64>，<64，57>，<64，82>，<25，36>，<25，75>}。E=（K，R），其中：K={1，2，3，4，5，6，7}，R={r}，r={<1，2>，<2，1>，<1，4>，<4，1>，<2，3>，<3，2>，<3，4>，<4，3>，<1，3>，<3，1>}。

第二章：鏈表一、單項(xiàng)選擇。1、不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL2、帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是A.head==NULLB.head->next==NULLChead->next==headDhead!=NULL3、非空的循環(huán)單連表head的尾結(jié)點(diǎn)（由p所指向）滿足。A.p->next==NULLB.p==NULLC.p->next==headD.p==head4、在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是.A.p->right=s;s->left=p;p->right->left=s;s->right=p->right;B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;D.s->left=p;s->right=p->right;p->right->left=s;p->right=s.5、在一個(gè)單鏈表中,已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn),則執(zhí)行.A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->next=s;s->next=q;6、在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行.A.s->next=p;p->next=sB.s->next=p->next;p->next=s;C.s->next=p->next;p=s;D.p->next=s;s->next=p;7、假設(shè)雙鏈表結(jié)點(diǎn)的類型如下:typedefstructlinknode{intdata;/*數(shù)據(jù)域*/structlinknode*llink;/*llink是指向前驅(qū)結(jié)點(diǎn)的指針域*/structlinknode*rlink;/*rlink是指向后續(xù)結(jié)點(diǎn)的指針域/}bnode下面給出的算法段是要把一個(gè)q所指新結(jié)點(diǎn)作為非空雙向鏈表中的p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)插入到該雙鏈表中,能正確完成要求的算法段是_______.A.q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;B.p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink;C.q->llink=p->llink;q->rlink=p;p->llink->rlink=q;p->llink=q;D.以上答案都不對(duì)。8、從一個(gè)具有N個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于X結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較______個(gè)結(jié)點(diǎn)。ANBN/2C（N-1）/2D（N+1）/29、在一個(gè)具有N個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的的時(shí)間復(fù)雜度是。AO（1）BO（N）CO（N2）DO（nlog2n）10、給定有N個(gè)元素的線性表，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是。AO（1）BO（N）CO（N2）DO(nlog2n)11、一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是。A.110B.108C.100D.12012、線性表是。A．一個(gè)有限序列，可以為空B．一個(gè)有限序列，不能為空C．一個(gè)無(wú)限序列，可以為空D．一個(gè)無(wú)限序列，不能為空13、在單鏈表中，增加頭結(jié)點(diǎn)的目的是。A．使單鏈表至少有一結(jié)點(diǎn)B．標(biāo)志表中首結(jié)點(diǎn)位置C．方便運(yùn)算的實(shí)現(xiàn)D．說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)14、下列有關(guān)線性表的敘述中，正確的是。A．線性表中的元素之間是線性關(guān)系B．線性表中至少有一個(gè)元素C．線性表中任何一個(gè)元素有且僅有一個(gè)直接前趨D．線性表中任何一個(gè)元素有且僅有一個(gè)直接后繼15、在單鏈表中，存儲(chǔ)每個(gè)結(jié)點(diǎn)需有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是指針域，它指向該結(jié)點(diǎn)的。A．直接前趨B．直接后繼C．開始結(jié)點(diǎn)D．終端結(jié)點(diǎn)16、將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是。A．nB.2n-1C.2nD.n-117、鏈表不具有的特點(diǎn)是。A．隨機(jī)訪問B．不必事先估計(jì)存儲(chǔ)空間C．插入刪除時(shí)不需移動(dòng)元素D．所需的空間與線性表成正比18、一個(gè)順序表一旦說明，其中可用空間大小。A．已固定 B．可以改變 C．不能固定 D．動(dòng)態(tài)變化19、若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表 B．單鏈表 C．雙向鏈表 D．單循環(huán)鏈表20、下面關(guān)于線性表的敘述中，錯(cuò)誤的是。A．線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B．線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作C．線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D．線性表采用鏈接存儲(chǔ)，便于進(jìn)行插入和刪除操作21、在長(zhǎng)度為n的順序線性表中刪除第i個(gè)元素(1<=i<=n)，則需要向前移動(dòng)的元素個(gè)數(shù)為（）。A．n-i B．n+1-i C．n-1-i D．i二填空題1、單鏈表是的鏈接存儲(chǔ)表示。2、可以使用表示樹型結(jié)構(gòu)。3、對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是。4、在一個(gè)單鏈表中的P所指結(jié)點(diǎn)之前插入一個(gè)S所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作：s->next=;p->next=s;t=p->data;p->data=;s->data=;5、在一個(gè)單鏈表中刪除P所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作；q=p->next;p->data=p->next->data;p->next=;free(q);6、帶有一個(gè)頭結(jié)點(diǎn)的單鏈表HEAD為空的條件是。7、給有N個(gè)元素的線性表，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是。8、非空的循環(huán)單鏈表HEAD的尾結(jié)點(diǎn)（由P所指向），滿足條件。9、在雙鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，其時(shí)間復(fù)雜度為。10、在帶頭結(jié)點(diǎn)的雙鏈表Ｌ中，指針Ｐ所指結(jié)點(diǎn)是開始結(jié)點(diǎn)的條件是。10、在一個(gè)鏈隊(duì)中，假設(shè)F和R分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算時(shí)。Ar=f->next;Br=r->next;Cf=f->next;Df=r->next;三、判斷題：1、在有序的順序表和有序的鏈表上，均可以使用折半查找法來(lái)提高查找速度。（）2、順序存儲(chǔ)的線性表可以隨機(jī)存取。（）3、線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。（）4、線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（）

第三章：棧和隊(duì)列一、單選1、一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是。A.edcbaB.decbaC.dceabD.abcde2、棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是。A．線性存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)B.散列方式和索引方式C.鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組D.線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)3、判定一個(gè)棧ST（最多元素為m0）為空的條件是。A.ST-〉top！=0B.ST-〉top==0C.ST-〉top！=m0D.ST-〉top==m0-14、判定一個(gè)棧ST（最多元素為m0）為滿的條件是。A．ST-〉top！=0B.ST-〉top==0C.ST-〉top！=m0-1D.ST-〉top==m0-15、棧的特點(diǎn)是，隊(duì)列的特點(diǎn)是。A.先進(jìn)先出B.先進(jìn)后出6、一個(gè)隊(duì)列的入列序列是1，2，3，4，則隊(duì)列的輸出序列是。A.4，3，2，1B.1，2，3，4C.1，4，2，3D.3，2，4，17、判斷一個(gè)隊(duì)列QU（最多元素為m0）為空的條件是。A．QU->rear-QU->front==m0B.QU->rear-QU->front-1==m0C.QU->front==QU->rearD.QU->front==QU->rear+18、判斷一個(gè)隊(duì)列QU（最多元素為m0）為滿的條件是。A．QU->rear-QU->front==m0B.QU->rear-QU->front-1==m0C.QU->front==QU->rearD.QU->front==QU->rear+19、判斷一個(gè)循環(huán)隊(duì)列QU（最多元素為m0）為空的條件是。A．QU->front==QU->rearB.QU->front！=QU->rearC.QU->front==（QU->rear+1）%m0DQU->front！=（QU->rear+1）%m010、判斷一個(gè)循環(huán)隊(duì)列QU（最多元素為m0）為滿的條件是。A．QU->front==QU->rearB.QU->front！=QU->rearC.QU->front==（QU->rear+1）%m0DQU->front！=（QU->rear+1）%m011、循環(huán)隊(duì)列用數(shù)組A[0，m-1]存放其元素值，以知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是。A.（rear-front+m）%mB.rear-front+1Crear-front-1Drear-front12、棧和隊(duì)列的共同點(diǎn)是。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)13、向一個(gè)棧頂指針為HS的鏈表中插入一個(gè)S所指結(jié)點(diǎn)時(shí)，則執(zhí)行A.HS->next=sB.s->next=HS->next;HS->next=s;C.s->next=HS;HS=s;D.s->next=HS;HS=HS->next;14、從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用X保存被刪結(jié)點(diǎn)的值,則執(zhí)行。A.x=HS;HS=HS->next;B.x=HS->data;C.HS=HS->next;x=HS->data;D.x=HS->data;HS=HS->next;15、在一個(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;16、鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是。A．插入操作更加方便B．刪除操作更加方便C．不會(huì)出現(xiàn)下溢的情況D．不會(huì)出現(xiàn)上溢的情況17、若一個(gè)棧的輸入序列是1,2,3……，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是。A．n-iB．n–i+1C．iD．不確定18、棧與一般線性表的區(qū)別主要在。A．元素個(gè)數(shù)B．元素類型C．邏輯結(jié)構(gòu)D．插入、刪除元素的位置19、在鏈隊(duì)列執(zhí)行入隊(duì)操作。A．需判別隊(duì)是否空B．需判別隊(duì)是否滿C．限制在鏈表頭p進(jìn)行D．限制在鏈表尾p進(jìn)行20、設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用數(shù)據(jù)結(jié)構(gòu)最佳。A．線性表的順序存儲(chǔ)結(jié)構(gòu)B．棧C．隊(duì)列D．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)21、循環(huán)隊(duì)列的特點(diǎn)之一是不會(huì)產(chǎn)生。A．上溢出B．下溢出C．隊(duì)滿D．假溢出二、填空題1、向量、棧和隊(duì)列都是結(jié)構(gòu)，可以在向量的位置插入和刪除元素；對(duì)于棧只能在插入和刪除元素；對(duì)于隊(duì)列只能在插入元素和刪除元素。2、在一個(gè)長(zhǎng)度為n的向量中的第i個(gè)元素（1<=I<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)個(gè)元素。3、一個(gè)棧的輸入序列是12345，則棧的輸出序列12345是。4、向棧中壓入元素的操作是。5、對(duì)棧進(jìn)行退棧時(shí)的操作是。6、在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的。7、從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是。8、在具有n個(gè)單元的循環(huán)序列中，隊(duì)滿時(shí)共有個(gè)元素。9、一個(gè)棧的輸入序列是12345，則棧的輸出序列43512是。10、在棧頂指針為HS的鏈棧中，判定?？盏臈l件是。11、在棧頂指針為HS的鏈棧中，計(jì)算該鏈棧中結(jié)點(diǎn)個(gè)數(shù)的函數(shù)是：。12、設(shè)n個(gè)元素的進(jìn)棧序列為1，2，3….，n，出棧序列為p1,p2,….pn，若p1=n，則pi（1<=i<n）的值為。13、設(shè)n個(gè)元素的進(jìn)棧序列為p1,p2,….pn，出棧序列為1，2，3….，n，若pn=1，則pi（1<=i<n）的值為。三、判斷題。1、循環(huán)隊(duì)列中無(wú)上溢現(xiàn)象。（）2、循環(huán)隊(duì)列只有下溢，沒有上溢。（）3、對(duì)順序棧而言，在棧滿狀態(tài)，如果此時(shí)再作進(jìn)棧運(yùn)算，則會(huì)發(fā)生“下溢”。（）4、順序隊(duì)列和循環(huán)隊(duì)列的隊(duì)滿和隊(duì)空的條件是一樣的。（）5、為解決隊(duì)列“假滿”問題，可以采用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列存儲(chǔ)。（）6、隊(duì)列是后進(jìn)先出表。（）7、棧是后進(jìn)先出表。()

第四章串一、單選1、空串與空格串是相同的,此說法().A．對(duì)B．錯(cuò)2、設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作().A．連接B．模式匹配C．求子串D．求串長(zhǎng)3、設(shè)串s1=`ABCDEFG`,s2=`PQRST`,函數(shù)con(x,y)返回x和y串的連接串，subs(s,I,j)返回串s的從序號(hào)I的字符開始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度,則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是().A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF二、填空題1、串的兩中最基本的存儲(chǔ)方式是.2、兩個(gè)串相等的充要條件是.3、空串是,其長(zhǎng)度等于零.4、空格串是,其長(zhǎng)度等于。5、設(shè)s=`IAMATEACHER`,其長(zhǎng)度是.6、設(shè)s1=`GOOD`,s2=`-`,s3=`BYE!`,則s1,s2,s3連接后的結(jié)果是.

第五章：數(shù)組和廣義表一、單選1、常對(duì)數(shù)組進(jìn)行的兩種基本操作是().A.建立與刪除B.索引與修改C.查找與修改D.查找與修改2、二維數(shù)組M的成員是6個(gè)字符組成的串，行下標(biāo)I的范圍從0到8,列下標(biāo)j的范圍從1到10,則存放M至少要()個(gè)字節(jié);M的第8列和第5行共占()個(gè)字節(jié);若M按行優(yōu)先方式存儲(chǔ)，元素M[8][5]的起始地址與當(dāng)M按列優(yōu)先方式存儲(chǔ)時(shí)的()元素的起始地址一致.(1)A.90B.180C.240D.540(2)A.108B.114C.54D.60(3)A.M[8][5]B.M[3][10]C.M[5][8]D.M[0][9]3、二維數(shù)組M的元素是4個(gè)字符組成的串,行下標(biāo)I的范圍從0到4,列下標(biāo)j的范圍從0到5,M按行存儲(chǔ)時(shí)元素M[3][5]的起始地址與M按列存儲(chǔ)時(shí)元素()的起始地址相同.A.M[2][4]B.M[3][4]C.M[3][5]D.M[4][5]4、數(shù)組A中,每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié),行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi),存放該數(shù)組至少要的單元數(shù)是().A.80B.100C.240D.2705、數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)I從1到8，列下標(biāo)J從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A[8][5]的起始地址為（）。A．SA+141B．SA+144C．SA+222D．SA+2256、數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)I從1到8，列下標(biāo)J從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A[5][8]的起始地址為（）A．SA+141B．SA+180C．SA+222D．SA+2257、稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（）A．二維數(shù)組和三維數(shù)組B．三元組和散列C．三元組和十字鏈表D．散列和十字鏈表8、若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下表和列下表互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn)（）A．正確B．錯(cuò)誤9、設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分（如圖5.7所示）按行序存放在一維數(shù)組B[1,n(n-1)/2]中，對(duì)下三角部分中任一元素aij(i>=j)，在一組數(shù)組B的下標(biāo)位置K的值是（）A．i(i-1)/2+j-1B．i(i-1)/2+jC．i(i+1)/2+j-1D．i(i+1)/2+j10、一個(gè)廣義表的表尾總是一個(gè)廣義表,這個(gè)斷言是（）A.對(duì)B.錯(cuò)11、廣義表((a))的表頭是（）,表尾是（）。A.aB.(a)C.(空格)D.((a))12、廣義表((a,b),c,d)的表頭是（）,表尾是（）A.aB.bC.(a,b)D.(c,d)13、廣義表(a,b,c,d)的表頭是（）,表尾是（）A.aB.bC.(a,b)D.(b,c,d)14、廣義表((a,b,c,d))的表頭是（）,表尾是（）A.aB.(空格)C.(a,b,c,d)D.((a,b,c,d))二填空題1、已知二維數(shù)組A[M][N]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占K個(gè)存儲(chǔ)單元，并且一個(gè)元素的存儲(chǔ)地址是LOC（A[0][0]），則A[I][J]的地址是2、二維數(shù)組A[10][20]采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，并且A[0][0]的存儲(chǔ)地址是200，則A[6][12]的地址是3、二維數(shù)組A[10..20][5..10]采用行序?yàn)橹饕绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A[10][5]的存儲(chǔ)地址是1000，則A[18][9]的地址是。4、有一個(gè)10階對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式（以行序?yàn)橹鞔鎯?chǔ)，且A[0][0]=1），則A[8][5]的地址是。5、設(shè)N行N列的下三角矩陣A已壓縮到一維數(shù)組S[1..N*（n+1）/2]中，若按行序?yàn)橹鞔鎯?chǔ)，則A[I][J]對(duì)應(yīng)的S中的存儲(chǔ)位置是6、一個(gè)稀疏矩陣如圖5.8所示，則對(duì)應(yīng)的三元組表示為：0020300000-1500007、廣義表(a,(a,b),d,e,((I,j),k))的長(zhǎng)度是,深度是8、廣義表((a),((b),c),(((d))))的表頭是,表尾是.9、廣義表((a),((b),c),(((d))))的長(zhǎng)度是,深度是10、設(shè)HEAD[p]為求廣義表p的表頭函數(shù),TAIL[p]為求廣義表p的表尾函數(shù),其中[]是函數(shù)的符號(hào),給出下列廣義表的運(yùn)算結(jié)果:HEAD[(a,b,c)]的結(jié)果是TAIL[(a,b,c)]的結(jié)果是HEAD[((a),(b))]的結(jié)果是TAIL[((a),(b))]的結(jié)果是HEAD[TAIL[(a,b,c)]]的結(jié)果是TAIL[HEAD((a,b),(c,d))]的結(jié)果是HEAD[HEAD[(a,b),(c,d)]]的結(jié)果是TAIL[TAIL[(a,(c,d))]]的結(jié)果是三、計(jì)算題。1.用三元組表表示下列稀疏矩陣：2.下列各三元組表分別表示一個(gè)稀疏矩陣，試寫出它們的稀疏矩陣。

第六章：樹和二叉樹一、單選1、如圖1所示的4棵二叉樹種,不是完全二叉樹.ABCD2、線索二叉樹是一種結(jié)構(gòu)。A.邏輯B.邏輯和存儲(chǔ)C.物理D.線性3、在線索化二叉樹中,t所指結(jié)點(diǎn)沒有左子樹的充要條件是A.t->left==NULLB.t->ltag==1C.t->ltag==1且t->left==NULLD.以上都不對(duì)4、二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其前趨和后續(xù)的線索，這種說法A．對(duì)B．錯(cuò)5、二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說法A．對(duì)B．錯(cuò)6、由于二叉樹中每一個(gè)結(jié)點(diǎn)的度最大為2，所以二叉樹是一種特殊的樹，這種說法A．對(duì)B．錯(cuò)abcdgabcdgefA.2hB.2h-1C.2h+1D.h+18、如圖示二叉樹的中序遍歷序列是A.abcdgefB.dfebagcC.dbaefcgD.defbagc9、已知某二叉樹的后續(xù)遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是A.acbedB.decabC.deabcD.cedba10、如果T2是由有序樹T轉(zhuǎn)換而來(lái)的二叉樹，那么T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的A.前序B.中序C.后序D.層次序11、如果T2是由有序樹T轉(zhuǎn)換而來(lái)的二叉樹，那么T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的A.前序B.中序C.后序D.層次序12、某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca13、二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值，小于右孩子的值。這種說法A對(duì)B錯(cuò)14、按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有種。aA.3B.4C.5D.615、一棵二叉樹如右圖示，其中序遍歷的序列為。bcA.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefghdefgh16、樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹。結(jié)論是正確的。A．樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同B．樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同C．樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同D．以上都不對(duì)17、深度為5的二叉樹至多有個(gè)結(jié)點(diǎn)。A.16B.32C.31D.1018、在一排空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊。A．只有右子樹上的所有結(jié)點(diǎn)B．只有右子樹上的部分結(jié)點(diǎn)C．只有左子樹上的部分結(jié)點(diǎn)D．只有左子樹上的所有結(jié)點(diǎn)19、樹最適合用來(lái)表示。A．有序數(shù)據(jù)元素B．無(wú)序數(shù)據(jù)元素C．元素之間具有分支層次關(guān)系的數(shù)據(jù)D．元素之間無(wú)聯(lián)系的數(shù)據(jù)20、任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序。A．不發(fā)生改變B．發(fā)生改變C．不能確定D．以上都不對(duì)21、實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不是用棧結(jié)構(gòu)，最佳方案是二叉樹采用存儲(chǔ)結(jié)構(gòu)。A．二叉鏈表B．廣義表存儲(chǔ)結(jié)構(gòu)C．三叉鏈表D．順序存儲(chǔ)結(jié)構(gòu)22、對(duì)一個(gè)滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h，則。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-123、如果某二叉樹的前序?yàn)閟tuwv，中序?yàn)閡wtvs，那么該二叉樹的后序中。A.uwvtsB.vwutsC.wuvtsD.wutsv24、具有五層結(jié)點(diǎn)的二叉平衡樹至少有個(gè)結(jié)點(diǎn)。A.10B.12C.15D.1725、如右圖示的t2示由有序樹t1轉(zhuǎn)換來(lái)得二叉樹，那么樹t1有個(gè)葉結(jié)點(diǎn)。A.4B.5C.6D.7abecfhdgIj26、設(shè)n，m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m當(dāng)前的條件是。A.n在m的右方B.n是m祖先C.n在m的左方D.n是m子孫27.假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15個(gè)，單分支結(jié)點(diǎn)數(shù)為32個(gè)，則葉子結(jié)點(diǎn)數(shù)為。A.15B.16C.17D.4728.假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18個(gè)，則它的最小高度。A.4B.5C.6D.1829.在一棵二叉樹中第五層上的結(jié)點(diǎn)數(shù)最多為。A.8B.15C.16D.3230.在一棵具有五層的滿二叉樹中，結(jié)點(diǎn)總數(shù)為。A.31B.32C.33D.1631.已知8個(gè)數(shù)據(jù)元素為(34、76、45、18、26、54、92、65)，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹后，最后兩層上的結(jié)點(diǎn)總數(shù)為。A.1B.2C.3D.432.由分別帶權(quán)為9、2、5、7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為。A.23B.37C.44D.4633.在樹中除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)分成m(m≥0)個(gè)的集合T1,T2,T3...Tm,每個(gè)集合又都是樹，此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)(1≤i≤m)。A.互不相交B.可以相交C.葉結(jié)點(diǎn)可以相交D.樹枝結(jié)點(diǎn)可以相交34.下面答案是查找二叉樹（又稱二叉排序樹）。A.二叉樹中的每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差的絕對(duì)值不大于１B.二叉樹中的每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于１C.二叉樹中的每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的D.二叉樹中的每個(gè)結(jié)點(diǎn)的關(guān)鍵字大于其左子樹（如果存在）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右子樹（如果存在）所有結(jié)點(diǎn)的關(guān)鍵字值。35.如果結(jié)點(diǎn)A有三個(gè)兄弟，而且B是A的雙親，則B的出度是。A.3B.4C.5D.136.一個(gè)深度為L(zhǎng)的滿K叉樹有如下性質(zhì)：第L層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有K棵非空子樹。如果按層次順序從１開始對(duì)全部結(jié)點(diǎn)編號(hào)，編號(hào)為n的有右兄弟的條件是。A.(n-1)%k==0B.(n-1)%k!=0C.n%k==0D.n%k!=037.在完全二叉樹中，當(dāng)i為奇數(shù)且不等于１時(shí)，結(jié)點(diǎn)i的左兄弟是結(jié)點(diǎn)，否則沒有左兄弟。A.2i-1B.i+1C.2i+1D.i-138.某二叉樹T有n個(gè)結(jié)點(diǎn)，設(shè)按某種遍歷順序?qū)中的每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)值為1,2,…,n且有如下性質(zhì)：T中任一結(jié)點(diǎn)V，其編號(hào)等于左子樹上的最小編號(hào)減1，而V的右子樹的結(jié)點(diǎn)中，其最小編號(hào)等于V左子樹上結(jié)點(diǎn)的最大編號(hào)加1。這時(shí)按編號(hào)。A.中序遍歷序列B.前序遍歷序列C.后序遍歷序列D.層次遍歷序列二、填空題1、指出樹的二叉樹的三個(gè)主要差別(1),(2),(3).2、從概念上講,樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu),將樹轉(zhuǎn)化為二叉樹的基本目的是_.3、一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu),存儲(chǔ)于數(shù)組t中，如圖8.13所示，則該二叉樹的二叉鏈表表示形式為（）。12345678910111213141516171819202122eafdgjihb圖8.13一棵二叉樹的順序存儲(chǔ)數(shù)組t4、深度為K的完全二叉樹至少有(1)個(gè)結(jié)點(diǎn),至多有(2)個(gè)結(jié)點(diǎn),若按自上而下,從左到右次序給結(jié)點(diǎn)編號(hào)(從1開始),則標(biāo)號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是(3)____________.5、在一棵二叉樹中，度為0的結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則：n0=6、一棵二叉樹的第I(I>=1)層最多有(1)個(gè)結(jié)點(diǎn);一棵有n(n>0)個(gè)結(jié)點(diǎn)的滿二叉樹共有(2)個(gè)葉子和(3)個(gè)非終端結(jié)點(diǎn).7、結(jié)點(diǎn)最少的樹為(1),結(jié)點(diǎn)最少的二叉樹為(2).8、一棵二叉樹的定義,具有三個(gè)結(jié)點(diǎn)的二叉樹有(1)-種不同的形態(tài),它們分別是(2)9、由右圖示的二叉樹，回答以下問題.a(1)其中序遍歷序列為(2)其前序遍歷序列bc(3)其后序遍歷序列為(4)該二叉樹的中序線索二叉樹為(4)def(5)該二叉樹的后序線索二叉樹為(5)(6)該二叉樹對(duì)應(yīng)的森林是(6)ghi10.以數(shù)據(jù)集{4，5，6，7，10，12，18}為結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹，其帶權(quán)路徑長(zhǎng)度為。11.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹，則該樹中所有結(jié)點(diǎn)的度之和為。12.在二叉樹的順序存儲(chǔ)中，對(duì)于下標(biāo)為5的結(jié)點(diǎn)，它的雙親結(jié)點(diǎn)的下標(biāo)為，若它存在左孩子，則左孩子結(jié)點(diǎn)的下標(biāo)為，若它存在右孩子，則右孩子結(jié)點(diǎn)的下標(biāo)為。13.假定一棵二叉樹的廣義表表示為A(B(，D)，C(E(G)，F(xiàn)))，則該樹的深度為，度為0的結(jié)點(diǎn)數(shù)為，度為1的結(jié)點(diǎn)數(shù)為，度為2的結(jié)點(diǎn)數(shù)為；C結(jié)點(diǎn)是A結(jié)點(diǎn)的孩子，E結(jié)點(diǎn)是C結(jié)點(diǎn)的孩子。14.在一棵二叉排序樹中，按遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。15.由分別帶權(quán)為3,9,6,2,5的共五個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長(zhǎng)度為2833406008545528334060085455三、計(jì)算題。1.給定如圖所示二叉樹T，請(qǐng)畫出與其對(duì)應(yīng)的中序線索二叉樹。2.試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。3.把如圖所示的樹轉(zhuǎn)化成二叉樹。4.畫出和下列二叉樹相應(yīng)的森林。5.設(shè)二叉樹BT的存儲(chǔ)結(jié)構(gòu)如下：１２３４５６７８９10┏━┳━┳━┳━┳━┳━┳━┳━┳━┳━┓Lchild┃０┃０┃２┃３┃７┃５┃８┃０┃10┃１┃┣━╋━╋━╋━╋━╋━╋━╋━╋━╋━┫data┃Ｊ┃Ｈ┃Ｆ┃Ｄ┃Ｂ┃Ａ┃Ｃ┃Ｅ┃Ｇ┃Ｉ┃┣━╋━╋━╋━╋━╋━╋━╋━╋━╋━┫Rchild┃０┃０┃０┃９┃４┃０┃０┃０┃０┃０┃┗━┻━┻━┻━┻━┻━┻━┻━┻━┻━┛(1)畫出圖。(2)寫出前序、中序、后序遍歷次序。(3)畫出后序線索二叉樹.已知一棵二叉樹先序遍歷結(jié)果為ABCDEFGHIJ，中序遍歷的結(jié)果為CBEDAHGIJF，試畫出該二叉樹。設(shè)某通訊電文由A、B、C、D、E、F六個(gè)字符組成，它們?cè)陔娢闹谐霈F(xiàn)的次數(shù)分別是16、5、9、3、30、1。試畫出編碼用的哈夫曼樹

第七章圖一、單選1.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的倍。A.1/2B.1C.2D.42.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。A.1/2B.1C.2D.43.一個(gè)有N個(gè)結(jié)點(diǎn)的無(wú)向圖最多有條邊。A.nB.n（n-1）C.n（n-1）/2D.2n4、具有4個(gè)頂點(diǎn)的無(wú)向完全圖有條邊。A6B12C16D205、具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有條邊才能確保是一個(gè)連通圖。AnBn+1Cn-1Dn/26、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要條邊。AnBn+1Cn-1Dn/27、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用領(lǐng)接矩陣表示，則該矩陣的大小是。8、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用領(lǐng)接表表示，則表頭向量的大小為（1）；所有領(lǐng)接表中的結(jié)點(diǎn)總數(shù)是（2）。（1）A.nB.n+1C.n-1D.n+e（2）A.e/2B.eC.2eD.n+e9、已知一個(gè)圖如下圖所示，若從頂點(diǎn)a出發(fā)安深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（1）；按寬度搜索法遍歷，則可能得到的一種頂點(diǎn)序列為（2）.abecdf(1)A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b(2)A.a,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,e,b,d10.已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示.=1\*GB2⑴根據(jù)有向圖的深度優(yōu)先遍歷算法,從頂點(diǎn)v1出發(fā),所得到的頂點(diǎn)序列是(1)A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v2=2\*GB2⑵根據(jù)有向圖的寬度優(yōu)先遍歷算法,從頂點(diǎn)v1出發(fā),所得到的頂點(diǎn)序列是(2)A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v21324^23454524一個(gè)有向圖的領(lǐng)接表存儲(chǔ)結(jié)構(gòu)11.采用鄰接表存儲(chǔ)的圖的寬度優(yōu)先遍歷算法類似于二叉樹的.A先序遍歷B中序遍歷C后序遍歷D按層遍歷12.判定一個(gè)有向圖是否在回路除了可以利用拓?fù)渑判蚍椒ㄍ?還可以利用.A求關(guān)鍵路徑的方法B求最短路徑的Dijkstra的方法C寬度優(yōu)先遍歷算法D深度優(yōu)先遍歷算法13.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的倍。A．1/2B.1C.2D.414.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。A．1/2B.1C.2D.415.有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有___________條邊。A．14B.28C.56D.11216.有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有條邊。A．5B.6C.7D.817.有8個(gè)結(jié)點(diǎn)的有向完全圖有條邊。A．14B.28C.56D.11218.用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用來(lái)實(shí)現(xiàn)算法的。A．棧B.隊(duì)列C.樹D.圖19.用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用來(lái)實(shí)現(xiàn)算法的。A．棧B.隊(duì)列C.樹D.圖A．0243156B.0136542C.0423165A．0243156B.0136542C.0423165D.036154221.已知圖的鄰接矩陣同上題，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是____A．0243156B.0135642C.0423165D.013425622.已知圖的鄰接矩陣同上題，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是____A．0243651B.0136425C.0423156D.013425623.已知圖的鄰接矩陣同上題，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是____A．0243165B.0135642C.0123465D.012345624.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是____A．0132B.A．0132B.0231C.0321D.012325.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是____A．0321B.A．0321B.0123C.0132D.031226.深度優(yōu)先遍歷類似于二叉樹的____A．先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷27廣度優(yōu)先遍歷類似于二叉樹的____A．先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷28.任何一個(gè)無(wú)向連通圖的最小生成樹____A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在二、填空題1.n個(gè)頂點(diǎn)的連通圖至少條邊.2.在無(wú)權(quán)圖G鄰接矩陣A,若(vi,vj)或<vi,vj>屬于圖G的邊集,則對(duì)應(yīng)元素A[i][j]等于否則等于3.在無(wú)向圖G的鄰接矩陣A中,若A[i][j]等于1,則A[j][i]等于.4.已知圖G的鄰接表如圖9.7所示,其從頂點(diǎn)v1出發(fā)的深度優(yōu)先搜索序,其從頂點(diǎn)v1出發(fā)的寬度優(yōu)先搜索序列為v2v5v4^v1v2v3v5^v3v4^v6^v5v6^v4v6v3^5.已知一個(gè)圖的鄰接矩陣表示,計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法6.已知一個(gè)圖的鄰接矩陣表示,刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是7.圖有、等存儲(chǔ)結(jié)構(gòu)，遍歷圖有、等方法。8.有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的。9.如果n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有棵生成樹。10.n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為。11.n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接表存儲(chǔ)，則空間復(fù)雜度為。12.設(shè)有一稀疏圖G，則G采用存儲(chǔ)較省空間。13.設(shè)有一稠密圖G，則G采用存儲(chǔ)較省空間。14.圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于圖。15.已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)頂點(diǎn)出發(fā)的方法是。16.圖的深度優(yōu)先遍歷序列惟一的。17.n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為；若采用鄰接表存儲(chǔ)時(shí)，該算法的時(shí)間復(fù)雜度為。18.n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，廣度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為；若采用鄰接表存儲(chǔ)，該算法的時(shí)間復(fù)雜度為。19.圖的BFS生成樹的樹高比DFS生成樹的樹高。20.用普里姆(Prim)算法求具有n個(gè)頂點(diǎn)e條邊的圖的最小生成樹的時(shí)間復(fù)雜度為；用克魯斯卡爾(Kruskal)算法的時(shí)間復(fù)雜度是。21.若要求一個(gè)稀疏圖G的最小生成樹，最好用算法來(lái)求解。22.若要求一個(gè)稠密圖G的最小生成樹，最好用算法來(lái)求解。23.用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長(zhǎng)度的次序來(lái)得到最短路徑的。24.拓?fù)渑判蛩惴ㄊ峭ㄟ^重復(fù)選擇具有個(gè)前驅(qū)頂點(diǎn)的過程來(lái)完成的。三、計(jì)算題1、設(shè)無(wú)向圖G如下圖：BEADGCF試給出該圖的鄰接矩陣；該圖的鄰接表；(3)從A出發(fā)的“深度優(yōu)先”遍歷序列；(4)從A出發(fā)的“廣度優(yōu)先”遍歷序列。2.已知如圖所示的有向圖，請(qǐng)給出該圖的:頂點(diǎn)12頂點(diǎn)123456入度出度鄰接矩陣；鄰接表；逆鄰接表。3.請(qǐng)對(duì)下圖的無(wú)向帶權(quán)圖：(1)寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；(2)寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。4.已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。5.試?yán)肈ijkstra算法求圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)。

第九章：查找一、單選1．順序查找法適合于存儲(chǔ)結(jié)構(gòu)為的線性表.A.散列存儲(chǔ)B.順序存儲(chǔ)或鏈接存儲(chǔ)C壓縮存儲(chǔ)D索引存儲(chǔ)2.對(duì)線性表進(jìn)行二分查找時(shí),要求線性表必須.A.已順序方式存儲(chǔ)B.已鏈接方式存儲(chǔ)C.已順序方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序D.已鏈接方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序3.采用順序查找方法查找長(zhǎng)度為n的線性表時(shí),每個(gè)元素的平均查找長(zhǎng)度為.A.nB.n/2C.(n+1)/2D.(n-1)/24.采用二分查找方式查找長(zhǎng)度為n的線性表時(shí),每個(gè)元素的平均查找長(zhǎng)度為.A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)5.二分查找和二叉排序樹的時(shí)間性能.相同B.不相同6.設(shè)哈希表長(zhǎng)m=14,哈希函數(shù)H(key)=key%11.表中已有4個(gè)結(jié)點(diǎn):addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址為空。如用二次探測(cè)再散列處理沖突,關(guān)鍵字為49的結(jié)點(diǎn)的地址是.A.8B.3C.5D.97.有一個(gè)長(zhǎng)度為12的有序表,按二分查找法對(duì)該表進(jìn)行查找,再表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為.A.35/12B.37/12C.39/12D.43/128.采用分塊查找時(shí),若線性表中共有625個(gè)元素,查找每個(gè)元素的概率相同,假設(shè)采用順序查找來(lái)確定結(jié)點(diǎn)所在的塊時(shí),每塊應(yīng)分個(gè)結(jié)點(diǎn)最佳.A.10B.25C.6D.6259.如果要求一個(gè)線性表既能較塊地查找,有能適應(yīng)動(dòng)態(tài)變化的要求,可以采用查找方式.A.分塊B.順序C.二分D.散列10.在表長(zhǎng)為ｎ的鏈表中進(jìn)行線性查找，它的平均查找長(zhǎng)度為Ａ.ＡＳＬ＝ｎ;Ｂ.ＡＳＬ＝（ｎ＋１）／２;Ｃ.ＡＳＬ＝＋１;Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１11.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中比較大小，查找結(jié)果是失敗。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，5012.對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較次關(guān)鍵字。A．3B．4C．5D．613.鏈表適用于查找A．順序B．二分法C．順序，也能二分法D．隨機(jī)14.折半搜索與二叉搜索樹的時(shí)間性能_________________。A.相同B.完全不同C.有時(shí)不相同D.數(shù)量級(jí)都是O（log2n）15.要進(jìn)行線性查找，則線性表A；要進(jìn)行二分查找，則線性表B；要進(jìn)行散列查找，則線性表C。某順序存儲(chǔ)的表格，其中有90000個(gè)元素，已按關(guān)鍵項(xiàng)的值的上升順序排列?，F(xiàn)假定對(duì)各個(gè)元素進(jìn)行查找的概率是相同的，并且各個(gè)元素的關(guān)鍵項(xiàng)的值皆不相同。當(dāng)用順序查找法查找時(shí)，平均比較次數(shù)約為D，最大比較次數(shù)為E。供選擇的答案：A~C：①必須以順序方式存儲(chǔ)②必須以鏈表方式存儲(chǔ)③必須以散列方式存儲(chǔ)④既可以以順序方式，也可以以鏈表方式存儲(chǔ)⑤必須以順序方式存儲(chǔ)且數(shù)據(jù)元素已按值遞增或遞減的次序排好⑥必須以鏈表方式存儲(chǔ)且數(shù)據(jù)元素已按值遞增或遞減的次序排好D，E：①25000②30000③45000④90000答案：A=B=C=D＝E＝16.數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。鏈表是一種A，它對(duì)于數(shù)據(jù)元素的插入和刪除B。通常查找線性表數(shù)據(jù)元素的方法有C和D兩種方法，其中C是一種只適合于順序存儲(chǔ)結(jié)構(gòu)但E的方法；而D是一種對(duì)順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)均適用的方法。供選擇的答案：A：①順序存儲(chǔ)線性表②非順序存儲(chǔ)非線性表 ③順序存儲(chǔ)非線性表 ④非順序存儲(chǔ)線性表B： ①不需要移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針②不需要移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針 ③只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針 ④既需移動(dòng)結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針C：①順序查找②循環(huán)查找 ③條件查找 ④二分法查找D：①順序查找②隨機(jī)查找 ③二分法查找 ④分塊查找E：①效率較低的線性查找②效率較低的非線性查找 ③效率較高的非線性查找④效率較高的線性查找答案：A＝B＝C＝D＝E＝17.在二叉排序樹中，每個(gè)結(jié)點(diǎn)的關(guān)鍵碼值A(chǔ)，B一棵二叉排序，即可得到排序序列。同一個(gè)結(jié)點(diǎn)集合，可用不同的二叉排序樹表示，人們把平均檢索長(zhǎng)度最短的二叉排序樹稱作最佳二叉排序，最佳二叉排序樹在結(jié)構(gòu)上的特點(diǎn)是C。供選擇的答案A：①比左子樹所有結(jié)點(diǎn)的關(guān)鍵碼