帶答案的數(shù)據(jù)結(jié)構(gòu)補充習(xí)題

1、補充習(xí)題第一章第五章一、 單選或填空題1. 下列程序段中S語句的執(zhí)行頻度為 n(n-1)/2 。for(i0；in；i+ ）for(j0；ji；j+ ） S；2. 下列算法的時間復(fù)雜度是（O(n)）。for(i0；in；i+ ）cii；3. 算法的時間復(fù)雜度可表示為 常數(shù)階 O(1)、線性階 O(n) 、平方階O(n2)、對數(shù)階O(logn)和指數(shù)階O(2n)等。4 以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的基本概念中，敘述正確的是 C A) 數(shù)據(jù)元素是數(shù)據(jù)不可分割的最小單位。B) 數(shù)據(jù)是數(shù)據(jù)對象的子集。C) 數(shù)據(jù)元素之間的關(guān)系在計算機中可用順序映像和非順序映像兩種不同的方法表示。D) 數(shù)據(jù)結(jié)構(gòu)在計算機中的表示又稱為

2、邏輯結(jié)構(gòu)。5. 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)包括（A）。 A) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) B) 邏輯結(jié)構(gòu)和物理結(jié)構(gòu) C) 順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu) D) 虛擬結(jié)構(gòu)和抽象結(jié)構(gòu) 6. 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的存儲結(jié)構(gòu)包括 C 。§ A) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) B) 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)§ C) 順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu) D) 虛擬結(jié)構(gòu)和抽象結(jié)構(gòu) 7. 線性結(jié)構(gòu)的數(shù)據(jù)元素之間存在一種( D )。A一對多關(guān)系B多對多關(guān)系C多對一關(guān)系D一對一關(guān)系8. 在長度為n的順序表中插入一個元素，需要平均移動 A 個元素。A) n/2 B)nC) n(n-1) D) n(n+1)9. 在有n個元素的順序表中做插入、刪

3、除運算，平均時間復(fù)雜度為 O(n) 。10. 順序表中邏輯上相鄰的元素物理位置 B 相鄰，單鏈表中邏輯上相鄰的元素的物理位置 相鄰。A)必然、必然 B)必然、不一定C)不一定、必然 D)不一定、不一定11相對于順序存儲而言，鏈?zhǔn)酱鎯Φ膬?yōu)點是（C）。A隨機存取B節(jié)約空間C增、刪操作方便D節(jié)點間關(guān)系簡單12 以下關(guān)于頭結(jié)點的描述中，敘述錯誤的是 A A) 頭結(jié)點是對鏈表首元結(jié)點的別稱B) 若鏈表中附設(shè)頭結(jié)點，則頭指針一定不為空C) 頭結(jié)點中不存儲鏈表的數(shù)據(jù)元素，而是一些諸如表長之類的輔助信息D) 在單鏈表中附設(shè)頭結(jié)點，插入或刪除首元素時不必進行特殊處理13已知L是無表頭結(jié)點的單鏈表，且P所指結(jié)點既

4、不是首元結(jié)點，也不是尾元結(jié)點，則在P之后插入S所指結(jié)點，則執(zhí)行（A）。A) S->next=P->next； P->next=S；B) P->next=S->next； S->next=P；C) S->next=P； P->nextS；D) P->next=S； S->next=P；14. 已知L是帶表頭結(jié)點的非空單鏈表，且P結(jié)點是S結(jié)點的直接前驅(qū)。則刪除S結(jié)點的語句序列為 B 。I. P->next = S ;free(P)II. P->next = P->next->next; free(S)III. P-

5、>next = S->next; free(S) IV. P = P->next ;free(S)A) I和II正確 B) II和 III正確C) III和IV正確 D) 全部正確15. 已知L是帶表頭結(jié)點的單鏈表，則刪除首元結(jié)點的語句序列是（ C）。A) L->next =L->next->next; free(L)B) P = L ;L= P->next ;free(P)C) P = L->next ; L->next= P->next ;free(P)D) P = L ;L= P->next ;free(P)16. 已知L

6、是一帶有頭結(jié)點的單鏈表的頭指針，則該單鏈表為空的條件是 L->next=NULL 。17. 已知P結(jié)點是某雙向鏈表的中間結(jié)點，則刪除P結(jié)點的語句序列是 P->prior->next=p->next ， P->next->prior=P->prior ，free(P);18. 設(shè)將整數(shù)1，2，3，4，5依次進棧，最后都出棧，出?？梢栽谌魏螘r刻(只要棧不空)進行，則出棧序列不可能的是（B ）。A) 32415 B) 45231 C) 32145 D) 4532119. 在棧中由頂向下已存放元素c, b, a 在第4個元素d入棧前，棧中元素可以出棧，則不可能

