2017年北京服装学院机械电子工程910数据结构与算法考研仿真模拟题
● 摘要
一、填空题
1． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
2． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】序查找效率一样为
3． 顺序栈用
【答案】
存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺
，
则结点
和
在同一层上的条件是
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
4． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
5． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ）而快速排序算法需要比较的次数达到最大，时间复杂度为
6． 阅读下列程序说明和裎序，填充程序中的_____。
本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：
（1）把根结点放入堆栈。
（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）
存放还没有转换过的结点，它的栈顶指针为
。
（3）重复（2）直到堆栈为空时为止。
（1）
{（2）
If （ （3） ）
} }} 【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。
7． 当两个栈共享一存储区时，栈利用一维数组当栈1空时，
【答案】
为_____，栈2空时
，
表示，两栈顶指针为则
为_____，栈满时为_____。
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
8． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
9． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
10．设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。
【答案】23; 100CH
11．在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。
【答案】
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，
所以
12．二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
二、选择题
13．若一棵二叉树的前序遍历序列为a ，e ，b ，d ，c ，后序遍历序列为b , c, d, e, a, 则根结点的孩子结点（ ）。
A. 只有e B. 有 e 、b C. 有 e 、c D. 无法确定 【答案】A 。
b , d, c, 后序遍历序列为b ，c , d, 【解析】由题目可知，若一棵二叉树的前序遍历序列为a , e，e , a , 其中a 为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为e , 而后序遍历的倒数第二个结点为e , 说 明a 的孩子结点只有e 。
14．在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
【答案】C
【解析】两个循环嵌套，那么语句x :=x＋l :
则被执行了次。
15．采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。
A. 数据元素过多 B. 负载因子过大 C. 哈希函数选择不当 D. 解决冲突的算法选择不好 【答案】D
【解析】开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。
16．用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（ ）
A. 存储效率 B. 数列函数