數(shù)據(jù)結(jié)構(gòu)模擬試卷二及答案

1、模擬試卷二一、 單選題（每題 2 分，共20分）1. 在一個(gè)帶有附加表頭結(jié)點(diǎn)的單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行(B )。 A. HL=p; p-next=HL; B. p-next=HL-next; HL-next=p; C. p-next=HL; p=HL; D. p-next=HL; HL=p; 2. 若順序存儲(chǔ)的循環(huán)隊(duì)列的QueueMaxSize=n,則該隊(duì)列最多可存儲(chǔ)（A B ）個(gè)元素. A. n B.n-1 C. n+1 D.不確定3. 下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？（C A ） A存儲(chǔ)密度大 B.插入和刪除運(yùn)算方便 C. 獲取符合某種條件的元素方便 D.

2、查找運(yùn)算速度快4. 設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在600(10)，A33存放位置在678(10)，每個(gè)元素占一個(gè)空間，問A23(10)存放在什么位置？(腳注(10)表示用10進(jìn)制表示,m3) BD A658 B648 C633 D653 3m+3=78 m=255. 下列關(guān)于二叉樹遍歷的敘述中，正確的是( DA ) 。A. 若一個(gè)樹葉是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)B若一個(gè)點(diǎn)是某二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn) C若一個(gè)結(jié)點(diǎn)是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序最后一個(gè)結(jié)點(diǎn) D若一

3、個(gè)樹葉是某二叉樹的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后一個(gè)結(jié)點(diǎn)6. k層二叉樹的結(jié)點(diǎn)總數(shù)最多為( A ). A2k-1 B.2K+1 C.2K-1 D. 2k-17. 對(duì)線性表進(jìn)行二分法查找，其前提條件是( ).A. 線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序 B. 線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序C. 線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序D. 線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序8. 對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為 A. O（1og2n） B. O（n） C. O（1） D. O（n2）9. 對(duì)于線性表（7，34，77，25

4、，64，49，20，14）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K %7作為散列函數(shù)，則散列地址為0的元素有（ ）個(gè)， A1 B2 C3 D410. 下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是( D ).A. 數(shù)組是不同類型值的集合 B. 遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C. 樹是一種線性結(jié)構(gòu)D. 用一維數(shù)組存儲(chǔ)一棵完全二叉樹是有效的存儲(chǔ)方法二、 填空題（每空1分，共26分）1. 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、_、_和_四種。2. 一個(gè)算法的時(shí)間復(fù)雜度為(3n3+2000nlog2n+90)/n2，其數(shù)量級(jí)表示為_。3. 對(duì)于一個(gè)長度為n的單鏈存儲(chǔ)的隊(duì)列，在表頭插入元素的時(shí)間復(fù)雜度為_，在表尾插入元

5、素的時(shí)間復(fù)雜度為_。4. 假定一棵樹的廣義表表示為A（D（E，G），H（I，J），則樹中所含的結(jié)點(diǎn)數(shù)為_個(gè)，樹的深度為_，樹的度為_。5. 后綴算式79 2 30 + - 4 2 / *的值為_。中綴算式（3+X*Y）-2Y/3對(duì)應(yīng)的后綴算式為_。6. 在一棵高度為5的理想平衡樹中，最少含有_個(gè)結(jié)點(diǎn)，最多含有_個(gè)結(jié)點(diǎn)。7. 在樹中，一個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)稱為該結(jié)點(diǎn)的_。一個(gè)結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的_。8. 在一個(gè)具有10個(gè)頂點(diǎn)的無向完全圖中，包含有_條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有_條邊。9. 假定一個(gè)線性表為(12,17,74,5,63,49,82,36)，若按Key %

6、 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為_、_、_和_。10. 對(duì)一棵B_樹進(jìn)行刪除元素的過程中，若最終引起樹根結(jié)點(diǎn)的合并時(shí)，會(huì)使新樹的高度比原樹的高度_。11. 在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_，整個(gè)堆排序過程的時(shí)間復(fù)雜度為_。12. 在線性表的散列存儲(chǔ)中，裝填因子a又稱為裝填系數(shù)，若用m表示散列表的長度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則a等于_。三、 運(yùn)算題（每題 6 分，共24分）1 在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針存放在A 0.next，試寫出該線性表。 A 0 1 2 3 4 5 6 7 data605078903

7、440next40527132 已知一棵二叉樹的前序遍歷的結(jié)果是ABKCDFGHIJ, 中序遍歷的結(jié)果是KBCDAFHIGJ, 試畫出這棵二叉樹。3 已知一個(gè)圖的頂點(diǎn)集V為： V=1,2,3,4,5,6,7; 其共有10條邊。該圖用如下邊集數(shù)組存儲(chǔ)：起點(diǎn)1225522613終點(diǎn)6454767775權(quán)1122233457試用克魯斯卡爾算法依次求出該圖的最小生成樹中所得到的各條邊及權(quán)值。4 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3, 6, 10, 1時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。四、 閱讀算法（每題7分，共14分）1. 在下面的每個(gè)程序段中，假定線性表La的類型為List，元素類型Elem

