2016年中国刑事警察学院计算机软件综合之数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。
答:D
【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息，解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b ; 结点b 无左子树，左链域指向其前驱结点山结点c 无左子树，左链域指向其前驱结点b ，无右子树，右链域指向其后继结点a 。所以正确选项为D 。
2． 某计算机的Cache 共有16块，采用2路组相联映射方式（即每组2块）。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache 组号是（ ）。
A.0 B.2 C.4 D.6 答:C
【解析】首先根据主存地址计算所在的主存块号，然后根据组相联映射的映射关系K=ImodQ（K 代表Cache 的组号，I 代表主存的块号，Q 代表Cache 的组数）来计算Cache 的组号。由于每个主存块大小为32字节，按字节编址，那么主存129号单元所在的主存块号是4, Cache 共有16，故Cache 有8组，按照上面的公式可以计算得到块，采用2路组相联映射方式（即每组2块）
Cache 的组号=4mod8=4。
3． 下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务 B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先 答:B
【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，因此首先排除时 间片轮转算法；因为作业调度算法中没有时间片轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个? 我们可以通过分析得到，非抢占式短任务优先算法不能解决饥饿问题，因为当一个系统短任务源源不断到达是，长任务必然会得不到 调度，产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法，并以高响应比值优先调度。这样，无论短任务或长任务，均可以得到调度，而且，较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有尚响应比优先算法。
4． 设栈S 和队列Q 的初始状态为空，元素
后即进队列Q ，若6个元素出队的序列是
A.6 B.4 C.3 D.2 答:C
5． 某以太网拓扑及交换机当前转发表如下图所示，主机发送1个数据帧，主机
A. B. C. D.
收到该帧后，向主机
交换机对这两个帧的转发端口分别是（ ）
依次通过栈S ，一个元素出栈 则栈S 的容量至少应该是（ ）。
向主机
发送一个确认帧，
答:B
【解析】
第一次交换机没有录这个数据报源MAC
地址的信息
的信息，只能选择从其他端口全部发送，同时记
确认帧发送时已经有
的信息
了所以只用从1端口转发。
6． 若一棵二叉树的前序遍历序列和后序遍历序列分别为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棵二叉树的中序序列分别为： （1）4. 3. 2. 1， （2）3, 4, 2, 1 （3）2, 4, 3, 1 （4）2, 3, 4，1 （5）1，4，3, 2 （6）1, 3, 4, 2 （7）1，2, 4, 3 （8）1, 2, 3, 4
显然选项C 的中序序列不会出现。
7． 下列关于图的叙述中，正确的是（ ）。
I. 回路是简单路径
II. 存储稀疏图，用邻接矩阵比邻接表更省空间 III. 若有向图中存在拓扑序列，则该图不存在回路 A. 仅 II B. 仅 I 、II C. 仅III D. 仅 I 、III 答:C