2017年中国农业科学院麻类所808数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 在下图所示的采用“存储一转发”方式的分组交换网络中，所有链路的数据传输速率为100Mbps 分组大小为1000B , 其中分组头大小20B , 若主机H1向主机H2发送一个大小为980000B 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是（ ）。
A.80ms
B.80.08ms C.80.16ms D.80.24ms 【答案】C
【解析】由题设可知，分组携带的数据长度为980B , 文件长度为980000B ，需拆分为1000个分组，加上头部后，每个分组大小为1000B , 总共需要传送的数据量大小为1MB 。由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过分组交换机。当t ＝1M ×8／100Mbps ＝80ms 时，HI 发送完最后一个比特；到达目的地，最后一个分组，需经过两个分组交换机的转发，
每次转发的时间为
所以，在不考虑分组拆
装时间和传播延时的情况下，当时，H2接受完文件，即所需的时间至少为80.16ms
2． 下面关于哈希（Hash ，杂凑）查找的说法正确的是（ ）。
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B. 除留余数法是所有哈希函数中最好的 C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可 【答案】C
【解析】若数据结构中存在关键字和K 值相等的记录，则必定在不需要进行比
较便可直接取得所查记录。在此，称这个对应关系f 为哈希（Hash ）函数，哈希函数的选择要视具体情况而定。
第 2 页，共 47 页
的存储位置上，由此，
3． —
组记录的关键码为
准得到的一次划分结果为（ ）。
则利用快速排序的方法，以第一个记录为基
【答案】C
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：46比84小，不交换； 第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为
一次划分结束。
4． 若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的是（ ）
I. 处理越界错 II. 置换页 III. 分配内存 A. 仅I 、II B .仅II 、III C. 仅I 、III D.I 、II 、和III 【答案】B
【解析】用户进程访问内存时缺页会发生缺页中断。发生缺页中断，系统地执行的操作可能是置换页面或分配内存。系统内没有越界的错误，不会进行越界出错处理。
5． 某计算机有16个通用寄存器，采用32位定长指令字操作码字段（含寻址方式位）为8位，Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式，若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store 指令中偏移量的取值范围是（ ）
A.-32768〜+32767 B.-32767〜+32768 C.-65536〜+65535 D.-65535〜+65536 【答案】A
【解析】寄存器个数指令编址方式如下所示：
16位补码取值范围为-32768〜+32767，所以偏移量取值范围为-32768〜+32767
第 3 页，共 47 页
偏移量有32-8-4-4=16位
6． 已知串
A.0123 B.1123 C.1231 D.1211 【答案】A
其Next 数组值为（ ）。
【解析】KMP 算法的next 数组建立的原则
7． 下述文件中适合于磁带存储的是（ ）。
A. 顺序文件 B. 索引文件 C. 哈希文件 D. 多关键字文件 【答案】A
【解析】磁带存储是一种顺序存储，顺序文件
是记录按其在文件中的逻辑顺序
依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。因此顺序文件适合磁带存储。
8． 设有数组数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素
【答案】B
【解析】在计算中，可以考虑按照列存放时，址。比如
顺序存放时，它是第
在内存的位置，比较容易计算元素的首地
个元素，由于首地址为BA ，
所以它的存储首地址为
的存储首地址为（ ）。
9． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。
【答案】D
【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。
10．对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储B. 以顺序方式存储，且数据元素有序
第 4 页，共 47 页