7、的出棧序列是 ( D )A) dcba B) cbda C) cdba D) cadb21. 設(shè)有棧S和隊列Q，其初始狀態(tài)為空，元素a1,a2,a3,a4,a5,a6依次入棧，出棧的元素進入隊列Q。若元素出隊列的順序是a2,a4,a3,a6,a5,a1，則棧的容量至少是 3 。22. 某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，則abcde順序入隊，不可能的到的順序是（C）。AbacdeBdbaceCdbcaeDecbad23. 設(shè)用一維數(shù)組An存儲一個棧，令A(yù)n為棧底，用整型變量T指示當(dāng)前棧頂位置，AT為棧頂元素。當(dāng)從棧中彈出一個元素時，變量T的變化為（A）。A) T=T+1

8、 B) T=T-1 C) T不變 D) T=n-124. 循環(huán)隊列是滿隊列的條件是 B 。A）Q.rearQ.front B）(Q.rear+1) % maxsizeQ.frontC）Q.rear0 D）Q.front025. 在具有m個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊首指針和隊尾指針，則判斷隊滿的條件是（A）A. front= (rear1) % m B. front1= rearC. front= rear D. rear= m26. 在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊首指針和隊尾指針，則判斷隊空的條件是（C）A)front=

9、 (rear1) % n B)front1=rearC)front=rear D)front=027. 循環(huán)隊列用數(shù)組A0m-1存放其數(shù)據(jù)元素。設(shè)front指向其實際的隊頭，rear指向其實際隊尾的下一個位置，則當(dāng)前隊列中的數(shù)據(jù)元素有 (rear-front+m)%m 個。28 在串的運算中，StrLength(Concat (aa，bb)的返回值為 D A) 0B) 8C) 6D) 429設(shè)s1”I have_”，s2”a dream”，則strcat(s1, s2)的值是 I have_ a dream ，SubString(s1,4,3)的值是 ave 。 30. 設(shè)s1”I am a

10、student”，s2”a student”，則Index(s1,s2)的值是 6 。31. 假設(shè)有二維數(shù)組A5×6，每個元素用相鄰的4個字節(jié)存儲，存儲器按字節(jié)編址。已知A的基地址為1000，則數(shù)組A的最后一個元素a45的第一個字節(jié)的地址是 1116 ；按行存儲時，元素a14的第一個字節(jié)的地址是 1040 。32. 已知二維數(shù)組A1.7，1.7按列存放，其起始存儲位置為100，每個元素占用4個字節(jié)，則元素A4,6的第一個字節(jié)的地址為 B 。A）204 B）252 C）208 D）25633. 一個非空廣義表的表頭（D）。A一定是子表 B一定是原子C不能是子表 D可以是原子，也可以是子

11、表34. 設(shè)廣義表L（(a,b),c,()），則head(L) (a,b) ，tail(L) ( c,() ) 。二、 算法題1. 寫出下列程序段的功能。Status A(LinkedList L) /L是無表頭結(jié)點的單鏈表If(L &&L->next) Q=L; L=L->next; P=L; While (P->next) P=P->next; P->next=Q; Q->next=NULL; Return OK; 2. 寫出下列程序段的輸出結(jié)果。void main() Stack S; char x,y; InitStack(S); x

12、=i; y=s; Push(S,x);Push(S,r);Push(S,y); Pop(S,x); Push(S,h);Push(S,x); Pop(S,x); Push(S,c); while (!StackEmpty(S) Pop(S,y);printf(y); printf(x);3. 寫出下列程序段的輸出結(jié)果。void main() Queue Q; InitQueue(Q); char x=e, y=c; EnQueue(Q, a);EnQueue(Q, d);EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); En

