數(shù)據(jù)結(jié)構(gòu)期末考試

1、數(shù)據(jù)結(jié)構(gòu)期末考試作者:日期:12數(shù)據(jù)結(jié)構(gòu)課后練習(xí)題一、填空題(第二章)1、順序表中邏輯上相鄰元素的物理位置世范，單鏈表中邏輯上相鄰的元素物理位置可以相鄰，也可以不相鄰。一2、在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素，平均要移動(dòng) n-i個(gè)元素，如果在第i個(gè)元素之前插入一個(gè)元素，平均要移動(dòng) n-i+1個(gè)元素。3、在一個(gè)單鏈表中，若 p所指的結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s結(jié)點(diǎn)，則執(zhí)行s->next=p->next;p->next=s。4、在一個(gè)長(zhǎng)度為n的順序表的表尾插入一個(gè)新元素的時(shí)間負(fù)責(zé)度為O。5、非空的單循環(huán)鏈表head的尾結(jié)點(diǎn)(由指針 P所指)滿足p->next=hea

2、d。(第三章)1 .棧和隊(duì)列都是線性結(jié)構(gòu)，對(duì)于棧來(lái)說(shuō)，它的插入和刪除操作智能在棧頂進(jìn)行,而隊(duì)列的插入操作是在隊(duì)星進(jìn)行，刪除元素的操作是在隊(duì)首進(jìn)行。2 .設(shè)有一順序棧s,元素s1,s2,s3,s4,s5,s6吃入棧，如果六個(gè)元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)該是3。3 .在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。4 .從棧頂指針為T(mén)op的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將結(jié)點(diǎn)值保存在X中，進(jìn)行的操作是x=Top->data;Top=Top->next。5 .中綴表達(dá)式(A+B ) *D+E/(F+A*D)對(duì)應(yīng)的后綴表達(dá)式為 AB+D*EFAD*+/+

3、6 .在操作序歹U push (1); push (2) ;pop (2);push (3); push (4); push (5); push (6); push (7); pop 之后棧頂元素和棧底元素分別是6和1。7 .在操作序歹U Qinsert(1);Qinsert(2);Qdelete(1);Qdelete(2);Qinsert(3);Qinsert(4);Qinsert (5); Qinsert(6);Qinsert(7);Qdelete(3);Qdelete(4);Qinsert(8);Qinsert(9);之后隊(duì)頭元素和隊(duì)尾元素分別是 5_和9。(第四章)1 .串是由0個(gè)或多

4、個(gè)字符組成的序列。2 .不包含任何字符串 稱為空串:由一個(gè)或多個(gè)空格組成的串 稱為空格串。3 .子用的定位運(yùn)算 稱為串的模式匹配;被匹配的主串稱為目標(biāo)串,子串稱為模式。(第五章)1 .廣義表的深度是等于括號(hào)嵌套的最大層數(shù)。2 .在廣義表的存儲(chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)均包含3個(gè)域。3 .一個(gè)廣義表的深度等于 括號(hào)!嵌套的最大層數(shù)。4 .對(duì)矩陣壓縮是為了 節(jié)省存儲(chǔ)空間。5 .當(dāng)廣義表中的每個(gè)元素都是原子時(shí)，廣義表便成了線性表。6 .廣義表的表尾是指除第一個(gè)元素之外，其余元素組成的表。7 .廣義表的 深必定義為廣義表中括弧的重?cái)?shù)。8 .設(shè)廣義表L=(), (),則hesd (L)是 ();tail (L)是

