數(shù)據(jù)結(jié)構(gòu)_習(xí)題集(含答案)

1、數(shù)據(jù)結(jié)構(gòu)課程習(xí)題集一、單選題1. 頭結(jié)點(diǎn)為L 的單循環(huán)鏈表為空的條件是（）A、 L=NULLB、 L->next=NULLC、 L->next=L D、 L!=NULL2. 與線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)特點(diǎn)不符的是：（）A、便于插入、刪除運(yùn)算R查找操作費(fèi)時C需要連續(xù)的地址空間D、空間動態(tài)分配3. 采用鄰接表存儲的圖，其深度優(yōu)先遍歷算法類似于二叉樹的（）A先序遍歷B、中序遍歷C后序遍歷D按層遍歷4. 對序列 1,5,7,10,12,15,19 ，采用折半查找1，需比較（）次。A、 1B、 2C、 3D、 45. 直接選擇排序算法的時間復(fù)雜度為（）A、 O（ n）B、 O（ n2）C、O（

2、n*log （ n） ）D 、 O（ 1）6. 一個棧的入棧序列為1 、 2、 3、 4，則棧的不可能的輸出序列是（）A、1 2 3 4B、4 3 2 1C、4 1 2 3D、3 4 2 17.判定一個順序棧 S為空的條件為（）。A、S.top=0B、S.base=0C、S.top=S.baseD、S.top>S.stacksize8. 設(shè)有兩個串r和t,求r在t中首次出現(xiàn)位置的運(yùn)算稱作（）A、求串長B、連接C、模式匹配D、求子串9. 按二叉樹的定義，具有3 個結(jié)點(diǎn)的二叉樹共有（）種形態(tài)。A、3B、4C、5D、610. 一個有 n 個頂點(diǎn)的完全無向圖共有（）條邊。A、nB、2nC、n*（

3、n-1）D、n*（n-1）/211. 對序列 5， 7， 12， 19， 20， 30，采用折半查找19，需比較（）次。A、1B、2C、3D、412. 直接插入排序算法的時間復(fù)雜度為：（）A、O（n2）B、O（n）C、O（n*log （n）D、O（1）13.在一個長度為n的順序表中，刪除第i個元素（1 wi wn+i）時，需要從前向后依次前移（ ）個元素。A、 n-iB、 n-i+1C、 n-i-1D 、 i14. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結(jié)點(diǎn)都具有相同的（）。A、行號B、列號C、元素值D 、 地址15. 在一個循環(huán)順序隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素（）位置。A后一

4、個B、前一個C當(dāng)前D 、后面16. 假定一個鏈隊(duì)的隊(duì)首和隊(duì)尾指針分別為front 和 rear ，則判斷隊(duì)空的條件是（） 。A、 front=rearB、 front!=NULLC、 rear!=NULLD 、 front=NULL17. 從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為（） 。A、 O（n）B、O（1）C、 O（log 2n）D 、O（n 2）18. 向二叉搜索樹中插入一個元素時，其時間復(fù)雜度大致為（） 。A、 O（1）B、O（log 2n ）C、 O（n）D 、 O（nlog 2n）19. （ ）是數(shù)據(jù)的基本單位。A數(shù)據(jù)項(xiàng)B、數(shù)據(jù)元素C數(shù)據(jù)對象D 、數(shù)據(jù)結(jié)構(gòu)20. 以下不屬

5、于線性結(jié)構(gòu)的是（）A堆棧日隊(duì)列C線性表D、樹21. 線性表采用鏈?zhǔn)酱鎯r，其地址（）A、必須是連續(xù)的Bk部分地址必須是連續(xù)的C 一定是不連續(xù)的D連續(xù)與否均可以22. 下面的不屬于線性結(jié)構(gòu)的有（）A、線性表B、棧C、隊(duì)列D、二叉樹23. 設(shè)一個棧的輸入序列為A, B, C,則借助一個棧所得的輸出序列不可能是（）A、A，B，CB、C，B，AC、A，C，BD、C，A，B24. 若一棵二叉樹具有10 個葉結(jié)點(diǎn)，則該二叉樹的度為2 的結(jié)點(diǎn)個數(shù)是（）D 、不確定C、 1225.不帶頭結(jié)點(diǎn)的單鏈表 head為空的判定條件是（）A、 head=NULLB 、 head->next=NULLC、 head

