西昌學(xué)院數(shù)據(jù)結(jié)構(gòu)導(dǎo)論期末考試復(fù)習(xí)題及參考答案

西昌學(xué)院成人在線學(xué)習(xí)平臺(tái)

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論在線考試

課程名稱：數(shù)據(jù)結(jié)構(gòu)導(dǎo)論（專升本）

1.（單選題）2線性表是具有n個(gè)（）的有限序列。（本題2.0分）

A.表元素

B.字符

C.數(shù)據(jù)元素

D.信息項(xiàng)

答案：C.

解析：無(wú).

2.（單選題）算法指的是（）。（本題2.0分）

A.計(jì)算機(jī)程序

B.解決問(wèn)題的計(jì)算方法

C.排序算法

D.解決問(wèn)題的有限運(yùn)算序列

答案:D.

解析：無(wú).

3.（單選題）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成【】。（本題

2.0分）

A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)

D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

答案：C.

解析：無(wú).

4.（單選題）數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指【】。（本題2.0分）

A.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

B.數(shù)據(jù)結(jié)構(gòu)

C.數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)

D.數(shù)據(jù)元素之間的關(guān)系

答案:A.

解析：無(wú).

5.（單選題）在存儲(chǔ)數(shù)據(jù)時(shí)，不僅要考慮存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)

【]o（本題2.0分）

A.數(shù)據(jù)處理的方法

B.數(shù)據(jù)元素的類型

C.數(shù)據(jù)元素之間的關(guān)系

D.數(shù)據(jù)的存儲(chǔ)方法

答案：C.

解析：無(wú).

6.（單選題）棧和隊(duì)列的共同點(diǎn)是【】。（本題2.0分）

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

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

C.只允許在端點(diǎn)處進(jìn)行插入和刪除

D.無(wú)共同點(diǎn)

答案：C.

解析：無(wú).

9.（單選題）采用順序查找法查找長(zhǎng)度為n的查找表時(shí)，每個(gè)元素查找的平均查

找長(zhǎng)度為【】。（本題2.0分）

A.n

B.n/

C.n+1/2

D.n-1/2

答案：c.

解析：無(wú).

10.（單選題）一個(gè)有N個(gè)頂點(diǎn)的有向圖最多有（）條邊。（本題2.0分）

A.N

B.N（N-l）

C.N（n-l）/2

D.2N

答案:B.

解析：無(wú).

11.（單選題）若串S="software",其子串的數(shù)目是（）。（本題2.0分）

A.8

B.37

C.36

D.9

答案：B.

解析：無(wú).

12.（單選題）在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的結(jié)構(gòu)。（本題

2.0分）

A.邏輯

B.存儲(chǔ)

C.邏輯和存儲(chǔ)

D.物理

答案：A.

解析：無(wú).

13.（單選題）一個(gè)具有N個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)使得數(shù)據(jù)仍然有

序,其算法時(shí)間復(fù)雜度為（）。（本題2.0分）

A.0（logn）

B,0（1）

C.0（n2）

D.0（n）

答案：D.

解析：無(wú).

14.（單選題）線性表是（）。（本題2.0分）

A.一個(gè)有限序列，可以為空

B.一個(gè)有限序列，不能為空

C.一個(gè)無(wú)限序列，可以為空

D.一個(gè)無(wú)序序列，不能為空

答案:A.

解析：無(wú).

15.（單選題）線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí),其地址（）。（本題2.0分）

A.必須是連續(xù)的

B.部分地址必須是連續(xù)的

C.一定是不連續(xù)的

D.連續(xù)與否均可以

答案：D.

解析：無(wú).

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

修改指針的操作為（）。（本題2.0分）

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

B.p=p->next

C.p=p->next->next

D.next=p

答案：A.

解析：無(wú).

17.（單選題）在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)需修改指針（）。（本

題2.0分）

A.p->prior->next=p->nextp->next->prior=p->prior

B.p->prior=p->prior->nextp->prior->prior->next=p

C.p->prior->prior->next=pp->prior=p->prior->prior

D.p->next->next->prior=pp->next=p->next->next

答案:A.

解析：無(wú).

18.（單選題）若元素a、b、c、d、e、f依次進(jìn)棧，允許進(jìn)棧、退棧的操作交替進(jìn)

行,但不允許連續(xù)3次退棧工作,則不可能得到的出棧序列是（）。（本題2.0分）

A.dcebfa

B.cbdaef

C.bcaefd

D.afedcb

答案：D.

解析：無(wú).

21.（單選題）棧和隊(duì)列具有相同的（）。（本題2.0分）

A.抽象數(shù)據(jù)類型

B.邏輯結(jié)構(gòu)

C.存:儲(chǔ)結(jié)構(gòu)

D.運(yùn)算

答案：B.

解析：無(wú).

22.（單選題）一個(gè)隊(duì)列的入隊(duì)序列為1234,則出隊(duì)序列是（）。（本題2.0分）

A.4321

B.1234

C.1432

D.3241

答案：B.

解析：無(wú).

23.（單選題）以下關(guān)于二叉樹(shù)的說(shuō)法正確的是（）。（本題2.0分）

A.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度均為2

B.二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2

C.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度可以小于2

D.二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)

答案：C.

解析：無(wú).

24.（單選題）一棵滿二叉樹(shù)共有64個(gè)葉子結(jié)點(diǎn)，則其結(jié)點(diǎn)個(gè)數(shù)為（）。（本題2.0

分）

A.64

