2023年10月自考02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題及答案含評(píng)分標(biāo)準(zhǔn)

絕密考試結(jié)束前

★

年月高等教育自學(xué)考試

202310

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

課程代碼:02142

請(qǐng)考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。

1.

答題前,考生務(wù)必將自己的考試課程名稱、姓名、準(zhǔn)考證號(hào)用黑色字跡的簽字筆或鋼筆

2.

填寫在答題紙規(guī)定的位置上。

選擇題部分

注意事項(xiàng):

每小題選出答案后用鉛筆把答題紙上對(duì)應(yīng)題目的答案標(biāo)號(hào)涂黑如需改動(dòng)用橡皮

,2B。,

擦干凈后再選涂其他答案標(biāo)號(hào)不能答在試題卷上

,。。

一、單項(xiàng)選擇題:本大題共15小題,每小題2分,共30分。在每小題列出的備選項(xiàng)中只有一項(xiàng)

是最符合題目要求的,請(qǐng)將其選出。

時(shí)間復(fù)雜度的常數(shù)階表示為

1.

2n

A.O(1)B.O(n)C.O(n)D.O(2)

下列關(guān)于單鏈表的描述錯(cuò)誤的是

2.,

所有結(jié)點(diǎn)通過指針鏈接?形?成鏈表頭指針變量不一定非要用來標(biāo)識(shí)

A.B.head

尾結(jié)點(diǎn)指針域的值稱為空指針通常用尾指針來表示一個(gè)單鏈表

C.NULLD.

線性表實(shí)現(xiàn)順序存儲(chǔ)可使用

3.

棧隊(duì)列數(shù)組鏈表

A.B.C.D.

設(shè)單鏈表中指針指向結(jié)點(diǎn)要?jiǎng)h除之后的結(jié)點(diǎn)若存在則修改指針的操作為

4.pA,A(),

A.pnext=pnextnextB.p=pnext

C.p=pnextnextD.pnext=p

出隊(duì)列操作使用的賦值語句是

5.

A.SQ.rear=SQ.rear+1B.SQ.rear=SQ.rear-1

C.SQ.front=SQ.front+1D.SQ.front=SQ.front-1

在一個(gè)具有個(gè)單元的順序棧中假定以地址低端即單元作為棧底以為棧頂指

6.n,(0),top

針當(dāng)棧未滿時(shí)進(jìn)行進(jìn)棧操作此時(shí)

,,

不變

A.topB.top--C.top++D.top=0

浙數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第頁共頁

02142#1(4)

帶頭結(jié)點(diǎn)鏈隊(duì)列的頭指針和尾指針分別為和則判斷隊(duì)列空的條件為

7.frontrear,

A.front==rearB.front!=NULL

C.rear!=NULLD.front==NULL

深度為的二叉樹的結(jié)點(diǎn)數(shù)最多為

8.k(k1)

≥

k-1kkk+1

A.2B.2-1C.2+1D.2

下列關(guān)于樹形結(jié)構(gòu)的描述正確的是

9.,

樹形結(jié)構(gòu)是線性結(jié)構(gòu)樹中每個(gè)結(jié)點(diǎn)可以有多個(gè)直接前驅(qū)結(jié)點(diǎn)

A.B.

樹可以用順序存儲(chǔ)樹中每個(gè)結(jié)點(diǎn)只能有一個(gè)直接后繼結(jié)點(diǎn)

C.D.

對(duì)任何一棵二叉樹若度數(shù)為的結(jié)點(diǎn)葉結(jié)點(diǎn)個(gè)數(shù)為度數(shù)為的結(jié)點(diǎn)個(gè)數(shù)為則

10.,0()n0,2n2,

等于

n0

A.0B.n2-1C.n2D.n2+1

設(shè)有個(gè)頂點(diǎn)的無向圖若它為連通圖則它具有的邊數(shù)最少為

11.10,,

A.9B.10C.11D.12

設(shè)含有個(gè)頂點(diǎn)條弧的有向圖采用鄰接表存儲(chǔ)則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為

12.n,eG,

2

A.O(n)B.O(n+e)C.O(n)D.O(n×e)

當(dāng)查找表中有個(gè)數(shù)據(jù)元素時(shí)假設(shè)為查找第個(gè)元素的概率在等概

13.n,Pi(i=1,2,…,n)i,Pi

率的條件下順序查找算法的平均查找長度為

,

A.n/2B.(n+1)/2C.nD.n+1

二維數(shù)組以行為主序存儲(chǔ)每個(gè)元素占個(gè)存儲(chǔ)單元若元素的存儲(chǔ)地址是

14.A,1。A[1][1]

的存儲(chǔ)地址是則的存儲(chǔ)地址是

420,A[3][3]446,A[5][5]

A.470B.471C.472D.473

冒泡排序?qū)儆?/p>

15.

插入排序歸并排序選擇排序交換排序

A.B.C.D.

非選擇題部分

注意事項(xiàng):

用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上不能答在試題卷上

,。

二、填空題:本大題共13小題,每小題2分,共26分。

在數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)又稱為字段或

16.▲。

在單鏈表存儲(chǔ)結(jié)構(gòu)中線性表的表長等于單鏈表中的結(jié)點(diǎn)個(gè)數(shù)

17.,▲。

二叉樹的順序存儲(chǔ)結(jié)構(gòu)可以用維數(shù)組來實(shí)現(xiàn)

18.▲。

在操作系統(tǒng)中為了保持多個(gè)進(jìn)程和按某種次序依次執(zhí)行需要一個(gè)

