自考真題是考生復(fù)習(xí)備考的一大法寶，需要好好利用，而且年份離的越近，參考價(jià)值越高。以下是希賽網(wǎng)自考頻道整理的全國(guó)2020年8月自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論02142真題試卷，考生可參考試卷題型、分值、重點(diǎn)考試內(nèi)容及答題規(guī)范，參考答案現(xiàn)在暫未公布，希賽網(wǎng)將持續(xù)更新。

全國(guó)2020年8月自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論02142真題試卷

注意事項(xiàng):

1.答題前,考生務(wù)必將自己的考試課程名稱姓名、準(zhǔn)考證號(hào)用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。

2.每小題選出答案后,用2B鉛筆把答題紙上對(duì)應(yīng)題目的答案標(biāo)號(hào)涂黑。如需改動(dòng),用橡皮擦干凈后,再選涂其他答案標(biāo)號(hào)。不能答在試題卷上。

一、單項(xiàng)選擇題:本大題共15小題,每小題2分,共30分。在每小題列出的備選項(xiàng)中只有一項(xiàng)是最符合題目要求的,請(qǐng)將其選出。

1.下面程序段的時(shí)間復(fù)雜度為

for(int i=0; i<n; i++)

for(int j=0;j<n;j++)

A[i][j]=i*j;

2.現(xiàn)有一“遺傳”關(guān)系:設(shè)x是y的父親,則x可以把它的屬性遺傳給y。表示該遺傳關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)為

A.線性表

B.樹

C.集合

D.圖

3.在具有101個(gè)元素的順序表中查找值為x的元素時(shí),平均查找長(zhǎng)度為

A.50

B.51

C.100

D.101

4.關(guān)于隊(duì)列，下列敘述正確的是

A.隊(duì)列的元素個(gè)數(shù)可以無(wú)窮大

B.隊(duì)列中元素的類型可以不同

C.隊(duì)列是一個(gè)非線性的序列

D.隊(duì)列的特點(diǎn)是先進(jìn)先出

5.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?則刪除棧頂元索的操作序列為

A. top= top+1;

B. top=top-l;

C. top->next= top;

D. top= top->next;

6.設(shè)某棵二叉樹中有2000個(gè)結(jié)點(diǎn),則該二叉樹的最小高度為

A.9

B.10

C.11

D.12

7.對(duì)二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號(hào),要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào),同.一結(jié)點(diǎn)的左右孩子中,其左孩子的編號(hào)小于其右孩子的編號(hào),可 采用實(shí)現(xiàn)編號(hào)的遍歷方法是

A.先序

B.后序

C.中序

D.層次

8.若一棵二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)是5,度為2的結(jié)點(diǎn)個(gè)數(shù)是3,則該二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)為

A. 2

B.3

C.4

D.5

9.對(duì)稀疏矩陣采用三元組表示法的目的是

A.便于輸人和輸出

B.便于進(jìn)行矩陣運(yùn)算

C.降低時(shí)間復(fù)雜度

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

10.在圖G中求兩個(gè)結(jié)點(diǎn)之間的最短路徑可以采用的算法是

A. Djkstra算法

B. Prim算法

C.克魯斯卡爾算法.

D.廣度優(yōu)先遍歷算法

11.如果按深度優(yōu)先搜索算法從圖中任意-一點(diǎn)出發(fā)均可以訪問(wèn)圖中所有的頂點(diǎn),則該圖一定是

A.連通圖

B.有回路圖

C.完全圖

D.無(wú)環(huán)圖

12.假定有k個(gè)關(guān)鍵字互為同義詞,若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表中,至少要進(jìn).行探測(cè)的次數(shù)是

A. k-1

B. k

C. k+1

D. k(k+1)/2

13.二叉排序樹中,若它的左子樹不空,則根結(jié)點(diǎn)的值比左子樹上所有結(jié)點(diǎn)的值

A.小

B.大

C.小或相等

D.大或相等

14.設(shè)一組初始記錄有8個(gè)關(guān)鍵字,使用直接插人排序得到有序序列，則需要經(jīng)過(guò)的趟數(shù)最多是

A.5

B.6

C.7

D.8

15.在最好情況下,只需要一趟就可以完成對(duì)--個(gè)數(shù)組的排序,可選擇的排序方法是

A.快速排序

B.冒泡排序

C.直接選擇排序

D.直接插入排序

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

16.數(shù)據(jù)結(jié)構(gòu)是指一組相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)的組織方式和它們?cè)谟?jì)算機(jī)內(nèi)的      ▲     方式,以及定義在該組數(shù)據(jù)上的一組操作。

17.數(shù)據(jù)不可分割的最小識(shí)別單位是     ▲     。

18.樹有如下三種常用的存儲(chǔ)結(jié)構(gòu):孩子鏈表表示法、孩子兄弟鏈表表示法和      ▲     。

19.在帶頭結(jié)點(diǎn)的單鏈表L中,第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)的指針為     ▲     。

20.麗數(shù)的嵌套調(diào)用使用的數(shù)據(jù)結(jié)構(gòu)是     ▲     。

21.圖有n個(gè)頂點(diǎn)e條邊，以鄰接表作存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為     ▲     。

22.一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖的邊數(shù)為     ▲     ,

23. -棵二叉樹的度數(shù)最大為     ▲     

24. n個(gè)頂點(diǎn)的連通圖的生成樹有     ▲     條邊。

25.就平均時(shí)間性能而言,快速排序方法的時(shí)間復(fù)雜度為     ▲     。

26.二分查找算法的時(shí)間復(fù)雜度為     ▲     。

27.解決沖突的方法主要有線性探查法、鏈地址法、多重散列法、公共溢出區(qū)法和     ▲     

28.冒泡排序的平均時(shí)間復(fù)雜度為     ▲     

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

29.有二叉樹如題29圖所示,寫出該二叉樹的先序遍歷、中序遍歷和后序遍歷序列。

30.如題30圖所示的圖結(jié)構(gòu),請(qǐng)寫出以10為源點(diǎn)的廣度優(yōu)先搜索得到的頂點(diǎn)訪問(wèn)序列,并畫出搜索過(guò)程圖。(同等情況下,值小的結(jié)點(diǎn)優(yōu)先訪問(wèn))

31.設(shè)散列表的長(zhǎng)度為11,散列麗數(shù)h(key)=key mod 11,采用線性探查法解決沖突。從空表開始,依次插人下列關(guān)鍵字值序列:80,40,7,18,13,2,請(qǐng)建立散列表。

32.依次輸人鍵值序列:30,10, 20,50,40,60,構(gòu)建二叉排序樹,要求給出構(gòu)建過(guò)程。

33.對(duì)序列(45,38,66 ,90,88,10,25,45)進(jìn)行冒泡排序,寫出前三趟排序結(jié)果。四算法設(shè)計(jì)題:本大題共2小題,每小題7分,共14分。

34.試寫出二分查找的非遞歸算法。

35.已知麗數(shù)swap(R[min],R[i])功能是將記錄R[min]和R[i]交換。試寫出直接選擇排序算法。