13、Queue(Q, r); while (!QueueEmpty(Q) DeQueue(Q, y); printf(y); printf(x);4. 已知L是帶頭結(jié)點的單鏈表。試寫一算法求該單鏈表的長度。5. 已知L是帶頭結(jié)點的單鏈表。試寫一算法在該鏈表上查找值為x的元素。6. 將帶頭結(jié)點的L中的第i個數(shù)據(jù)元素刪除。7. 在帶頭結(jié)點的L中第i個元素之前插入數(shù)據(jù)元素e 。8. 正位序輸入n個元素的值，建立帶頭結(jié)點的單鏈表L。9. 已知線性表中的元素以值遞增有序排列，并以帶有頭結(jié)點的單鏈表作存儲結(jié)構(gòu)。試寫一算法刪除表中所有值大于mink且小于maxk的元素，同時釋放被刪除的結(jié)點空間。10. LA和L

14、B是兩個數(shù)據(jù)元素按升序排列的單鏈表，將LA和LB合并為有序單鏈表LC。寫出這兩個有序鏈表合并的算法。第六章一、 單選或填空題1. 已知完全二叉樹的第7層上有10個葉子結(jié)點，則整個二叉樹的結(jié)點數(shù)最多是 C A) 73 B) 63 C) 235 D) 2452. 300個結(jié)點的完全二叉樹的葉結(jié)點有 150 個。3一個具有1025個結(jié)點的二叉樹的高h為_C_。A）11 B）10 C）11至1025之間 D）10至1024之間4. m叉樹的第i層至多有 mi-1 個結(jié)點5. 將一棵有100個節(jié)點的完全二叉樹從上到下，從左到右依次對節(jié)點進行編號，根節(jié)點的編號為1，則編號為49的節(jié)點的右孩子編號為（A）。

15、ABCDEFA99B98C50D486把如右圖所示的樹轉(zhuǎn)換成二叉樹時，C是（ D ） A. A的左子女 B. A的右子女 C. B的左子女 D. B的右子女7. 設(shè)森林F中有3棵樹，其結(jié)點個數(shù)分別是n1、n2和n3，則與森林對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是 D 。 A) n1-1 B)n1+n2 C) 0 D) n2+n38.在一顆度為4的樹T中，若有20個度為4的結(jié)點，10個度為3的結(jié)點，5個度為2的結(jié)點，10個度為1的結(jié)點，則樹T的葉結(jié)點個數(shù)有 86 個。9. 一棵二叉樹中序遍歷結(jié)果為DCBAEFG，后序遍歷結(jié)果為DCBGFEA。則此二叉樹先序遍歷的結(jié)果應(yīng)為AA) ABCDEFG

16、B)ABECFDG C)AEBFCGD D)不能確定10. 將一棵樹t 轉(zhuǎn)換為孩子兄弟鏈表表示的二叉樹h，則t 的后根遍歷是h 的 BA）先序遍歷 B）中序遍歷 C）后序遍歷 C）層序遍歷11.現(xiàn)有一段電文共100個字符，其中A出現(xiàn)50次，B出現(xiàn)20次，C出現(xiàn)5次，D出現(xiàn)10次，E出現(xiàn)15次?，F(xiàn)對這5個字符進行哈夫曼編碼，則其平均碼長為 1.95 。二、 解答題1. 某二叉樹的中序遍歷結(jié)果為DEFABCG；后序遍歷結(jié)果為FEDCBAG。（1）畫出此二叉樹，并給出其先序遍歷的結(jié)果。 GADBEFC（2）畫出與這棵二叉樹對應(yīng)的樹（森林）。2. 已知一個二叉樹的先序遍歷序列為：ABDGIECFH；中

17、序遍歷序列為：DIGBEAFHC。（1）畫出該二叉樹（2）畫出下圖所示森林對應(yīng)的二叉樹。AACABADAEAHAIAFAGAJAKLA3. 某二叉樹層序序列為abcdefghij，中序序列為bgdhjaecif。（1）畫出該二叉樹；（2）畫出該二叉樹的后序后繼線索樹；（3）畫出該二叉樹對應(yīng)的樹或森林。4. 已知某通訊用電文僅有A、B、C、D、E、F六個字符構(gòu)成，其出現(xiàn)的頻率分別為26，8，17，11，28，10，請首先建立哈夫曼樹，然后給出六個字符的哈夫曼編碼（注：建立哈夫曼樹時權(quán)值小的為左子樹，權(quán)值大的為右子樹）。三、算法題1. 以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，編寫以下算法：（1）求先序序列

18、為k的結(jié)點的值（2）求二叉樹中葉子結(jié)點的數(shù)目（3）交換所有結(jié)點的左右子樹（4）求二叉樹的深度第七章一 單選或填空題1. 若某有向圖的鄰接矩陣A只有0和1兩種元素，其中aij1表示有向圖中存在弧<i,j>，則編號為i頂點的入度可用 B 表示。A) 鄰接矩陣中第i行元素之和 B) 鄰接矩陣中第i列元素之和 C) 鄰接矩陣中對角線元素之和 D) 以上均不正確2. 使用鄰接表作為某無向圖的存儲結(jié)構(gòu)，若無向完全圖中有n個頂點，則鄰接表中必存在 個表結(jié)點。 A)n2 B)2n C)n(n-1) D) 2n-13. 一個含有n個頂點和e條邊的無向圖，在其鄰接矩陣存儲結(jié)構(gòu)中共有（）零元素。AeB2