6、->next=headD、 head!=NULL26. 具有 6 個頂點(diǎn)的無向圖，至少要有（）條邊，才能確保是一個連通圖A、 5B、 6C、 7D、 8B、 12D、 25）不是樹的存儲結(jié)構(gòu)。B 、孩子表示法 D 、順序存儲表示法27. 設(shè)有 13 個葉子結(jié)點(diǎn)，用它們組成一顆哈夫曼樹，則該哈夫曼樹共有（）個結(jié)點(diǎn)。A、 13C、 2628. 在下列存儲形式中，A、雙親表示法C、孩子兄弟表示法29. 在以 HL 為頭結(jié)點(diǎn)的單鏈表中，若要向表頭插入一個由指針P 指向的結(jié)點(diǎn)，則執(zhí)行（）。B 、 P->next=HL;HL->next=PD 、 P->next=HL->ne

7、xt; HL->next=PB、插入刪除不需要移動元素D、所需空間與線性表長度成正比A、 HL=P;P->next=HLC、 P->next=HL ;HL=P 30. 鏈表不具有的特點(diǎn)是（A、可隨機(jī)訪問任一元素C、不必事先估計(jì)存儲空間31. 在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。A、 1/2B、 1C、 2D、 432. 對線性表進(jìn)行二分查找時，要求線性表必須（） 。A、以順序方式存儲B 、以鏈接方式存儲C、以順序方式存儲，且結(jié)點(diǎn)按關(guān)鍵字有序排列D 、以鏈接方式存儲，且結(jié)點(diǎn)按關(guān)鍵字有序排列33. 在待排序的元素序列基本有序的前提下，效率最高的排序方

8、法是（） 。A、插入排序B、選擇排序C、快速排序D、歸并排序34. 下描述中正確的是（ ）A、線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)日對棧的插入和刪除元素的操作都可在棧底進(jìn)行C棧的操作方式是先進(jìn)先出D隊(duì)列的操作方式是先進(jìn)先出35. 在一個單鏈表中，若刪除*p 所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（ ）A、 s=p->next;p->next=s->next; free（s）B、 p=p->next; p->next=p->next->next第 3 頁 共 21 頁C、 p->next=p->nextD、 p=p->next->next36

9、. 棧的插入和刪除操作在（）進(jìn)行。A棧頂以棧底C任意位置D指定位置37. 一顆有 124 個葉子結(jié)點(diǎn)的完全二叉樹，最多有（）個結(jié)點(diǎn)。A、247B、248C、249D、25038. n 個頂點(diǎn)的連通圖至少有（）條邊。A、n -1B、nC、 n+1D 、 039. 衡量查找算法效率的主要標(biāo)準(zhǔn)是（） 。B、所需的存儲量、算法難易程度B、排序方法D調(diào)度方法A元素個數(shù)C平均查找長度D40. 計(jì)算機(jī)算法指的是（ ）A、計(jì)算方法C解決問題的有限操作序列41. 對二叉排序樹進(jìn)行（ ） 遍歷，可以得到該二叉樹所有結(jié)點(diǎn)構(gòu)成的有序序列。A前序日中序D 、按層次42. 順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。A、散列

10、存儲B、順序存儲或鏈?zhǔn)酱鎯壓縮存儲D、索引存儲43. 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為（） 。A希爾排序B、起泡排序C插入排序D 、選擇排序44. 計(jì)算機(jī)算法它必具備輸入、輸出和（ ） 等五個特性。A、可行性、可移植性和可擴(kuò)充性R可行性、確定性和有窮性C確定性、有窮性和穩(wěn)定性D、易讀性、穩(wěn)定性和安全性45. 假設(shè)隊(duì)列的對頭指示器為front ，隊(duì)尾指示器尾rear ，隊(duì)列的最大存儲空間大小為max,則順序循環(huán)隊(duì)列為空的標(biāo)志是（）。A、rear=frontB、 rear!=frontC、 rear=（f

11、ront+1）%maxD、 front=（rear+1）%max46. 在有 n 個葉子結(jié)點(diǎn)的哈夫曼樹中，總的結(jié)點(diǎn)個數(shù)是（） 。A、 nB、 2n-1C、 2n+1 D 、 2n 47. 棧和隊(duì)列的共同點(diǎn)是（ ） 。A、都是先進(jìn)后出以只允許在端點(diǎn)處插入和刪除C沒有共同點(diǎn)D、都是后進(jìn)先出48. 串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。A、可以順序存儲B、數(shù)據(jù)元素是字符C可以鏈接存儲D 、數(shù)據(jù)元素可以是多個字符49. 就平均性能而言，目前最好的內(nèi)排序方法是A冒泡（ ） 排序法。日希爾C交換D快速50. N 個結(jié)點(diǎn)的二叉樹中，用二叉鏈表存儲，非空指針數(shù)目為（） 。A、 NB、 2NC、 N-1D

