2016年4月自考02331數(shù)據(jù)結(jié)構(gòu)試題及答案含解析

數(shù)據(jù)結(jié)構(gòu)年月真題

0233120164

1、【單選題】1.下列選項(xiàng)中，屬于非線性數(shù)據(jù)結(jié)構(gòu)的是

隊(duì)列

棧

A:

二叉排序樹

B:

線性表

C:

答D:案：C

解析：二叉排序樹屬于非線性結(jié)構(gòu)。棧是一種特殊的線性表，只能在固定的一端進(jìn)行插入

和刪除操作隊(duì)列可看作是插入在一端進(jìn)行，刪除在另一端進(jìn)行的線性表。

2、【單選題】2.瑞士計(jì)算機(jī)科學(xué)家沃思教授曾指出:算法+數(shù)據(jù)結(jié)構(gòu)=程序.這里的數(shù)據(jù)結(jié)構(gòu)指

的是

數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

數(shù)據(jù)的線性結(jié)構(gòu)和非線性結(jié)構(gòu)

A:

數(shù)據(jù)的緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

B:

數(shù)據(jù)的順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)

C:

答D:案：A

解析：瑞士計(jì)算機(jī)科學(xué)家沃思教授曾指出:算法+數(shù)據(jù)結(jié)構(gòu)-程序。數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)的邏

輯結(jié)構(gòu)和存儲結(jié)構(gòu)，而算法是指對數(shù)據(jù)的操作方法。

3、【單選題】3.線性表順序存儲時(shí)，邏輯上相鄰的兩個(gè)數(shù)據(jù)元素.其存儲地址

一定相鄰

一定不相鄰

A:

不一定相鄰

B:

可能不相鄰

C:

答D:案：A

解析：參考解析：線性表有兩種存儲方式，在順序存儲時(shí)，邏輯上相鄰的元素在存儲的

物理位置次序上也相鄰。

4、【單選題】4.數(shù)據(jù)元素1,2,3,4,5依次入棧，則不可能得到的出找序列是

4,5,3,2,1

A:

1,2,3,4,5

4,3,5,1,2

B:

5,4,3,2,1

C:

答D:案：C

解析：若3先出棧，那么1和2必須先進(jìn)棧，然后3進(jìn)棧，再出棧，而此時(shí)棧的棧頂元素

為2，所以第二個(gè)出棧的元素不可能是1，只能是2，所以此時(shí)的出棧序列必為:321

5、【單選題】5.設(shè)順序表首元素A[0]的存儲地址是4000,每個(gè)數(shù)據(jù)元素占5個(gè)存儲單元，則

元素A[20]的起始存儲地址是

4005

4020

A:

4100

B:

4105

C:

答D:案：C

解析：

