2017年河北大学电信学院893数据结构考研强化模拟题
● 摘要
一、选择题
1． 动态存储管理系统中，通常可有（ ）种不同的分配策略。
【答案】C
【解析】动态存储管理系统中有以下三种：首次拟合法、最佳拟合法、最差拟合法。①首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。②最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n 且最接近n 的空闲块进行分配。③最差拟合法，将可利用空间表中不小于n 且是链表中最大的空闲块的一部分分配给用户。
2． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
【答案】D
【解析】至少探测次数
3． 假定下列指令已装入指令寄存器。则执行时不可能导致CPU 从用户态变为内核态（系统态）的是（ ）。 A.
B. 产生软中断
D.
【答案】C
【解析】A 项，除法操作出现除数为零的情况时，会产生内中断，CRJ 切换为内核态进行中断处理；B 项，直接产生中断，会切换到内核态；D 项，addr 出现非法地址，会出现中断，进而切换到内核态。
4． 在参考摸型中，下列功能需由应用层的相邻层实现的是（ ）
A. 对话管理
B. 数据格式转换
C. 路由选择
D. 可靠数据传输
【答案】B
C.NOTRO ；寄存器R0的内容取非 把地址处的内存数据放入寄存器R0中
【解析】应用层的相邻层即为表示层，表示层负责管理数据的压缩、加密与解密、格式装换等，故答案为B 。
5． 在子网192.168.4.0/30中， 能接收目的地址为192.168.4.3的IP 分组的最大主机数是（ ）。
A.0
B.1
C.2
D.4
【答案】C
【解析】每个子网中忽略子网内全为0和全为1的地址剩下的就是有效主机地址，本题中由于子网的比特数是30, 因此用于主机的只有2位，即00, 01, 10, 11，有效主机地址是2个，这里192.168.4.3显然是其广播地址，因此答案是C 。
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.
【答案】A
【解析】函数S （intn ）是一个递归函数：①当实际参数小于等于零时则返回0, 并终止递归；
，并将S （n-1）的结果加上n 作为返回值。程序从②当实际参数大于零时则递归调用S （n-1）
main （ ）函数开始，首先调用main （ ）函数；在main （ ）函数中调用S （1）
；由于函数S （1）的函数时，将main （ ）函数的上下文保存到栈中，并进入函数S （1）
；在S 实际参数大于零，需要调用S （0）, 故将S （1）函数的上下文保存到栈中，进入S （0）
（0）中，实际参数小于等于零，递归终止。
8． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
【答案】D
【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。
9． 设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块的大小均为256字节，则可表示的单个文件最大长度是（ ）。
A.33KB
B.519KB
C.1057KB
D.16513KB
【答案】C
【解析】4个地址项为直接地址索引，其指向的数据块大小4×256B=lKB，一级间接地址索引可以索引256/4=64个直接地址索引，故2个一级间接地址索引指向的数据块大小为2×64×256B=32KB，二级间接地址索引为256/4×256/4=4096个直接地址索引，故1个二级间接地址索引指向的数据块大小为4096×256B=1024KB, 共计1KB+32KB+1024KB=1057KB。
10．—棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有（ ）个结点。
A.2h B. C. D.
【答案】B
【解析】此树满足哈夫曼树，除根节点外每层有两个节点。
二、判断题
11．串是一种数据对象和操作都特殊的线性表。（ ） 【答案】
【解析】串是一种操作特殊的线性表，其特殊性主要体现在数据元素是一个字符。在内存中，