數(shù)據(jù)結(jié)構(gòu)試題（三）

1、數(shù)據(jù)結(jié)構(gòu)試題（三）一、選擇題（共20分，每題1分）1在有向圖G的拓?fù)湫蛄兄校繇旤c(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（ ）。AG中有弧<Vi，Vj> BG中有一條從Vi到Vj的路徑 CG中沒(méi)有弧<Vi,Vj> DG中有一條從Vj到Vi的路徑2. 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ ）倍。A. 1/2 B. 2 C. 1 D. 43. n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有( )。 An-1條有向邊 Bn條有向邊 Cn(n-1)/2條有向邊 Dn(n-1)條有向邊4. 在一棵度為3的樹(shù)中,度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2 的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為(

2、)A 4 B5 C6 D75. 圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于( )圖A有向 B無(wú)向 C森林 D連通6. 若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為( )。A. (n-1)/2 B. n/2 C. n D. (n+1)/27. 下面關(guān)于二分查找的敘述正確的是 ( )。A. 表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ) B. 表必須有序，而且只能從小到大排列 C. 表必須有序，且表只能以順序方式存儲(chǔ) D. 表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型8. 在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A,并已知

3、A無(wú)左孩子的平衡因子為，右孩子的平衡因子為1,則應(yīng)作( ) 型調(diào)整以使其平衡。A. LL B. LR C RL D RR9散列表的地址區(qū)間為0-17,散列函數(shù)為H(K)=K mod 17。采用線(xiàn)性探測(cè)法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59依次存儲(chǔ)到散列表中。存放元素59需要搜索的次數(shù)是（ ）。A. 2 B. 3 C.4 D.510. 設(shè)要排序（Sort）的數(shù)據(jù)為：5, 1, 10, 2, 15, 3，若采用堆排序法（Heap Sort）排為升序，則當(dāng)堆樹(shù)（Heap tree）第三次建成時(shí)，其樹(shù)根節(jié)點(diǎn)數(shù)據(jù)內(nèi)容是( )。A. 3 B. 10 C.15 D.511在對(duì)n個(gè)元

4、素進(jìn)行冒泡排序的過(guò)程中，最好情況下的時(shí)間復(fù)雜度為( )。AO(1) BO(log2n) CO(sqt(n) DO(n)12有一個(gè)100*90的稀疏矩陣，非0元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是（ ）。A60 B66 C18000 D3313. 設(shè)給定權(quán)值總數(shù)有n 個(gè)，其哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為( ) A不確定 B2n C2n+1 D2n-114. 已知廣義表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列運(yùn)算的結(jié)果: tail(head(tail(C) =( )。A（a） BA Ca D（A）15. 設(shè)有一個(gè)8階的對(duì)稱(chēng)矩陣A，采用以

5、行優(yōu)先的方式壓縮存儲(chǔ)。a11為第1個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間。試問(wèn)元素a85的地址為（ ）。A33 B30 C13 D2316. 下面說(shuō)法不正確的是( )。A. 廣義表的表頭總是一個(gè)廣義表 B. 廣義表的表尾總是一個(gè)廣義表 C. 廣義表難以用順序存儲(chǔ)結(jié)構(gòu) D. 廣義表可以是一個(gè)多層次的結(jié)構(gòu)17. 在下述結(jié)論中，正確的是（ ） 只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0; 二叉樹(shù)的度為2； 二叉樹(shù)的左右子樹(shù)可任意交換; 深度為K的完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿(mǎn)二叉樹(shù)。A B C D 18. 對(duì)于有n 個(gè)結(jié)點(diǎn)的二叉樹(shù), 其高度為（ ）Anlog2n Blog2n C|log2n|

6、+1 D不確定19. 設(shè)給定權(quán)值總數(shù)有n 個(gè)，其哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為( )A不確定 B2n C2n+1 D2n-120. 已知一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為( )。ACBEFDA BFEDCBA CCBEDFA D不定二、填空題（共30分，每空2分）1. 一個(gè)循環(huán)隊(duì)列的最大容量為m，Cq_front為隊(duì)首指針，Cq_rear為隊(duì)尾指針。那么進(jìn)隊(duì)操作時(shí)求隊(duì)位Cq_rear =（1）。2. 一棵二叉樹(shù)高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹(shù)最少有（2）個(gè)結(jié)點(diǎn)3.對(duì)一組數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過(guò)

7、程中的變化為（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 則采用的排序是（3）排序。4. 樹(shù)是結(jié)點(diǎn)的有限集合, 樹(shù)是由根結(jié)點(diǎn)和若干顆子樹(shù)構(gòu)成的。一個(gè)節(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱(chēng)為該節(jié)點(diǎn)（4）；一棵樹(shù)高為K的完全二叉樹(shù)至少有（5）個(gè)結(jié)點(diǎn)；高度為 K的二叉樹(shù)最大的結(jié)點(diǎn)數(shù)為（6）。5. 二叉樹(shù)中某一結(jié)點(diǎn)左子樹(shù)的深度減去右子樹(shù)的深度稱(chēng)為該結(jié)點(diǎn)的（ 7 ）。6. 具有256個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（ 8 ）。7. 就希爾排序的穩(wěn)定性而言，是一種（ 9 ）的排序方法。8. 字符串a(chǎn)babaabab的nex

8、tval 為（ 10 ）（答案數(shù)值用逗號(hào)隔開(kāi)，勿添加空格和括號(hào)）。9. 數(shù)據(jù)結(jié)構(gòu)分別為邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)），邏輯結(jié)構(gòu)有分為四類(lèi)基本結(jié)構(gòu)，分別是（11）、（12）、（13）、（14）。10. 去除廣義表LS=(a1,a2,a3,，an)中第1個(gè)元素，由其余元素構(gòu)成的廣義表稱(chēng)為L(zhǎng)S的（ 15 ）。三、簡(jiǎn)答題（共60分）1.（5分）如圖1所示的二叉樹(shù)，請(qǐng)分別寫(xiě)出前序和中序遍歷序列。 圖1 第一題圖 圖2第二題圖2 .（5分）對(duì)于圖2所示的無(wú)向帶權(quán)圖，構(gòu)造最小生成樹(shù)。3.（8分）關(guān)鍵字序列 T=(20，25，49，49*，13，05），請(qǐng)寫(xiě)出快速排序的結(jié)果。該排序方法是穩(wěn)定的嗎？為什么？4.

9、（8分）根據(jù)給定集合15,3,14,2,6,9,16,17，構(gòu)造相應(yīng)的huffman樹(shù)，給出計(jì)算它的帶權(quán)路徑長(zhǎng)度，以及集合中每個(gè)元素對(duì)應(yīng)的huffman編碼。5.（8分）簡(jiǎn)述線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)的不同點(diǎn)。6.（8分）給出一組關(guān)鍵字T=(12,2,16,30,8,28,4,10,20,6,18),寫(xiě)出用希爾排序（第一趟排序的增量為5）從小到大排序時(shí)第一趟結(jié)束時(shí)的序列。7. （8分）若線(xiàn)性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線(xiàn)性表中的元素，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？8. （10分）已知關(guān)鍵字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 ，設(shè)定哈希函數(shù) H(key) = key MOD 11，請(qǐng)構(gòu)造哈希表，利用線(xiàn)性探測(cè)再散列 di = cÍi ，其中 c=1解決沖突,并計(jì)算平均查找長(zhǎng)度