計算機系數(shù)據(jù)結(jié)構(gòu)平時測試試題一

1、臨沂大學 2015-2016 學年度第一學期數(shù)據(jù)結(jié)構(gòu)平時測試試題一選擇題(共 20題，每題 2 分，共 40分)1. 以下哪一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？()。A.棧B.哈希表C.線索樹D.雙向鏈表2. 下面的敘述不正確的是 () 。A. 線性表在鏈式存儲時，查找第B. 線性表在鏈式存儲時，查找第C. 線性表在順序存儲時，查找第i 個元素的時間同 i 的值成反比 i 個元素的時間同 i 的值無關(guān)i 個元素的時間同 i 的值成正比D. 線性表在順序存儲時，查找第i 個元素的時間同 i 的值無關(guān)3. 向一個有 127 個元素原順序表中插入一個新元素并保存原來順序不變，平均要移動( )個元素。A.

2、8 B.63.5 C.63 D.74. 單鏈表中，增加頭結(jié)點的目的是為了 ()。A. 使單鏈表至少有一個結(jié)點B.標示表結(jié)點中首結(jié)點的位置C.方便運算的實現(xiàn)D.說明單鏈表是線性表的鏈式存儲實現(xiàn)5. 在一個單鏈表中，已知 q 所指結(jié)點是 p 所指結(jié)點的前驅(qū)結(jié)點，若在 q 和 p 之間插入 s 結(jié) 點，則執(zhí)行 ()。A. s-next=p-next;p-next=s;B. p-next=s-next;s-next=p;C. q-next=s;s-next=p;D. p-next=s;s-next=q;A.n6. 從一個具有 n 個結(jié)點的單鏈表中查找其值等于 x 的結(jié)點時，在查找成功的情況下，需平 均

3、比較 ( )個結(jié)點？7.若已知一個棧的入棧序列為B. n/2 C.(n-1)/2 D.(n+1)/21,2,3, ,n 其輸出序列為 p1,p2,p3, ,pn 若 p1=n，則 pi 為() 。A.i B.n-iC.n-i+1D.不確定D.a,b,c,d,eD.-+*abcd10.設 n ，m 為一棵二叉樹的兩個結(jié)點，在中序遍歷時， A.n 在 m 的右方 C.n 在 m 的左方 11.樹中所有結(jié)點的度等于所有結(jié)點數(shù)加 A.0B.1C.-1D.212.設樹 T 的度為 4，其中度為 1，2，n在 m前的條件是 (B.n 是 m 的祖先D.n 是 m 的子孫() 。)。3和 4的結(jié)點個數(shù)分別為

4、 4，2，1，1 則 T中的葉子8.一個棧的入棧序列是 a,b,c,d,e ，則出棧序列不可能是 ()。A.e,d,c,b,a B.d,e,c,b,a C.d,c,e,a,b9.表達式 a*(b+c)-d 的后綴表達式是 ()。A.abcd*+- B.abc+*d- C.abc*+d-數(shù)為 ()。A.5 B.6 C.7 D.813. 對含有 ()個結(jié)點的非空二叉樹，采用任何一種遍歷方式，其結(jié)點訪問序列均相同。A.0 B.1 C.2D.不存在這樣的二叉樹32，10，43，18，則完成工程14.從 AOE 網(wǎng)絡的源點到終點共有 4 條路徑，路徑長度分別是 的最短時間是 ()。A.10 B. 43

5、C .32+10+43+18 D. (32+10+43+18)/4A.4 B.3 C.2D.116. 無向圖中一個頂點的度是指圖中 ()。A.通過該頂點的簡單路徑數(shù)B. 通過該頂點的回路數(shù)C. 與該頂點相鄰接的頂點數(shù)D. 與該頂點連通的頂點數(shù)17. 具有 12 個關(guān)鍵字的有序表，對每個關(guān)鍵字的查找概率相同，折半查找查找成功的平均 查找長度 ASL為 ()。A.37/12 B.35/12 C.39/12 D.43/1218. 在常用的描述二叉排序樹的存儲結(jié)構(gòu)中，關(guān)鍵字值最大的結(jié)點()。A.左指針一定為空B.右指針一定為空C. 左右指針均為空D.左右指針均不為空19. 有一組數(shù)據(jù) 15,9,7,8

