西安交通大學(xué)《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)答卷

西交《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)

試卷總分：100得分：100

一、單選題（共30道試題，共60分）

1.若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[l]中，現(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

答案:D

2.利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為（）。

A.O（n）

B.0（nlog2n）

C.O（n）

D.O（log2n）

答案:C

3.若一棵二叉樹(shù)有10個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)的葉子結(jié)點(diǎn)的個(gè)數(shù)為（）。

A.9

B.11

C.12

D.不能確定

答案:B

4.已知二維數(shù)組A[4,6]采用行優(yōu)先存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用3個(gè)存儲(chǔ)單元，并

且A[L1]的存儲(chǔ)地址為1200,元素A[[2,4]的存儲(chǔ)地址是（）。

A.1221

B.1227

C.1239

D.1257

答案:B

5.設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動(dòng)（）個(gè)元素。

A.n-i

B.n+1-i

C.n-1-i

D.i

答案:A

6.設(shè)某棵三叉樹(shù)中有40個(gè)結(jié)點(diǎn)，則該三叉樹(shù)的最小高度為（）。

A.3

B.4

C.5

D.6

答案:B

7.對(duì)5個(gè)不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行()次比較。

A.8

B.10

C.15

D.25

答案:B

8.｛圖｝

A.A

B.B

C.C

D.D

答案:A

9.下列說(shuō)法中，正確的是()。

A.度為2的樹(shù)是二叉樹(shù)

B.度為2的有序樹(shù)是二叉樹(shù)

C.子樹(shù)有嚴(yán)格的左、右之分的樹(shù)是二叉樹(shù)

D.子樹(shù)有嚴(yán)格的左、右之分，且度不超過(guò)2的樹(shù)是二叉樹(shù)

答案:D

10.設(shè)一個(gè)順序有序表A[l:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過(guò)

程中比較元素的順序?yàn)?)

A.A[1LA⑵,A[3],A[4]

B.A[1LA[14],A[7],A[4]

C.A[7],A[3],A[5],A[4]

D.A[7LA[5],A[3],A[4]

答案:C

11.設(shè)一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結(jié)點(diǎn)，則其判空條件是()。

A.head==0

B.head->next==0

C.head->next==head

D.head!=0

答案:A

12.設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD,前序遍歷序列為CABI),則后序遍歷該

二叉樹(shù)得到序列為()

A.BADC

B.BCDA

C.CDAB

D.CBDA

答案:A

13.程序段s=i=O；do{i=i+l；s=s+i；}while(i<=n)；的時(shí)間復(fù)雜度為()。

A.0(n)

B.0(nlog2n)

C.O(n)

D.O(n/2)

答案:A

14.設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則該無(wú)向圖中所有頂點(diǎn)的入度之和為()。

A.n

B.e

C.2n

D.2e

答案:D

15.設(shè)一組權(quán)值集合歸{2,3,4,5,6},則由該權(quán)值集合構(gòu)造的哈夫曼樹(shù)中帶權(quán)

路徑長(zhǎng)度之和為()

A.20

B.30

C.40

D.45

答案:D

16.用二分(對(duì)半)查找表的元素的速度比用順序法()

A.必然快

B.必然慢

C.相等

D.不能確定

答案:D

17.如下陳述中正確的是()

A.串是一種特殊的線性表

B.串的長(zhǎng)度必須大于零

C.串中元素只能是字母

D.空串就是空白串

答案:A

18.棧的插入和刪除操作在()進(jìn)行。

A.棧頂

B.棧底

C.任意位置

D.指定位置

答案:A

19.如果要求頻繁的對(duì)線性表進(jìn)行插入和刪除操作，則線性表應(yīng)該采用()存儲(chǔ)

結(jié)構(gòu)。

A.散列

B.順序

C.鏈?zhǔn)?/p>

D.任意

答案:C

20.用鏈表表示線性表的優(yōu)點(diǎn)是()

A.便于隨機(jī)存取

B.花費(fèi)的存儲(chǔ)空間比順序表少

C.便于插入與刪除

D.數(shù)據(jù)元素的物理順序與邏輯順序相同

答案:C

21.設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有()條邊。

A.n(n-l)/2

B.n(n-l)

C.n(n+l)/2

D.(n-l)/2

答案:A

22.設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列()存

儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

A.單向鏈表

B.單向循環(huán)鏈表

C.雙向鏈表

D.雙向循環(huán)鏈表

答案:D

23.判斷一個(gè)圖中是否存在回路可以利用()方法。

A.求最小生成樹(shù)

B.求最短路徑

C.拓?fù)渑判?/p>

