《數(shù)據(jù)結(jié)構(gòu)2264》21秋在線作業(yè)1-00001
試卷總分:100 得分:100
一、單選題 (共 25 道試題,共 50 分)
1.對線性表進(jìn)行二分法查找，其前提條件是（ ）。
A.線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序
B.線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序
C.線性表以順序方式存儲，并且按關(guān)鍵碼值排好序
D.線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序
2.對一棵有100個結(jié)點的完全二叉樹按層編號，根結(jié)點編號為1，則編號為49的結(jié)點的父結(jié)點的編號為（ ）。
A.24
B.5
C.98
D.99
3.樹最適合用來表示（ ）。
A.有序數(shù)據(jù)元素
B.無序數(shù)據(jù)元素
C.元素之間具有分支層次關(guān)系的數(shù)據(jù)
D.元素之間無聯(lián)系的數(shù)據(jù)
4.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有（ ）條邊才能確保是一個連通圖。
A.5
B.6
C.7
D.8
5.若用鄰接矩陣表示一個有向圖，則其中每一列包含的″1″的個數(shù)為（ ）。
A.圖中每個頂點的入度
B.圖中每個頂點的出度
C.圖中每個頂點的度
D.圖中連通分量的數(shù)目
6.對于關(guān)鍵字序列（ ）進(jìn)行散列存儲時，若選用H（ ）=K%7作為散列函數(shù)，則散列地址為0的元素有（ ）個。
A.1
B.2
C.3
D.4
7.對關(guān)鍵字序列（ ）進(jìn)行增量為3的一趟希爾排序的結(jié)果為（ ）。
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.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A[3]的比較序列的下標(biāo)依次為（ ）。
A.1，2，3
B.9，5，2，3
C.9，5，3
D.9，4，2，3
9.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？（ ）
A.隊列
B.棧
C.線性表
D.二叉樹
10.設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p，p的右子樹上的結(jié)點個數(shù)為n，森林F中第一棵樹的結(jié)點個數(shù)是（ ）。
A.m-n-1
B.n+1
C.m-n+1
D.m-n
11.二維數(shù)組A[8][9]按行優(yōu)先順序存儲，若數(shù)組元素A[2][3]的存儲地址為1087，A[4][7]的存儲地址為1153，則數(shù)組元素A[6][7]的存儲地址為（ ）。
A.1207
B.1209
C.1211
D.1213
12.如表r有100000個元素，前99999個元素遞增有序，則采用（ ）方法比較次數(shù)較少。
A.直接插入排序
B.快速排序
C.歸并排序
D.選擇排序
13.設(shè)Huffman樹的葉子結(jié)點數(shù)為m，則結(jié)點總數(shù)為（ ）。
A.2m
B.2m-1
C.2m+1
D.m+1
14.帶有頭結(jié)點的單循環(huán)鏈表的頭指針為head，則該鏈表為空的判定條件是（ ）。
A.head= =NUL
B.head->next= =NULL
C.head!=NULL
D.head->next= =head
15.中綴表達(dá)式2+X*（ ）的后綴形式是（ ）。
A.3 Y X 2 + * +
B.Y 3 + X * 2 +
C.2 X Y 3 * + +
D.2 X Y 3 + * +
16.k層（ ）二叉樹的結(jié)點總數(shù)最多為（ ）。
A.2k-1
B.2K+1
C.2K-1
D.2k-1
17.對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（ ）
A.經(jīng)常需要隨機地存取元素
B.經(jīng)常需要進(jìn)行插入和刪除操作
C.表中元素需要占據(jù)一片連續(xù)的存儲空間
D.表中元素的個數(shù)不變
18.由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ）。
A.11
B.35
C.19
D.53
19.在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素可由（ ）。
A.實體
B.域
C.數(shù)據(jù)項
D.字段
20.數(shù)據(jù)的基本單位是（ ）。
A.數(shù)據(jù)項
B.數(shù)據(jù)類型
C.數(shù)據(jù)元素
D.數(shù)據(jù)變量
21.AOV網(wǎng)是一種（ ）。
A.有向圖
B.無向圖
C.無向無環(huán)圖
D.有向無環(huán)圖
22.含有10個結(jié)點的二叉樹中，度為0的結(jié)點數(shù)為4，則度為2的點數(shù)為（ ）。
A.3
B.4
C.5
D.6
23.從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為（ ）。
A.O(n)
B.O(1)
C.O(log2n)
D.O(n2)
24.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是（ ）。
A.數(shù)組是不同類型值的集合
B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉
C.樹是一種線性結(jié)構(gòu)
D.用一維數(shù)組存儲一棵完全二叉樹是有效的存儲方法
25.若有序表為（ ），則在二分查找關(guān)鍵字b的過程中，先后進(jìn)行比較的關(guān)鍵字依次為（ ）。
A.f,c,b
B.f,d,b
C.g,c,b
D.g,d,b
二、多選題 (共 4 道試題,共 20 分)
26.以下哪些是隊列的基本運算？（ ）
A.在隊列第i個元素之后插入一個元素
B.從隊頭刪除一個元素
C.判斷一個隊列是否為空
D.讀取隊頭元素的值
E.將隊列中的元素排序
27.對一個算法的評價，主要包括如下（ ）方面的內(nèi)容。
A.健壯性和可讀性
B.并行性
C.正確性
D.時空復(fù)雜度
E.界面友好性
28.棧和隊列的共同特點是（ ）。
A.只允許在端點處插入和刪除元素
B.都是先進(jìn)后出
C.都是先進(jìn)先出
D.沒有共同點
E.都可以采用順序存儲方式和鏈?zhǔn)酱鎯Ψ绞?/p>
29.若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出棧可以穿插進(jìn)行，則不可能出現(xiàn)的出棧序列為（ ）。
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
三、判斷題 (共 15 道試題,共 30 分)
30.在線性鏈表中刪除某個結(jié)點時，只需將被刪結(jié)點釋放。
31.對任何用頂點表示活動的網(wǎng)絡(luò)（ ）進(jìn)行拓?fù)渑判虻慕Y(jié)果都是唯一的。
32.進(jìn)行折半搜索的表必須是順序存儲的有序表。
33.一個廣義表（ ）,（ ）,c),（ ）))) 的表尾是（ ）,c),（ ）))。
34.鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。
35.若一棵二叉樹的任一非葉子結(jié)點的度為2，則該二叉樹為滿二叉樹。
36.為度量一個搜索算法的效率，需要在時間和空間兩個方面進(jìn)行分析。
37.二維數(shù)組是數(shù)組元素為一維數(shù)組的線性表，因此二維數(shù)組元素之間是線性結(jié)構(gòu)。
38.在用循環(huán)單鏈表表示的鏈?zhǔn)疥犃兄?，可以不設(shè)隊頭指針，僅在鏈尾設(shè)置隊尾指針。
39.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的。
40.線性表的長度是線性表所占用的存儲空間的大小。
41.棧和隊列都是順序存取的線性表，但它們對存取位置的限制不同。
42.圖G的某一最小生成樹的代價一定小于其他生成樹的代價。
43.鏈?zhǔn)綏Ｅc順序棧相比, 一個明顯的優(yōu)點是通常不會出現(xiàn)棧滿的情況。
44.有回路的有向圖不能完成拓?fù)渑判颉?/p>