12、、 N+1二、簡答題51. 設(shè)散列表的長度m = 13，散列函數(shù)H（ K ） = K mod m ，給定的關(guān)鍵碼序列為19，14， 23， 01， 68， 20， 84， 27， 55， 11 ，試畫出用線性探查法解決沖突時所構(gòu)造的散列表。并求出在等概率的情況下，這種方法的搜索成功時的平均搜索長度。52. 已知一組元素為（46， 25， 78， 62， 12， 37， 70， 29） ，試畫出按元素排列次序插入生成的一棵二叉搜索樹。53. 請分別畫出具有三個結(jié)點(diǎn)的樹和二叉樹的所有形態(tài)。54. 用直接選擇排序方法對下列關(guān)鍵字進(jìn)行排序，請寫出每一趟排序的結(jié)果。55. 已知有序序列3,12,24,3

13、7,45,53,61,78,90,100, 請用二分查找法查找元素 37, 并寫出每次查找比較的過程，用" T”標(biāo)示 查找過程的 mid元素，分別用“和""標(biāo) 示 low 和 high 元素。56. 已知序列17,18,60,40,7,32,73,65,85, 請給出分別構(gòu)建大根堆和小根堆后的順序序列 .57. 已知一組關(guān)鍵字為（Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May,July,Jan,Mar ） , 按哈希函數(shù)H（key）= key mod 12 和鏈地址法處理沖突構(gòu)造長度為12的哈希表，并求平均查找長度。58. 有七個帶權(quán)結(jié)

14、點(diǎn)，其權(quán)值分別為3,7,8,2,6,10,14 ，試以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，并計(jì)算出帶權(quán)路徑長度WPL。59. 已知二元組C=（D，S），其中：D=1 ，2，3，4， 5，S=（ 1，2）、 （ 1，3）、 （2，4）、（3，4）、 （ 2，5）、 （3，5）（1，2）表示元素1 和 2 之間有一條連接線，畫出其邏輯圖表示，并指出其屬于何種數(shù)據(jù)結(jié)構(gòu)。60. 畫出如下所示的有向圖的鄰接表。第 5 頁 共 21 頁61.畫出樹的孩子兄弟表示法存儲結(jié)構(gòu)(每結(jié)點(diǎn)三個域)62 .已知序列19, 20, 80, 55, 7, 35, 90, 88, 66,給出采用起泡排序按升序排序時 每一趟的示

15、意圖。63 .無向圖進(jìn)行如下操作：(1)畫出其鄰接矩陣；(2)根據(jù)普里姆算法求最小生成樹。64 .對于下圖：(1)寫出從頂點(diǎn)0出發(fā)按度優(yōu)先搜索遍歷得到的頂點(diǎn)序列；(2)寫出從頂點(diǎn)0出發(fā)按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序歹U；(3)結(jié)點(diǎn)2的度是多少？65.如下圖所示的樹,回答以下問題：(1)該樹的深度是；(2)該樹的度是；(3)該樹的葉子結(jié)點(diǎn)有哪些 66.由如圖所示的二叉樹,回答以下問題這棵二叉樹的先序,中序和后序遍歷序列分別是 ,和(1)結(jié)點(diǎn)3的度為。(2)給出該圖的一個拓?fù)溆行蛐蛄?。68.對于下圖，分別畫出用克魯斯卡爾(Kruskal)算法構(gòu)造最小生成樹的過程。A69.設(shè)數(shù)據(jù)元素關(guān)鍵字序列為7

16、5, 37, 81, 19, 82, 74, 50, 26, 15, 06,分別寫出采用下列排序算法排序的第一趟排序結(jié)果。(1)希爾排序(d=5)；(2)直接選擇排序(3)快速排序(4)二路歸并排序70.知一組關(guān)鍵字為(46,88,45,39,70,58,44,12,27,66),地址空間為0至12按哈希函數(shù)H(key尸 key % 11。(1)用開放地址法線性探測處理沖突構(gòu)造該哈希表。(2)求出等概率情況下查找成功的平均查找長度。0123456789101112、算法設(shè)計(jì)題71 .有一個帶頭結(jié)點(diǎn)的單鏈表Head,在其數(shù)據(jù)域?yàn)閍的結(jié)點(diǎn)后加入新元素一個新的結(jié)點(diǎn)s(s為指向新插入結(jié)點(diǎn)的指針)O設(shè)計(jì)

