鹽城師范學院數據結構與算法期末復習題及參考答案

鹽城師范繼續(xù)教育學院

數據結構與算法普通用卷

-單選題（共50題，總分值75分）

1.設有一組關鍵字值（46,79,56,38,40,84）,則用堆

排序的方法建立的初始堆為（）。（L5分）

A.79,46,56,38,40,84

B.84,79,56,38,40,46

C.84,79,56,46,40,38

D.84,56,79,40,46,38

2.在帶有頭結點的單鏈表HL中，要向表頭插入一個由

指針P指向的結點，則執(zhí)行（）（L5分）

A.p->next=HL->next;HL->next=p

B.p->next=HL;HL=p

C.p->next=HL;p=HL

D.HL=p;p->next=HL

3.下列是動態(tài)規(guī)劃算法基本要素的是（（1.5分）

A.定義最優(yōu)解

B.構造最優(yōu)解

C.算出最優(yōu)解

D.子問題重疊性質

4.不帶頭結點的單鏈表（頭指針為head）為空的判定

條件是（）。（1.5分）

A.head==NULL

B.head->next==head

C.head->next==NULL

D.head!=NULL

5.直接插入排序在最好情況下的時間復雜度為()。

(1.5分)

A.O(logn)

B.0(n)

C.O(n*logn)

D.0(n2)

6.設有一個二維數組A[m][n],假設A[0][0]存放位置

在644(10),A[2][2]存放位置在676(10),每個元

素占一個空間，問A[3][3](10)存放在什么位置？

腳注(10)表示用10進制表示。()(1.5分)

A.688

B.678

C.692

D.696

7.設串sl='abcdefg',s2='ab',則Concat(si,s2)

的返回值()。(1.5分)

A.ab

B.cdefg

C.abcdefg

D.abcdefgab

8.一個棧的輸入序列為123,則下列序列中不可能是

棧的輸出序列的是()(1.5分)

A.231

B.321

C.312

D.123

9.使用分治法求解不需要滿足的條件是（）。（1.5

分）

A.子問題必須是一樣的

B.子問題不能夠重復

C.子問題的解可以合并

D.原問題和子問題使用相同的方法解

10.設無向圖的頂點個數為n,則該圖最多有（）條

邊。（1.5分）

A.n-1

B.n（n-l）/2

C.n（n+l）/2

D.n2

11.分支限界法解旅行售貨員問題時，活結點表的組織

形式是（）。（1.5分）

A.最小堆

B.最大堆

C.棧

D.數組

12.在樹形結構中，數據元素間存在（）的關系。（1.5

分）

A.一對一

B.一對多

C.多對多

D.除同屬一個集合外別無關系

13.（）是貪心算法與動態(tài)規(guī)劃算法的共同點。（1.5

分）

A.重疊子問題

B.構造最優(yōu)解

C.貪心選擇性質

D.最優(yōu)子結構性質

14.設對下圖從頂點a出發(fā)進行深度優(yōu)先遍歷，則（）

