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

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

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

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

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

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

參考答案：2n-1個(gè)，因?yàn)榉侨~結(jié)點(diǎn)數(shù)比葉結(jié)點(diǎn)數(shù)少一個(gè)。

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

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

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

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

6.問答題 下列是在具有頭結(jié)點(diǎn)單向鏈表中刪除第i個(gè)結(jié)點(diǎn)的算法，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z(yǔ)句。

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

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

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

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

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