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