2016年辽宁大学信息学院计算机专业相关知识之数据结构复试笔试仿真模拟题
● 摘要
一、选择题
1． 循环队列元素数是（ ）。
【答案】A
【解析】对于循环队列，需要深刻理解队头在队尾进行进队操作。
和队尾
的概念，在队头进行出队操作，
如果为负则元
可能为正也可能为负，为正时元素个数=
存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的
素的个数=所以统一的公式就是
2． 某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为90ns 、80ns 、70ns 和60ns , 则该计算机的CPU 时钟周期至少是（ ）。
A.90ns B.80ns C.70ns D.60ns 【答案】A
【解析】对于各功能段执行时间不同的指令流水线，计算机的CPU 时钟周期应当以最长的功能段执行时间为准。
3． 希尔排序的组内排序采用的是（ ）。
A. 直接插入排序 B. 折半插入排序 C. 快速排序 D. 归并排序 【答案】A
【解析】希尔排序基本思想是：先将整个待排元素序列按某个增量分割成若干个子序列，在子序列内进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
4．
已知操作符包括
将中缀表达式的后缀表达式
空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。
A.5 B.7 C.8 D.11
转换为等价
时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为
【答案】A 。
【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先出栈的运算符先计算，同优先级的运算符在栈中的先计算）
。表达式所列：
产生后缀表达式的过程如下表
通过上表可以看出，显然转换过程中同时保存在栈中的操作符的最大个数是5。
5． 采用指令Cache 与数据Cache 分离的主要目的是（ ）
A. 减低Cache 的缺失损失 B. 提高Cache 的命中率 C. 减低CPU 平均访问时间 D. 减少指令流水线资源冲突 【答案】D
【解析】指令流水线不会断流，预取过来的都是指令
6． 某二叉树结点的中序序列为BDAECF ，后序序列为DBEFCA ，则该二叉树对应的森林包括（ ）棵树。
A.1 B.2 C.3 D.4
【答案】C
【解析】由两序列可知，A 为根节点，ECF 为右子树，C 为右子树的根，F 为C 的右孩子。再由二叉树和森林的对应关系可知该二叉树对应的森林包括3棵树。根据中序序列和后序序列画出二叉树，根据二叉树得出对应的森林包含的树的棵数。
7． 已知一算术表达式的中缀表达式为其后缀形式为（ ）。
【答案】D 【解析】后缀表达式：在程序语言中，运算符位于两个操作数后面的表达式。
8． 在下面的排序方法中，辅助空间为的是（ ）。
A. 希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 【答案】D
9． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是（ ）。
A.1, 2.3.4 B.2，3, 4.1 C.3, 2, 4, 1 D.4, 3, 2, 1
【答案】C
【解析】题目中的二叉树的先序序列和后序序列正好相反，这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。
从左至右，这8棵二叉树的中序序列分别为：
相关内容
相关标签