6、【單選題】6.廣義表A=(a,(b,c,(e,f))),函數(shù)head=(head(tail（A））)的運(yùn)算結(jié)果是

a

b

A:

c

B:

e

C:

答D:案：B

解析：tail(A)=((b,c,(e,f))),head(tail(A))=

(b,c,(e,f)),head(head(tail(A)))=b。

7、【單選題】7.設(shè)高度為h的二叉樹中，只有度為0和2的結(jié)點(diǎn)，則此類二叉樹包含的結(jié)點(diǎn)

數(shù)至少是

2h

2h-1

A:

2h+1

B:

h+1

C:

答D:案：B

解析：最少情況為除了第h層，每層度為2的節(jié)點(diǎn)只有1個(gè)，共有2（h-1）個(gè)，再加根節(jié)

點(diǎn)就是24-2+1-2n-1個(gè)。

8、【單選題】8.一棵非空二叉樹T的前序遍歷和后序遍歷序列正好相反，則T一定滿足

所有結(jié)點(diǎn)均無左孩子

所有結(jié)點(diǎn)均無右孩子

A:

只有一個(gè)葉子結(jié)點(diǎn)

B:

是一棵滿二叉樹

C:

答D:案：C

解析：前序遍歷序列是＂根左右＂，后序遍歷序列是＂左右根＂，若兩個(gè)序列相反，則

此樹沒有左子樹或者右子樹。

9、【單選題】設(shè)圖的鄰接矩陣A如下所示。各頂點(diǎn)的度依次是

1,2,1,2

2,2,1,1

A:

3,4,2,3

B:

4,4,2,2

C:

答D:案：C

解析：各頂點(diǎn)的度是矩陣中此結(jié)點(diǎn)對應(yīng)的橫行和縱列非零元素之和。?

10、【單選題】10.無向圖G如題10圖所示，從頂點(diǎn)a開始進(jìn)行深度優(yōu)先遍歷，下列遍歷

序列中，正確的是?

a,b,e,c,d,f

a,c,f,e,d,b

A:

a,c,b,e,f,d

B:

a,e,d,f,c,b

C:

答D:案：B

解析：深度優(yōu)先遍歷是從一個(gè)頂點(diǎn)出發(fā)，依次對訪問過的頂點(diǎn)做標(biāo)記，并尋找沒有訪問過

的相鄰頂點(diǎn)，依次找直接相在的點(diǎn)回

11、【單選題】11.設(shè)帶權(quán)連通圖G中含有n(n>1)個(gè)頂點(diǎn)，下列關(guān)于G的最小生成樹T的敘

述中，正確的是

T中可能含有回路

T中含有圖G的所有邊

A:

T是唯一的，且含有n-1條邊

B:

T可能不唯一，但權(quán)一定相等

C:

答D:案：D

解析：某幾條邊的權(quán)可能相等，所以路徑不唯一。

12、【單選題】12.若要求對序列進(jìn)行穩(wěn)定的排序，則在下列選項(xiàng)中應(yīng)選擇

希爾排序

快速排序

A:

直接插入排序

B:

直接選擇排序

C:

答D:案：C

解析：簡單選擇排序，冒泡排序，直接插入排序是穩(wěn)定的排序方法。直接選擇排序，快速

排序，推排序是不穩(wěn)定的。

13、【單選題】13.下列排序算法中，空間復(fù)雜度最差的是

歸并排序

希爾排序

A:

冒泡排序

B:

堆排序

C:

答D:案：A

解析：

14、【單選題】14.下列排序算法中，初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而更多的算法是

插入排序

冒泡排序

A:

快速排序

B:

希爾排序

C:

答D:案：C

解析：快速排序的特點(diǎn)是越有序，越慢。

15、【單選題】15.對線性表L進(jìn)行二分查找時(shí)，要求L必須滿足

以順序方式存儲

以順序方式存儲，且數(shù)據(jù)元素有序

A:

以鏈接方式存儲

B:

以鏈接方式存儲，且數(shù)據(jù)元素有序

C:

答D:案：B

解析：對線性表進(jìn)行二分查找時(shí)，要求線性表存儲方式必須是順序存儲，且數(shù)據(jù)元素有

序。

16、【填空題】18\.只能在線性表的兩端進(jìn)行插入或刪除操作的兩種邏輯結(jié)構(gòu)分別是

____。

答案：棧和隊(duì)列

17、【填空題】19\.廣義表A=（x,(y,z,(u,v,w))）的長度是____。

答案：2

18、【填空題】20\.一棵樹的后序遍歷序列與其對應(yīng)的二叉樹的____序遍歷序列相同。

答案：中

19、【填空題】21\.在有向圖、無向圖中，其鄰接矩陣一定對稱的是____。

答案：無向圖

20、【填空題】22\.要計(jì)算圖中從某一頂點(diǎn)出發(fā)到其余各頂點(diǎn)的最短路徑，可選用____算

法。

答案：迪杰斯特拉

21、【填空題】23\.設(shè)關(guān)鍵字序列為28,72,97,63,4,53,84，使用希爾排序法將其排成升序

序列，若第一趟采用的間隔是3，則該趟排序的結(jié)果是____。

答案：28,4,53,63,72,9