8、Type為int，并假定每個(gè)程序段是連續(xù)執(zhí)行的。試寫出每個(gè)程序段執(zhí)行后所得到的線性表La。（1） InitList(La); Int a=100,26,57,34,79; For (i=0;i5;i+) Insert(La,ai); TraverseList(La);（2） DeleteFront(La);InsertRear(La, DeleteFront(La); TraverseList(La);（3） ClearList(La); For (i=0;i5;i+) InsertFront(La,ai); TraverseList(La);2. 現(xiàn)面算法的功能是什么？void ABC(BT

9、Node * BT) if BT coutdataleft); ABC(BT-right); 五、 算法填空（共8分）二分查找的遞歸算法。 Int Binsch(ElemType A,int low,int high,KeyType K) if _ int mid=(low+high)/2; if (_) return mid; /查找成功，返回元素的下標(biāo) else if (KAmid.key) return Binsch(A,low,mid-1,K); /在左子表上繼續(xù)查找 else return_； /在右子表上繼續(xù)查找 else _； /查找失敗，返回-1 六、 編寫算法（共8分）HL為

10、單鏈表的表頭指針，試寫出在該單鏈表中查找具有給定的元素item的算法。bool Find(LNode* HL, ElemType &item)模擬試卷二參考答案一、 單選題（每題2分，共20分）1.B 2.B 3.A 4.D 5.A 6.A 7.C 8.C 9.D 10.D二、 填空題（每空1分，共26分）1. 集合結(jié)構(gòu) 線性結(jié)構(gòu) 樹結(jié)構(gòu) 圖結(jié)構(gòu)2. O(n)3. O(1) O(1)4. 7 3 25. 94 3 X Y * + 2 Y * 3 / -6. 16 317. 孩子（或子）結(jié)點(diǎn) 雙親（或父）結(jié)點(diǎn)8. 45 n(n-1)9. （12，36） （17,5,49） （74，82） （63

11、）10. 減少1（或減少）11. O(log2n) O(nlog2n)12. n/m三、 運(yùn)算題（每題6分，共24分）1. 線性表為：（90，40，78，50，34，60）2. 當(dāng)前序序列為ABKCDFGHIJ，中序序列為KBCDAFHIGJ時(shí)，逐步形成二叉樹的過程如下圖4所示： FHIGJAABKFCDHIGJABKFCDGJHIABKFCDGJHIKBCD圖43. 用克魯斯卡爾算法得到的最小生成樹為： (1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)74. 見圖5。424442255522884352834652834610513246108528

12、344圖5四、 閱讀算法（每題7分，共14分）1. (1) La=(26,34,57,79,100) (2)La=(57,79,100,34) (3)La=(79,34,57,26,100) 2. 前序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹。五、 算法填空（每空2分，共8 分）(lowdata=item) return true; else p=p-next; return false;模擬試卷二七、 單選題（每題 2 分，共20分）11. 在一個(gè)帶有附加表頭結(jié)點(diǎn)的單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行( )。 A. HL=p; p-next=HL; B. p-next=HL-next; H

13、L-next=p; C. p-next=HL; p=HL; D. p-next=HL; HL=p; 12. 若順序存儲(chǔ)的循環(huán)隊(duì)列的QueueMaxSize=n,則該隊(duì)列最多可存儲(chǔ)（ ）個(gè)元素. A. n B.n-1 C. n+1 D.不確定13. 下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？（ ） A存儲(chǔ)密度大 B.插入和刪除運(yùn)算方便 C. 獲取符合某種條件的元素方便 D.查找運(yùn)算速度快14. 設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在600(10)，A33存放位置在678(10)，每個(gè)元素占一個(gè)空間，問A23(10)存放在什么位置？(腳注(10)表示用10進(jìn)制表示,m3) A658 B648 C633

14、 D65315. 下列關(guān)于二叉樹遍歷的敘述中，正確的是( ) 。A. 若一個(gè)樹葉是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)B若一個(gè)點(diǎn)是某二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn) C若一個(gè)結(jié)點(diǎn)是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序最后一個(gè)結(jié)點(diǎn) D若一個(gè)樹葉是某二叉樹的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后一個(gè)結(jié)點(diǎn)16. k層二叉樹的結(jié)點(diǎn)總數(shù)最多為( ). A2k-1 B.2K+1 C.2K-1 D. 2k-117. 對(duì)線性表進(jìn)行二分法查找，其前提條件是( ).E. 線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好

