《數(shù)據(jù)結(jié)構(gòu)2264》23春在線作業(yè)2題目
試卷總分:100 得分:100
一、單選題 (共 25 道試題,共 50 分)
1.由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為（ ）。
A.11
B.35
C.19
D.53
2.一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是（ ）。
A.2 3 1
B.3 2 1
C.3 1 2
D.1 2 3
3.帶有頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針為head，則該鏈表為空的判定條件是（ ）。
A.head= =NUL
B.head->next= =NULL
C.head!=NULL
D.head->next= =head
4.一散列表長(zhǎng)度m為100，采用除留余數(shù)法構(gòu)造散列函數(shù)，即H（ ）=K%P （ ）,，為使散列函數(shù)具有較好的性能，P的選擇應(yīng)是（ ）。
A.99
B.100
C.97
D.93
5.設(shè)森林F對(duì)應(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
6.在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系的運(yùn)算是（ ）。
A.插入
B.刪除
C.排序
D.查找
7.對(duì)于線性表（ ）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（ ）=K % 9作為散列函數(shù)，則散列地址為1的元素有（ ）個(gè)。
A.1
B.2
C.3
D.4
8.k層（ ）二叉樹的結(jié)點(diǎn)總數(shù)最多為（ ）。
A.2k-1
B.2K+1
C.2K-1
D.2k-1
9.樹最適合用來(lái)表示（ ）。
A.有序數(shù)據(jù)元素
B.無(wú)序數(shù)據(jù)元素
C.元素之間具有分支層次關(guān)系的數(shù)據(jù)
D.元素之間無(wú)聯(lián)系的數(shù)據(jù)
10.采用開放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度（ ）。
A.低于鏈接法處理沖突
B.高于鏈接法處理沖突
C.與鏈接法處理沖突相同
D.高于二分查找
11.中綴表達(dá)式2+X*（ ）的后綴形式是（ ）。
A.3 Y X 2 + * +
B.Y 3 + X * 2 +
C.2 X Y 3 * + +
D.2 X Y 3 + * +
12.如表r有100000個(gè)元素，前99999個(gè)元素遞增有序，則采用（ ）方法比較次數(shù)較少。
A.直接插入排序
B.快速排序
C.歸并排序
D.選擇排序
13.對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為（ ）。
A.O（1og2n
B.O（n）
C.O（1）
D.O（n2）
14.含有10個(gè)結(jié)點(diǎn)的二叉樹中，度為0的結(jié)點(diǎn)數(shù)為4，則度為2的點(diǎn)數(shù)為（ ）。
A.3
B.4
C.5
D.6
15.對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（ ）方面的內(nèi)容。
A.健壯性和可讀性
B.并行性
C.正確性
D.時(shí)空復(fù)雜度
16.下面關(guān)于廣義表的敘述中，不正確的是（ ）。
A.廣義表可以是一個(gè)多層次的結(jié)構(gòu)
B.廣義表至少有一個(gè)元素
C.廣義表可以被其他廣義表所共享
D.廣義表可以是一個(gè)遞歸表
17.對(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)
18.對(duì)一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(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
19.若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則最節(jié)省運(yùn)算時(shí)間的存儲(chǔ)方式是（ ）。
A.單鏈表
B.僅有頭指針的單循環(huán)鏈表
C.雙鏈表
D.僅有尾指針的單循環(huán)鏈表
20.設(shè)Huffman樹的葉子結(jié)點(diǎn)數(shù)為m，則結(jié)點(diǎn)總數(shù)為（ ）。
A.2m
B.2m-1
C.2m+1
D.m+1
21.若有序表為（ ），則在二分查找關(guān)鍵字b的過(guò)程中，先后進(jìn)行比較的關(guān)鍵字依次為（ ）。
A.f,c,b
B.f,d,b
C.g,c,b
D.g,d,b
22.隊(duì)列的特點(diǎn)是（ ）。
A.先進(jìn)后出
B.先進(jìn)先出
C.任意位置進(jìn)出
D.前面都不正確
23.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是（ ）。
A.數(shù)組是不同類型值的集合
B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉
C.樹是一種線性結(jié)構(gòu)
D.用一維數(shù)組存儲(chǔ)一棵完全二叉樹是有效的存儲(chǔ)方法
24.在對(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
25.在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn)，則執(zhí)行如下（ ）語(yǔ)句序列。
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;
二、多選題 (共 4 道試題,共 20 分)
26.對(duì)一個(gè)算法的評(píng)價(jià)，主要包括如下（ ）方面的內(nèi)容。
A.健壯性和可讀性
B.并行性
C.正確性
D.時(shí)空復(fù)雜度
E.界面友好性
27.以下哪些是隊(duì)列的基本運(yùn)算？（ ）
A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素
B.從隊(duì)頭刪除一個(gè)元素
C.判斷一個(gè)隊(duì)列是否為空
D.讀取隊(duì)頭元素的值
E.將隊(duì)列中的元素排序
28.下述（ ）是順序存儲(chǔ)方式的優(yōu)點(diǎn)。
A.存儲(chǔ)密度大
B.插入和刪除運(yùn)算方便
C.獲取符合某種條件的元素方便
D.查找運(yùn)算速度快
E.可以很方便地存取第i個(gè)元素
29.以下序列中，是堆（ ）的有（ ）。
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}
三、判斷題 (共 15 道試題,共 30 分)
30.用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中的頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。
31.快速排序算法在每一趟排序中都能找到一個(gè)元素放在其最終的位置上。
32.棧和隊(duì)列都是順序存取的線性表，但它們對(duì)存取位置的限制不同。
33.鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用。
34.用字符數(shù)組存儲(chǔ)長(zhǎng)度為n的字符串，數(shù)組長(zhǎng)度至少為n+1。
35.一個(gè)廣義表（ ）,（ ）,c),（ ）))) 的表尾是（ ）,c),（ ）))。
36.線性表若采用鏈?zhǔn)酱鎯?chǔ)表示, 在刪除時(shí)不需要移動(dòng)元素。
37.線性表的長(zhǎng)度是線性表所占用的存儲(chǔ)空間的大小。
38.在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針。
39.若一棵二叉樹的任一非葉子結(jié)點(diǎn)的度為2，則該二叉樹為滿二叉樹。
40.在一棵二叉樹中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒(méi)有右子女，對(duì)它分別進(jìn)行前序遍歷和后序遍歷，則具有相同的結(jié)果。
41.圖G的某一最小生成樹的代價(jià)一定小于其他生成樹的代價(jià)。
42.存儲(chǔ)無(wú)向圖的鄰接矩陣是對(duì)稱的，因此可以只存儲(chǔ)鄰接矩陣的下（ ）三角部分。
43.若僅知道某二叉樹的中序遍歷序列和后序遍歷序列，則不能夠確定此二叉樹的層次遍歷的序列。
44.對(duì)任何用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)（ ）進(jìn)行拓?fù)渑判虻慕Y(jié)果都是唯一的。
奧鵬，國(guó)開，廣開，電大在線，各省平臺(tái)，新疆一體化等平臺(tái)學(xué)習(xí)
詳情請(qǐng)咨詢QQ : 3230981406或微信:aopopenfd777
