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

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

1.填空題要在一個單向鏈表中p所指向的結(jié)點之后插入一個S所指向的新結(jié)點，若鏈表中結(jié)點的指針域為next，可執(zhí)行（）和p->next==s的操作。

參考答案：s->next===p->next；

2.填空題圖的深度優(yōu)先搜索遍歷類似于樹的（）遍歷。

3.填空題在一個鏈隊中，設(shè)f和r分別為隊頭和隊尾指針，則插入s所指結(jié)點的操作為r->next=s；和（）（結(jié)點的指針域為next）。

參考答案：r->next=s；

4 利用3、6、8、12這四個值作為葉子結(jié)點的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子結(jié)點中的最長帶權(quán)路徑長度為（）。

5 有序表為{1，2，4，6，10，18，20，32}，用課本中折半查找算法查找值18，經(jīng)（）次比較后成功查到。

6 一棵具有35個結(jié)點的完全二叉樹，最后一層有（）個結(jié)點。

7.填空題具有m個葉子結(jié)點的哈夫曼樹共有（）個結(jié)點。

8.填空題一棵二叉樹總結(jié)點數(shù)為11，葉結(jié)點數(shù)為5，該樹有（）個雙分支結(jié)點，（）個單分支結(jié)點。

9.填空題設(shè)有一個頭指針為head的單向鏈表，p指向表中某一個結(jié)點，且有p->next==NULL，通過操作（），就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表。

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

10.問答題 以下函數(shù)為鏈棧的進棧操作，x是要進棧的結(jié)點的數(shù)據(jù)域，top為錢頂指針，補充程序。