2018年杭州电子科技大学计算机学院851数据结构考研基础五套测试题
● 摘要
一、是非题
1． 一个稀疏矩阵A m*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m 和n 的值互换，则就完成了A m*n的转置运算。（ ）
【答案】 ×
【解析】稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。
2． 一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第k ﹣1层具有的最多结点数为余下的
【答案】 √
【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为k ﹣1层全满时，此时从根结点到第k ﹣1层具有最大的结点数为
3． 队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ）
【答案】 ×
【解析】队列只在下端(队尾) 增加，在上端(队头) 减少。
4． 在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（ ）
【答案】×
【解析】伙伴系统的伙伴不一定是位置相邻的内存块。
起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:
只要符合公式的内存块都是伙伴。
5． 设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为O(1)（ ）。
【答案】 √
【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操作的时间复杂度是O(1)。
个结点在第k 层的任一位置上。（ ）
6． 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）
【答案】×
【解析】例如起泡排序是稳定排序，将4， 3， 2，1按起泡排序排成升序序列，第一趟变成3， 2，1，4，此 时3就朝向最终位置的相反方向移动。
二、单项选择题
7． 下列关于最小生成树的叙述中, 正确的是（ ）。
Ⅰ. 最小生成树的代价唯一
Ⅱ. 所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ. 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同
IV. 使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树总不相同
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、Ⅲ
D. 仅Ⅱ、Ⅳ
【答案】A 。
【解析】当图中存在相同权值的边时, 其最小生成树可能是不唯一的, 但最小生成树的代价一定是相同的, 所以说法Ⅰ正确。从n 个顶点的连通图中选取n-1条权值最小的边可能构成回路, 所以说法Ⅱ错误。
当某个顶点有权值相同的边, 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树并不一定相同, 所以说法Ⅲ错误。当最小生成树不唯一时, 使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树可能相同, 也可能不同, 所以说法Ⅳ错误。由此可得出正确答案。
8． 本地用户通过键盘登录系统时，首先获得的键盘输入信息的程序是（ ）.
A. 命令解释程序
B. 中断处理程序
C. 系统调用服务程序
D. 用户登录程序
【答案】B
【解析】外部设备在与计算机连接时有多种方式，中断技术就是一种常用方式. 其工作原理是:利用处理机中断信号线，外部设备在需要服务的时候将该线设置为有效，计算机若同意接受中断则会停止当前进程的运行，转而服务发出中断的物理设备(注意与陷阱，即软中断有区别），那么对不同外部设备进行服务的程序代码是不同的，如何找到这些代码呢? 这就要借助中断向量，中断向量一般是由硬件根据中断的类型(不同外设不同）计算所得，或计算机系统在开机配置时所配置
的. 处理机取得中断向量，其实就是一个物理地址，该地址下存放的是为此中断服务的代码的起始地址. 所以，当键盘按下的时候，键盘控制器获得该操作动作，先将键盘扫描码读入键盘缓冲区，再向处理机发出键盘中断，适当的时候(一条指令的末尾或一条原语结束）处理机会响应中断，调用指定服务程序将键盘缓冲区中的键盘扫描码输入到登录进程中去. 如此，最先响应键盘的必然是中断处理程序. 本题中，像命令解释器(例如cmd 窗口）、系统调用服务和用户登录程序都在中断处理程序后面.
9． 某数采用IEEE754单精度浮点数格式表示为C640 0000H, 则该数的值是（ ） A. B. C. D.
【答案】A
【解析】IEEE754单精度浮点数格式为C640 0000H表示为二进制格式为
1100 01 10 0100 0000 0000 0000 0000 0000,
转换为标准的格式为:
因此, 浮点数的值为。
10．某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第1字节为操作码字段，第2字节为相对位移量字段. 假定取指令时，每取一个字节PC 自动加1. 若某转移指令所在主存地址为2000H ，相对位移量字段的内容为06H ，则该转移指令成功转移后的目标地址是（ ）.
A.2006H
B.2007H
C.2008H
D.2009H
【答案】C
【解析】相对寻址方式的有效地址EA ＝(PC)＋D ，其中PC 为程序计数器，D 为相对偏移量. 主存按字节编址，取指令时，每取一个字节PC 值自动加1. 由于转移指令由两个字节组成，取出这条转移指令之后的PC 值自动加2，为2002H ，故转移的目标地址为2002H ＋06H ＝2008H.
11．某计算机的Cache 共有16块，采用2路组相联映射方式(即每组2块). 每个主存块大小为32字节，按字节编址. 主存129号单元所在主存块应装入到的Cache 组号是（ ）.
A.0
B.2
C.4
D.6
【答案】C