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

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

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

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

2 數(shù)據(jù)結(jié)構(gòu)是一門研究計(jì)算機(jī)中（）對(duì)象及其關(guān)系的科學(xué)。

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

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

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

5.填空題在一棵樹中，每個(gè)結(jié)點(diǎn)的（）或者說每個(gè)結(jié)點(diǎn)的（）稱為該結(jié)點(diǎn)的（），簡(jiǎn)稱為孩子。

參考答案：子樹的根；后繼結(jié)點(diǎn)；孩子結(jié)點(diǎn)

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

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

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

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

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

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

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