2017年合肥工业大学计算机与信息学院848软件工程学科专业基础综合之数据结构考研仿真模拟题
● 摘要
一、填空题
1． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
2． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】
其中
表示，两栈顶指针为
则
队头和队尾指针分别为front 和rear , 则此循
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为
3． 已知一循环队列的存储空间为环队列判满的条件是（ ）
【答案】
4． 当两个栈共享一存储区时，栈利用一维数组当栈1空时，
【答案】
为_____，栈2空时
，
为_____，栈满时为_____。
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
5．
每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。
【答案】
.
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。
6． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
7． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
8． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
9． 组成串的数据元素只能是_____。
【答案】字符
10．设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。
【答案】23; 100CH
二、判断题
11．2，... ，n , 输出序列是
栈的输入序列是1，
【答案】
比如1进栈，然后出栈，
【解析】出栈序列不一定满足
12．设栈采用顺序存储结构。若已有杂性为
（ ）
【答案】
若
则有：
（ ）
个元素入栈，则将第i 个元素入栈时，入栈算法的时间复
【解析】由于该栈采用顺序存储结构，时间复杂度应该为0（1）。
13．若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。（ ）
【答案】×
【解析】堆中某个节点的值总是不大于或不小于其父节点的值，这个并不是二叉排序树的性质。
14．完全二叉树肯定是平衡二叉树。（ ）
【答案】×
【解析】从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。
15．在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ）
【答案】×
【解析】不一定。插入二叉排序树的原则：将新节点元素值与根结点元素值相比较，如小于
根结点元素值则插入到左子树口，否则插入到右子树中。所以就可能插在一个度为1的结点下面。
16．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）
【答案】×
【解析】排序的稳定性指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，
且ri 在rj 之前，而在排序后的
序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。
17．栈和队列都是限制存取点的线性结构。（ ）
【答案】
18．即使有向无环图的拓扑序列唯一，也不能唯一确定该图。（ ）
【答案】×
【解析】如果有向无环图的拓扑序列唯一，则能够确定每个结点的唯一前驱和后继，因此能够确定该图。
19．串长度是指串中不同字符的个数。（ ）
【答案】
【解析】不是，串长度是指串中字符的总个数。需要注意的是，在计算字符串的长度时，不要漏掉了空格。
20．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）
【答案】
【解析】数据的逻辑结构是指数据元素之间的逻辑关系。
三、算法设计题
21．编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。
【答案】算法如下：
//全局变量链表头指针head ,
pre
//将BiTree 树中的所有叶结点链成带头结点的双链表
//若bt 不空
//中序遍历左子树
//叶结点
//第一个叶结点
//生成头结点
//头结点的左链空，右链指向第一个结点