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

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

1 若讓元素1，2，3依次進棧，則出棧順序不可能為（）。

2.填空題若以4，5，6，7，8作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是（）。

3.問答題 以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點的數(shù)據(jù)域的值，front、rear分別是鏈隊列的隊頭、隊尾指針。

malloc（sizeof（structnode））；rear->next=p；p

4 對n個元素進行冒泡排序，通常要進行n-1趟冒泡，在第j趟冒泡中共要進行（）次元素間的比較。

5.問答題設(shè)有查找表{5，14，2，6，18，7，4，16，3}，依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。并說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對上述二叉排序給出中序遍歷的結(jié)果。

（1）

（2）中序遍歷：中序2，3，4，5，6，7，14，16，18

6 設(shè)top是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，設(shè)用x接收棧頂元素，則出棧操作為（）。

7.判斷題圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。

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

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

9 設(shè)有一個12階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中（矩陣A的第一個元素為a1，1，數(shù)組b的下標從1開始），則矩陣A中第4行的元素在數(shù)組b中的下標i一定有（）。

10.填空題 如圖所示的二叉樹，其前序遍歷序列為（）。