2017年内蒙古师范大学计算机与信息工程学院840数据结构与操作系统考研导师圈点必考题汇编
● 摘要
一、选择题
1． 下列有关浮点数加减运算的叙述中，正确的是（ ）。
对阶操作不会引起阶码上溢或下溢
右规和尾数舍入都可能引起价码上溢
左规时可能引起阶码下溢
尾数溢出时结果不一定溢出 A. 仅B. 仅C. 仅
D. 【答案】D
【解析】浮点数的加减运算步骤包括：①对阶，使两个操作数的小数点位置对齐，阶码小的尾数右移，可能产生溢出，但是阶码不会溢出；②尾数求和，将对阶后的尾数按定点数加（减）运算规则运算；③规格化，包括左规和右规，左规时阶码减少，可能出现阶码下溢，而右规时，阶码増加可能出现阶码上溢；④舍入，该过程可能需要右规调整，因此可能出现阶码上溢；⑤溢出判断，浮点数的溢出与否是由阶码的符号决定的，而不是由尾数溢出判断的，因此尾数溢出时结果不一定溢出。因此均正确。
2． 执行完下列语句段后，f 值为（ ）。
A.2 B.4 C.8
D. 无限递归 【答案】B
【解析】该程序使用了递归调用，由题知，所以结果为4。
3． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。
【答案】D
【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。
4． 为提高散列（Hash ）表的查找效率，可以采用的正确措施是（ ）。
I .增大装填（载）因子
II. 设计冲突（碰撞）少的散列函数
III. 处理冲突（碰撞）时避免产生聚集（堆积）现象 A. 仅I B. 仅 II C. 仅 I 、II D. 仅 II 、III 【答案】D
【解析】散列表的查找效率（比较次数）取决于：散列函数、处理冲突的方法和散列表的装填因子a 。CX 标 志着散列表的装满程度，通常情况下，（X 越小，发生冲突的可能性越小；反之，a 越大，表示已填入的记录越多， 再填入记录时，发生冲突的可能性越大。因此选项I 错误，越是增大装填因子，发生冲突的可能性就越大，查找 效率也越低。选项II 正确。选项III 正确。采用合适的处理冲突的方法避免产生聚集现象，也将提高查找效率。例如，用拉链法解决冲突时不存在聚集现象，用线性探测法解决冲突时易引起聚集现象。
5． 用数组r 存储静态链表，结点的next 域指向后继，工作指针j 指向链中结点，使j 沿链移动的操作为（ ）。
【答案】A
【解析】因为是用数组存储，这里所说的工作指针j 相当于数组的下标，结点是存储一个值域和next 域，next 域就是存放下一个结点的下表，所以只要将next 域中的值赋给j 就可以实现j 沿链移动。
6． 有一个
的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩
阵时，所需的字节数是（ ）。
A.60 B.66 C.18000 D.33
【答案】B
【解析】如果是全部，
则是需要10个非零整数则是
个字节；但是用三元组表示的话，只需要记录非零
字节，
数据的X 坐标，Y 坐标，数值即可，就是每个非零数字需要占用三个整数的空间，即
字节；如果问有效元素占的空间大小，则选A 项，但是如果从整体
来看，应该多一个用来记录矩阵宽（100）、高（90）、默认值（0）的元素，所以还应该多算6个字节。所以全部为66字节，选B 项。
7． 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树 B. 哈夫曼树
C. D. 堆 【答案】D
【解析】堆的定义： n 个关键字序列（1）
（2）
且且
或
称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
树
满足第（1）种情况的堆，称为小顶堆；满足第（2）种情况的堆，称为大顶堆。
由堆的定义可知堆可以满足上述性质。
8． 假定不采用Cache 和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是（ ）。
A. 每个指令周期中CPU 都至少访问内存一次 B. 每个指令周期一定大于或等于一个CPU 时钟周期 C. 空操作指令的指令周期中任何寄存器的内容都不会被改变 D. 当前程序在每条指令执行结束时都可能被外部中断打断 【答案】C
【解析】本题涉及的概念比较多。首先，如果不采用Cache 和指令预取技术，每个指令周期中至少要访问内 存一次，即从内存中取指令。其次，指令有的简单有的复杂，每个指令周期总大于或等于一个CPU 时钟周期。第三，即使是空操作指令，在指令周期中程序计数器PC 的内容也会改变
为取下一条指令做准备。第四，如果机器处于“开中断”状态，在每条指
令执行结束时都可能被新的更高级的中断请求所打断。所以应选择选项C 。
9． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257 B.258 C.384 D.385 【答案】C
【解析】由
：_
则
和
_
_可知
，
即
显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个
性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。