2018年长沙理工大学计算机与通信工程学院920数据结构[专业硕士]考研仿真模拟五套题
● 摘要
一、单项选择题
1． 对于100Mbps 的以太网交换机, 当输出端口无排队直通(
太网帧(不包括前导码) 时, 引入的转发延迟至少是（ ） A. B. C. D.
【答案】B
【解析】直通交换方式是指以太网交换机可以在各端口间交换数据。它在输入端口检测到一个数据包时, 检查该包的包头, 获取包的目的地址, 启动内部的动态查找表转换成相应的输出端口, 在输入与输出交叉处接通, 把数据包直通到相应的端口, 实现交换功能。通常情况下, 直通交换方式只检查数据包的包头即前14个字节, 由于不需要考虑前导码, 只需要检测目的地址的6B , 所以最短的传输延迟是。
2． 文件系统中，文件访问控制信息存储的合理位置是（ ）.
A. 文件控制块
B. 文件分配表
C. 用户口令表
D. 系统注册表
【答案】A
【解析】文件控制块是文件存在的标志，文件的相关信息(基本信息、存取控制信息以及使用信息) 都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息.
3． 排序过程中, 对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中, 每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。
Ⅰ. 简单选择排序
Ⅱ. 希尔排序
Ⅲ. 快速排序
Ⅳ. 堆排
Ⅴ. 二路归并排序
A. 仅Ⅰ、Ⅲ、Ⅳ
) 方式转发一个以
B. 仅Ⅰ、Ⅱ、Ⅲ
C. 仅Ⅱ、Ⅲ、Ⅳ
D. 仅Ⅲ、Ⅳ、Ⅴ
【答案】A 。
【解析】其中简单选择排序、堆排序属于选择类排序, 每一趟排序结束时将确定最大(或最小) 关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。
4． 有向带权图如下图图所示, 若采用迪杰斯特拉(Dijkstta)算法求从源点a 到其他各顶点的最短路径, 则得到的第一条最短路径的目标顶点是b , 第二条最短路径的目标顶点是c , 后续得到的其佘各最短路径的目标顶点依次是（ ）。
图 有向带权图
A.d , e , f
B.e , d , f
C.f , d , e
D.f , e , d
【答案】C 。
【解析】本题主要考查Dijkstta 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstta 算法过程中各步的状态表, 故后续目标顶点依次为f , d , e 。
5． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入
B. 选择
C. 希尔
D. 二路归并
【答案】A
【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是:假设待排序的记
录存放在数组中，排序过程的某一中间时刻，R
被划分成两个子区间
插入到有序区中适当的位置上。使和，其中:前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。将当前无序区的第1个记录变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。
6． 已知字符串S 为“abaabaabacacaabaabcc ”, 模式串t 为“abaabc ”, 采用KMP 算法进行匹配, 第一次出现“失配”(
A.i=l, j=0
B.i=5, j=0
C.i=5, j=2
D.i=6, j=2
【答案】C
【解析】模式匹配(KMP)算法对普通的暴力匹配的改进在于:每当匹配过程中匹配失败时, 主串(本题为S) 的指针(i)不需要回溯, 而是利用已经得到的“部分匹配”的结果将模式串(t)向右“滑动”尽可能远的一段距离后, 继续进行比较。模式串“滑动”的距离是由模式串(t)本身决定的, 即t
的子串
中前缀串和后缀串相等的最长长度。本题中第一次失配i=5, 字串为“abaab”, 其相等且最长的前后缀为“ab”, 一次下一个j=2。
7． 如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（ ）.
A.1条，1条
B.1条，多条
C. 多条，1条
D. 多条，多条
【答案】A
【解析】所谓递归查询方式就是:如果主机所询问的本地域名服务器不知道被查询域名的IP 地址，那么本地域名服务器就以DNS 客户的身份向其他服务器继续发出查询请求报文，而不是让该主机自行下一步的查询. 所以主机只需向本地域名服务器发送一条域名请求，采用递归查询方法，本地域名服务器也只需向上一级的根域名服务器发送一条域名请求，然后依次递归. 正确选项为A.
) 时, i=j=5, 则下次开始匹配时, i 和j 的值分别是（ ）。