自考真題是考生復習備考的一大法寶，需要好好利用，而且年份離的越近，參考價值越高。以下是希賽網自考頻道整理的全國2020年10月自考數據結構導論02142真題，考生可參考試卷題型、分值、重點考試內容及答題規范，參考答案現在暫未公布，希賽網將持續更新。

全國2020年10月自考數據結構導論02142真題

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

1.數據的最小標識單位是

A.數據項

B.數據類型

C.數據元素

D.數據變量

2.下面程序段的時間復雜度為

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.設帶頭結點的單向循環鏈表的頭指針變量為head,則空循環鏈表的判定條件是

A.head= =NULL

B.head->next= =NULL

C.head->next= =head

D.head=NULL

4.設輸入序列為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.隊列是一種線性表,其具有的特征是

A.先進后出

B.只能插入

C.只能刪除

D.先進先出

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

A.10

B.19

C.28

D.55

7.設某棵二叉樹中只有度數為0和度數為2的結點且度數為0的結點數為n,則這棵二叉樹中共有結點個數是

A.2n

B.n+l

C.2n-1

D.2n+l

8.設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號,若結點i有左孩子,則編號為i結點的左孩子結點的編號為

A.2i+1

B.2i

C.i/2

D.2i-1

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

A.CBEFDA

B.FEDCBA

C.CBEDFA

D.CEFBDA

10.一個具有n個頂點的無向完全圖的邊數為

A.n-1

B.n2

C.n(n+1)/2

D.n(n-1)/2

11.設某有向圖中有n個頂點,則該有向圖對應的鄰接表中表頭結點個數為

A.n-1

B.n

C.n+1

D.2n-1

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

A.(n-1)/2

B.n/2

C.(n+1)/2

D.n

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

A.奇數

B.素數

C.偶數

D.合數

14.下列排序算法中,穩定的排序算法是

A.堆排序

B.快速排序

C.直接選擇排序 

D.冒泡排序

15.下列四個序列中,是堆的序列為

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.數據的四類基本邏輯結構是:線性結構、樹形結構、圖結構和   ▲    。

17.數據的存儲結構有順序存儲、鏈式存儲、索引存儲和   ▲   存儲。

18.順序表插入算法的時間復雜度是   ▲   。

浙02142# 數據結構導論試題 第 2頁(共4頁)19.設r指向單鏈表的最后一個結點,要在最后一個結點之后插入s所指的結點,需執行的語句序列是r->next=s;r=s;   ▲   。

20.一般情況下,函數的嵌套調用和程序遞歸的處理都是用   ▲   來實現的。

21.m 行n列的矩陣有t個非零元素,當t滿足   ▲   條件時,稱該矩陣為稀疏矩陣。

22.二叉樹的第i(i≥1)層上至多有   ▲   個結點。

23.雙親表示法由一個一維數組構成,數組的每個分量包含兩個域: ▲ 和雙親域。

24.無向圖的鄰接矩陣是一個   ▲   矩陣。

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

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

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

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

三、應用題:本大題共5小題,每小題6分,共30分。

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

30.已知二叉樹如題30圖所示,請將該二叉樹轉換為對應的森林。

31.設某通信系統中一個待傳輸的文本有6個不同字符,它們的出現頻率分別是0.5,0.7,1.4,2.2,2.4,2.8,試畫出哈夫曼樹,并給出每個字符的哈夫曼編碼。(要求任一結點的左孩子權值小于右孩子)

32.選定散列函數為 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,請分別寫出直接選擇排序和冒泡排序的第一趟排序結果。

四、算法設計題:本大題共2小題,每小題7分,共14分。

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

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