2016年辽宁大学信息学院计算机专业相关知识之数据结构考研复试题库
● 摘要
一、选择题
1． 有一个的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。
A.60
B.66
C.18000
D.33
答:B
【解析】如果是全部，
则是需要
10个非零整数则是个字节；但是用三元组表示的话，只需要记录非零字节，数据的X 坐标，Y 坐标，数值即可，就是每个非零数字需要占用三个整数的空间，即字节；如果问有效元素占的空间大小，则选A 项，但是如果从整体来看，应该多一个用来记录矩阵宽（100）、高（90）、默认值（0）的元素，所以还应该多算6个字节。所以全部为66字节，选B 项。
2． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257
B.258
C.384
D.385
答:C
【解析】由
：
_则和
__可知
，
即显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
3． 设有两个串S1和S2, 求S2在S1中首次出现的位置的运算称作（ ）。
A. 求子串
B. 判断是否相等
C. 模型匹配
D. 连接
答:C
【解析】常用的串的基本操作有七种，INDEX （s ，t ）是其中的定位函数，这种运算就是所说的模式匹配。
4． 下列命中组合情况中，一次访存过程中不可能发生的是（ ）。
A.TLB 未命中，Cache 未命中，Page 未命中
B.TLB 未命中，Cache 命中，Page 命中
C.TLB 命中，Cache 未命中，Page 命中
D.TLB 命中，Cache 命中，Page 未命中
答:D
【解析】TLB （快表）和慢表（页表，Page ）构成二级存储系统，若TLB 命中，则Page 必命中。因此不可能发生的是D 选项。
5． 响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（ ）。
I. 开关中断II. 保存通用寄存器的内容III. 形成中断服务程序入口地址并送PC
A. 仅I 、II
B. 仅 I 、III
C. 仅 II 、III
D.I 、II 、III
答:B 。
【解析】中断隐指令完成的操作有3个：①保存断点；②关中断；③引出中断服务程序（形成中断服务程序入口地址并送PC ）。而保存通用寄存器内容的操作是由软件来实现，不是由中断隐指令实现的。
6． 当系统发生抖动（thrashing ）时，可以采取的有效措施是（ ）。
I. 撤销部分进程
II. 增加磁盘交换区的容量
III. 提高用户进程的优先级
A. 仅I
B. 仅 II
C. 仅III
D. 仅 I 、II
答:A
【解析】“抖动”现象是指刚刚被换出的页很快又要被访问，为此，又要换出其他页，而该页
必须换入，又很快被访问，如此频繁地置换页面，以致操作系统的大部分时间都花在页面置换上，
引起系统性能下降甚至崩溃。 引起系统抖动现象的原因是对换的信息量过大，内存容量不足，置换算法选择不当。所以解决的办法就是降低交 换页面数量，加大内存容量，改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统 来讲是不可能的，只能增加内存容量。増加内存容量可以是直接添加物理内存（大型计算机都可以在不关机的情 况下增加物理内存
，或者，降低进程数量，相对地增加内存。而増加交换区容量并不能解决物理内存不足的 问条）