17、一個算法實(shí)現(xiàn)上述功能。第9頁共21頁72 .順序循環(huán)隊(duì)列類型模塊說明如下:#define Max 100/Typedef structQElemType *base; / int front, rear;SeQueue;最大隊(duì)列長度初始化的動態(tài)分配存儲空間/頭指針和尾指針填寫畫線部分空白處，完成下列入隊(duì)列函數(shù)。Status EnQueue(SqQueue &Q,QElemType e) if( )/ 隊(duì)列滿return Error；return OK;73 .針對帶頭結(jié)點(diǎn)的單鏈表，試編寫統(tǒng)計(jì)函數(shù) 個數(shù)。假設(shè)已經(jīng)對單鏈表進(jìn)行了結(jié)構(gòu)體定義，74 .閱讀下面的算法，補(bǔ)上空格處的語句。type

18、def structElemtype *elem; /數(shù)據(jù)元素存儲空間基址int length; 表長度SSTable; /靜態(tài)查找表的順序存儲結(jié)構(gòu)int Search_Bin(SSTable St,KeyType key) low=1;high=St.length;while(low<=high)mid=(low+high)/2;if EQ(key,St.elemmid.key) returnelse if LT(key,St.elemmid.key) else ;return 0;count,統(tǒng)計(jì)單鏈表中給定值x的所有元素數(shù)據(jù)域?yàn)閐ata,指針域?yàn)閚ext,頭結(jié)點(diǎn)為head。,建表時

19、按實(shí)際長度分配,0號單元留空關(guān)鍵字從小到大排好;/ LT表示第一個參數(shù)值比第二個小Search_Bin75. 編寫算法實(shí)現(xiàn)用遞歸方法對 alow-ahigh進(jìn)行快速排序。四、填空題76. 一個對象序列的關(guān)鍵碼為 46, 79, 56, 38, 40, 84 ,采用快速排序以位于最左位 置的對象為基準(zhǔn)而得到的第一次劃分結(jié)果為（）。77. 設(shè)有一個10階的對稱矩陣A 1010，采用壓縮存儲方式按行將矩陣中下三角部分 的元素存入一維數(shù)組B 中，A 00存入B 0中，則A 85 在B 中的位置是（）。78. 具有65個結(jié)點(diǎn)的完全二叉樹的高度為（）。79. 在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)

20、的（）倍。80. 數(shù)據(jù)元素從邏輯上分為線性結(jié)構(gòu)和（）結(jié)構(gòu)。81. 將插入限定在表的一端，而刪除限定在表的另一端進(jìn)行的線性表是（）。82. 若規(guī)定空二叉樹的深度為-1 ，則深度為k 的二叉樹的最大結(jié)點(diǎn)數(shù)是（）個。83. 存儲數(shù)據(jù)時，不僅要存儲數(shù)據(jù)的值，還要存儲元素之間的（） 。84. N 個頂點(diǎn)的有向完全圖具有（）條弧。85. （ ） 是數(shù)據(jù)的基本單位。86. 數(shù)據(jù)結(jié)構(gòu)被形式的定義為（D,S）,其中D是（）的有限集合，S是D上關(guān)系的有限集合。87. 深度為3 的二叉樹至少有（）個結(jié)點(diǎn)。88. 若二叉樹中不含有度為1的結(jié)點(diǎn)，那么此二叉樹中度為2的結(jié)點(diǎn)數(shù)n2與度為0的結(jié)點(diǎn)數(shù)n0之間滿足（）關(guān)系式。8

21、9. 已知一棵二叉樹中序遍歷和后序遍歷結(jié)果都是cba, 它的先序遍歷結(jié)果是（）。90. 兩個串相等的充分必要條件是（） 。91. 對于長度為N 的線性表進(jìn)行順序查找，則時間復(fù)雜度為（） 。92. 對于長度為N 的線性表采用二分查找，則時間復(fù)雜度為（） 。93. 一棵有k 層的滿二叉樹一共有（）個結(jié)點(diǎn)。（根結(jié)點(diǎn)為第1 層）94. 在一棵二叉樹中，第5 層上的結(jié)點(diǎn)數(shù)最多為（） 。95. 對序列（10， 5， 17， 5*， 1， 9）排序時，若采用穩(wěn)定的排序算法遞增排序，其結(jié)果為（） 。96. 有n個元素的數(shù)組a, Loc （a。）是a。的存儲地址，每個元素需占用L個存儲單元，則第i 個元素的存儲

