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

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

1 對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在等概率情況下，平均查找長(zhǎng)度為（）。

2 把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（）。

3.填空題一棵二又樹沒有單分支結(jié)點(diǎn)，有6個(gè)葉結(jié)點(diǎn)，則該樹總共有（）個(gè)結(jié)點(diǎn)。

4 絨性表的順序結(jié)構(gòu)中，（）。

5 元素2，4，6按順序依次進(jìn)棧，則該棧的不可能的輸出序列是（）。

6 非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）。

7.問答題 以下是用頭插法建立帶頭結(jié)點(diǎn)且有n個(gè)結(jié)點(diǎn)的單向鏈表的程序，要求結(jié)點(diǎn)中的數(shù)據(jù)域從前向后依次為n，n-1，……，1，完成程序中空格部分。

（1）p
（2）q=p
（3）（NODE*）malloc（sizeof（NODE））
（4）q->next
（5）p

8.問答題對(duì)上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉樹描述建堆過程）。

9.填空題廣義表A（（a，b，c），（d，e，f））的表尾為（）。

參考答案：（（d，e，f））

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

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