2017年北京市培养单位计算机网络信息中心863计算机学科综合(专业)之数据结构考研题库
● 摘要
一、填空题
1． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
2． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。
【答案】23; 100CH
3． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树 【解析】二叉排序树
或者是一棵空树，或者是具有下列性质的二叉树：①若它
的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
4． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
5． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
6． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
7． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
8． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
9． 试利用下列栈和串的基本操作完成下述填空题。
initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数；
置串 判串 返回联接
empty （st ） 判串空函数
{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。）
注意：毎个空格只填一个语句。 【答案】（1）（2）（3）
栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符
为空串；
是否相等的函数；
之后的串；
length （st ） 返回串st 的长度；
sub （S , i , 1） 返回S 中第i 个字符；
（4）（5）（6）（7）exp （8）（9）exp （10）（11
）（12）
如ch 是运算符，则入操作符栈s 判栈8是否为空
若读出ch 是操作数且栈为空，则按出错处理
若ch 是操作数且栈非空，则形成部分中缀表达式
取栈顶操作符 操作符取出后，出栈
将pre 的最后一个字符（操作数）加入到中缀式exp 的最后
10．设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
二、判断题
11．哈夫曼树无左右子树之分。（ ）
【答案】×
【解析】哈夫曼树就是一棵二叉树。
12．若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【答案】×
【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
13．若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。（ ）
【答案】×
【解析】堆中某个节点的值总是不大于或不小于其父节点的值，这个并不是二叉排序树的性质。
14．—个稀疏矩阵
【答案】×
【解析】稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。
15．队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ）
【答案】
【解析】队列只在下端（队尾）增加，在上端（队头）减少。
采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m
的转置运算。（ ）
和n 的值互换，则就完成了