22、地址為（） 。97. 采用哈希存儲方法時，用于計(jì)算結(jié)點(diǎn)存儲地址的是（） 。98. 在排序過程中，任何情況下都不比較關(guān)鍵字大小的排序算法是（） 。99. 有一組序列 48, 36, 68, 99, 75, 24, 28, 52進(jìn)行快速排序，要求結(jié)果從小到大排列，則進(jìn)行一趟快速排序的結(jié)果是（） 。100. 若以4, 5, 6, 7, 8作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是 （）。五、判斷題（略）答案、單選題1. C2. C3. A4. C5. B6. C7. A8. C9. C10. D11. C12. A13. A14. A15. B16. A17. C18. B19. B20.

23、D21. D22. D23. D24. A25. A26. A27. D28. D29. D30. A31. B32. C33. A34. D35. A36. A37. B38. A39. C第 11 頁 共 21 頁40. C41. B42. B43. C44. B45. A46. B47. B48. B49. D50. D、簡答題51. 設(shè)散列表的長度 m = 13 ;散列函數(shù)為H( K ) = K mod m，給定的關(guān)鍵碼序列為 19, 14, 23, 01, 68, 20, 84, 27, 55, 11,貝U有H (19)= 6,成功；H (14)= 1,成功；H (23)= 10,成

24、功；H (01)= 1，沖突，=2, 成功；H (68) =3,成功；H (20) = 7,成功；H (84) = 6,沖突，=7,沖突，=8 成 功；H (27) =1,沖突，=2 ,沖突，=3 ,沖突，=4 ,成功；H (55) = 3 ,沖突， =4 ,沖突，=5 ,成功；H (11) = 11 ,成功；012345678910111252.14016827551920842311在等概率的情況下，搜索成功時的平均搜索長度：ASLSUCC = 18/10 = 1.854.68 45 20 90 15 10 50第一趟10 45 2090 15 68 50第二趟10 1520 9045 6

25、8 50第三趟10 1520 90 4568 50第四趟10 15 20 45 90 68 50第五趟10 15 20 45 50 68 90用八趟10 15 20 45 50 68 90第七趟10 15 20 45 50 68 9055.原始：3122437455361 78 90 100T lowT midT high第一次后3122437455361 78 90 100T low T midT high第二次后 3122437455361 78 90 100T low T high第三次后 3122437455361 78 90 100T low T highT mid經(jīng)過3次比較后，找

26、到了元素 37小根堆序列：7, 17, 32, 40, 18, 60, 73, 65, 8556.大根堆序列：85 , 65, 73, 40,7, 32,60, 18,1757.第17頁共21頁ASL=(7*1+2*2+3*2+4*1)/12=21/12=7/458.50WPL=1(X 2+2X 4+3X 4+6X3+14X2+7X3 + 8X3= 13159.圖型數(shù)據(jù)結(jié)構(gòu)60.第三趟62.初始第趟第二趟1919191972020207198055720205573535357355555553580806666第四趟 第五趟結(jié)束908866 80886688012OO5OO120881088

27、08858806810860883811oo83811 0(2)最小生成樹如下:64. (1) 0 1 4 2 5 3101011I 001000111000011 11 0 01001 第16頁共21頁669063. (1)鄰接矩陣如下:a b c d e f65. （ 1 ） 4，（ 2） 4，gdbeca（ 3） C F G L I M K 66. abdgce dgbaec 67. （ 1 ） 3（ 2） 2 5 4 3 6 1第 19 頁 共 21 頁第21頁共21頁74, 50, 26, 15, 0650, 26, 15, 75 50, 26, 15, 0650, 26, 15,

28、0669.(1)75 ,37,81,19,82,(2) 06,37,81 ,19,82,74,(3) 75,37,81 ,19,82,74,(4) 75,37,81 ,19,82,74,70.884546587044391227660123456789101112ASL=(1*6+1*6+1*7+1*4+1*10)/10=33/10=3.3三、算法設(shè)計(jì)題71. void insert( ListNode *Head, int item) ListNode *p;p=Head->next;while(p!=Null&&p->data!=a) p=p->next;if(p=Null) printf( "不存在結(jié)點(diǎn) a"); elses->next=p->next