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

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

1.填空題一個有序表{3，4，10，14，34，43，46，64，75，78，90，96，130}用折半查找法查找值為90的結(jié)點，經(jīng)（）次比較后查找成功。

2.問答題計算其帶權(quán)路徑長度WPL。

參考答案：其帶權(quán)路徑長度WPL值為270。

3.問答題一棵哈夫曼樹有n個葉結(jié)點，它一共有多少個結(jié)點？簡述理由？

參考答案：2n-1個，因為非葉結(jié)點數(shù)比葉結(jié)點數(shù)少一個。

4.問答題刪除鏈表的第一個結(jié)點。

參考答案：head=head->next；

5.填空題對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的（）、（）和（）三項信息。

參考答案：行下標(biāo)；列下標(biāo)；非零元素值

6.問答題 下列是在具有頭結(jié)點單向鏈表中刪除第i個結(jié)點的算法，請在空格內(nèi)填上適當(dāng)?shù)恼Z句。

q=q->next；p=q->next；q->next=p->next

7 在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（）倍。

8 已知如圖所示的一個圖，若從頂點V1出發(fā)，按廣度優(yōu)先法進(jìn)行遍歷，則可能得到的一種頂點序列為（）。

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

10.問答題設(shè)計一棵哈夫曼樹。