2017年杭州师范大学阿里巴巴商学院826计算机基础之数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 设有两个串S1和S2, 求S2在S1中首次出现的位置的运算称作（ ）。
A. 求子串
B. 判断是否相等
C. 模型匹配
D. 连接
【答案】C
【解析】常用的串的基本操作有七种，INDEX （s ，t ）是其中的定位函数，这种运算就是所说的模式匹配。
2． 若一棵二叉树的前序遍历序列为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 。
3． 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）。
A.
B.
C.
D. 字节
字节
字节
字节
【答案】C
【解析】段内位移的最大值就是最大段长。段号长度占了8位，剩下32-8=24位是段内位移空间，因此最大段长为
B 。
4． 若一棵二叉树的前序遍历序列和后序遍历序列分别为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 的中序序列不会出现。
5． 下列选项中，不会引起指令流水线阻塞的是（ ）。
A. 数据旁路（转发）
B. 数据相关
C. 条件转移
D. 资源冲突
【答案】A
【解析】由于采用流水线方式，相邻或相近的两条指令可能会因为存在某种关联，后一条指令不能按照原指定的时钟周期运行，从而使流水线断流。有三种相关可能引起指令流水线阻塞：
①结构相关，又称资源相关；
②数据相关；
③控制相关，又称指令相关，主要由转移指令引起。
6． 数据链路层采用后退N 帧（GBN ）协议，发送方已经发送了编号为0〜7的倾。当计时器超时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是（ ）。
A.2
B.3
C.4
D.5
【答案】C
【解析】后退N 帧协议，即GO-BACK-N 策略的基本原理是，当接收方检测出失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧；或者当发送方发送了N 个帧后，若发现该N 帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方就不得不重新发送出错帧及其后的N 帧。本题收到3号帧的确认，说明0，1，2，3号帧已经收到，丢失的是4，5，6, 7号帧，共4帧。因此答案为C 项。
7． 下面关于求关键路径的说法不正确的是（ ）。
A. 求关键路径是以拓扑排序为基础的
B. —个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D. 关键活动一定位于关键路径上
【答案】C
【解析】一个事件的最迟开始事件是这个事件能够拖到的最晚时间，从这个时刻开始做完这个事件不影响其后续事件的开始时间。
8． 在系统内存中设置磁盘缓冲区的主要目的是（ ）。
A. 减少磁盘I/O次数
B. 减少平均寻道时间
C. 提高磁盘数据可靠性
D. 实现设备无关性
【答案】A
【解析】访问磁盘的开销远远大于访问内存的开销。磁盘缓冲区便是利用主存中的存储空间，来暂存从磁盘中读出（或写入）的信息，频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。
9． 在采用中断I/O方式控制打印输出的情况下，CPU 和打印控制接口中的I/O端口之间交换的信息不可能是（ ）。
A. 打印字符