2018年兰州交通大学电子与信息工程学院828数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 文件系统中，文件访问控制信息存储的合理位置是（ ）.
A. 文件控制块
B. 文件分配表
C. 用户口令表
D. 系统注册表
【答案】A
【解析】文件控制块是文件存在的标志，文件的相关信息(基本信息、存取控制信息以及使用信息) 都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息.
2． 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）.
A.28字节
B.216字节
C.224字节
D.232字节
【答案】C
【解析】段内位移的最大值就是最大段长. 段号长度占了8位，剩下32﹣8＝24位是段内位移
24空间，因此最大段长为2B.
3． 对下图进行拓扑排序, 可以得到不同的拓扑序列的个数是（ ）。
图
A.4
B.3
C.2
D.1
【答案】B
【解析】拓扑排序的步骤为:
(1)在有向图中选一个没有前驱的顶点并且输出它;
(2)从图中删除该顶点和以它为尾的弧。重复上述两步, 直至全部顶点均已输出。由于没有前驱的顶点可能不唯一, 所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑排序序列, 分别为abced , abecd , aebcd 。
4． 下面关于哈希(Hash，杂凑) 查找的说法正确的是（ ）。
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B. 除留余数法是所有哈希函数中最好的
C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可
【答案】C
【解析】若数据结构中存在关键字和K 值相等的记录，则必定在f(K)的存储位置上，由此，不需要进行比较便可直接取得所查记录。在此，称这个对应关系f 为哈希(Hash)函数，哈希函数的选择要视具体情况而定。
5． 下列有关浮点数加减运算的叙述中, 正确的是（ ）。
Ⅰ. 对阶操作不会引起阶码上溢或下溢
Ⅱ. 右规和尾数舍入都可能引起阶码上溢
Ⅲ. 左规时可能引起阶码下溢
Ⅳ. 尾数溢出时结果不一定溢出
A. 仅Ⅱ Ⅲ
B. 仅Ⅰ Ⅱ Ⅳ
C. 仅Ⅰ Ⅲ Ⅳ
D. Ⅰ Ⅱ ⅢⅣ
【答案】D
【解析】浮点数的加减运算步骤包括:①对阶, 使两个操作数的小数点位置对齐, 阶码小的尾数右移, 可能产生溢出, 但是阶码不会溢出; ②尾数求和, 将对阶后的尾数按定点数加(减) 运算规则运算; ③规格化, 包括左规和右规, 左规时阶码减少, 可能出现阶码下溢, 而右规时, 阶码增加可能出现阶码上溢; ④舍入, 该过程可能需要右规调整, 因此可能出现阶码上溢; ⑤溢出判断, 浮点数的溢出与否是由阶码的符号决定的, 而不是由尾数溢出判断的, 因此尾数溢出时结果不一定溢出。因此Ⅰ Ⅱ Ⅲ Ⅳ均正确。
6． 主机甲与主机乙之间已建立一个TCP 连接, 主机甲向主机乙发送了3个连续的TCP 段, 分别包含300字节、400字节和500字节的有效载荷, 第3个段的序号为900。若主机乙仅正确接收到第1和第3个段, 则主机乙发送给主机甲的确认序号是（ ）。
A.300
B.500
C.1200
D.1400
【答案】B
【解析】本题考查TCP 的确认机制, TCP 首部的序号字段是指本报文所发送的数据的第一个字节的序号。本题中首先根据第3个段的序号为900, 可以得出第2个段的序号为500, 第1个段的序号为200, 这里主机乙仅正确接收了第1段和第3段, 这意味着第2段丢失, 需要超时重传, 因此主机乙发送给主机甲的确认序号, 也就是此时接收端期望收到的下一个数据包中第一个字节的序号应该是第二段的第一个字节的序号, 也就是500, 因此答案是B 。
7．
参考模型的网络层提供的是（ ）。
A. 无连接不可靠的数据报服务
B. 无连接可靠的数据报服务
C. 有连接不可靠的虚电路服务
D. 有连接可靠的虚电路服务
【答案】A
【解析】TCP/IP的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务, 因此答案是A 。
8． 已知有向图G=(V，E) , 其中
,
G 的拓扑序列是（ ）。 A.
B.
C. D.
【答案】A
拓扑序列的条件:若
在顶
点 能被称为必须排
【解析】设G=(V，E) 是一个具有n 个顶点的有向图，V 中顶点序列是图中的边(即从顶点。 到有一条路径) ，则在序列中顶点之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列
是
9． 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历, 其算法时间复杂度是（ ）。 A. B. C. D.
【答案】C 。
【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所