19、eCn2-eDn2-2e4在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。A1/2B1C2D45下列關(guān)于圖的敘述中，正確的是（ ）、 回路是簡單路徑 、存儲稀疏圖，用鄰接矩陣比鄰接表更省空間 、若有向圖中存在拓撲序列，則該圖不存在回路 A僅 B僅、 C僅 D僅、 6. 有n個頂點的無向圖至少有 條邊才能確保是一個連通圖。7在有n個結(jié)點的無向圖中，其邊數(shù)最多為 。8. 對于具有n個結(jié)點的連通圖，它的最小生成樹中有 條邊。A)n2 B)n-1 C)n(n-1) D) n(n-1)/29. 關(guān)鍵路徑是AOE網(wǎng)中A）從源點到匯點的最長路徑 B）從源點到匯點的最短路徑C）最長回路D）最

20、短回路10. 以下關(guān)于圖的描述中，正確的是A) n個頂點的無向完全圖有條邊。B) 對任何用頂點表示活動的網(wǎng)絡(luò)（AOV網(wǎng)）進行拓撲排序的結(jié)果是唯一的。C) 若圖G的鄰接矩陣是對稱的，則G一定是無向圖cabedD) 有向圖的鄰接矩陣一定是非對稱矩陣11. 對下圖進行拓撲排序，可以得到不同的拓撲序列的個數(shù)是（）A5B3C2D112下圖為用邊表示活動的AOE-網(wǎng)。則V8的最早發(fā)生時間是 。二、解答題1. 已知某無向圖的鄰接表存儲結(jié)構(gòu)如下圖所示，求解下列問題：（1）畫出它的無向圖；（2）畫出它的的鄰接矩陣存儲結(jié)構(gòu)；（3）從頂點A出發(fā)，畫出其廣度優(yōu)先生成樹。0 A 1 41 B 0 2 52 C 1 3

21、43 D 2 54 E 0 2 55 F 1 3 42. 已知無向帶權(quán)圖G的鄰接矩陣如下所示。（1）從頂點a出發(fā)，求其深度優(yōu)先生成樹； （2）從頂點a出發(fā)，根據(jù)普里姆算法構(gòu)造最小生成樹，過程在下面的圖(1)至(5)中畫出。（3）給出鄰接表存儲結(jié)構(gòu)；3. 對于如下圖所示的帶權(quán)有向圖，求解關(guān)鍵路徑, 計算各事件（頂點）的最早發(fā)生時間和最遲發(fā)生時間，各活動（?。┑淖钤玳_始時間和最遲開始時間。請?zhí)顚懺诖痤}紙的表格中。bbdg64521187244acdefhk表1 計算各事件（頂點）的最早發(fā)生時間和最遲發(fā)生時間，請?zhí)顚懺诒?的空白處。頂點abcdefghkve06457151418vl08101614

22、18表2 計算各活動（?。┑淖钤玳_始時間和最遲開始時間，請?zhí)顚懺诒?的空白處?；bacadbecedfegehfhgkhke00064571514l38101614 4.對于右圖，求解下列問題：（1）寫出該圖的鄰接矩陣；（2）寫出全部拓撲排序序列；（3）從頂點V1出發(fā)，給出深度優(yōu)先遍歷生成樹；（4）按照迪杰斯特拉算法，求V1結(jié)點到各點的最短路徑，填寫表1的空白處。終點從V1到各終點的距離和最短路徑的求解過程i=1i=2i=3i=4i=5i=6i=7V22-V333-V4-V51313-V6-V7-V8161616vjv2v3第九章一單選或填空題1已知一個長度為11的有序表，使用折半查找的方法

23、，查找第8個元素時所需進行的關(guān)鍵字比較次數(shù)為 。2. 已知一個長度為16的有序表，使用折半查找的方法，查找一個不存在的元素，則所需進行的關(guān)鍵字比較次數(shù)最多是 。A4B5C6D73. 在二叉排序樹中，關(guān)鍵字值最大的結(jié)點A）左指針一定為空 B）右指針一定為空C）左右指針均為空 D）左右指針均不為空4 對于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是（ ） A95,22,91,24,94,71 B92,20,91,34,88,35 C21,89,77,29,36,38 D12,25,71,68,33,34 5AVL樹是一種平衡的二叉排序樹，樹中任一結(jié)點的A左、右子樹的高度均相同 B.

