北交《數(shù)據(jù)結(jié)構(gòu)（專(zhuān)）》在線(xiàn)作業(yè)一-0005

試卷總分：100得分：100

一、單選題（共38道試題，共95分）

1.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要

移動(dòng)（）個(gè)元素。

A.8

B.63.5

C.64

D.7

答案:B

2.設(shè)有1000個(gè)元素，用折半查找時(shí)，最大比較次數(shù)是（）。

A.1

B.7

C.10

D.25

答案:C

3.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）。

A.n

B.（n-1）（n-1）

C.n-l

D.n*n

答案:D

4.鏈表不具有的特點(diǎn)是（）。

A.不必事先估計(jì)存儲(chǔ)空間

B.可隨機(jī)訪(fǎng)問(wèn)任一元素

C.插入刪除不需要移動(dòng)元素

D.所需空間與線(xiàn)性表長(zhǎng)度成正比

答案:B

5.具有2000個(gè)節(jié)點(diǎn)的二叉樹(shù)，其高度至少為（）。

A.9

B.10

C.11

D.12

答案:C

6.具有65個(gè)結(jié)點(diǎn)的完全二叉樹(shù)其深度為（）。

A.8

B.7

C.6

D.5

答案:B

7.設(shè)在棧中，由頂向下已存放元素c、b、a,在第4個(gè)元素d入棧之前，棧中元素

可以出棧，試問(wèn)d入棧前后，不可能的出棧序列是（）。

A.dcba

B.cbda

C.cadb

D.cdba

答案:c

8.廣義表（（a）,a）的表頭是（）。

A.a

B.b

C.（a）

D.（（a））

答案:C

9.若待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，則采用（）方法比較

次數(shù)最少。

A.直接插入排序

B.快速排序

C.歸并排序

D.直接選擇排序

答案:A

10.隊(duì)列操作的原則是（

A.先進(jìn)先出

B.后進(jìn)先出

C.只能進(jìn)行插入

D.只能進(jìn)行刪除

答案:A

11.在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（）。

A.e

B.2e

C.n*n—e

D.n*n—2e

答案:D

12.隊(duì)列的刪除操作是在（）進(jìn)行。

A.隊(duì)首

B.隊(duì)尾

C.隊(duì)前

D.隊(duì)后

答案:A

13.在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中，其結(jié)點(diǎn)總數(shù)為（）。

A.不確定

B.2n

C.2n+l

D.2n-l

答案：D

14.設(shè)一數(shù)列的順序?yàn)?,2,3,4,5,6,通過(guò)棧結(jié)構(gòu)不可能排成的順序數(shù)列為（）。

A.3,2,5,6,4,1

B.1,5,4,6,2,3

C.2,4,3,5,1,6

D.4,5,3,6,2,1

答案:B

15.n個(gè)頂點(diǎn)的連通圖至少有（）條邊。

A.n-l

B.n

C.n+1

D.0

答案:A

16.采用順序查找方法查找長(zhǎng)度為n的線(xiàn)性表時(shí)，每個(gè)元素的平均長(zhǎng)度為（）。

A.n

B.n/2

C.（n+l）/2

D.（n-l）/2

答案:C

17.在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線(xiàn)性表中，向第i個(gè)元素（lWiWn+1）之前插

入一個(gè)新元素時(shí)，需要從前向后依次后移（）個(gè)元素。

A.n-i

B.n-i+1

C.n-i-1

D.i

答案:B

18.設(shè)有50行60列的二維數(shù)組A[50][60],其元素長(zhǎng)度為4字節(jié),按行優(yōu)先順序

存儲(chǔ)，基地址為200,則元素A[18][25]的存儲(chǔ)地址為（）。

A.3700

B.4376

C.3900

D.4620

答案:D