6、,20,-1,7,4 ，對其進行建堆，則初始堆為 ()。A.-1,4,8,9,20,7,15,7B.-1,7,15,7,4,8,20,9C.-1,4,7,8,20,15,7,9D.以上都不是20. 下述排序算法中，穩(wěn)定的是 ( )。A.直接選擇排序B.基數(shù)排序C.快速排序D.堆排序二、 判斷題(共 10題，每題 1 分，共 10分)1. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。( )2. 在帶頭結(jié)點的單循環(huán)鏈表中，任一結(jié)點的后繼指針均不空。()3. 雙循環(huán)鏈表中，任一個結(jié)點的后繼指針均指向其邏輯后繼。()4. 通在對鏈隊列作出隊列操作，不會改變front 指針的值。 ( )5. 由于二叉樹中每個結(jié)點

7、的度最大為2，所以二叉樹是一種特殊的樹。 ( )6. 完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是樹葉。 ( )7. 在葉子數(shù)目和權(quán)值相同的所有二叉樹中，最優(yōu)二叉樹一定是完全二叉樹。( )8. 有 n 個頂點的無向圖 , 采用鄰接矩陣表示 , 圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。 （ ）9. 對一棵二叉排序樹按先序方法遍歷得出的結(jié)點序列是從小到大的序列。（ ）10. 歸并排序輔助存儲為 O（1）。 （）三、解答題（共 7 題，每題 5 分，共 35分）1. 已知一棵二叉樹的中序遍歷序列 :GLDHBEIA和后序遍歷序列 :LGHDIEBA （1）試畫出該二叉樹； （3 分）（2）試畫出

8、該二叉樹對應的樹； （ 2 分 ）2. 假設通信電文使用的字符集為 a,b,c,d,e,f,g，字符的赫夫曼編碼依次為： 0110 ，10，110， 111，00， 0111 和 010。（1）請根據(jù)赫夫曼編碼畫出此赫夫曼樹，并在葉子結(jié)點中標注相應字符；（3 分 ）（2）若這些字符在電文中出現(xiàn)的頻度分別為：3，35，13， 15，20，5 和 9，求該赫夫曼樹的帶權(quán)路徑長度。 （ 2 分）3. 已知有向圖（1） 試畫出它的鄰接表。 （表結(jié)點按頂點編號遞減排列） （3 分）（2） 求出從頂點 v1 開始深度優(yōu)先遍歷序列。 （2 分）4. 請對下圖的無向帶權(quán)圖：從頂點a 開始按普里姆算法求其最小生

9、成樹 ,（1）寫出頂點集（ 2 分）（2）寫出邊集（ 3 分）5. 根 據(jù) 關(guān) 鍵 字 序 列 48,68,72,60,36,25,45,40 （1）構(gòu)造一棵二叉排序樹； （ 3 分） （2）求出等概率下的平均查找長度 ASL。（2 分）6. 已知待散列的線性表為（ 36，15，40，63，22），哈希地址空間為 0.6 ，假定選用的哈希 函數(shù)是 H（K）= K %7，若發(fā)生沖突采用線性探測再散列處理，試： （1）在下圖中填寫出哈希表： （3 分） （2）求出在查找每一個元素概率相等情況下的平均查找長度。（2 分）地址空間0123456關(guān)鍵字試探次數(shù)7. 給出一組關(guān)鍵字 T=（12,2,16,30,8,28,4,10,20,6,18）, 寫出用下列算法從小到大排序時第一趟結(jié) 束時的序列；得分閱卷人（1） 希爾排序（第一趟排序的增量為 5 ）（2） 快速排序（選第一個記錄為樞軸（分隔）2 分）四、算法設計題（共 2 題，共 15分）（ 3 分）1.試寫出一遞歸算法，判別兩棵樹是否相等。所謂兩棵二叉樹s和 t 相等為:兩棵空二叉樹相等;若不空 ,根結(jié)點的數(shù)據(jù)域的值