2017年齐鲁工业大学信息学院872数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 下列选项中，描述浮点数操作速度指标的是（ ）。
A.MIPS B.CPI C.IPC
D.MFLOPS 【答案】D
【解析】
表示每秒执行多少百万次浮点
. 表示每秒执行多少百万条指令。对于一个给定的程序，
MIPS 定义为
这里所说的指令一般是指加、减运算这类短指令。
就是每条指令执行所用的时钟周期数。由于不同指令的功能不同，
造成指令执行时间不同，也即指令执行所用的时钟数不同，所以CPI 是一个平均值。
每个时钟周期执行的指令数。
2． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
【答案】D
【解析】至少探测次数
3． 假定主存地址为32位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（WriteBack ）方式，则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。
A.146k B.147K C.148K D.158K 【答案】B
【解析】Cache 和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数据块，每个块和缓存块容量相同；主存中某块只能映象到Cache 的一个特
运算，用来描述计算机的浮点运算速度，适用于衡量处理机的性能。
定的块中。本题中，Cache 总共存放4K 字数据，块大小为4个字，因此cache 被分为4K/4 = 1K 个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为32-10-14= 18位。所以，Cache 的每一行需要包含所存的数据4个字，每个字32位，18位标记位和一个有效位，因此总容=147K。 量为：
4． 下列调整中，不可能导致饥饿现象的是（ ）
A. 时间片转移 B. 静态优先及调度 C. 非抢占式作业优先 D. 抢占式短作业优先 【答案】A
【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU 使用时间，不会产生饥饿的现象，其余三个都会产生饥饿。
5． 下列选项中，能引起外部中断的事件是（ ）。
A. 键盘输入 B. 除数为0 C. 浮点运算下溢 D. 访存缺页 【答案】A
【解析】所谓外部中断是指由外部事件引起的中断，在这4个选项中，只有键盘输入是真正由外部事件引起的中断。
6． 已知一棵有2011个结点的树，其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。
A.115 B.116 C.1895 D.1896 【答案】D
【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点（因为一个非终端结点，另外，树根结点转至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子）
换成二叉树后也没有右孩子。题目中树的总结点数是2011，叶结点个数是116, 则非终端结点个数是2011-116=1895, 则该树对应的二叉树中 无右孩子的结点个数是1895+1=1896。
7． 在虚拟存储管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是（ ）。
A. 编辑
B. 编译 C. 链接 D. 装载 【答案】B
【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本，不涉及到任何与计算机运 行相关的事；编译是由编译程序将用户源代码编译成若干个目标模块，源地址编译成目标程序时，会形成逻辑地址；链接是由链接程序将编译后形成的一组目标模块，以及所需库函数链接，形成完整的装入模块；装入是由装入程序将装入模块装入内存。
8． 下列序列中，（ ）是执行第一趟快速排序后所得的序列。
【答案】C
【解析】快速排序将数据划分成两部分，其中一部分关键字比另一部分关键字小。
9． 为提高散列（Hash ）表的查找效率，可以采用的正确措施是（ ）。
I .增大装填（载）因子
II. 设计冲突（碰撞）少的散列函数
III. 处理冲突（碰撞）时避免产生聚集（堆积）现象 A. 仅I B. 仅 II C. 仅 I 、II D. 仅 II 、III 【答案】D
【解析】散列表的查找效率（比较次数）取决于：散列函数、处理冲突的方法和散列表的装填因子a 。CX 标 志着散列表的装满程度，通常情况下，（X 越小，发生冲突的可能性越小；反之，a 越大，表示已填入的记录越多， 再填入记录时，发生冲突的可能性越大。因此选项I 错误，越是增大装填因子，发生冲突的可能性就越大，查找 效率也越低。选项II 正确。选项III 正确。采用合适的处理冲突的方法避免产生聚集现象，也将提高查找效率。例如，用拉链法解决冲突时不存在聚集现象，用线性探测法解决冲突时易引起聚集现象。
10．某以太网拓扑及交换机当前转发表如下图所示，主机发送1个数据帧，主机
A. B. C. D.
收到该帧后，向主机
交换机对这两个帧的转发端口分别是（ ）
向主机
发送一个确认帧，
相关内容
相关标签