19.,P1、P2、P3P4,▲

來實(shí)現(xiàn)這個(gè)過程

。

浙數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第頁共頁

02142#2(4)

對(duì)稱矩陣有近一半元素可以通過其對(duì)稱元素獲得因此可將含有2個(gè)元素的對(duì)稱矩陣壓

20.,n

縮存儲(chǔ)到含有個(gè)元素的一維數(shù)組中

▲。

設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈棧其頭指針為現(xiàn)有一個(gè)新結(jié)點(diǎn)入棧指向該結(jié)點(diǎn)的指針為

21.,head,,

則入棧操作為和

p,▲headnext=p。

滿二叉樹一定是二叉樹

22.▲。

在樹形結(jié)構(gòu)中結(jié)點(diǎn)間具有關(guān)系

23.,▲。

在圖中序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為路徑

24.,▲。

算法用于求問題

25.Dijkstra▲。

求最小生成樹有方法和方法

26.▲Kruskal。

若在查找過程中向表中插入不存在的數(shù)據(jù)元素或者從表中刪除某個(gè)數(shù)據(jù)元素則稱此類

27.,,,

表為查找表

▲。

在二分查找索引順序查找和散列查找三種查找方法中平均查找長度與元素個(gè)數(shù)沒有關(guān)

28.、,

系的查找方法是

▲。

三、應(yīng)用題:本大題共5小題,每小題6分,共30分。

設(shè)有一個(gè)鏈棧的輸入序列為當(dāng)輸出序列分別為和時(shí)請(qǐng)寫出對(duì)應(yīng)的進(jìn)

29.A、B、C,ABCBCA,

棧和出棧過程

。

設(shè)有一森林如題圖所示請(qǐng)分別寫出先序遍歷和中序遍歷的序列

30.F30,。

題圖

30

如題圖所示長度為的散列表其散列函數(shù)為在表中已填入鍵

31.3113,H(key)=keymod13,

值分別為的元素

16,30,54。

現(xiàn)要插入鍵值為的元素應(yīng)用線性探測法計(jì)算填入散列表中單元的序號(hào)

(1)29,,。

要求給出求解過程

()

線性探測法中如何減少堆積的機(jī)會(huì)

(2),?

0123456789101112

541630

題圖

31

浙數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第頁共頁

02142#3(4)

如題圖所示的圖結(jié)構(gòu)請(qǐng)寫出以為源點(diǎn)的廣度優(yōu)先搜索得到的頂點(diǎn)訪問序列并畫

32.32,10,

出搜索過程圖同等情況下值小的結(jié)點(diǎn)優(yōu)先訪問

。(,)

題圖

32

給定有序表用二

33.D={006,087,155,188,220,465,505,508,511,586,656,670,700,766},

分查找法在中查找試給出查找過程

D511,。

四、算法設(shè)計(jì)題:本大題共2小題,每小題7分,共14分。

編制函數(shù)求

34.1+2+…+n。

已知循環(huán)隊(duì)列的結(jié)構(gòu)類型如下

35.:

typedefstructcycqueue

{

DataTypedatamaxsize

intfrontrear

}CcQue

y

CycQueCQ

設(shè)計(jì)入隊(duì)列的算法

。

浙數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第頁共頁

02142#4(4)

絕密啟用前

★

年月高等教育自學(xué)考試全國統(tǒng)一命題考試

202310

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題答案及評(píng)分參考

課程代碼02142

()

一、單項(xiàng)選擇題:本大題共15小題,每小題2分,共30分。

1.A2.D3.C4.A5.C6.C7.B8.B9.C10.D

11.A12.B13.B14.C15.D

二、填空題:本大題共13小題,每小題2分,共26分。

域數(shù)據(jù)元素一

16.17.18.

隊(duì)列

19.20.n(n+1)/221.pnext=headnext

完全層次簡單

22.23.24.

單源最短路徑動(dòng)態(tài)

25.26.Prim27.

散列查找

28.

三、應(yīng)用題:本大題共5小題,每小題6分,共30分。

輸出進(jìn)出進(jìn)出進(jìn)出分

29.ABC:A,A,B,B,C,C;(3)

輸出進(jìn)進(jìn)出進(jìn)出出分

BCA:A,B,B,C,C,A。(3)

先序序列為分

30.ABCDEFGHJI;(3)

中序序列為分

BCDAFEJHIG。(3)

散列函數(shù)求出其散列地址為在地址上面已有元素發(fā)生沖突分應(yīng)用線性

31.(1)3,316,。(1)

探測法得到下一個(gè)地址為仍沖突分則再求下一個(gè)地址這個(gè)位置

,d+1=4,,(1)d+2=5,

上沒有元素將元素填入散列表中序號(hào)為的單元分

,5。(2)

應(yīng)設(shè)法使后繼散列地址盡量均勻地分散在整個(gè)散列表中分

(2)。(2)

序列分

32.:10,20,30,50,40,60(3)

分

(3)

答圖

32

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題答案及評(píng)分參考第頁共頁

1(2)

33.0102030405060708091011121314

(1)006087155188220465505508511586656670700766

↑↑↑

lowmidhigh

分

(2)

(2)006087155188220465505508511586656670700766

↑↑↑

lowmidhigh

分

(2)

(3)006087155188220465505508511586656670700766

↑↑↑

lowmidhigh

分

(2)

四、算法設(shè)計(jì)題:本大題共2小題,每小題7分,共14分。

34.intfact1(intn)

{inti,j,temp,s;

分

s=0;(2)

<=