24、 左、右子樹高度差的絕對值不超過1C. 左子樹的高度均大于右子樹的高度 D. 左子樹的高度均小于右子樹的高度6. 以下關(guān)于查找方法的描述中，錯誤的是 A) 平衡二叉樹一定也是二叉排序樹。B) 有序表的折半查找判定樹是二叉排序樹。C) 中序遍歷一棵二叉排序樹，可以得到其數(shù)據(jù)元素的升序排列。D) 后序遍歷一棵二叉排序樹，可以得到其數(shù)據(jù)元素的降序排列。7.下列二叉排序樹中，滿足平衡二叉樹定義的是（ ）8、在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點的左、右子結(jié)點中保存的關(guān)鍵字分別是（ ）A、13，48 B、24，48 C、24，53 D、24，9

25、09. 從理論上講，將數(shù)據(jù)以何（）結(jié)構(gòu)存放，則查找一個數(shù)據(jù)所用時間不依賴于數(shù)據(jù)個數(shù)n.A）二叉查找數(shù) B）鏈表 C）二叉樹D）哈希表10 為提高散列（Hash）表的查找效率，可以采取的正確措施是（ ）、增大裝填（載）因子 、設(shè)計沖突（碰撞）少的散列函數(shù)、處理沖突（碰撞）時避免產(chǎn)生聚集（堆積）現(xiàn)象A僅 B僅 C僅、 D僅、二、解答題1. 設(shè)記錄關(guān)鍵字集合key=33,20,53,55,23,38,40,65，選取哈希函數(shù)為H(x)=key mod 11；解決沖突的方法為“線性探測法”。（1）請按上述條件將key中各值依次填入下表中：（2）求該哈希表查找成功和查找不成功情況下的平均查找長度。2.

26、設(shè)記錄關(guān)鍵字集合key=32,13,49,55,22,39,20，選取哈希函數(shù)為H(x)=key mod 7；解決沖突的方法為“鏈地址法”。（1）畫出所構(gòu)造的哈希表；（2）求該哈希表查找成功和查找不成功情況下的平均查找長度。3. 設(shè)記錄關(guān)鍵字集合key=32,13,49,55,22,39,20，解決沖突的方法為“線性探測法”，要求裝填因子為：0.7，哈希函數(shù)的形式為H(x)=key mod P，散列表的地址從0開始。（1）構(gòu)造哈希函數(shù)；（2）畫出所構(gòu)造的哈希表；（2）求該哈希表查找成功和查找不成功情況下的平均查找長度。4. 選取哈希函數(shù)H(key)=(3*key) mod 11。用開放定址法處

27、理沖突，di=i(7*key) % 10+1)(i=1,2,3)。試在010的散列地址空間對關(guān)鍵字序列（22，41，53，46，30，13，01，67）：1） 構(gòu)造該序列對應(yīng)的哈希表；2） 求等概率情況下查找成功的平均查找長度。哈希表如下圖所示：5. 從空樹開始，依次插入13，34，51，24，62，43，75，18，畫出建立2-3樹后的狀態(tài)，并分別畫出刪除43、24后的2-3樹狀態(tài)。6. 畫出對長度為12的有序表進行折半查找的判定樹，并求其等概率查找成功時的平均查找長度。第十章一、 單選或填空題1. 數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60。下面是一組用不同排序方法進行一趟排序

28、后的結(jié)果。則ABCD四個選項中，說法正確的是 I 12，13，15，18，20，60 II 13，15，18，12，20，60III 13，15，20，18，12，60 IV 12，13，20，18，15，60V 13，15，18，20，12，60A) I快速排序；II簡單選擇排序；III直接插入排序；IV冒泡排序；V歸并排序B) I冒泡排序；II快速排序；III歸并排序；IV簡單選擇排序；V直接插入排序C) I快速排序；II冒泡排序；III直接插入排序；IV簡單選擇排序；V歸并排序D) I直接插入排序；II歸并排序；III快速排序；IV簡單選擇排序；V冒泡排序 2. 對一組數(shù)據(jù)(2，12，16，88，5，10)進行排序，若前三趟排序結(jié)果如下：第一趟：2，12，16，5，10，88第二趟：2，12，5，10，1