《數(shù)據(jù)結(jié)構(gòu)2264》22春在線作業(yè)1-00001
試卷總分:100 得分:100
一、單選題 (共 25 道試題,共 50 分)
1.設(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
2.一散列表長度m為100，采用除留余數(shù)法構(gòu)造散列函數(shù)，即H（ ）=K%P （ ）,，為使散列函數(shù)具有較好的性能，P的選擇應(yīng)是（ ）。
A.99
B.100
C.97
D.93
3.對n個記錄進行堆排序，所需要的輔助存儲空間為（ ）。
A.O（1og2n
B.O（n）
C.O（1）
D.O（n2）
4.設(shè)Huffman樹的葉子結(jié)點數(shù)為m，則結(jié)點總數(shù)為（ ）。
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.在二叉樹結(jié)點的先序序列、中序序列和后序序列中，所有葉子結(jié)點的先后順序（ ）
A.都不相同
B.完全相同
C.先序和中序相同，而與后序不同
D.中序和后序相同，而與先序不同
7.對關(guā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.采用開放定址法處理散列表的沖突時，其平均查找長度（ ）。
A.低于鏈接法處理沖突
B.高于鏈接法處理沖突
C.與鏈接法處理沖突相同
D.高于二分查找
9.AOV網(wǎng)是一種（ ）。
A.有向圖
B.無向圖
C.無向無環(huán)圖
D.有向無環(huán)圖
10.如表r有100000個元素，前99999個元素遞增有序，則采用（ ）方法比較次數(shù)較少。
A.直接插入排序
B.快速排序
C.歸并排序
D.選擇排序
11.對于關(guān)鍵字序列（ ）進行散列存儲時，若選用H（ ）=K%7作為散列函數(shù)，則散列地址為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.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是（ ）。
A.數(shù)組是不同類型值的集合
B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉
C.樹是一種線性結(jié)構(gòu)
D.用一維數(shù)組存儲一棵完全二叉樹是有效的存儲方法
14.從一個長度為n的順序表中刪除第i個元素（ ）時，需向前移動的元素個數(shù)是（ ）。
A.n-i
B.n-i+1
C.n-i-1
D.i
15.對一棵有100個結(jié)點的完全二叉樹按層編號，根結(jié)點編號為1，則編號為49的結(jié)點的父結(jié)點的編號為（ ）。
A.24
B.5
C.98
D.99
16.若某二叉樹結(jié)點的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。 則該二叉樹結(jié)點的前序遍歷的序列為（ ）。
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（ ）的結(jié)果是（ ）。
A.(e,f)
B.((e,f))
C.(f)
D.( )
18.k層（ ）二叉樹的結(jié)點總數(shù)最多為（ ）。
A.2k-1
B.2K+1
C.2K-1
D.2k-1
19.對線性表進行二分法查找，其前提條件是（ ）。
A.線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序
B.線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序
C.線性表以順序方式存儲，并且按關(guān)鍵碼值排好序
D.線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序
20.帶有頭結(jié)點的單循環(huán)鏈表的頭指針為head，則該鏈表為空的判定條件是（ ）。
A.head= =NUL
B.head->next= =NULL
C.head!=NULL
D.head->next= =head
21.若有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
22.在對n個關(guān)鍵字進行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關(guān)鍵字元素，則在進行第i趟排序之前，無序區(qū)中元素的個數(shù)為（ ）。
A.i
B.i+1
C.n-i
D.n-i+1
23.設(shè)有一個二維數(shù)組A[m][n] （ ），假設(shè)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個關(guān)鍵字互為同義詞，若用線性探測法把這K個關(guān)鍵字存入散列表中，至少要進行（ ）次探測。
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行，則不可能出現(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
29.對一個算法的評價，主要包括如下（ ）方面的內(nèi)容。
A.健壯性和可讀性
B.并行性
C.正確性
D.時空復(fù)雜度
E.界面友好性
三、判斷題 (共 15 道試題,共 30 分)
30.在采用線性探測法處理沖突的哈希表中，所有同義詞在表中相鄰。
31.線性表的長度是線性表所占用的存儲空間的大小。
32.若僅知道某二叉樹的中序遍歷序列和后序遍歷序列，則不能夠確定此二叉樹的層次遍歷的序列。
33.二維數(shù)組是數(shù)組元素為一維數(shù)組的線性表，因此二維數(shù)組元素之間是線性結(jié)構(gòu)。
34.順序表用一維數(shù)組作為存儲結(jié)構(gòu)，因此順序表是一維數(shù)組。
35.若一棵二叉樹的任一非葉子結(jié)點的度為2，則該二叉樹為滿二叉樹。
36.鏈式棧與順序棧相比, 一個明顯的優(yōu)點是通常不會出現(xiàn)棧滿的情況。
37.已知指針P指向鏈表L中的某結(jié)點，執(zhí)行語句P：=P?NEXT不會刪除該鏈表中的結(jié)點。
38.一個廣義表的表頭總是一個廣義表。
39.快速排序算法在每一趟排序中都能找到一個元素放在其最終的位置上。
40.為度量一個搜索算法的效率，需要在時間和空間兩個方面進行分析。
41.對任何用頂點表示活動的網(wǎng)絡(luò)（ ）進行拓撲排序的結(jié)果都是唯一的。
42.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的。
43.存儲無向圖的鄰接矩陣是對稱的，因此可以只存儲鄰接矩陣的下（ ）三角部分。
44.在順序表中，邏輯上相鄰的元素在物理位置上不一定相鄰。
奧鵬，國開，廣開，電大在線，各省平臺，新疆一體化等平臺學(xué)習(xí)
詳情請咨詢QQ : 3230981406或微信:aopopenfd777
