《數(shù)據(jù)結(jié)構(gòu)2264》21秋在線作業(yè)2-00001
試卷總分:100 得分:100
一、單選題 (共 25 道試題,共 50 分)
1.設(shè)森林F對應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p，p的右子樹上的結(jié)點(diǎn)個(gè)數(shù)為n，森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（ ）。
A.m-n-1
B.n+1
C.m-n+1
D.m-n
2.對一個(gè)算法的評價(jià)，不包括如下（ ）方面的內(nèi)容。
A.健壯性和可讀性
B.并行性
C.正確性
D.時(shí)空復(fù)雜度
3.設(shè)Huffman樹的葉子結(jié)點(diǎn)數(shù)為m，則結(jié)點(diǎn)總數(shù)為（ ）。
A.2m
B.2m-1
C.2m+1
D.m+1
4.一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是（ ）。
A.2 3 1
B.3 2 1
C.3 1 2
D.1 2 3
5.有n個(gè)記錄的文件，如關(guān)鍵字位數(shù)為d，基數(shù)為r，則基數(shù)排序共要進(jìn)行（ ）遍分配與收集。
A.n
B.d
C.r
D.n - d
6.對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（ ）
A.經(jīng)常需要隨機(jī)地存取元素
B.經(jīng)常需要進(jìn)行插入和刪除操作
C.表中元素需要占據(jù)一片連續(xù)的存儲空間
D.表中元素的個(gè)數(shù)不變
7.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是（ ）。
A.數(shù)組是不同類型值的集合
B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉
C.樹是一種線性結(jié)構(gòu)
D.用一維數(shù)組存儲一棵完全二叉樹是有效的存儲方法
8.若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則最節(jié)省運(yùn)算時(shí)間的存儲方式是（ ）。
A.單鏈表
B.僅有頭指針的單循環(huán)鏈表
C.雙鏈表
D.僅有尾指針的單循環(huán)鏈表
9.在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素可由（ ）。
A.實(shí)體
B.域
C.數(shù)據(jù)項(xiàng)
D.字段
10.假定有K個(gè)關(guān)鍵字互為同義詞，若用線性探測法把這K個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行（ ）次探測。
A.K-1次
B.K次
C.K＋l次
D.K(K+1)/2次
11.在一個(gè)帶有附加表頭結(jié)點(diǎn)的單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（ ）。
A.HL=p; p->next=HL;
B.p->next=HL->next; HL->next=p;
C.p->next=HL; p=HL;
D.p->next=HL; HL=p;
12.下面關(guān)于廣義表的敘述中，不正確的是（ ）。
A.廣義表可以是一個(gè)多層次的結(jié)構(gòu)
B.廣義表至少有一個(gè)元素
C.廣義表可以被其他廣義表所共享
D.廣義表可以是一個(gè)遞歸表
13.樹最適合用來表示（ ）。
A.有序數(shù)據(jù)元素
B.無序數(shù)據(jù)元素
C.元素之間具有分支層次關(guān)系的數(shù)據(jù)
D.元素之間無聯(lián)系的數(shù)據(jù)
14.帶有頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針為head，則該鏈表為空的判定條件是（ ）。
A.head= =NUL
B.head->next= =NULL
C.head!=NULL
D.head->next= =head
15.從L=（ ）,（ ）)中，取出banana元素的表達(dá)式為（ ）。
A.head(tail(L))
B.head(head(tail(L)))
C.tail(head(tail(L)))
D.head(tail(head(tail(L))))
16.在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn)，則執(zhí)行如下（ ）語句序列。
A.p=q; p->next=q;
B.p->next=q; q->next=p;
C.p->next=q->next; p=q;
D.q->next=p->next; p->next=q;
17.對于線性表（ ）進(jìn)行散列存儲時(shí)，若選用H（ ）=K % 9作為散列函數(shù)，則散列地址為1的元素有（ ）個(gè)。
A.1
B.2
C.3
D.4
18.對廣義表L=（ ）,（ ）,（ ）執(zhí)行操作tail（ ）的結(jié)果是（ ）。
A.(e,f)
B.((e,f))
C.(f)
D.( )
19.下面關(guān)于圖的存儲的敘述中正確的是（ ）。
A.用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)。
B.用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān)
C.用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān)。
D.用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)。
20.已知一個(gè)圖的頂點(diǎn)集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
21.AOV網(wǎng)是一種（ ）。
A.有向圖
B.無向圖
C.無向無環(huán)圖
D.有向無環(huán)圖
22.在二叉樹結(jié)點(diǎn)的先序序列、中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（ ）
A.都不相同
B.完全相同
C.先序和中序相同，而與后序不同
D.中序和后序相同，而與先序不同
23.一散列表長度m為100，采用除留余數(shù)法構(gòu)造散列函數(shù)，即H（ ）=K%P （ ）,，為使散列函數(shù)具有較好的性能，P的選擇應(yīng)是（ ）。
A.99
B.100
C.97
D.93
24.對關(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)
25.從一個(gè)長度為n的順序表中刪除第i個(gè)元素（ ）時(shí)，需向前移動(dòng)的元素個(gè)數(shù)是（ ）。
A.n-i
B.n-i+1
C.n-i-1
D.i
二、多選題 (共 4 道試題,共 20 分)
26.下述（ ）是順序存儲方式的優(yōu)點(diǎn)。
A.存儲密度大
B.插入和刪除運(yùn)算方便
C.獲取符合某種條件的元素方便
D.查找運(yùn)算速度快
E.可以很方便地存取第i個(gè)元素
27.以下哪些是隊(duì)列的基本運(yùn)算？（ ）
A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素
B.從隊(duì)頭刪除一個(gè)元素
C.判斷一個(gè)隊(duì)列是否為空
D.讀取隊(duì)頭元素的值
E.將隊(duì)列中的元素排序
28.對一個(gè)算法的評價(jià)，主要包括如下（ ）方面的內(nèi)容。
A.健壯性和可讀性
B.并行性
C.正確性
D.時(shí)空復(fù)雜度
E.界面友好性
29.棧和隊(duì)列的共同特點(diǎn)是（ ）。
A.只允許在端點(diǎn)處插入和刪除元素
B.都是先進(jìn)后出
C.都是先進(jìn)先出
D.沒有共同點(diǎn)
E.都可以采用順序存儲方式和鏈?zhǔn)酱鎯Ψ绞?/p>
三、判斷題 (共 15 道試題,共 30 分)
30.有回路的有向圖不能完成拓?fù)渑判颉?/p>
31.一個(gè)廣義表（ ）,（ ）,c),（ ）))) 的表尾是（ ）,c),（ ）))。
32.線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r(shí)，其存儲結(jié)點(diǎn)的地址可連續(xù)也可不連續(xù)。
33.快速排序算法在每一趟排序中都能找到一個(gè)元素放在其最終的位置上。
34.存儲無向圖的鄰接矩陣是對稱的，因此可以只存儲鄰接矩陣的下（ ）三角部分。
35.線性表若采用鏈?zhǔn)酱鎯Ρ硎? 在刪除時(shí)不需要移動(dòng)元素。
36.二維數(shù)組是數(shù)組元素為一維數(shù)組的線性表，因此二維數(shù)組元素之間是線性結(jié)構(gòu)。
37.線性表的長度是線性表所占用的存儲空間的大小。
38.在采用線性探測法處理沖突的哈希表中，所有同義詞在表中相鄰。
39.用鄰接矩陣存儲一個(gè)圖時(shí)，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中的頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。
40.一個(gè)廣義表的表頭總是一個(gè)廣義表。
41.使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲空間。
42.在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針。
43.為度量一個(gè)搜索算法的效率，需要在時(shí)間和空間兩個(gè)方面進(jìn)行分析。
44.鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。
