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