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

來源：考試資料網

1.填空題樹的度是指（）。

參考答案：樹中所有結點的度的最大值

2 已知一個圖的邊數為m，則該圖的所有頂點的度數之和為（）。

3.填空題設有一個鏈棧，棧頂指針為hs，現有一個s所指向的結點要入棧，則可執(zhí)行操作（）和hs=s；。

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

4.問答題給定數列{8，17，5，9，21，10，7，19，6}，依次取序列中的數構造一棵二叉排序樹。并對上述二叉樹給出中序遍歷得到的序列。

（1）

（2）5，6，7，8，9，10，17，18，19，21

5 算法分析的目的是（）。

6.問答題一棵哈夫曼樹有n個葉結點，它一共有多少個結點？簡述理由？

參考答案：2n-1個，因為非葉結點數比葉結點數少一個。

7.問答題 如圖所示的二叉樹，給出中序遍歷序列、先序遍歷序列和后序遍歷序列。

（1）dgbaechif
（2）abdgcefhi
（3）gdbeihfca

8.填空題除了第1個和最后一個結點外，其余結點有且只有一個前驅結點和后繼結點的數據結構為（），每個結點可有任意多個前驅和后繼結點數的結構為（）。

參考答案：線性結構；非線性結構

9 在數據結構中，從邏輯上可以把數據結構分為（）。

10 串函數StrCmp（“abA”，”aba”）的值為（）。