《數據結構2264》22春在線作業(yè)1-00001
試卷總分:100 得分:100
一、單選題 (共 25 道試題,共 50 分)
1.設森林F對應的二叉樹為B，它有m個結點，B的根為p，p的右子樹上的結點個數為n，森林F中第一棵樹的結點個數是（ ）。
A.m-n-1
B.n+1
C.m-n+1
D.m-n
2.一散列表長度m為100，采用除留余數法構造散列函數，即H（ ）=K%P （ ）,，為使散列函數具有較好的性能，P的選擇應是（ ）。
A.99
B.100
C.97
D.93
3.對n個記錄進行堆排序，所需要的輔助存儲空間為（ ）。
A.O（1og2n
B.O（n）
C.O（1）
D.O（n2）
4.設Huffman樹的葉子結點數為m，則結點總數為（ ）。
A.2m
B.2m-1
C.2m+1
D.m+1
5.已知一個圖的頂點集V={1,2,3,4,5,6,7}；邊集E={（ ）3, （ ）5, （ ）8, （ ）10, （ ）6, （ ）15, （ ）12, （ ）9, （ ）4, （ ）20, （ ）18, （ ）25}，用克魯斯卡爾算法得到最小生成樹，則在最小生成樹中依次得到的各條邊為（ ）。
A.(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
B.(1,2)3, (4,6)4, (1,3)5, (2,3)6, (1,4)8, (3,6)9
C.(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20
D.(1,2)3, (1,3)5, (1,4)8, (2,5)10, (4,6)4, (4,7)20
6.在二叉樹結點的先序序列、中序序列和后序序列中，所有葉子結點的先后順序（ ）
A.都不相同
B.完全相同
C.先序和中序相同，而與后序不同
D.中序和后序相同，而與先序不同
7.對關鍵字序列（ ）進行增量為3的一趟希爾排序的結果為（ ）。
A.(19, 23, 56, 34, 78, 67, 88, 92)
B.(23, 56, 78, 66, 88, 92, 19, 34)
C.(19, 23, 34, 56, 67, 78, 88, 92)
D.(19, 23, 67, 56, 34, 78, 92, 88)
8.采用開放定址法處理散列表的沖突時，其平均查找長度（ ）。
A.低于鏈接法處理沖突
B.高于鏈接法處理沖突
C.與鏈接法處理沖突相同
D.高于二分查找
9.AOV網是一種（ ）。
A.有向圖
B.無向圖
C.無向無環(huán)圖
D.有向無環(huán)圖
10.如表r有100000個元素，前99999個元素遞增有序，則采用（ ）方法比較次數較少。
A.直接插入排序
B.快速排序
C.歸并排序
D.選擇排序
11.對于關鍵字序列（ ）進行散列存儲時，若選用H（ ）=K%7作為散列函數，則散列地址為0的元素有（ ）個。
A.1
B.2
C.3
D.4
12.中綴表達式2+X*（ ）的后綴形式是（ ）。
A.3 Y X 2 + * +
B.Y 3 + X * 2 +
C.2 X Y 3 * + +
D.2 X Y 3 + * +
13.下列關于數據結構的敘述中，正確的是（ ）。
A.數組是不同類型值的集合
B.遞歸算法的程序結構比迭代算法的程序結構更為精煉
C.樹是一種線性結構
D.用一維數組存儲一棵完全二叉樹是有效的存儲方法
14.從一個長度為n的順序表中刪除第i個元素（ ）時，需向前移動的元素個數是（ ）。
A.n-i
B.n-i+1
C.n-i-1
D.i
15.對一棵有100個結點的完全二叉樹按層編號，根結點編號為1，則編號為49的結點的父結點的編號為（ ）。
A.24
B.5
C.98
D.99
16.若某二叉樹結點的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。 則該二叉樹結點的前序遍歷的序列為（ ）。
A.G、F、A、C、D、B
B.A、G、C、F、B、D
C.A、C、B、D、G、F
D.G、A、C、D、F、B
17.對廣義表L=（ ）,（ ）,（ ）執(zhí)行操作tail（ ）的結果是（ ）。
A.(e,f)
B.((e,f))
C.(f)
D.( )
18.k層（ ）二叉樹的結點總數最多為（ ）。
A.2k-1
B.2K+1
C.2K-1
D.2k-1
19.對線性表進行二分法查找，其前提條件是（ ）。
A.線性表以鏈接方式存儲，并且按關鍵碼值排好序
B.線性表以順序方式存儲，并且按關鍵碼值的檢索頻率排好序
C.線性表以順序方式存儲，并且按關鍵碼值排好序
D.線性表以鏈接方式存儲，并且按關鍵碼值的檢索頻率排好序
20.帶有頭結點的單循環(huán)鏈表的頭指針為head，則該鏈表為空的判定條件是（ ）。
A.head= =NUL
B.head->next= =NULL
C.head!=NULL
D.head->next= =head
21.若有18個元素的有序表存放在一維數組A[19]中，第一個元素放A[1]中，現進行二分查找，則查找A[3]的比較序列的下標依次為（ ）。
A.1，2，3
B.9，5，2，3
C.9，5，3
D.9，4，2，3
22.在對n個關鍵字進行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關鍵字元素，則在進行第i趟排序之前，無序區(qū)中元素的個數為（ ）。
A.i
B.i+1
C.n-i
D.n-i+1
23.設有一個二維數組A[m][n] （ ），假設A[0][0]存放位置在600，A[3][3]存放位置在678，每個元素占一個空間，則A[2][3]的存放位置是（ ）。
A.658
B.648
C.633
D.653
24.若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則最節(jié)省運算時間的存儲方式是（ ）。
A.單鏈表
B.僅有頭指針的單循環(huán)鏈表
C.雙鏈表
D.僅有尾指針的單循環(huán)鏈表
25.假定有K個關鍵字互為同義詞，若用線性探測法把這K個關鍵字存入散列表中，至少要進行（ ）次探測。
A.K-1次
B.K次
C.K＋l次
D.K(K+1)/2次
二、多選題 (共 4 道試題,共 20 分)
26.以下哪些是隊列的基本運算？（ ）
A.在隊列第i個元素之后插入一個元素
B.從隊頭刪除一個元素
C.判斷一個隊列是否為空
D.讀取隊頭元素的值
E.將隊列中的元素排序
27.以下序列中，是堆（ ）的有（ ）。
A.{15,26,38,49,27,51,39,62}
B.{15,23,71,94,72,68,26,73}
C.{15,27,26,49,38,62,39,51}
D.{15,23,26,68,94,72,71,73}
E.{94,72,73,26,71,23,68,15}
28.若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行，則不可能出現的出棧序列為（ ）。
A.3，2，6，1，4，5
B.3，4，2，1，6，5
C.1，2，5，3，4，6
D.5，6，4，2，3，1
E.6，5，4，3，2，1
29.對一個算法的評價，主要包括如下（ ）方面的內容。
A.健壯性和可讀性
B.并行性
C.正確性
D.時空復雜度
E.界面友好性
三、判斷題 (共 15 道試題,共 30 分)
30.在采用線性探測法處理沖突的哈希表中，所有同義詞在表中相鄰。
31.線性表的長度是線性表所占用的存儲空間的大小。
32.若僅知道某二叉樹的中序遍歷序列和后序遍歷序列，則不能夠確定此二叉樹的層次遍歷的序列。
33.二維數組是數組元素為一維數組的線性表，因此二維數組元素之間是線性結構。
34.順序表用一維數組作為存儲結構，因此順序表是一維數組。
35.若一棵二叉樹的任一非葉子結點的度為2，則該二叉樹為滿二叉樹。
36.鏈式棧與順序棧相比, 一個明顯的優(yōu)點是通常不會出現棧滿的情況。
37.已知指針P指向鏈表L中的某結點，執(zhí)行語句P：=P?NEXT不會刪除該鏈表中的結點。
38.一個廣義表的表頭總是一個廣義表。
39.快速排序算法在每一趟排序中都能找到一個元素放在其最終的位置上。
40.為度量一個搜索算法的效率，需要在時間和空間兩個方面進行分析。
41.對任何用頂點表示活動的網絡（ ）進行拓撲排序的結果都是唯一的。
42.數據的邏輯結構是指各數據元素之間的邏輯關系，是用戶根據應用需要建立的。
43.存儲無向圖的鄰接矩陣是對稱的，因此可以只存儲鄰接矩陣的下（ ）三角部分。
44.在順序表中，邏輯上相鄰的元素在物理位置上不一定相鄰。
