《數(shù)據(jù)結(jié)構(gòu)2264》22春在線作業(yè)2-00001
試卷總分:100 得分:100
一、單選題 (共 25 道試題,共 50 分)
1.二維數(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
2.在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系的運(yùn)算是（ ）。
A.插入
B.刪除
C.排序
D.查找
3.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放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
4.樹最適合用來表示（ ）。
A.有序數(shù)據(jù)元素
B.無序數(shù)據(jù)元素
C.元素之間具有分支層次關(guān)系的數(shù)據(jù)
D.元素之間無聯(lián)系的數(shù)據(jù)
5.有n個記錄的文件，如關(guān)鍵字位數(shù)為d，基數(shù)為r，則基數(shù)排序共要進(jìn)行（ ）遍分配與收集。
A.n
B.d
C.r
D.n - d
6.若有序表為（ ），則在二分查找關(guān)鍵字b的過程中，先后進(jìn)行比較的關(guān)鍵字依次為（ ）。
A.f,c,b
B.f,d,b
C.g,c,b
D.g,d,b
7.隊列的特點是（ ）。
A.先進(jìn)后出
B.先進(jìn)先出
C.任意位置進(jìn)出
D.前面都不正確
8.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是（ ）。
A.數(shù)組是不同類型值的集合
B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉
C.樹是一種線性結(jié)構(gòu)
D.用一維數(shù)組存儲一棵完全二叉樹是有效的存儲方法
9.從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為（ ）。
A.O(n)
B.O(1)
C.O(log2n)
D.O(n2)
10.對于線性表（ ）進(jìn)行散列存儲時，若選用H（ ）=K % 9作為散列函數(shù)，則散列地址為1的元素有（ ）個。
A.1
B.2
C.3
D.4
11.若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則最節(jié)省運(yùn)算時間的存儲方式是（ ）。
A.單鏈表
B.僅有頭指針的單循環(huán)鏈表
C.雙鏈表
D.僅有尾指針的單循環(huán)鏈表
12.k層（ ）二叉樹的結(jié)點總數(shù)最多為（ ）。
A.2k-1
B.2K+1
C.2K-1
D.2k-1
13.對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（ ）
A.經(jīng)常需要隨機(jī)地存取元素
B.經(jīng)常需要進(jìn)行插入和刪除操作
C.表中元素需要占據(jù)一片連續(xù)的存儲空間
D.表中元素的個數(shù)不變
14.對一棵有100個結(jié)點的完全二叉樹按層編號，根結(jié)點編號為1，則編號為49的結(jié)點的父結(jié)點的編號為（ ）。
A.24
B.5
C.98
D.99
15.設(shè)Huffman樹的葉子結(jié)點數(shù)為m，則結(jié)點總數(shù)為（ ）。
A.2m
B.2m-1
C.2m+1
D.m+1
16.數(shù)據(jù)的基本單位是（ ）。
A.數(shù)據(jù)項
B.數(shù)據(jù)類型
C.數(shù)據(jù)元素
D.數(shù)據(jù)變量
17.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有（ ）條邊才能確保是一個連通圖。
A.5
B.6
C.7
D.8
18.中綴表達(dá)式2+X*（ ）的后綴形式是（ ）。
A.3 Y X 2 + * +
B.Y 3 + X * 2 +
C.2 X Y 3 * + +
D.2 X Y 3 + * +
19.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？（ ）
A.隊列
B.棧
C.線性表
D.二叉樹
20.在對n個關(guān)鍵字進(jìn)行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關(guān)鍵字元素，則在進(jìn)行第i趟排序之前，無序區(qū)中元素的個數(shù)為（ ）。
A.i
B.i+1
C.n-i
D.n-i+1
21.對關(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)
22.一散列表長度m為100，采用除留余數(shù)法構(gòu)造散列函數(shù)，即H（ ）=K%P （ ）,，為使散列函數(shù)具有較好的性能，P的選擇應(yīng)是（ ）。
A.99
B.100
C.97
D.93
23.若某二叉樹結(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
24.帶有頭結(jié)點的單循環(huán)鏈表的頭指針為head，則該鏈表為空的判定條件是（ ）。
A.head= =NUL
B.head->next= =NULL
C.head!=NULL
D.head->next= =head
25.在一個單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點后面插入一個由q指向的結(jié)點，則執(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;
二、多選題 (共 4 道試題,共 20 分)
26.若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出棧可以穿插進(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
27.下述（ ）是順序存儲方式的優(yōu)點。
A.存儲密度大
B.插入和刪除運(yùn)算方便
C.獲取符合某種條件的元素方便
D.查找運(yùn)算速度快
E.可以很方便地存取第i個元素
28.以下哪些是隊列的基本運(yùn)算？（ ）
A.在隊列第i個元素之后插入一個元素
B.從隊頭刪除一個元素
C.判斷一個隊列是否為空
D.讀取隊頭元素的值
E.將隊列中的元素排序
29.對一個算法的評價，主要包括如下（ ）方面的內(nèi)容。
A.健壯性和可讀性
B.并行性
C.正確性
D.時空復(fù)雜度
E.界面友好性
三、判斷題 (共 15 道試題,共 30 分)
30.快速排序算法在每一趟排序中都能找到一個元素放在其最終的位置上。
31.用字符數(shù)組存儲長度為n的字符串，數(shù)組長度至少為n+1。
32.鄰接矩陣適用于稠密圖（ ），鄰接表適用于稀疏圖（ ）。
33.鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。
34.為度量一個搜索算法的效率，需要在時間和空間兩個方面進(jìn)行分析。
35.線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r，其存儲結(jié)點的地址可連續(xù)也可不連續(xù)。
36.一個廣義表（ ）,（ ）,c),（ ）))) 的表尾是（ ）,c),（ ）))。
37.鏈?zhǔn)綏Ｅc順序棧相比, 一個明顯的優(yōu)點是通常不會出現(xiàn)棧滿的情況。
38.在用循環(huán)單鏈表表示的鏈?zhǔn)疥犃兄?，可以不設(shè)隊頭指針，僅在鏈尾設(shè)置隊尾指針。
39.線性表的長度是線性表所占用的存儲空間的大小。
40.二維數(shù)組是數(shù)組元素為一維數(shù)組的線性表，因此二維數(shù)組元素之間是線性結(jié)構(gòu)。
41.存儲無向圖的鄰接矩陣是對稱的，因此可以只存儲鄰接矩陣的下（ ）三角部分。
42.在采用線性探測法處理沖突的哈希表中，所有同義詞在表中相鄰。
43.在順序表中，邏輯上相鄰的元素在物理位置上不一定相鄰。
44.棧和隊列都是順序存取的線性表，但它們對存取位置的限制不同。
