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

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

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

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

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

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

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

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. 樹是結(jié)點的有限集合, 樹是由根結(jié)點和若干顆子樹構(gòu)成的。一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點（4）；一棵樹高為K的完全二叉樹至少有（5）個結(jié)點；高度為 K的二叉樹最大的結(jié)點數(shù)為（6）。5. 二叉樹中某一結(jié)點左子樹的深度減去右子樹的深度稱為該結(jié)點的（ 7 ）。6. 具有256個結(jié)點的完全二叉樹的深度為（ 8 ）。7. 就希爾排序的穩(wěn)定性而言，是一種（ 9 ）的排序方法。8. 字符串a(chǎn)babaabab的nex

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

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