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

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

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

1.數(shù)據(jù)的最小標(biāo)識單位是

A.數(shù)據(jù)項(xiàng)

B.數(shù)據(jù)類型

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

D.數(shù)據(jù)變量

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

for(inti=0;i<n;i++)< p="">

for(intj=0;j<n;j++)< p="">

a[i][j]=i*j;

A.O(1)

B.O(n)

C.O(2n)

D.O(n2)

3.設(shè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head,則空循環(huán)鏈表的判定條件是

A.head= =NULL

B.head->next= =NULL

C.head->next= =head

D.head=NULL

4.設(shè)輸入序列為1、2、3、4、5、6,則通過棧的作用后可以得到的輸出序列為

A.5,3,4,6,1,2

B.3,2,5,6,4,1

C.3,1,2,5,4,6

D.1,5,4,6,2,3

5.隊(duì)列是一種線性表,其具有的特征是

A.先進(jìn)后出

B.只能插入

C.只能刪除

D.先進(jìn)先出

6.設(shè)有一個(gè)10階的下三角矩陣 A(包括對角線),按照從上到下、從左到右的順序存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中,每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間,則a54地址與a00的地址之差為

A.10

B.19

C.28

D.55

7.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n,則這棵二叉樹中共有結(jié)點(diǎn)個(gè)數(shù)是

A.2n

B.n+l

C.2n-1

D.2n+l

8.設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號,若結(jié)點(diǎn)i有左孩子,則編號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號為

A.2i+1

B.2i

C.i/2

D.2i-1

9.已知一棵二叉樹的先序遍歷結(jié)果為 ABCDEF,中序遍歷結(jié)果為 CBAEDF,則后序遍歷的結(jié)果為

A.CBEFDA

B.FEDCBA

C.CBEDFA

D.CEFBDA

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

A.n-1

B.n2

C.n(n+1)/2

D.n(n-1)/2

11.設(shè)某有向圖中有n個(gè)頂點(diǎn),則該有向圖對應(yīng)的鄰接表中表頭結(jié)點(diǎn)個(gè)數(shù)為

A.n-1

B.n

C.n+1

D.2n-1

12.若查找每個(gè)記錄的概率均等,則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找算法查找一個(gè)記錄,其平均查找長度 ASL為

A.(n-1)/2

B.n/2

C.(n+1)/2

D.n

13.設(shè)散列表中有n個(gè)存儲(chǔ)單元,散列函數(shù) H(key)= key% p,則p最好選擇小于散列表長度n的

A.奇數(shù)

B.素?cái)?shù)

C.偶數(shù)

D.合數(shù)

14.下列排序算法中,穩(wěn)定的排序算法是

A.堆排序

B.快速排序

C.直接選擇排序 

D.冒泡排序

15.下列四個(gè)序列中,是堆的序列為

A.75,45,65,30,15,25,20,10

B.75,65,45,10,30,25,20,15

C.75,65,30,15,25,45,20,10

D.75,45,65,10,25,30,20,15

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

16.數(shù)據(jù)的四類基本邏輯結(jié)構(gòu)是:線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖結(jié)構(gòu)和   ▲    。

17.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和   ▲   存儲(chǔ)。

18.順序表插入算法的時(shí)間復(fù)雜度是   ▲   。

浙02142# 數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題 第 2頁(共4頁)19.設(shè)r指向單鏈表的最后一個(gè)結(jié)點(diǎn),要在最后一個(gè)結(jié)點(diǎn)之后插入s所指的結(jié)點(diǎn),需執(zhí)行的語句序列是r->next=s;r=s;   ▲   。

20.一般情況下,函數(shù)的嵌套調(diào)用和程序遞歸的處理都是用   ▲   來實(shí)現(xiàn)的。

21.m 行n列的矩陣有t個(gè)非零元素,當(dāng)t滿足   ▲   條件時(shí),稱該矩陣為稀疏矩陣。

22.二叉樹的第i(i≥1)層上至多有   ▲   個(gè)結(jié)點(diǎn)。

23.雙親表示法由一個(gè)一維數(shù)組構(gòu)成,數(shù)組的每個(gè)分量包含兩個(gè)域: ▲ 和雙親域。

24.無向圖的鄰接矩陣是一個(gè)   ▲   矩陣。

25.設(shè)有散列函數(shù) H 和鍵值k1、k2,若k1≠k2,但是 H(k1)=H(k2),則稱這種現(xiàn)象為   ▲   。

26.向一個(gè)長度為n的順序表中第i(1≤i≤n)個(gè)元素之前插入一個(gè)元素時(shí),需向后移動(dòng)    ▲   個(gè)元素。

27.直接插入排序的空間復(fù)雜度為   ▲   。

28.設(shè)記錄數(shù)為n,冒泡排序算法在最好情況下所作的比較次數(shù)為   ▲   。

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

29.題29圖給出了一個(gè)稀疏矩陣 A,請寫出該稀疏矩陣的三元組表。

30.已知二叉樹如題30圖所示,請將該二叉樹轉(zhuǎn)換為對應(yīng)的森林。

31.設(shè)某通信系統(tǒng)中一個(gè)待傳輸?shù)奈谋居?個(gè)不同字符,它們的出現(xiàn)頻率分別是0.5,0.7,1.4,2.2,2.4,2.8,試畫出哈夫曼樹,并給出每個(gè)字符的哈夫曼編碼。(要求任一結(jié)點(diǎn)的左孩子權(quán)值小于右孩子)

32.選定散列函數(shù)為 H(key)= keymod13,試用鏈地址法建立鍵值為26,41,25,05,07,15,12,49,51,31,62的散列表。

33.對于給定的一組鍵值:83,40,63,13,84,35,96,57,39,79,61,15,請分別寫出直接選擇排序和冒泡排序的第一趟排序結(jié)果。

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

34.寫出一個(gè)將線性表的順序表存儲(chǔ)方式(數(shù)組a、表長為n)改成單鏈表存儲(chǔ)方式(其頭結(jié)點(diǎn)由頭指針head指向)的算法。設(shè)函數(shù)頭為:Node*CreateLinkedList(DataTypea[],intn)

35.以二叉鏈表作存儲(chǔ)結(jié)構(gòu),請寫出二叉鏈表類型定義;利用二叉樹遍歷的遞歸算法,試編寫求二叉樹高度的算法。