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

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

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

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

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

4 在一個棧頂指針為top的鏈棧中，將一個p指針所指的結(jié)點入棧，應(yīng)執(zhí)行（）。

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

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

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

參考答案：順序存儲；鏈式存儲

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

（1）

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

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

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

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

10.問答題解釋順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的特點，并比較順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點。

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