是可能得到的遍歷序列。(1.5

分）

A.acfgdeb

B.abcdefg

C.acdgbef

D.abefgcd

15.分支限界法在問題的解空間樹中，按（）策略,

從根結點出發(fā)搜索解空間樹（1.5分）

A.廣度優(yōu)先

B.活結點優(yōu)先

C.擴展結點優(yōu)先

D.深度優(yōu)先

16.下面關于NP問題說法正確的是（）（1.5分）

A.NP問題都是不可能解決的問題

B.P類問題包含在NP類問題中

C.NP完全問題是P類問題的子集

D.NP類問題包含在P類問題中

17.n個結點的線索二叉樹上含有的線索數為

__________________o（1.5分）

A.0

B.n-1

C.n+1

D.2n

18.NP類語言在圖靈機下的定義為（）（1.5分）

A.NP={L|L是一個能在非多項式時間內被一臺

NDTM所接受的語言}

B.NP={L|L是一個能在多項式時間內被一臺

NDTM所接受的語言}

C.NP={L|L是一個能在多項式時間內被一臺DTM

所接受的語言}

D.NP={L|L是一個能在多項式時間內被一臺

NDTM所接受的語言}

19.在一個可存放n個數據元素的順序棧中，假設以高

地址端為棧底，以top為棧頂指針，當向棧中壓入

一個數據元素時，top的變化是（）。（1.5分）

A.不變

B.top=n

C.top++

D.top-

20.串的長度是指（）。（1.5分）

A.串中所含不同字母的個數

B.串中所含字符的個數

C.串中所含不同字符的個數

D.串中所含非空格字符的個數

21.動態(tài)規(guī)劃算法的基本要素（）（1.5分）

A.最優(yōu)子結構性質與貪心選擇性質

B.重疊子問題性質與貪心選擇性質

C.最優(yōu)子結構性質與重疊子問題性質

D.預排序與遞歸調用

22.已知二叉樹T的先序序列為abdegcfh,中序序列

為dbgeachf,則T的后序序列為（）o（1.5分）

A.gedhfbca

B.dgebhfca

C.abcdefgh

D.acbfedhg

23.設連通圖G中的邊集E={（a,b）,（a,e）,（a,

c）,（b,e）,（e,d）,（d,f）,（f,c）},

則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點

序列為（）（1.5分）

A.abedfc

B.acfebd

C.aebdfc

D.aedfcb

24.二叉樹的第k層的結點數最多為（）.（1.5分）

A.2k-l

B.2K+1

C.2K-1

D.2k-l

25.若需要利用形參直接訪問實參時，應將形參變量說

明為（）參數。（）（1.5分）

A.值

B.函數

C.指針

D.引用

26.若采用順序映象，則數據元素在內存中占用的存儲

空間（）。（1.5分）

A.一定連續(xù)

B.一定不連續(xù)

C,可連續(xù)可不連續(xù)

27.設哈希表地址范圍為0~19,哈希函數

H（key）=key%17,使用二次探測再散列法處理沖突。

若表中已存放有關鍵字值為6、22、38、55的記錄,

則再放入關鍵字值為72的記錄時，其存放地址應為

（）o（1.5分）

A.2

B.3

C.4

D.7

E.8

F.以上都不對

28.下列排序算法中（）不能保證每趟排序至少能將

一個元素放到其最終的位置上。（1.5分）

A.快速排序

B.shell排序

C.堆排序

D.冒泡排序

29.一棵高為k的二叉樹最少有（）個結點。（1.5分）

A.k-1

B.k

C.k+1

D.2匕1

E.2k-l

30.蒙特卡羅算法是（）的一種。（1.5分）

A.分支界限算法

B.概率算法

C.貪心算法

D.回溯算法

31.對二叉排序樹進行（）遍歷所得的遍歷序列中，

關鍵字值是按升序排列的。（1.5分）

A前序

中

序

BC.后

序

層

D.序

32.k帶圖靈機的空間復雜性S（n）是指（）（1.5分）

A.k帶圖靈機處理所有長度為n的輸入時，在某

條帶上所使用過的最大方格數

B.k帶圖靈機處理所有長度為n的輸入時，在k

條帶上所使用過的方格數的總和

C.k帶圖靈機處理所有長度為n的輸入時，在k

條帶上所使用過的平均方格數

D.k帶圖靈機處理所有長度為n的輸入時，在某

條帶上所使用過的最小方格數

33.對于線性表（7,34,55,25,64,46,20,10）

進行散列存儲時，若選用H（K）=K%9作為散列函

數，則散列地址為1的元素有（）個，（1.5分）

A.1

B.2

C.3

D.4

34.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單

鏈表中的結點都具有相同的（）（1.5分）

A.行號

B.列號

C.元素值

D.非零元素個數

35.將兩個各有n個元素的有序表歸并成一個有序表，

最少進行（）次比較。（1.5分）

A.n

B.2n-l

C.2n

D.n-1

36.Strassen矩陣乘法是利用（）實現的算法。（1.5

分）

A.分治策略

B.動態(tài)規(guī)劃法

C.貪心法

D.回溯法

37.隊列的刪除操作是在（）進行。（1.5分）

A.隊首

B.隊尾

C.隊首前一單元

D.隊尾后一單元

38.設輸入序列為ABC,輸出序列為CBA,則經過的棧

操作為（）。（1.5分）

A.push,pop,push,pop,push,pop

B.push,push,push,pop,pop,pop

C.push,push7pop,pop,push,pop

D.push,pop,push,push,pop,pop

39.實現最長公共子序列利用的算法是（）（1.5

分）

A.分治策略

B.動態(tài)規(guī)劃法

C.貪心法

D.回溯法

40.下列不屬算法特性的是（）。（1.5分）

A.有窮性

B.確定性

C.零或多個輸入

D.健壯性

41.在一般輸入數據的程序里，輸入多多少少會影響到

算法的計算復雜度，為了消除這種影響可用()對

輸入進行預處理(1.5分)

A.蒙特卡羅算法

B.拉斯維加斯算法

C.舍伍德算法

D.數值概率算法

42.設廣義表L=((a,()),b,(c,d,e)),則

Head(Tail(Tail(L)))的值為()。(1.5分)

A.b

B.c

c.(C)

D.(c,d,e)

43.設一個有序的單鏈表中有n個結點，現要求插入一

個新結點后使得單鏈表仍然保持有序，則該操作的

時間復雜度為()(1.5分)

A.0(Iog2n)

B.0(1)

C.0(n2)

D.0(n)

44.銀行業(yè)務叫號系統采用了數

據結構。（1.5分）

A.棧

B.廣義表

C.隊列

D.圖

45.以下屬單鏈表優(yōu)點的是（）。（1.5分）

A.順序存取

B.插入操作能在。⑴的時間復雜度上完成

C.插入時不需移動數據元素

D.節(jié)省存儲空間

46.在對問題的解空間樹進行搜索的方法中，一個活結

點有多次機會成為活結點的是（）（1.5分）

A.回溯法

B.分支限界法

C.回溯法和分支限界法

D.動態(tài)規(guī)劃

47.若有18個元素的有序表存放在一維數組A[19]中,

第一個元素放A[l]中，現進行二分查找，則查找A

[3]的比較序列的下標依次為（）（1.5分）

A,1,2,3

B,9,5,2,3

C.9,5,3

D.9,4,2,3

48.假設為循環(huán)隊列分配的向量空間為Q[20],若隊列

的長度和隊頭指針值分別為13和17,則當前尾指

針的值為o（L5分）

A.10

B.11

C.12

D.13

49.樹最適合用來表示（）。（1.5分）

A,有序數據元素

B.無序數據元素

C.元素之間具有分支層次關系的數據

D.元素之間無聯系的數據

50.一棵度為3的樹中，度