B.65

C.127

D.128

答案：C.

解析：無(wú).

25.（單選題）有n個(gè)元素的數(shù)組，查找其中最大值的元素，一般需要（）次元素的

比較。（本題2.0分）

A.1

B.n

C.n+1

D.n-1

答案：C.

解析：無(wú).

26.（單選題）以下排序中，關(guān)鍵字比較的次數(shù)與元素的初始排列的次序無(wú)關(guān)的是

（）。（本題2.0分）

A.希爾排序

B.冒泡排序

C.插入排序

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

答案：D.

解析：無(wú).

27.（單選題）（）不是算法的基本特性。（本題2.0分）

A.可行性

B.長(zhǎng)度有限

C.在規(guī)定的時(shí)間內(nèi)完成

D.確定性

答案：B.

解析：無(wú).

28.（單選題）某算法的時(shí)間復(fù)雜度為0（n2）,表明該算法的（）。（本題2.0分）

A.問(wèn)題規(guī)模是n2

B.執(zhí)行時(shí)間等于n2

C.執(zhí)行時(shí)間與n2成正比

D.問(wèn)題規(guī)模與n2成正比

答案：C.

解析：無(wú).

29.（單選題）線性表的靜態(tài)鏈表存儲(chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比，優(yōu)點(diǎn)是（）。（本

題2.0分）

A.所有的操作算法實(shí)現(xiàn)簡(jiǎn)單

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

C.便于插入和刪除

D.便于利用零散的存儲(chǔ)器空間

答案：C.

解析：無(wú).

30.（單選題）帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件時(shí)（）。（本題2.0分）

A.L==NULL

B.L->next==NULL

C.L->next==L

D.L!=NULL

答案：B.

解析：無(wú).

31.（單選題）在雙向鏈表存儲(chǔ)結(jié)構(gòu)中,刪除p所指的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)（若存在）時(shí)

需修改指針（）。（本題2.0分）

A.p->prior->next=p->nextp->next->prior=p->prior

B.p->prior=p->prior->nextp->prior->prior->next=p

C.p->prior->prior->next=pp->prior=p->prior->prior

D.p->next->next->prior=pp->next=p->next->next

答案：c.

解析：無(wú).

32.（單選題）一個(gè)棧的進(jìn)棧序列是a、b、c、d、e,則棧的不可能輸出序列是（）。

（本題2.0分）

A.edcba

B.decba

C.dceab

D.abcde

答案：c.

解析：無(wú).

33.（單選題）遞歸模型為f（l）=l,f（n）=f（n-l）+n（n〉l）,其中遞歸體是（）。（本

題2.0分）

A.f（n）=f（n-l）+n

B.f（0）=l

C.f（l）=0

D.f（n）=n

答案：A.

解析：無(wú).

34.（單選題）已知輸入序列是abed,經(jīng)過(guò)輸出受限的雙端隊(duì)列后能得到的輸出序

列是（）。（本題2.0分）

A.dacb

B.cadb

C.dbea

D.以上序列都不能得到

答案：B.

解析：無(wú).

35.（單選題）以下（）是“abcd321ABCD”串的子串。（本題2.0分）

A.abed

B.321AB

C.“abcABC”

D.“21AB”

答案:D.

解析：無(wú).

36.（判斷題）順序隊(duì)列中的元素個(gè)數(shù)，可以根據(jù)隊(duì)首指針和隊(duì)尾指針的值計(jì)算出

來(lái)。（）（本題2.0分）

A.true

B.false

答案：A.

解析：無(wú).

37.（判斷題）二分查找可以在有序的雙向鏈表上進(jìn)行。（）（本題2.0分）

A.true

B.false

答案：B.

解析：無(wú).

38.（判斷題）邏輯結(jié)構(gòu)不相同的數(shù)據(jù)，必須采用不同類型的存儲(chǔ)方法（）。（本題

2.0分）

A.正確

B.錯(cuò)誤

答案：B.

解析：無(wú).

39.（判斷題）在單鏈表中，可以從頭結(jié)點(diǎn)開(kāi)始查找任何一個(gè)結(jié)點(diǎn)。（）（本題2.0

分）

A.正確

B.錯(cuò)誤

答案：A.

解析：無(wú).

40.（判斷題）棧底元素是不能刪除的元素。（）（本題2.0分）

A.正確

B.錯(cuò)誤

答案：B.

解析：無(wú).

41.（判斷題）用一維數(shù)組存儲(chǔ)特殊矩陣，可以簡(jiǎn)化對(duì)矩陣的存取操作。（）（本題

2.0分）

A.正確

B.錯(cuò)誤

答案：B.

解析：無(wú).

42.（判斷題）樹(shù)適合表示層次關(guān)系。（）（本題2.0分）

A.正確

B.錯(cuò)誤

答案：A.

解析：無(wú).

43.（判斷題）在先序、中序和后序序列中，葉子結(jié)點(diǎn)出現(xiàn)的相對(duì)次序是相同的。

（）（本題2.0分）

A.正確

B.錯(cuò)誤

答案：A.

解析：無(wú).

44.（判斷題）對(duì)一個(gè)圖進(jìn)行廣度優(yōu)先遍歷時(shí),每個(gè)頂點(diǎn)恰好進(jìn)隊(duì)和出隊(duì)各一次。

（）（本題2.0分）

A.正確

B.錯(cuò)誤

答案:A.

解析：無(wú).

45.（判斷題）基數(shù)排序是一種穩(wěn)定