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

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

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

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

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

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

7、的結(jié)點存入a0元素中，讓編號為 2的結(jié)點存入a1元素中，其余類推，則編號為i結(jié)點的左孩子結(jié)點對應(yīng)的存儲位置為2i-1。12 .對于一棵具有n個結(jié)點的二叉樹，對應(yīng)二叉鏈接表中指針總數(shù)為2n個，其中n-1個用于指向孩子結(jié)點，n+1個指向空閑著。13 .一棵二叉樹廣義表表示為a(b(d(h),c(e,f(g,i(k),該樹的結(jié)點數(shù)為10個，深度為5O14 .假定一棵二叉樹廣義表表示為a (b(c),d(e,f)，則對它進(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用鄰接矩陣存儲，其第i行的所有元素之

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

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

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

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

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

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

14、/2D、（n+1）/27、帶頭結(jié)點的單鏈表head為空的條件是（B）A、head=NULL B、head->next=NULL C、head->next=head D、head!=NULL8、非空循環(huán)單鏈表 head的尾結(jié)點*p滿足（C）A、p->next=NULLB、p=NULL C、p->next=head D、p=head9、在循環(huán)雙鏈表的*p結(jié)點之后插入*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、在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費(fèi)時間最少的是（ D） A、單鏈表 B、雙鏈表C、循環(huán)列表D、順序表（第三章）1.有一棧的輸入序列是a、b、c,則通過入棧、出棧操作可能得到a、b、c的不同

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

17、axisize8 .循環(huán)隊列用數(shù)組A0 則當(dāng)前隊列中的元素個數(shù)是A.(rear-front+m)%mC.read-front-19 .在一個鏈隊中，假設(shè)A)。B通常不會出現(xiàn)棧空的情況D刪除操作更容易實現(xiàn)3、4、n,輸出序列第一個元素是C n-i+1D n-i-1d、e,則棧的不可能輸出序列是( b、a C d、c、e、a、b D a、4,則隊列的可能輸出序列是(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個輸出元素是(C)。C)b、 c、 d、 eD

18、.3、2、4、1m-1存放其元素值，已知其頭、尾指針分別是(A)。B read-front+1D.read-frontf和r分別為隊首和隊尾指針，則刪除一個結(jié)點的運(yùn)算是(front 和 rear,C)。A,r=f->next B.r=r->next(第四章)1 .串是(D)A. 一些符號構(gòu)成的序列C. 一個以上的字符構(gòu)成的序列C.f=f->next D f=r->nextB.一些字母構(gòu)成的序列D.任意有限個字符構(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)行時間是(以一次內(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 .將一個A1100,110曲三對角矩陣，按行優(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的每個元素是由6個字符組成的串，其行下標(biāo) i=0,1, 丁 8,列下標(biāo)j=1,2,，10.若A按行先 存儲，元素A8,5的起始地址與當(dāng) A按列先存儲時的元素(B)的起始地址相同。設(shè)每

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

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

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

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

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

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

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

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

29、元素按值有序，且采用順序存儲結(jié)構(gòu)D.元素按值有序，且采用鏈?zhǔn)酱鎯Y(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 .用折半查找法查找一個長度為10的、排好序的線性表，查找不成功時，最多需要比較(C)次。A.5B.2C.4D.18 .采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為( C)。A.nB.n/2 C. (n+1) /2D.(n-1)/29 .有一個長度為12的有序表，按折半查找法對該表進(jìn)行查找，在表內(nèi)每個元素等概率情況下查找成功時所需的平均比較次數(shù)

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

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

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

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

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

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