D.圖的遍歷

答案:C

24.｛圖｝

A.A

B.B

C.C

D.D

答案:B

25.棧和隊(duì)列的共同特點(diǎn)是()。

A.只允許在端點(diǎn)處插入和刪除元素

B.都是先進(jìn)后出

C.都是先進(jìn)先出

D.沒(méi)有共同點(diǎn)

答案:A

26.設(shè)有一組初始記錄關(guān)鍵字序列為(34,76,45,18,26,54,92),則由這組記

錄關(guān)鍵字生成的二叉排序樹(shù)的深度為()?

A.4

B.5

C.6

D.7

答案:A

27.設(shè)有一個(gè)二維數(shù)組假設(shè)A[0][個(gè)存放位置在644(10),A[2][2]存放

位置在676(10),每個(gè)元素占一個(gè)空間，問(wèn)A[3][3](10)存放在什么位置()?腳

注(10)表示用10進(jìn)制表示。

A.688

B.678

C.692

D.696

答案:C

28.對(duì)一棵二叉排序樹(shù)進(jìn)行()遍歷,可以得到該二叉樹(shù)的多有結(jié)點(diǎn)按值從小到大

排列的序列。

A.前序

B.中序

C.后序

D.按層次

答案:B

29.設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為m,若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼

樹(shù)中總共有()個(gè)空指針域。

A.2m-1

B.2m

C.2m+l

D.4m

答案:B

30.程序段如下:s=i=0；do{i=i+l；s=s+i；}while(i<=n)；其時(shí)間復(fù)雜度為

()。

A.O(n)

B.0(nlog2n)

C.0(n2)

D.0(n3/2)

答案:A

二、判斷題(共20道試題，共40分)

31.有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。

答案:錯(cuò)誤

32.哈夫曼樹(shù)中沒(méi)有度數(shù)為2的結(jié)點(diǎn)。

答案:錯(cuò)誤

33.設(shè)一棵樹(shù)T可以轉(zhuǎn)化成二叉樹(shù)BT,則二叉樹(shù)BT中一定沒(méi)有右子樹(shù)。

答案:正確

34.稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來(lái)表示稀疏矩陣中的非0元素。

答案:正確

35.中序遍歷二叉排序樹(shù)可以得到一個(gè)有序的序列。

答案:正確

36.分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。

答案:正確

37.｛圖｝

答案:正確

38.二維數(shù)組是數(shù)組元素為一維數(shù)組的線性表，因此它是線性結(jié)構(gòu)。

答案:錯(cuò)誤

39.先序遍歷一棵二叉排序樹(shù)得到的結(jié)點(diǎn)序列不一定是有序的序列。

答案:正確

40.｛圖｝

答案:錯(cuò)誤

41.子串“ABC”在主串“AABCABCD”中的位置為3。

答案:錯(cuò)誤

42.在拓?fù)渑判蛐蛄兄?，任意兩個(gè)相繼結(jié)點(diǎn)Vi和Vj都存在從Vi到VJ的路徑。()

答案:錯(cuò)誤

43.堆排序所需的時(shí)間與待排序的記錄個(gè)數(shù)無(wú)關(guān)。()

答案:錯(cuò)誤

44.一棵m階B樹(shù)中每個(gè)結(jié)點(diǎn)最多有m個(gè)關(guān)鍵碼，最少有2個(gè)關(guān)鍵碼。

答案:錯(cuò)誤

45.在鏈隊(duì)列上做出隊(duì)操作時(shí)，會(huì)改變front指針的值。()

答案:錯(cuò)誤

46.具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為L(zhǎng)log2nJ+1。

答案:錯(cuò)誤

47.在拓?fù)渑判蛐蛄兄校我鈨蓚€(gè)相繼結(jié)點(diǎn)V