《數(shù)據(jù)結(jié)構(gòu)概論》期末試卷
姓名: 專業(yè):
學(xué)號(hào): 學(xué)習(xí)中心:
? 成績(jī):
一、單項(xiàng)選擇題 (請(qǐng)將答案填寫在后面的表格中,每小題2分,共30分)
1.查找n個(gè)元素的有序表時(shí),最有效的查找方法是( )
A.順序查找 B.分塊查找
C.折半查找 D.二叉排序樹查找
2.具有12個(gè)關(guān)鍵字的有序表,查找成功時(shí)折半查找的平均查找長(zhǎng)度是( )
A.3.1 B.4 C.2.5 D.5
3.在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表仍然有序的時(shí)間復(fù)雜度是( )
A.O(1) B.O(n)
C.O(nlogn) D.O(n2)
4.對(duì)平均性能而言,以下最好的內(nèi)排序方法是( )。
A.冒泡排序 B.希爾排序
C.交換排序 D.快速排序
5.鏈棧與順序棧相比,比較明顯的優(yōu)點(diǎn)是( )
A.插入操作更加方便 B.刪除操作更加方便
C.不會(huì)出現(xiàn)下溢的情況 D.不會(huì)出現(xiàn)上溢的情況
6.二叉樹中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多為( )
A.8 B.15
C.16 D.32
7.以下數(shù)據(jù)結(jié)構(gòu)中,( )是非線性數(shù)據(jù)結(jié)構(gòu)。
A.樹 B.字符串
C.隊(duì) D.棧
8.一個(gè)向量的第一個(gè)元素的地址是100,每個(gè)元素的長(zhǎng)度是2 ,則第五個(gè)元素的地址是( )。
A.102 B.110
C.108 D.120
9.已知圖的鄰接表如下所示,根據(jù)算法,則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是( )
A. 0 3 2 1 B. 0 1 2 3
C. 0 1 3 2 D.0 3 1 2
(第9題配圖:數(shù)組的下標(biāo)為0,1,2,3)
10.對(duì)于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是( )
A.35和41 B.23和39
C.15和44 D.25和51
11.有一個(gè)有序表為{ 1,3,9,12,32,41,45,62,77,88,92,100},用折半查找法,若要找63,要經(jīng)過(guò)( )次與63比較。
A.12 B.6
C.4 D.5
12.下述幾種排序方法中,穩(wěn)定的排序算法是( )
A.直接插入排序 B.快速排序
C.堆排序 D.希爾排序
13.具有n個(gè)頂點(diǎn)的無(wú)向圖至少要有( )條邊才能確保是一個(gè)連通圖。
A.n(n+1) B.n-1
C.n+1 D.n(n-1)
14.二叉樹是非線性數(shù)據(jù)結(jié)構(gòu),所以 ( )
A.它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ) B.它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)
C.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ) D.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用
15.有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有( )條邊。
A.14 B.28
C.56 D.112
單項(xiàng)選擇題答題表格(請(qǐng)將答案填寫在下表中)
題號(hào) 1 2 3 4 5 6 7 8 9 10
答案
題號(hào) 11 12 13 14 15
答案
二、填空題(每小題2分,共30分)
1. 下面程序段的時(shí)間復(fù)雜度為________。
sum=1; for(i=0;sum<n;i++) sum+=1;
2. 設(shè)數(shù)組a[M](M為最大空間個(gè)數(shù))作為循環(huán)隊(duì)列Q的存儲(chǔ)空間,front為隊(duì)頭指針(指向第一個(gè)存放數(shù)據(jù)的位置),rear為隊(duì)尾指針(指向最后一個(gè)存放數(shù)據(jù)位置的下一個(gè)),則判定Q隊(duì)列的隊(duì)滿條件是_____________。
3. 若已知一棵二叉樹的前序序列是BEFCGDH,中序序列是FEBGCHD,則它的后序序列必是________。
4. 散列法存儲(chǔ)的基本思想是由_______________決定數(shù)據(jù)的存儲(chǔ)地址。
5. 在一棵度為3的樹中,度為2的結(jié)點(diǎn)個(gè)數(shù)是1,度為0的結(jié)點(diǎn)個(gè)數(shù)是6,則度為3的結(jié)點(diǎn)個(gè)數(shù)是________。
6. 設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn),則共有____________個(gè)葉子結(jié)點(diǎn) 。
7. n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ),深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為_______________;若采用鄰接表存儲(chǔ)時(shí),該算法的時(shí)間復(fù)雜度為______________ 。
8. 在堆排序和快速排序中,若初始記錄接近正序或反序,則選用______________;若初始記錄基本無(wú)序,則最好選用_______________。
9. 若要求一個(gè)稀疏圖G的最小生成樹,最好用_______________ 算法來(lái)求解。
10. 一棵深度為6的滿二叉樹有 ________________ 個(gè)分支結(jié)點(diǎn)和____________個(gè)葉子。
11.用5個(gè)權(quán)值{3, 2, 4, 5, 1}構(gòu)造的哈夫曼(Huffman)樹的帶權(quán)路徑長(zhǎng)度是__________。
12. 有向圖G用鄰接矩陣存儲(chǔ),其第i行的所有元素之和等于頂點(diǎn)i的____________。
三、解答題(每小題9分,共27分)
1. 已知以下的有向圖,用Dijkstra算法求出從頂點(diǎn)1出發(fā)到各頂點(diǎn)的最短路徑(按步給分)。
2.待排序的序列為:25,47,36,21,90,84,62,78,15,32。寫出用(大根)堆排序的每一趟的結(jié)果。
3.一棵度為2的有序樹與一棵二叉樹有何區(qū)別?
四、程序設(shè)計(jì)題(共13分)
1、已知r[]為一維數(shù)組,其中r[0]到r[n-1]為待排序的n個(gè)元素,排序好的元素仍放在r[0]到r[n-1]中,請(qǐng)寫出對(duì)該數(shù)組進(jìn)行非遞歸的直接插入排序算法,取名為insertsort(elemtype r[],int n)。