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

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

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

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

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

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

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

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

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

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

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

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

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

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

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