2017年大连理工大学软件学院810数据结构和计算机组成原理之数据结构考研冲刺密押题
● 摘要
一、选择题
1． 用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，则校验位数至少为（ ）
A.2
B.3
C.4
D.5
【答案】C
【解析】设校验位的位数为k ，数据位的位数为n ，根据海明码编码k 和n
应满足下述关系。
当k=4时， 符合要求，校验位至少是4位，故答案为C 。
2． 在子网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 。
3． 图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 ）。
4． 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。
A. 逻辑设备名
B. 物理设备名
C. 主设备号
D. 从设备号
【答案】A
【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等。而操作系统内部管理设备使用的是设备编号。
5． 已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（ ）。
A.39
B.52
C.111
D.119
【答案】C
【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层。题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度。根据题意，一棵完全二叉树的第6层（设根为第1层）有8个叶结点，可知此二叉树的高度是6或7。题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7。由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是-1=63。又根据二叉树的性质1可知，题目中二叉树的第6层结点数是=32个结点，已知有8个叶子结点，那么其余32-8=24个结点均为分支结点，这些结点在第7层上最多有48个子结点（即叶子结点）。所以此二叉树的结点数最多可达-1+（-8）×2=lll。
6． 下列选项中，能缩短程序执行时间的措施是（ ）。
I. 提高CPU 时钟频率
II. 优化数据通路结构
III. 对程序进行编译优化
A. 仅I 和II
B. 仅I 和III
C. 仅II 和III
D.I 、II 和III
【答案】D
【解析】一般说来，CPU 时钟频率（主频）越高，CPU 的速度就越快；优化数据通路结构，可以有效提高计算机系统的吞吐量；编译优化可得到更优的指令序列。所以I 、II 、III 都是有效措
施。
7． 归并排序中，归并的趟数是（ ）。
【答案】B
【解析】不妨设归并的趟数为m ，第一次归并每组有两个元素，最后一次归并只剩下一组，这组的元素个数为n
。因此每次归并元素的个数增加一倍。所以
所以归并的趟数为
8． 某计算机主存地址空间大小为256MB , 按字节编址。虚拟地空间大小为4GB ，采用页式存储管理，页面大小为4KB ，TLB （快表）采用全相联映射，有4个页表项，内容如下表所示。
则对虚拟地址03FFF180H 进行虚实地址变换的结果是（ ）
A.0153180H
B.0035180H
C.TLB 缺失
D. 缺页
【答案】A
【解析】虚拟地址为03FFF180H ，其中页号为03FFFH , 页内地址为180H ，根据题目中给出的页表项可知页标记为03FFFH 所对应的页框号为0153H , 页框号与页内地址之和即为物理地址015 3180H。
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。