2018年北京交通大学计算机与信息技术学院925数据结构考研基础五套测试题
● 摘要
一、判断题
1． 若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【答案】 ×
【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
2． 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）
【答案】 ×
【解析】栈只能在一端进行操作，队列可以在表的两端进行运算。
3． 二元查找树的任何结点的左右子树都是二元查找树。（ ）
【答案】√
【解析】二元查找树也称作二元排序树。二元查找树的性质:①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树所有结点的值均大于它的根结点的值；③左右子树也分别为二元查找树。
4． 通常使用队列来处理函数或过程的调用。（ ）
【答案】 ×
【解析】经常使用栈来处理函数或过程的调用。
5． 若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（ ）
【答案】×
【解析】在含有N 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。关键字有序，可能叶子结点部分的关键字最大，根结点的关键字部分最小，此时就不是哈夫曼树。
6． 串是一种数据对象和操作都特殊的线性表。（ ）
【答案】 √
【解析】串是一种操作特殊的线性表，其特殊性主要体现在数据元素是一个字符。在内存中，一份文本都可以看做是一个字符串，而每一行都可以看做是其子串。
二、单项选择题
7． 已知有向图G=(V，E) , 其中
,
G 的拓扑序列是（ ）。 A.
B.
C. D.
【答案】A
拓扑序列的条件:若
在顶
点 能被称为必须排【解析】设G=(V，E) 是一个具有n 个顶点的有向图，V 中顶点序列是图中的边(即从顶点。 到有一条路径) ，则在序列中顶点之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列
是
8． 元素a , b , c , d , e 依次进入初始为空的栈中, 若元素进栈后可停留、可出栈, 直到所有元素都出栈, 则在所有可能的出栈序列中, 以元素d 开头的序列个数是（ ）。
A.3
B.4
C.5
D.6
【答案】B
【解析】d 首先出栈后的状态如下图所示。
此时可有以下4种操作:
(1)e进栈后出栈, 出栈序列为decba 。
(2)c出栈, e 进栈后出栈, 出栈序列为dceba 。
(3)cb出栈, e 进栈后出栈, 出栈序列为dcbea 。
(4)cba出栈, e 进栈后出栈, 出栈序列为dcbae 。
9． 下列寄存器中, 汇编语言程序员可见的是（ ）。
A. 存储器地址寄存器(MAR)
B. 程序计数器(PC)
C. 存储器数据寄存器(MDR)
D. 指令寄存器(IR)
【答案】B
【解析】CPU 有5个专用寄存器, 它们是程序计数器(PC)、指令寄存器(IR)、存储器地址寄存
器(MAR)、存储器数据寄存器(MBR)和状态标志寄存器(PSWR), 这些寄存器中有些是CPU 的内部工作寄存器, 对汇编语言程序员来说是透明的, 在汇编语言程序设计中不会出现。但汇编语言程序员可以通过制定待执行指令的地址来设置PC 的值, 所以程序计数器(PC)对于汇编语言程序员可见的。
10．下列二叉排序树中查找效率最高的是（ ）。
A. 平衡二叉树
B. 二叉查找树
C. 没有左子树的二叉排序树
D. 没有右子树的二叉排序树
【答案】A
【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。这就保证了二叉树的深度是级别的。二叉查找树或者是一颗空数；或者是具有下列性质的二叉树:①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树上所有结点的值均大于它的根结点的值；③左、右子树也分别为二叉排序树。B 、C 、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1, 甚至很大，因此查找效率低。
11．下列关于RISC 的叙述中，错误的是（ ）.
A.RISC 普遍采用微程序控制器
B.RISC 大多数指令在一个时钟周期内完成
C.RISC 的内部通用寄存器数量相对CISC 多
D.RISC 的指令数、寻址方式和指令格式种类相对CISC 少
【答案】A
【解析】B 项、C 项、D 项都是RISC 的特点之一，所以它们都是正确的，只有A 项是CISC 的特点，因为RISC 的速度快，所以普遍采用硬布线控制器，而非微程序控制器.
12．下列不是设计一个“好”的算法应考虑达到的目标是（ ）。
A. 可行的
B. 健壮的
C. 无二义性的
D. 可读性好的
【答案】A
【解析】设计一个“好”的算法应考虑以下目标:正确性；可读性；健壮性；效率和低存储量需求。可行性是算法的五个基本特征之一，不是一个好的算法该达到的目标。