國(guó)家開放大學(xué)(數(shù)據(jù)結(jié)構(gòu))章節(jié)練習(xí)(2020.04.13)

來源：考試資料網(wǎng)

1 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)10行8列的稀疏矩陣A，其相應(yīng)的三元組表共有6個(gè)元素，矩陣A共有（）個(gè)零元素。

2 一組記錄的關(guān)鍵字序列為（47，80，57，39，41，46），利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（）。

3.填空題有一個(gè)有序表{2，3，9，13，33，42，45，63，74，77，82，95，110}，用折半查找法查找值為82的結(jié)點(diǎn)，經(jīng)（）次比較后查找成功。

4 在一個(gè)棧頂指針為top的鏈棧中，將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（）。

5.填空題數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為（）。

參考答案：樹形結(jié)構(gòu)

6.填空題串的兩種最基本的存儲(chǔ)方式是（）和（）。

參考答案：順序存儲(chǔ)；鏈?zhǔn)酱鎯?chǔ)

7.問答題設(shè)有查找表{5，14，2，6，18，7，4，16，3}，依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。并說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對(duì)上述二叉排序給出中序遍歷的結(jié)果。

（1）

（2）中序遍歷：中序2，3，4，5，6，7，14，16，18

8.填空題哈希函數(shù)是記錄關(guān)鍵字值與該記錄（）之間所構(gòu)造的對(duì)應(yīng)關(guān)系。

參考答案：存儲(chǔ)地址

9.填空題哈希表是用來存放查找表中記錄序列的表，每一個(gè)記錄的存儲(chǔ)位置是以該記錄得到關(guān)鍵字為（），由相應(yīng)哈希函數(shù)計(jì)算所得到的（）。

參考答案：自變量；函數(shù)值

10.問答題解釋順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)，并比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。

參考答案：順序結(jié)構(gòu)存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是統(tǒng)一的，要求內(nèi)存中存儲(chǔ)單元的地址必須是連續(xù)的。