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

填空题
树的度是指（）。
答案：树中所有结点的度的最大值
单项选择题
已知一个图的边数为m，则该图的所有顶点的度数之和为（）。
A.2m
B.m
C.2m+1
D.m/2
填空题
设有一个链栈，栈顶指针为hs，现有一个s所指向的结点要入栈，则可执行操作（）和hs=s；。
答案：s->next=hs；
问答题
给定数列{8，17，5，9，21，10，7，19，6}，依次取序列中的数构造一棵二叉排序树。并对上述二叉树给出中序遍历得到的序列。
答案：
（1）

（2）5，6，7，8，9，10，17，18，19，21
单项选择题
算法分析的目的是（）。
A.找出数据结构的合理性
B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进
D.分析算法的易懂性和文档性
问答题
一棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由？
答案：2n-1个，因为非叶结点数比叶结点数少一个。
问答题
如图所示的二叉树，给出中序遍历序列、先序遍历序列和后序遍历序列。
答案：
（1）dgbaechif
（2）abdgcefhi
（3）gdbeihfca
填空题
除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为（），每个结点可有任意多个前驱和后继结点数的结构为（）。
答案：线性结构；非线性结构
单项选择题
在数据结构中，从逻辑上可以把数据结构分为（）。
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部机构
单项选择题
串函数StrCmp（“abA”，”aba”）的值为（）。
A.1
B.0
C.“abAaba”
D.-1