15、序 F. 線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序G. 線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序H. 線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序18. 對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為 A. O（1og2n） B. O（n） C. O（1） D. O（n2）19. 對(duì)于線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K %7作為散列函數(shù)，則散列地址為0的元素有（ ）個(gè)， A1 B2 C3 D420. 下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是( ).E. 數(shù)組是不同類型值的集合 F. 遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精

16、煉G. 樹是一種線性結(jié)構(gòu)H. 用一維數(shù)組存儲(chǔ)一棵完全二叉樹是有效的存儲(chǔ)方法八、 填空題（每空1分，共26分）13. 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、_、_和_四種。14. 一個(gè)算法的時(shí)間復(fù)雜度為(3n3+2000nlog2n+90)/n2，其數(shù)量級(jí)表示為_。15. 對(duì)于一個(gè)長度為n的單鏈存儲(chǔ)的隊(duì)列，在表頭插入元素的時(shí)間復(fù)雜度為_，在表尾插入元素的時(shí)間復(fù)雜度為_。16. 假定一棵樹的廣義表表示為A（D（E，G），H（I，J），則樹中所含的結(jié)點(diǎn)數(shù)為_個(gè)，樹的深度為_，樹的度為_。17. 后綴算式79 2 30 + - 4 2 / *的值為_。中綴算式（3+X*Y）-2Y/3對(duì)應(yīng)的后綴算式為_。18. 在一

17、棵高度為5的理想平衡樹中，最少含有_個(gè)結(jié)點(diǎn)，最多含有_個(gè)結(jié)點(diǎn)。19. 在樹中，一個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)稱為該結(jié)點(diǎn)的_。一個(gè)結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的_。20. 在一個(gè)具有10個(gè)頂點(diǎn)的無向完全圖中，包含有_條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有_條邊。21. 假定一個(gè)線性表為(12,17,74,5,63,49,82,36)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為_、_、_和_。22. 對(duì)一棵B_樹進(jìn)行刪除元素的過程中，若最終引起樹根結(jié)點(diǎn)的合并時(shí)，會(huì)使新樹的高度比原樹的高度_。23. 在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為

18、_，整個(gè)堆排序過程的時(shí)間復(fù)雜度為_。24. 在線性表的散列存儲(chǔ)中，裝填因子a又稱為裝填系數(shù)，若用m表示散列表的長度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則a等于_。九、 運(yùn)算題（每題 6 分，共24分）5 在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針存放在A 0.next，試寫出該線性表。 A 0 1 2 3 4 5 6 7 data605078903440next40527136 已知一棵二叉樹的前序遍歷的結(jié)果是ABKCDFGHIJ, 中序遍歷的結(jié)果是KBCDAFHIGJ, 試畫出這棵二叉樹。7 已知一個(gè)圖的頂點(diǎn)集V為： V=1,2,3,4,5,6,7; 其共有10條邊。該圖用如下邊集數(shù)組存儲(chǔ)：起

19、點(diǎn)1225522613終點(diǎn)6454767775權(quán)1122233457試用克魯斯卡爾算法依次求出該圖的最小生成樹中所得到的各條邊及權(quán)值。8 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3, 6, 10, 1時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。十、 閱讀算法（每題7分，共14分）3. 在下面的每個(gè)程序段中，假定線性表La的類型為List，元素類型ElemType為int，并假定每個(gè)程序段是連續(xù)執(zhí)行的。試寫出每個(gè)程序段執(zhí)行后所得到的線性表La。（4） InitList(La); Int a=100,26,57,34,79; For (i=0;i5;i+) Insert(La,ai); TraverseL

20、ist(La);（5） DeleteFront(La);InsertRear(La, DeleteFront(La); TraverseList(La);（6） ClearList(La); For (i=0;i5;i+) InsertFront(La,ai); TraverseList(La);4. 現(xiàn)面算法的功能是什么？void ABC(BTNode * BT) if BT coutdataleft); ABC(BT-right); 十一、 算法填空（共8分）二分查找的遞歸算法。 Int Binsch(ElemType A,int low,int high,KeyType K) if _ int mid=(low+high)/2; if (_) return mid; /查找成功，返回元素的下標(biāo) else if (KAmid.key) return Binsch(A,low,mid-1,K); /在左子表上繼續(xù)查找 else return_； /在右子表上繼續(xù)查找 else _； /查找失敗，返回-1 十二、 編寫算法（共8分）HL為單鏈表的表頭指針，試寫出在該單鏈表中查找具有給定的元素item的算法。bool Find(LNode* HL, ElemType &item)模擬試卷二參考答案七、 單選題（每題2分，共20分）1.