国家开放大学(数据结构)章节练习(2020.05.02)

来源：考试资料网

1.填空题树的度是指（）。

参考答案：树中所有结点的度的最大值

2 已知一个图的边数为m，则该图的所有顶点的度数之和为（）。

3.填空题设有一个链栈，栈顶指针为hs，现有一个s所指向的结点要入栈，则可执行操作（）和hs=s；。

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”）的值为（）。