2017年武汉理工大学计算机科学与技术学院852数据结构(C语言版)考研题库
● 摘要
一、选择题
1． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）
A.G 的邻接多重表需要n （n-l ）个边结点和n 个顶点结点
B.G 的连通分量个数最少
C.G 为连通图
D.G 所有顶点的度的总和为n （n-1）
【答案】A
【解析】A 项中G 的邻接多重表中需要n （n-l ）/2个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n-1，则n 个结点的度的总和为n （n-l ）。
2． 下列选项中，能缩短程序执行时间的措施是（ ）。
I. 提高CPU 时钟频率
II. 优化数据通路结构
III. 对程序进行编译优化
A. 仅I 和II
B. 仅I 和III
C. 仅II 和III
D.I 、II 和III
【答案】D
【解析】一般说来，CPU 时钟频率（主频）越高，CPU 的速度就越快；优化数据通路结构，可以有效提高计算机系统的吞吐量；编译优化可得到更优的指令序列。所以I 、II 、III 都是有效措施。
3． 若某通信链路的数据传输速率为
A.600波特
B.1200波特
C.4800波特
D.9600波特
【答案】B
【解析】注意无噪声下的码元速率极限值B 与信道带宽H 的关系：B = 2xH （Baud ）, 而奈奎斯特公式一无噪信道传输能力公式是
第 2 页，共 52 页 采用4相位调制，则该链路的波特率是（ ）。 N 为一个码元所取的离散值个数。从
而可以得到波特率与数据传输速率的关系，即在本题中数据传输速率C = 2400, N=4，因此波特率是1200, 答案是B 。
4． 用户在删除某文件的过程中，操作系统不可能执行是（ ）
A. 删除此文件所在的目录
B. 删除与此文件关联的目录项
C. 删除与此文件对应的控制块
D. 释放与此文件关联的内存级冲区
【答案】A
【解析】删除文件不需要删除文件所在的目录，而文件的关联目录项和文件控制块需要随着文件一同删除，同时释放文件的关联缓冲区。
5． 对同一待排序列分别进行折半插入排序和直接插入排序， 两者之间可能的不同之处是（ ）。
A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数
【答案】D 。
【解析】折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，
而记录的移动次数不变。折半插入排序的时间复杂度仍为
所以两者之间的不同只可能是元素之间的比较次数。
6． 已知串
A.0123
B.1123
C.1231
D.1211
【答案】A
【解析】KMP 算法的next 数组建立的原则
其Next 数组值为（ ）。
7． 执行完下列语句段后，f 值为（ ）。
A.2
第 3 页，共 52 页
B.4
C.8
D. 无限递归
【答案】B
【解析】该程序使用了递归调用，由题知，所以结果为4。
8． 某计算机处理器主频为50MHz ，采用定时查询方式控制设备A 的I/0, 查询程序运行一次所用的时钟 周期数至少为500。在设备A 工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU 用于设备A 的I/0的时间占整个CPU 时间的百分比至少是（ ）。
A.0.02%
B.0.05%
C.0.20%
D.0.50%
【答案】C
【解析】对于设备A ，每秒中查询至少200次，每次查询至少500个时钟周期，总的时钟周期数为100000, 又因为处理器主频为50MHz 。所以CPU 用于设备A 的I/0的时间占整个CPU 时间的百分比至少为100000/50=0.20%。
9． 下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）。
A. 连续结构
B. 索引结构
C. 链式结构且磁盘块定长
D. 链式结构且磁盘块变长
【答案】B
【解析】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问。链式结构的优点是文件易于扩展，缺点是不易随机访问。索引结构的优点是具有链式结构的优点并克服了它的缺点，可随机存取，易于文件扩展。
10．假设变址寄存器R 的内容为1000H , 指令中的形式地址为2000H ; 地址1000H 中的内容为2000H , 地 址2000H 中的内容为3000H ，地址3000H 中的内容为4000H , 则变址寻方式下访问到的操作数是（ ）
A.1000H
B.2000H
C.3000H
D.4000H
【答案】D
【解析】根据变址寻址的
作数的实际地址，
由题可知
4000H 。
第 4 页，共 52 页 变址寄存器的内容与形式地址的内容相加之后得到操根据实际地址访问内存，获取操作数
相关内容
相关标签