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

絕密考試結(jié)束前

★

全國(guó)年月高等教育自學(xué)考試

202010

數(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ù)據(jù)的最小標(biāo)識(shí)單位是

1.

數(shù)據(jù)項(xiàng)數(shù)據(jù)類型數(shù)據(jù)元素?cái)?shù)據(jù)變量

A.B.C.D.

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

2.

;;

for(inti=0i<ni++)

;;

for(intj=0j<nj++)

;

a[i][j]=i*j

2

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

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

3.head,

A.head==NULLB.head->next==NULL

C.head->next==headD.head=NULL

設(shè)輸入序列為則通過(guò)棧的作用后可以得到的輸出序列為

4.1、2、3、4、5、6,

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

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

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

5.,

先進(jìn)后出只能插入只能刪除先進(jìn)先出

A.B.C.D.

設(shè)有一個(gè)階的下三角矩陣包括對(duì)角線按照從上到下從左到右的順序存儲(chǔ)到連續(xù)

6.10A(),、

的個(gè)存儲(chǔ)單元中每個(gè)數(shù)組元素占個(gè)字節(jié)的存儲(chǔ)空間則地址與的地址之差為

55,1,a54a00

A.10B.19C.28D.55

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

02142#1(4)

設(shè)某棵二叉樹中只有度數(shù)為和度數(shù)為的結(jié)點(diǎn)且度數(shù)為的結(jié)點(diǎn)數(shù)為則這棵二叉樹

7.020n,

中共有結(jié)點(diǎn)個(gè)數(shù)是

A.2nB.n+lC.2n-1D.2n+l

設(shè)按照從上到下從左到右的順序從開始對(duì)完全二叉樹進(jìn)行順序編號(hào)若結(jié)點(diǎn)有左孩

8.、1,i

子則編號(hào)為結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為

,i

A.2i+1B.2iC.i/2D.2i-1

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

9.ABCDEF,CBAEDF,

果為

A.CBEFDAB.FEDCBAC.CBEDFAD.CEFBDA

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

10.n

2

A.n-1B.nC.n(n+1)/2D.n(n-1)/2

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

11.n,

A.n-1B.nC.n+1D.2n-1

若查找每個(gè)記錄的概率均等則在具有個(gè)記錄的連續(xù)順序文件中采用順序查找算法查找

12.,n

一個(gè)記錄其平均查找長(zhǎng)度為

,ASL

A.(n-1)/2B.n/2C.(n+1)/2D.n

設(shè)散列表中有個(gè)存儲(chǔ)單元散列函數(shù)則最好選擇小于散列表長(zhǎng)度

13.n,H(key)=key%p,p

的

n

奇數(shù)素?cái)?shù)偶數(shù)合數(shù)

A.B.C.D.

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

14.,

堆排序快速排序直接選擇排序冒泡排序

A.B.C.D.

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

15.,

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

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

非選擇題部分

注意事項(xiàng):

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

,。

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

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

16.:、、▲。

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

17.、、▲。

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

18.▲。

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

02142#2(4)

設(shè)指向單鏈表的最后一個(gè)結(jié)點(diǎn)要在最后一個(gè)結(jié)點(diǎn)之后插入所指的結(jié)點(diǎn)需執(zhí)行的語(yǔ)

19.r,s,

句序列是;;

r->next=sr=s▲。

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

20.,▲。

行列的矩陣有個(gè)非零元素當(dāng)滿足條件時(shí)稱該矩陣為稀疏矩陣

21.mnt,t▲,。

二叉樹的第層上至多有個(gè)結(jié)點(diǎn)

22.i(i≥1)▲。

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

23.,:▲。

無(wú)向圖的鄰接矩陣是一個(gè)矩陣

24.▲。

設(shè)有散列函數(shù)和鍵值若但是則稱這種現(xiàn)象為

25.Hk1、k2,k1≠k2,H(k1)=H(k2),▲。

向一個(gè)長(zhǎng)度為的順序表中第個(gè)元素之前插入一個(gè)元素時(shí)需向后移動(dòng)

26.ni(1≤i≤n),▲

個(gè)元素

。

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

27.▲。

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

28.n,▲。

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

題圖給出了一個(gè)稀疏矩陣請(qǐng)寫出該稀疏矩陣的三元組表

29.29A,。

éù

ê050000ú

êú

ê000000ú

êú

ê0-10700ú

A=êú

ê060000ú

êú

ê000090ú

?ê?ú

000008

題圖

29

已知二叉樹如題圖所示請(qǐng)將該二叉樹轉(zhuǎn)換為對(duì)應(yīng)的森林

30.30,。

題圖

30

設(shè)某通信系統(tǒng)中一個(gè)待傳輸?shù)奈谋居袀€(gè)不同字符它們的出現(xiàn)頻率分別是

31.6,0.5,0.7,

試畫出哈夫曼樹并給出每個(gè)字符的哈夫曼編碼要求任一結(jié)點(diǎn)的

1.4,2.2,2.4,2.8,,。(

左孩子權(quán)值小于右孩子

)

選定散列函數(shù)為試用鏈地址法建立鍵值為

32.H(key)=keymod13,26,41,25,05,07,15,

的散列表

12,49,51,31,62。

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