2018年塔里木大学信息工程学院813数电与数据结构之数据结构考研核心题库
● 摘要
一、单项选择题
1． 某同步总线的时钟频率为100MHz , 宽度为32位, 地址/数据线复用, 每传输一个地址或数据占用一个时钟周期。若该总线支持突发(猝发) 传输方式, 则一次“主存写”总线事务传输128位数据所需要的时间至少是（ ）。
A.20ns
B.40ns
C.50ns
D.80ns
【答案】C 。
【解析】总线的时钟频率为100MHz , 则时钟周期为10ns 。数据是128位, 总线宽度是32位, 所以需要4个时钟周期, 而传输地址还需要一个周期, 所以传输一个128位的数据至少需要5个时钟周期, 所以至少需要。
2． 一个C 语言程序在一台32位机器上运行. 程序中定义了3个变量x 、Y 和z ，其中x 和z 为int
Y 为short 型. 当x ＝127，Y ＝-9时，x 、Y 和z 的值分别是. 型，执行赋值语句z ＝x ＋Y 后，（ ）
A.x ＝0000007FH ， Y ＝FFF9H ， z ＝00000076H
B.x ＝0000007FH ， Y ＝FFF9H ， z ＝FFFF0076H
C.x ＝0000007FH ， Y ＝FFF7H ， z ＝FFFF0076H
D.x ＝0000007FH ， Y ＝FFF7H ， z ＝00000076H
【答案】D
【解析】当两个不同长度的数据，要想通过算术运算得到正确的结果，必须将短字长数据转换成长字长数据，这被称为“符号扩展”.例如，x 和z 为int 型，数据长32位，Y 为short 型，数据长16位，因此首先应将y 转换成32位的数据，然后再进行加法运算.
运算采用补码的形式，而x 的补码是0000007FH ，Y 的补码是FFFFFFF7H ，所以x ＋Y ＝00000076H.
3． 用希尔排序方法对一个数据序列进行排序时, 若第1趟排序结果为9, 1, 4, 13, 7, 8, 20, 23, 15, 则该趟排序采用的增量(间隔) 可能是（ ）
A.2
B.3 C.4
D.5
【答案】B
【解析】对于A , 增量为2, 那么9, 4, 7, 20, 15是一组, 而它们是无序的, 所以A 错误
对于C , 增量为4, 那么9, 7, 15是一组, 而它们是无序的, 所以C 错误
对于D , 增量为5, 那么9, 8是一组, 降序, 1, 20是一组, 而它们是升序, 所以D 也错误。对于B , 分为3组:9, 13, 20; 1, 7, 23; 4, 8, 15都是升序有序, 所以B 正确
4．
操作系统的子系统通常由四个层次组成, 每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是（ ）。
A. 用户级
B. 用户级
C. 用户级
D. 用户级
【答案】A 。
【解析】对于一次设备的调用, 操作系统为用户准备了系统调用的接口, 当用户使用设备时, 首先在用户程序中发起一次系统调用, 操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理, 根据调用格式和形参, 再转到相应的设备驱动程序去处理; 大部分设备在运行时是需要时间的, 所以设备驱动程序会以中断方式驱动设备, 即设置好控制寄存器参数和中断向量等参数后阻塞自己; 当设备准备好或所需数据到达后设备硬件发出中断, 设备驱动程序唤醒, 将数据按上述调用顺序逆向回传到用户程序中, 或继续驱动设备执行下一条指令。因此, 软件从上到下分为四个层次:用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。
5． 若需在的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序
【答案】C
【解析】稳定排序有:插入排序、起泡排序、归并排序、基数排序。不稳定排序有:快速排序、
堆排序、shell 排序。时间复杂度平均为的有:归并排序、堆排序、shell 排序、快速排序。
6． 对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次釆用的增量是（ ）。
A.1
B.4
C.3
D.2
【答案】B
【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的
软件、设备无关软件、设备驱动程序、中断处理程序 软件、设备无关软件、中断处理程序、设备驱动程序 软件、设备驱动程序、设备无关软件、中断处理程序 软件、中断处理程序、设备无关软件、设备驱动程序
序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的增量是4。
7． 最大容量为n 的循环队列，队尾指针是rear ，队头:front ，则队空的条件是（ ）。
A.(rear+1)MODn＝front
B.rear ＝front
C.rear+1＝front
D.(rear-1)MODn＝front
【答案】B
【解析】循环队列队空的条件是:rear ＝front 。循环队列队满的条件，
通常采用(rear+1)%MAXQSIZE＝front 来判定队满，其中MAXQSIZE 表示队列的长度。
8． 在下图所示的采用“存储一转发”方式的分组交换网络中，所有链路的数据传输速率为100Mbps ，分组大小为1000B ，其中分组头大小20B ，若主机H1向主机H2发送一个大小为980000B 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是（ ）
.
A.80ms B.
C.
D.
【答案】c
【解析】由题设可知，分组携带的数据长度为980B ，文件长度为980000B ，需拆分为1000个分组，加上头部后，每个分组大小为1000B ，总共需要传送的数据量大小为IMB. 由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过分组交换机. 当t ＝lM ×8/100Mbps＝80ms 时，HI 发送完最后一个比特；到达目的地，最后一个分组，需经过两个分组交换机的转发，每次转发的时间为t 0＝lK ×8/100Mbps＝，所以，在不考虑分组拆装时间和传播延时的情况下，当时，H2接受完文件，
即所需的时间至少为
9． n 个结点的线索二叉树上含有的线索数为（ ）。
A.2n
B.n ﹣1
C.n ＋1
D.n
【答案】C