2017年齐鲁工业大学理学院872数据结构考研冲刺密押题
● 摘要
一、选择题
1． 设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，放于
中，那么第i 行的对角元素【答案】A
【解析】
中列标不大于行标，
又
存放在
中，
所以
存放的位置为
存放于B 中（ ）处。
存
2． 线性表是具有n 个（ ）的有限序列（n ＞0）。
A. 表元素 B. 字符 C. 数据元素 D. 数据项E. 信息项 【答案】C
【解析】一个线性表是n 个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同。
3． 设有数组数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素
【答案】B
【解析】在计算中，可以考虑按照列存放时，址。比如
顺序存放时，它是第
在内存的位置，比较容易计算元素的首地
个元素，由于首地址为BA ，
所以它的存储首地址为
的存储首地址为（ ）。
4． 下列有关RAM 和ROM 的叙述中，正确的是（ ）。
I.RAM 是易失性存储器，ROM 是非易失性存储器 II.RAM 和ROM 都采用随机存取方式进行信息访问 III.RAM 和ROM 都可用作Cache IV .RAM 和ROM 都需要进行刷新
A. 仅I 和II B. 仅II 和III C. 仅 I 、II 和IV D. 仅II 、III 和IV 【答案】A
RAM 中的内容断电后即丢失ROM 中的内容断电后不会丢失，，【解析】（易失性）（非易失性），区别在同时RAM 和ROM 都采用随机存取方式（即CPU 对任何一个存储单元的存取时间相同）于RAM 可读可写，ROM 只读不写。而ROM 显然不可用作Cache , 也不需要刷新，所以III 和IV 的叙述都是错误的。
5． 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。
A.
B.
C.
D. 【答案】C 。
【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间
为
其中n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为
其
中e 为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为即可得出正确答案。
6． 某设备中断请求的相应和处理时间为100m ，每400ns 发出一次中断请求，中断相应所容许的最长延迟时间为50ns , 贝U 在该设备持续工作过程中CPU 用于该设备的百分比至少是（ ）
A.
B.
C.
D. 【答案】B
【解析】每400m 响应一次中断并且用100m 进行处理，所以该设备的
时间占用CPU 时间
百分比为中断响应容许的延迟时间对此没有影响，属于干扰条件。
7． 采用指令Cache 与数据Cache 分离的主要目的是（ ）
A. 减低Cache 的缺失损失 B. 提高Cache 的命中率 C. 减低CPU 平均访问时间 D. 减少指令流水线资源冲突
时间占整个CPU 时间
【答案】D
【解析】指令流水线不会断流，预取过来的都是指令
8． —个非空广义表的表尾（ ）。
A. 不能是子表 B. 只能是子表 C. 只能是原子 D. 是原子或子表 【答案】B
【解析】广义表的定义是一个递归定义，当广义表非空时，称第一个元素是它的表头，称其余元素构成的表称为它的表尾。因此一个非空广义表的表尾只能是子表。
9． 现在有一颗无重复关键字的平衡二叉树（A VL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。
A. 根节点的度一定为2 B. 树中最小元素一定是叶节点 C. 最后插入的元素一定是叶节点 D. 树中最大元素一定是无左子树 【答案】D
【解析】二叉树的中序遍历定义是“若二叉树为空，则空操作；否则：①中序遍历左子树；②访问根节点；③中序遍历右子树”。A 项错误，当树中仅有一个或者两个结点时，根节点的度就可能不为2；B 项错误，树中最小元素是中序遍历时最后访问的节点，当没有右子树时，最后访问的节点是根节点；C 项错误，当最后插入的元素破坏树的平衡后，树会进行调整，使其成为中间节点；D 项正确，由中序遍历的特点可知，左子树的值大于根节点，所以最大元素一定没有左子树。
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。