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

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

1 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（）。

2.問答題給出G的鄰接矩陣和鄰接表。

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

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

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

5.問答題試給出用歸并排序法對該序列作升序排序時的每一趟的結(jié)果。

參考答案：初始 11，19，5，4，7，13，2，10
第一趟[11，19][4，5][7，13][2，10]

6.問答題說明成功查找到元素40需要經(jīng)過多少次比較？

7 判斷一個順序隊列（最多元素為m）為空的條件是（）。

8.問答題設棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4，e3，e6，e5，e1，則棧S的容量至少應該是多少？

參考答案：出隊序列是e2，e4，e3，e6，e5，e1的過程：
（1）e1入棧（棧底到棧頂元素是e1）
（2）...

9.填空題設一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為偶數(shù)，該葉節(jié)點的雙親結(jié)點的編號為9，該完全二叉樹一共有（）個結(jié)點。

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

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