2017年江西理工大学信息工程学院873数据结构考研题库
● 摘要
一、选择题
1． 某以太网拓扑及交换机当前转发表如下图所示，主机发送1个数据帧，主机
A. B. C. D.
收到该帧后，向主机
交换机对这两个帧的转发端口分别是（ ）
向主机
发送一个确认帧，
【答案】B
【解析】
第一次交换机没有录这个数据报源MAC
地址的信息
的信息，只能选择从其他端口全部发送，同时记
确认帧发送时已经有
的信息
了所以只用从1端口转发。
2． 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）。
A. B. C. D.
字节 字节 字节 字节
【答案】C
【解析】段内位移的最大值就是最大段长。段号长度占了8位，剩下32-8=24位是段内位移空间，因此最大段长为B 。
3． 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）
。
【答案】B
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：28比72小，不交换； 第二次比较：28比5大，交换，此时为第三次比较：16比28小，不交换； 第四次比较：32比28大，交换，此时为第五次比较：28比2大，交换，此时为第六次比较：28比12大，不交换； 第七次比较：28比60小，交换，此时为一次划分结束。
4． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度 B. 为了能在二叉树中方便地进行插入与删除 C. 为了能方便地找到双亲 D. 使二叉树的遍历结果唯一 【答案】A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
5． 某时刻进程的资源使用情况如下表所示
此时的安全序列是（ ）。 A.P1, P2, P3, P4 B.P1, P3, P2, P4 C.P1, P4, P3, P2 D 不存在 【答案】D
【解析】典型的死锁避免算法，银行家算法的应用。银行家算法是操作系统中的一个重点知识单元，考生对此应该非常熟悉，本题并无难点。分析一下下表，可以看到，经过P1, P4的运行以后，可用资源是2, 2，1，而 P2, P3所需资源分别是1，3, 2和1，3，1。所以剩余资源已经不够P2或P3的分配，亦即找不到能够安全运行的序 列，因此此时是处于不安全状态，所以不存在这样的安全序列。
6． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表 C. 双链表
D. 仅有尾指针的单循环链表 【答案】D
【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。
7． 下述文件中适合于磁带存储的是（ ）。
A. 顺序文件 B. 索引文件 C. 哈希文件 D. 多关键字文件 【答案】A
【解析】磁带存储是一种顺序存储，
顺序文件
是记录按其在文件中的逻辑顺序
依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。因此顺序文件适合磁带存储。
8． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0（n ） B.0（n+e） C.0（n*n） D.0（n*n*n） 【答案】B
【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0（n+e）
9． 用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，则校验位数至少为（ ）
A.2 B.3 C.4 D.5
【答案】C