2018年西安交通大学前沿科学技术研究院814计算机基础综合之数据结构考研核心题库
● 摘要
一、单项选择题
1． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素, 则关键字的比较次数最多是（ ）。
A.4
B.5
C.6
D.7
【答案】B
【解析】
折半查找法在查找不成功时和给定值进行比较的关键字个数最多为
题中, n=16, 故比较次数最多为5。
2． —个多道批处理系统中仅有P1和P2两个作业, P2比P1晚5ms 到达。它们的计算和作顺序如下:P1:计算60ms
, , 计算20ms ; P2:计算120ms
,
不考虑调度和切换时间, 则完成两个作业需要的时间最少是（ ）。
A.240ms
B.260ms
C.340ms
D.360ms
【答案】B 。
【解析】考查处理系统的性能计算, 由于P2比P1晚5ms 到达, P1先占用CPU , 根据P1和P2的执行过程, 作业运行的甘特图如下所示, 故答案为B 。
, 在本操, 计算40ms 若
图 甘特图
3． 若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。
A. 单链表
B. 双向链表
C. 单循环链表
D. 顺序表
【答案】D
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素。
4． 对一组数据(2, 12, 16, 88, 5, 10) 进行排序, 若前三趟排序结果如下:
第一趟:2, 12, 16, 5, 10, 88
第二趟:2, 12, 5, 10, 16, 88
第三趟:2, 5, 10, 12, 16, 88
则采用的排序方法可能是（ ）。
A. 起泡排序
B. 希尔排序
C. 归并排序
D. 基数排序
【答案】A
【解析】题目中所给的三趟排序过程, 显然是使用起泡排序方法, 每趟排序时从前往后依次比较, 使大值“沉底”。希尔排序的基本思想是:先对序列进行“宏观调整”, 待序列中的记录“基本有序”时再进行直接插入排序。宏观调整的方法是:通过某种规则将大的待排序序列分割为若干小的待排序序列, 再依次对这些小的序列直接插入排序。宏观调整可以多次, 每次分割的序列数逐渐增多, 而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序列合并为一个大的有序序列, 然后“逐趙归并”, 直至整个序列为有序为止。基数排序是分配排序的一种, 这类排序不是通过关键字比较, 而是通过“分配”和“收集”过程来实现排序的。本题中, 很容易看出大值逐渐“沉底”, 显然使用的是起泡排序法。
5． 在虚拟存储管理中, 地址变换机构将逻辑地址变换为物理地址, 形成该逻辑地址的阶段是（ ）。
A. 编辑
B. 编译
C. 链接
D. 装载
【答案】B
【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本, 不涉及到任何与计算机运行相关的事; 编译是由编译程序将用户源代码编译成若干个目标模块, 源地址编译成目标程序时, 会形成逻辑地址; 链接是由链接程序将编译后形成的一组目标模块, 以及所需库函数链接, 形成完整的装入模块; 装入是由装入程序将装入模块装入内存。
6． 设二维数组
A.(i﹣1)*n＋j
B.(i﹣1)*n＋j ﹣l
C.i*(j﹣1)
D.j*m＋i ﹣l
【答案】A (即m 行n 列) 按行存储在数组中，则二维数组元素A[i，j]在一维数组B 中的下标为（ ）。
【解析】前i ﹣1的元素个数为(i﹣1)*n，所以二维数组元素A[i，j]在一维数组B 中的下标为(i﹣1)*n＋j 。需要注意数组B 的下标是从0开始，还是从1开始。
7． 某以太网拓扑及交换机当前转发表如下图所示, 主机后, 向主机
A.
C.
D. 和和 B.{2, 3}和{1} 和
{1}
向主机发送1个数据帧, 主机收到该帧发送一个确认帧, 交换机对这两个帧的转发端口分别是（ ）
【答案】B
【解析】
第一次交换机没有
这个数据报源MAC 地址的信息的信息, 只能选择从其他端口全部发送, 同时记录, 确认帧发送时已经有的信息了所以只用从1端口转发。
8． n 个结点的线索二叉树上含有的线索数为（ ）。
A.2n
B.n ﹣1
C.n ＋1
D.n
【答案】C
【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n ＋1个空链域。