國家開放大學(數據結構)章節(jié)練習(2020.04.16)

來源：考試資料網

1.問答題 以下函數在a[0]到a[n-1]中，用折半查找算法查找關鍵字等于k的記錄，查找成功返回該記錄的下標，失敗時返回-1，完成程序中的空格。

low<=high；mid；a[mid].key<k；high=mid-1；return-1

2 數據結構是一門研究計算機中（）對象及其關系的科學。

3 設top是一個鏈棧的棧頂指針，棧中每個結點由一個數據域data和指針域next組成，設用x接收樓頂元素，則出棧操作為（）。

4.問答題 以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域分別為left和right，數據域data為字符型，BT指向根結點）。

參考答案：（1）Inorder（BT->left）；
（2）printf（“%c”，BT->da...

5.填空題在一棵樹中，每個結點的（）或者說每個結點的（）稱為該結點的（），簡稱為孩子。

參考答案：子樹的根；后繼結點；孩子結點

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

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

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

9.問答題設棧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）...

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

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