19.若從二叉樹(shù)的任一節(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過(guò)的節(jié)點(diǎn)序列按其關(guān)鍵字有序,

則該二叉樹(shù)是（

A.二叉排序樹(shù)

B.哈夫曼樹(shù)

C.堆

D.AVL樹(shù)

答案:C

20.算法分析的目的是（）。

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性

B.研究算法中的輸入和輸出的關(guān)系

C.分析算法的效率以求改進(jìn)

D.分析算法的易讀性和文檔性

答案:C

21.由兩個(gè)棧共享一個(gè)向量空間的好處是（）。

A.減少存取時(shí)間，降低下溢發(fā)生的機(jī)率

B.節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率

C.減少存取時(shí)間，降低上溢發(fā)生的機(jī)率

D.節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率

答案:B

22.帶頭節(jié)點(diǎn)的單鏈表head為空的判定條件（）。

A.head=NULL

B.head->next=NULL

C.head->next=head

D.head!=head

答案:B

23.深度為5的二叉樹(shù)至多有（）個(gè)節(jié)點(diǎn)。

A.16

B.32

C.31

D.10

答案:C

24.串的長(zhǎng)度是（）o

A.串中不同字符的個(gè)數(shù)

B.串中不同字母的個(gè)數(shù)

C.串中所含字符的個(gè)數(shù)且字符個(gè)數(shù)大于0

D.串中所含字符的個(gè)數(shù)

答案:D

25.向二叉排序樹(shù)中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為()。

A.O(log以2為底的n)

B.O(n)

C.O(l)

D.0(n*log2n)

答案:A

26.算法的時(shí)間復(fù)雜度是指()。

A.執(zhí)行算法程序所需要的時(shí)間

B.算法程序的長(zhǎng)度

C.算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)

D.算法程序中的指令條數(shù)

答案:C

27.由權(quán)值分別為3,6,7,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為

()。

A.23

B.51

C.53

D.74

答案:B

28.每次從無(wú)序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方

法叫做()排序.

A.插入

B.交換

C.選擇

D.歸并

答案:A

29.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為()的線(xiàn)性表。

A.散列表

B.順序存儲(chǔ)或鏈接存儲(chǔ)

C.壓縮存儲(chǔ)

D.索引存儲(chǔ)

答案:B

30.如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒,

則稱(chēng)該排序是不穩(wěn)定的。下列選項(xiàng)中，()就是不穩(wěn)定的排序方法。

A.起泡排序

B.歸并排序

C.直接插入法排序

D.簡(jiǎn)單選擇排序

答案:D

31.若某線(xiàn)性表中最常用的操作是取第I個(gè)元素和找第I個(gè)元素的前趨元素，則采

用（）存儲(chǔ)方式最節(jié)省時(shí)間。

A.順序表

B.單鏈表

C.雙鏈表

D.單循環(huán)鏈表

答案:A

32.若由森林轉(zhuǎn)化得到的二叉樹(shù)是非空的二叉樹(shù)，則二叉樹(shù)形狀是（）。

A.根結(jié)點(diǎn)無(wú)右子樹(shù)的二叉樹(shù)

B.根結(jié)點(diǎn)無(wú)左子樹(shù)的二叉樹(shù)

C.根結(jié)點(diǎn)可能有左二叉樹(shù)和右二叉樹(shù)

D.各結(jié)點(diǎn)只有一個(gè)兒子的二叉樹(shù)

答案:C

33.非空的循環(huán)單鏈表head的尾節(jié)點(diǎn)（由p所指向）滿(mǎn)足（）。

A.p->next=NULL

B.p=NULL

C.p->next=head

D.p=head

答案:C

34.如果一個(gè)樹(shù)中，結(jié)點(diǎn)A有3個(gè)兄弟，而且B為A的雙親，則B的度為（）。

A.1

B.3

C.4

D.5

答案:C

35.設(shè)單鏈表中指針p指著結(jié)點(diǎn)A,若要?jiǎng)h除A之后的結(jié)點(diǎn)（若存在），則需要修改

指針操作為（）。

A.p->next=p->next->next

B.p=p->next

C.p=p->next->next

D.p->next=p

答案:A

36.在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)行單鏈表中的結(jié)點(diǎn)都具有相同

的（）。

A.行號(hào)

B.列號(hào)

C.元素值

D.地址

答案:A

37.以下數(shù)據(jù)結(jié)構(gòu)中不屬于線(xiàn)性數(shù)據(jù)結(jié)構(gòu)的是()。

A.線(xiàn)性表

B.隊(duì)列

C.二叉樹(shù)

D.棧

答案:C

38.設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊，采用領(lǐng)接表作為其存儲(chǔ)表示，在進(jìn)行拓?fù)渑判?/p>

時(shí)，