5、();L的長(zhǎng)度是2；深度是2。9 .廣義表(a, (a,b) ,d,e,(i,j),k)的長(zhǎng)度是5,深度是3。(第六章)1 .對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為nzlo2 .一顆二棵深度為5的滿二叉樹(shù)中的結(jié)點(diǎn)樹(shù)為31個(gè)。3 .假定一棵樹(shù)的廣義表表示為A (B(C,D(E,F,G),H(I,J),則樹(shù)種所含的結(jié)點(diǎn)數(shù)為 10個(gè)，樹(shù)的深度為四個(gè)，樹(shù)的度為3.4 .假定一棵樹(shù)的廣義表表示為A ( B(C,D(E,F,G),H(I,J)，則度為3, 2, 1, 0的結(jié)點(diǎn)樹(shù)分別為 2、1、1和§個(gè)。5 .假定一棵樹(shù)的廣義表表示為A ( B(C,D(E,F,G),H(I,J),則

6、結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為 B，孩子結(jié)點(diǎn)為I和J。6 .在哈夫曼編碼中，若編碼長(zhǎng)度只允許小于等于4,則除了已對(duì)兩個(gè)字符編碼為0和10外，還可以最多對(duì)4個(gè)字符編碼。7 .對(duì)于一棵二叉樹(shù)，若一個(gè)結(jié)點(diǎn)的編碼為i,則它的左孩子結(jié)點(diǎn)的編號(hào)為2i,右孩子結(jié)點(diǎn)的編號(hào)為2i+1,雙親結(jié)點(diǎn)編號(hào)為i/2 o8 .在一棵二叉樹(shù)中，第 5層上的結(jié)點(diǎn)數(shù)最多為 16。9 .假定一棵二叉樹(shù)的結(jié)點(diǎn)樹(shù)為18,則它的最小深度為 5,最大深度為18。10 .假定一棵二叉樹(shù)順序存儲(chǔ)在一維數(shù)組a中，則ai元素的左孩子元素為a2i,右孩子元素為 a2i+1,雙親元素(i-1)為ai/2。11 .假定一棵二叉樹(shù)順序存儲(chǔ)在一維數(shù)組a中，但讓編號(hào)為1

7、的結(jié)點(diǎn)存入a0元素中，讓編號(hào)為 2的結(jié)點(diǎn)存入a1元素中，其余類推，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)對(duì)應(yīng)的存儲(chǔ)位置為2i-1。12 .對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，對(duì)應(yīng)二叉鏈接表中指針總數(shù)為2n個(gè)，其中n-1個(gè)用于指向孩子結(jié)點(diǎn)，n+1個(gè)指向空閑著。13 .一棵二叉樹(shù)廣義表表示為a(b(d(h),c(e,f(g,i(k),該樹(shù)的結(jié)點(diǎn)數(shù)為10個(gè)，深度為5O14 .假定一棵二叉樹(shù)廣義表表示為a (b(c),d(e,f)，則對(duì)它進(jìn)行的先序遍歷結(jié)果為a b c d e f,中序遍歷結(jié)果為c b a e d f,后續(xù)序遍歷結(jié)果為 c b e f d a。(第七章)1 .有向圖G用鄰接矩陣存儲(chǔ)，其第i行的所有元素之

8、和等于頂點(diǎn)i的出度。2 .圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)之適用于有向圖。3 .圖的深度優(yōu)先遍歷序列 不是唯一的。4 .圖的BFS生成樹(shù)的樹(shù)高比 DFS生成樹(shù)的樹(shù)高 矮或相當(dāng)。5 .拓?fù)渑判蜉敵龅捻旤c(diǎn)數(shù)小于有向圖的頂點(diǎn)數(shù)，則該圖一定存在 如。6 .若要求一個(gè)稀疏圖 G的最小生成樹(shù)，最好用 Kruskal算法來(lái)求解。1 .關(guān)鍵字是數(shù)據(jù)元素(或記錄)中某個(gè)屬性，用它的標(biāo)識(shí)(或識(shí)別)一個(gè)查找表中的 數(shù)據(jù)元素(或記錄)。并且，在一個(gè)查找表中，能夠唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素(或記錄)的關(guān)鍵字稱為主關(guān)鍵字。2 .查找又稱為(檢索),它是根據(jù)給定的某個(gè)值，在查找表中確定是否有元素或記錄的關(guān)鍵字等于給定值的操作。若操作之后確定

9、表中存在這樣的記錄，則稱為查找是成功的，否則稱為不成功(或失敗)。3 .平均查找長(zhǎng)度是指為確定所查找的記錄在查找表中的位置，需要與給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的平均伯(或期望值)。4 .采用順序查找法查找長(zhǎng)度為n大的線性表時(shí)，假設(shè)查找成功與查找不成功的概率對(duì)等，對(duì)每個(gè)記錄的查找概率也相等，則平均查找長(zhǎng)度為3 (n+1) /4。5 .折半查找又稱為 二分杳找,其查找思路是：每次將給定值與查找表中所要查找區(qū)域中間位置的關(guān)鍵字進(jìn)行比較，而不是查找表中的第一條或最后一條。6 .在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是哈希表杳找法。7 .哈希表的查找小綠主要取決于哈希表建表時(shí)選擇的哈希函

10、數(shù) 和裝埴因子。8 .構(gòu)造哈希函數(shù)的方法有 直接岸址法、數(shù)字分析法、平方取中法、折疊法和除留余數(shù)法。9 .假定有K個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這K個(gè)關(guān)鍵字存入哈希表中，至少要進(jìn)行(K/1 )82_次探測(cè)。10 .二叉排序樹(shù)又稱為 二叉杳找樹(shù)，它或者是一棵空樹(shù)，或者是具有下列性質(zhì)的一棵二叉樹(shù)；(1)若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值。(2)若右子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值大干根結(jié)點(diǎn)的俏。(3)左、右子樹(shù)又分別是一棵二叉排序樹(shù)。11 .平衡二叉樹(shù)是有 Abelson-Velskil和Landis提出的一種附加一定限制條件的二叉樹(shù)。又稱為AVL樹(shù)。平衡二叉樹(shù)定義為：它或者

11、是一棵空樹(shù)；或者是具有這樣性質(zhì)的二叉樹(shù)；它的左子樹(shù)和右子樹(shù)都是一棵平衡二叉樹(shù),且左子樹(shù)和右子樹(shù)的深度之差絕對(duì)值不大于112.在向哈希表中存儲(chǔ)關(guān)鍵字的時(shí)候，有時(shí)會(huì)出現(xiàn)一個(gè)待插入關(guān)鍵字的記錄已經(jīng)被占用的情況，這種對(duì)不同關(guān)鍵字得到同一地址的現(xiàn)象稱為沖突（或碰撞），相應(yīng)的把這些具有相同哈希函數(shù)值得關(guān)鍵字稱為同義而。 13.構(gòu)造哈希函數(shù)應(yīng)當(dāng)盡量減少?zèng)_突，但是還是無(wú)法避免沖突的發(fā)生，一旦沖突發(fā)生了，就必須訊企鵝合適的方法來(lái)解決沖突。常用開(kāi)放地址法和鏈地址法兩種方法來(lái)解決沖突。 14.對(duì)長(zhǎng)度n=50的有序表進(jìn)行折半查找，則對(duì)應(yīng)的判定樹(shù)高度為6,判定樹(shù)前5層的結(jié)點(diǎn)樹(shù)是31,最后一層的結(jié)點(diǎn)樹(shù)為9。二、單選題（第

12、二章）1、線性表L= （ ai,a2,，a，a）,下列說(shuō)法正確的是（ D） A、每個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼 B、線性表中至少有一個(gè)元素C、表中諸元素的排列順序必須是從小到大或由大到小D、除第一個(gè)元素和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。2、對(duì)于順序表，以下說(shuō)法錯(cuò)誤的是（ A）A、順序表是一維數(shù)組實(shí)現(xiàn)的線性表，數(shù)組的下標(biāo)可以看成是元素的絕對(duì)地址 B、順序表的所有存儲(chǔ)結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列 C、順序表的特點(diǎn)是邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰 D、順序表的特點(diǎn)是邏輯上相鄰的元素，存儲(chǔ)在物理位置也相鄰的單元中 3、對(duì)順序表上的插入、

13、刪除、算法的時(shí)間復(fù)雜度分析來(lái)說(shuō)，通常以（ B）對(duì)標(biāo)準(zhǔn)操作。 A、條件判斷 B、結(jié)點(diǎn)移動(dòng)C、算術(shù)表達(dá)式D、賦值語(yǔ)句4、對(duì)于順序表的優(yōu)、缺點(diǎn)，以下說(shuō)法錯(cuò)誤的是（ C） A、無(wú)須為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間 B、可以方便的隨機(jī)存儲(chǔ)表中任一結(jié)點(diǎn) C、插入和刪除操作較方便D、由于順序表要求占用連續(xù)的空間，存儲(chǔ)分配只能預(yù)先進(jìn)行（靜態(tài)分配）5、在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中，在任一結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)所需移動(dòng)的點(diǎn)的平均次數(shù)為（B）A、nB、n/2C、（n-1）/2D、（n+1）/26、在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中，刪除一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為（C）A、nB、n/2C、（n-1）

14、/2D、（n+1）/27、帶頭結(jié)點(diǎn)的單鏈表head為空的條件是（B）A、head=NULL B、head->next=NULL C、head->next=head D、head!=NULL8、非空循環(huán)單鏈表 head的尾結(jié)點(diǎn)*p滿足（C）A、p->next=NULLB、p=NULL C、p->next=head D、p=head9、在循環(huán)雙鏈表的*p結(jié)點(diǎn)之后插入*s滿足（D）A、p->next=s;s->prior=p;p->next->prior=s;s->next=p->next; B、p->next=s;p->nex

15、t->prior=s;s->prior=p;s->next=p->next; C、s->prior=p;s->next=p->next;p->next=s;p->next->prior=s; D、s->prior=p;s->next=p->next;p->next->prior=s;p->next=s; 10、在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是（ D） A、單鏈表 B、雙鏈表C、循環(huán)列表D、順序表（第三章）1.有一棧的輸入序列是a、b、c,則通過(guò)入棧、出棧操作可能得到a、b、c的不同

16、排列個(gè)數(shù)為（B）。A. 42 .和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是(A通常不會(huì)出現(xiàn)棧滿的情況C插入操作更容易實(shí)現(xiàn)3 .若一個(gè)棧的輸入序列是1、2、A不確定 B n-i4 .一個(gè)棧的入棧序列是a、b、c、A e、d、c、b、a B d、e、c、5 .一個(gè)隊(duì)列的入隊(duì)列是1、2、3、A. 4、3、2、1B. 1、2、6 .順序列隊(duì)的出隊(duì)操作為(B)A sq.front=(sq.front+1)%maxsizeCsq.rear=(sq.rear+1)maxsize7 .循環(huán)隊(duì)列q的出隊(duì)操作為(A)A q,front=(q.front+1)%maxsizeC q.rear=(q.rear+1)%m

17、axisize8 .循環(huán)隊(duì)列用數(shù)組A0 則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是A.(rear-front+m)%mC.read-front-19 .在一個(gè)鏈隊(duì)中，假設(shè)A)。B通常不會(huì)出現(xiàn)?？盏那闆rD刪除操作更容易實(shí)現(xiàn)3、4、n,輸出序列第一個(gè)元素是C n-i+1D n-i-1d、e,則棧的不可能輸出序列是( b、a C d、c、e、a、b D a、4,則隊(duì)列的可能輸出序列是(B)4C.1、4、3、2B sq.front=sq.front+1D sq.rear=sq.rear+1B q.front=q.front+1Dq.rear=q.rear+13、n,則第i個(gè)輸出元素是(C)。C)b、 c、 d、 eD

18、.3、2、4、1m-1存放其元素值，已知其頭、尾指針?lè)謩e是(A)。B read-front+1D.read-frontf和r分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算是(front 和 rear,C)。A,r=f->next B.r=r->next(第四章)1 .串是(D)A. 一些符號(hào)構(gòu)成的序列C. 一個(gè)以上的字符構(gòu)成的序列C.f=f->next D f=r->nextB.一些字母構(gòu)成的序列D.任意有限個(gè)字符構(gòu)成的序列2.S1= " abcd "S2= " cd,” 貝U S2 在 S1 中的位置是(C)。A.1B.2C.3D.43 .下

19、列為空串的是(C)。A. " B. ”“ C.” "D "4 .樸素模式匹配算法在最好的情況下的運(yùn)行時(shí)間是(以一次內(nèi)循環(huán)為單位)(C)。A.M B.NC.MXN D.M+N(第五章)1 .已知廣義表LS= (a,b,c), (d,e,f),運(yùn)用head和tail函數(shù)取出LS中元素e的運(yùn)算是(C)A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)2 .將一個(gè)A1100,110曲三對(duì)角矩陣，按行優(yōu)先存入一維數(shù)組 B1 298中，A中元素a66, 65 (即該元

20、 素下標(biāo)i=66,j=65 )在B數(shù)組中白位置 K為(B)A.198B.195C.197D.1963 .若廣義表 A滿足Head (A) =Tail (A),則A為(B)。A.()B.()C.(),()D.(),(),()4 .廣義表 A= (a,b,(c,d),(e,(f,g)，則下面式子 Head (Tail(Head(Tail(Tail(A)的值為(D)。A.(g) B. (d) C.cD.d5 .二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，其行下標(biāo) i=0,1, 丁 8,列下標(biāo)j=1,2,，10.若A按行先 存儲(chǔ)，元素A8,5的起始地址與當(dāng) A按列先存儲(chǔ)時(shí)的元素(B)的起始地址相同。設(shè)每

21、個(gè)字符占一個(gè)字節(jié)。A. A8 , 5B.A3 , 10C,A5 , 8D.A0 , 96 .在以下的敘述中，正確的是（ B）A.線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B.二維數(shù)組是其數(shù)據(jù)元數(shù)為線性表的線性表C.棧的操作方式是先進(jìn)先出D.隊(duì)列的操作方式是先進(jìn)后出7二維數(shù)組SA中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從07,歹U下標(biāo)j從09,從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素 SA47的起始地址為（B）。A.SA+141B.SA+180C.SA+222D.SA+2258 .下面結(jié)論正確的是（B）。A. 一個(gè)廣義表的表頭肯定不是一個(gè)廣義表。B. 一個(gè)廣義表的表尾肯定是一個(gè)廣義表。

22、C.廣義表L=（）,（A,B）的表頭為空表D.廣義表中原子個(gè)數(shù)即為廣義表的長(zhǎng)度9 .下面說(shuō)法不正確的是（A）A.廣義表的表頭總是一個(gè)廣義表B.廣義表的表尾總是一個(gè)廣義表C.廣義表難以用順序存儲(chǔ)結(jié)構(gòu)D,廣義表可以是一個(gè)多層次的結(jié)構(gòu)（第六章）1 .一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足（C）。A.所有的結(jié)點(diǎn)均無(wú)左孩子B.所有的結(jié)點(diǎn)均無(wú)右孩子C.只有一個(gè)葉子結(jié)點(diǎn)D.是任意一棵二叉樹(shù)2 .一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中椰子結(jié)點(diǎn)個(gè)數(shù)是（ D）。A.250B.500C.254D.以上答案都不對(duì)3 .任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在前（先）序、中序、后序遍歷序列中的相對(duì)次序

23、（A）。A不發(fā)生變化B.發(fā)生變化C.不能確定4 .設(shè)A,B為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)， A在B前面的條件是（B）。.A在B的右方B. A在B的左方C.A是B的祖先D.A是B的子孫5 .在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，數(shù)值結(jié)點(diǎn)最大編號(hào)為（D）A. （n+1）/2B.（n-1）/2C. n/2D. n/26 .在N個(gè)結(jié)點(diǎn)的線索二叉樹(shù)中，線索的數(shù)目為（C）。A.N-1B.NC.N+1 D.2N7 .設(shè)深度為K的二叉樹(shù)上只有度為 0和度為2的結(jié)點(diǎn)，則這類二叉樹(shù)上所含的結(jié)點(diǎn)總數(shù)為（ C）A.K+1B.2KC. 2K 1D, 2K+18 .下列有關(guān)二叉樹(shù)的說(shuō)法，正確的是（B）。A.二叉樹(shù)的度

24、為2B. 一棵二叉樹(shù)度可以小于2C.二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹(shù)中任意個(gè)結(jié)點(diǎn)的度都為29.在一棵深度為 H的完全二叉樹(shù)中,A.2HB.2 H-1C.2H-1所含結(jié)點(diǎn)的個(gè)數(shù)不小于（D.2H+1D）。10.在一棵具有N個(gè)結(jié)點(diǎn)的二叉樹(shù)第I層上，最多具有（C）個(gè)結(jié)點(diǎn)。A. 2IB. 2H-1C. .2H -1D.2N11 .在下列情況下，可稱為二叉樹(shù)的是（A.每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的樹(shù)C.每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的有序樹(shù)12 .樹(shù)最適合用來(lái)表示（C）。A.有序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)A）。B.哈夫曼樹(shù)D.每個(gè)結(jié)點(diǎn)只有一棵右子樹(shù)B.無(wú)序數(shù)據(jù)元素D.元素之間無(wú)聯(lián)系的數(shù)據(jù)A）的二

25、叉樹(shù)。13 .某二叉樹(shù)的前序序列和后序序列正好相反，則二叉樹(shù)A.空或只有一個(gè)結(jié)點(diǎn)B.任一結(jié)點(diǎn)無(wú)左子樹(shù)C.高度等于其結(jié)點(diǎn)數(shù)D.任一結(jié)點(diǎn)無(wú)右子樹(shù)14 .按照二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有（C）種。.A.3B.4C.5D.615 .對(duì)一個(gè)滿二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)結(jié)點(diǎn)，深度為h,則（D）。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-116 .在一非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊（ A）。A.只有右子樹(shù)上的所有結(jié)點(diǎn)B.只有右子樹(shù)上的部分結(jié)點(diǎn)C.只有左子樹(shù)上的部分結(jié)點(diǎn)D.只有左子樹(shù)上的所有結(jié)點(diǎn)17 .任何一棵二叉樹(shù)的結(jié)點(diǎn)在先序、中序、后序遍歷中的相對(duì)次序（ A）。A.不發(fā)生改變

26、B.發(fā)生改變C.不能確定D.以上都不對(duì)D)18 .已知某二叉樹(shù)的后序遍歷序列是dabec,中序遍歷序列是 debac,它的前序遍歷序列是（A.acbedB.decabC.deabc D.cedba19 .由帶權(quán)為8、2、5、7的4個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為（ DA.23B.37C.46D.4320 .對(duì)二叉排序樹(shù)進(jìn)行（B）遍歷，可以得到該二叉樹(shù)所有結(jié)點(diǎn)構(gòu)成的排序序列。A.前序 B.中序C.后序D.按層次（第七章）1 .在一個(gè)有向圖中，所有頂點(diǎn)的入度和等于所有頂點(diǎn)的出度之和的（ B）倍。A 1/2B.1C.2D.42 .用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常采用（ B）來(lái)實(shí)

27、現(xiàn)算法。A.棧B.隊(duì)列C.樹(shù)D.圖3 .具有n個(gè)頂點(diǎn)的無(wú)向完全圖，邊的總數(shù)為（D）。A,nB.n+1C.2n-1D.n （n-1） /24 .有n個(gè)頂點(diǎn)的連通 G的最小生成樹(shù)有（C）條邊。A.n-1B.nC.n+1D.不確定5 .一個(gè)有向無(wú)環(huán)圖的拓?fù)湫蛄袀€(gè)數(shù)是（B）。A.1個(gè) B.1個(gè)或多個(gè) C.0個(gè) D.多個(gè)6 .在AOE網(wǎng)中，入度為0的頂點(diǎn)稱為（B）A.起點(diǎn) B.源點(diǎn)C.終點(diǎn)D.匯點(diǎn)7 .Prim算法的時(shí)間復(fù)雜度是（B）A.O （n） B.O （n2）C.O （e） D.O（eloge）8 .在無(wú)向圖的鄰接矩陣 A中，若Aij=1 ,則A皿i的值為（C）A.i+jB.i-jC.1D.0（第

28、八章）1 .靜態(tài)查找表與動(dòng)態(tài)查找表的根本區(qū)別在于（ B）A.它們的邏輯結(jié)構(gòu)不一樣B.施加在其上的操作不一樣C.所包含的數(shù)據(jù)元素類型不一樣D.存儲(chǔ)實(shí)現(xiàn)不一樣2 .順序查找適用于存儲(chǔ)結(jié)構(gòu)為（C）的線性表。A.哈希表B.壓縮存儲(chǔ)C.順序存儲(chǔ)或鏈接存儲(chǔ)D.索引存儲(chǔ)3 .對(duì)線性表進(jìn)行折半查找最方便的存儲(chǔ)結(jié)構(gòu)是（B）。A.順序表B.有序的順序表C.鏈表D,有序的鏈表4 .對(duì)一個(gè)排好序的線性表，用折半查找法檢索表中的元素，被檢索的表應(yīng)當(dāng)采用（A）。A.順序存儲(chǔ)B.鏈接存儲(chǔ)C.散列法存儲(chǔ)D.存儲(chǔ)表示不受限制5 .若在線性表中采用折半查找法查找元素，該線性表應(yīng)該（ C）。A.元素按值有序B.采用順序存儲(chǔ)結(jié)構(gòu)C.

29、元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)D.元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)6 .在順序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半查找法查找關(guān)鍵碼值11,所需的關(guān)鍵碼比較次數(shù)為(C)。A.2B.3C.4D.57 .用折半查找法查找一個(gè)長(zhǎng)度為10的、排好序的線性表，查找不成功時(shí)，最多需要比較(C)次。A.5B.2C.4D.18 .采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為( C)。A.nB.n/2 C. (n+1) /2D.(n-1)/29 .有一個(gè)長(zhǎng)度為12的有序表，按折半查找法對(duì)該表進(jìn)行查找，在表內(nèi)每個(gè)元素等概率情況下查找成功時(shí)所需的平均比較次數(shù)

30、是(B)A.35/12B.37/12C.39/12D.41/1210 .設(shè)有100個(gè)元素，用折半查找法進(jìn)行查找時(shí)，最小比較次數(shù)是( D)。A.1B.2C.4D.711 .利用逐點(diǎn)插入法建立序列(50,72,43,85,75,20,35,45,65,30)對(duì)應(yīng)的二叉排序樹(shù)以后，查找元素35要進(jìn)行(A)次元素間的比較。A.4B.5C.6D.712 .在關(guān)鍵字隨機(jī)分布的情況下，用二叉排序樹(shù)的方法進(jìn)行查找，其查找長(zhǎng)度與(B)量級(jí)相當(dāng)。A順序查找B折半查找C分塊查找D以上都不正確13 .如果要求一個(gè)線性表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用(C)查找方法。A順序B折半C散列D以上都不正確14

31、 .一棵平衡二叉樹(shù)，其每個(gè)非終端節(jié)點(diǎn)的平衡因子均為0,則該樹(shù)共有(D)個(gè)結(jié)點(diǎn)。A.2 k-1-1B.2k-1C2k-1+1D.2k-115 .設(shè)哈希表上 m=14,哈希表函數(shù) H(key尸key%11。表中已有 4 個(gè)結(jié)點(diǎn)：addr(15)=4 ; addr(38)=5 ; ;addr(61)=6 ; addr(84)=7;其余地址為空，如果用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是(D)A.9B.8C.5D.316 .在哈希查找中，平均查找長(zhǎng)度主要與(C)有關(guān)。A.哈希表長(zhǎng)度B哈希元素的個(gè)數(shù)C裝填因子 D處理沖突方法17 .在采用線性探測(cè)法處理沖突的散列表上，假定裝填因子”的值為0

32、.5,則查找任一元素的平均查找長(zhǎng)度約為(B)A 1B 1.5C2D3.518 .在采用鏈接法處理沖突的散列表上，假定裝填因子 a的值為4,則查找任一元素的平均查找長(zhǎng)度約為(A)A 3B 3.5C2D 419 .若對(duì)一組關(guān)鍵字(23,44,36,48,52,73,64,58)建立散列表，采用 H (K) =K%7計(jì)算散列地址，則同義詞 元素的個(gè)數(shù)最多為(B)個(gè)A 2 B 3 C 4 D 520 .若對(duì)一組關(guān)鍵字(23,44,36,48,52,73,64,58)建立散列表，采用 H(K)=K%13計(jì)算散列地址，并采用鏈接 法處理沖突，則元素 64的初始散列地址(C)A.2B.8C.12D.13三、

33、簡(jiǎn)答題(第二章)(1)簡(jiǎn)述合適選用順序表或鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜。答：在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問(wèn)題的要求和性質(zhì)來(lái)選擇順序表或鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)，通常 有以下幾方面的考慮?；诳臻g的考慮。當(dāng)要求存儲(chǔ)的線性表長(zhǎng)度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表；反之，當(dāng)線性表長(zhǎng)度變化大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好?；跁r(shí)間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ) 結(jié)構(gòu)為宜；反之，若需要對(duì)線性表進(jìn)行頻繁地插入或刪除等操作時(shí)，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。并且，若鏈 表的插入和刪除主要發(fā)生在表的首、尾兩端，則采用尾指針表示

34、循環(huán)單鏈表為宜。(2)為什么在循環(huán)單鏈表中設(shè)置尾指針比設(shè)置頭指針更好？答：尾指針是指向終端節(jié)點(diǎn)的指針，用它來(lái)表示循環(huán)單鏈表可以使得查找鏈表的開(kāi)始節(jié)點(diǎn)和終端節(jié)點(diǎn) 都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear,則開(kāi)始節(jié)點(diǎn)和終端節(jié)點(diǎn)的位置分別是rear->next->next 和 rear,查找時(shí)間者B是 O (1)。(第三章)1 .鏈棧中為何不設(shè)置頭結(jié)點(diǎn)？答：鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要對(duì)頭結(jié) 點(diǎn)之后的結(jié)點(diǎn)進(jìn)行操作，反而使算法更加復(fù)雜。所以只要有鏈表的頭指針就可以了。2 .循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判別它的空和滿？答：循環(huán)列隊(duì)

35、的優(yōu)點(diǎn)是：它可以克服順序列隊(duì)的假上溢”現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分利用。判別循環(huán)隊(duì)列的空”或 滿”不能以頭尾指針是否相等來(lái)確定，一般是通過(guò)以下幾種方法：一個(gè)是另設(shè)一個(gè)布爾變量來(lái)區(qū)別隊(duì)列的空和滿；二是少用一個(gè)元素的空間，每次入隊(duì)前測(cè)試入隊(duì)后頭尾指針是否會(huì) 重合，如果會(huì)重合就認(rèn)為隊(duì)列已滿；三是設(shè)置一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素總數(shù)，不僅可判別空或滿，還可 以得到隊(duì)列中元素的個(gè)數(shù)。(第四章)1 .試回答空串與空格串有何區(qū)別？答：空串是不含任何字符的串，長(zhǎng)度為0,空格串是有空格字符組成的串，串的長(zhǎng)度為空格的個(gè)數(shù)。2 .試找出分別滿足下面條件的所有二叉樹(shù)(1)前序序列和中序序列相同。答：空二叉樹(shù)或沒(méi)有左子樹(shù)的二叉樹(shù)(右單支樹(shù))(2)中序序列和后序序列相同。答：空二叉樹(shù)或沒(méi)有右子樹(shù)的二叉樹(shù)(左單支樹(shù))(3)前序序列和后序序列相同。答：空二叉樹(shù)或只有根的二叉樹(shù)。(4)前序、中序、后序序列相同。答：空樹(shù)或只有根結(jié)點(diǎn)的二叉樹(shù)3