2017年常州大学商学院858数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 动态存储管理系统中，通常可有（ ）种不同的分配策略。
【答案】C
【解析】动态存储管理系统中有以下三种：首次拟合法、最佳拟合法、最差拟合法。①首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。②最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n 且最接近n 的空闲块进行分配。③最差拟合法，将可利用空间表中不小于n 且是链表中最大的空闲块的一部分分配给用户。
2． 执行完下列语句段后，f 值为（ ）。
A.2 B.4 C.8
D. 无限递归 【答案】B
【解析】该程序使用了递归调用，由题知，
3． 下列关于UDP 协议的叙述中，正确的是（ ）
I 提供无连接服务 II 提供复用/分用服务
III 通过差错校验，保障可靠数据传输 A. 仅I B. 仅 I 、II C. 仅 II 、III D.I 、II 、III 【答案】B
【解析】UDP 无连接创建，提供多路复用服务。虽然有差错检验，但是不能保证可靠数据传输，所以III 错误。
第 2 页，共 59 页
所以结果为4。
4． 若串
A.8 B.37 C.36 D.9
【答案】B
其子串的数目是（ ）。
【解析】子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为长为为：
故选B 。
向主机
发送一个确认帧，
长为n 的子串有1个，长为
的子串有2个，
的子串有3个，……，长为1的子串有n 个。由于空串是任何串的子串，所以本题的答案
5． 某以太网拓扑及交换机当前转发表如下图所示，主机发送1个数据帧，主机
A. B. C. D.
收到该帧后，向主机
交换机对这两个帧的转发端口分别是（ ）
【答案】B
【解析】第一次交换机没有录这个数据报源MAC
地址的信息
的信息，只能选择从其他端口全部发送，同时记
确认帧发送时已经有
的信息
了所以只用从1端口转发。
6． 5个字符有如下4种编码方案，不是前缀编码的是（ ）
A.
B.
C.
D. 【答案】D
【解析】在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。约定左分支
表示字符
右分支表示字符
则可以用从根结点到叶子结点的路径上的分支字符串作为该叶
第 3 页，共 59 页
子结点字符的编码。如此得到的编码必是前缀编码。D 选项中，编码110是编码1100的前缀，故不符合前缀编码的定义。
7． 对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（ ）
A.
B.
C.
D.
【答案】D
【解析】拓扑排序方法如下：
（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它； （2）从图中删去该顶点，并且删去从该顶点发出的全部有向边； （3）重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。 对于此有向图进行拓扑排序所有序列为：和
8． 下列有关总线定时的叙述中，错误的是（ ）。
A. 异步通信方式中，全互锁协议最慢 B. 异步通信方式中，非互锁协议的可靠性最差 C. 同步通信方式中，同步时钟信号可由多设备提供 D. 半同步通信方式中，握手信号的采样由同步时钟控制 【答案】C
【解析】A 项正确，异步通信方式中，全互锁协议最慢，主从模块都需要等待确认后才能撤销其信号；B 项正确，异步通信方式中，非互锁协议没有相互确认机制，因此可靠性最差；C 项错误，同步通信要遵循统一的时钟信号，不能由多设备提供；D 项正确，半同步通信方式中，握手信号的采样由同步时钟控制。
9． 若某通信链路的数据传输速率为
A.600波特 B.1200波特 C.4800波特 D.9600波特 【答案】B
【解析】注意无噪声下的码元速率极限值B 与信道带宽H 的关系：B = 2xH （Baud ）, 而奈
第 4 页，共 59 页
所以选D
采用4相位调制，则该链路的波特率是（ ）。