2018年太原科技大学计算机科学与技术学院828数据结构考研核心题库
● 摘要
一、单项选择题
1． 下列关于图的叙述中, 正确的是（ ）。
Ⅰ. 回路是简单路径
Ⅱ. 存储稀疏图, 用邻接矩阵比邻接表更省空间
Ⅲ. 若有向图中存在拓扑序列, 则该图不存在回路
A. 仅Ⅱ
B. 仅Ⅰ、Ⅱ
C. 仅Ⅲ
D. 仅Ⅰ、Ⅲ
【答案】C
【解析】第一个顶点和最后一个顶点相同的路径称为回路; 序列中顶点不重复出现的路径称为简单路径; 回路显然不是简单路径, 所以选项Ⅰ错误。稀疏图用邻接表表示比邻接矩阵节省存储空间, 稠密图适合用邻接矩阵的存储表示, 所以选项Ⅱ错误。利用拓扑排序算法可以判断图中是否存在回路, 即在拓扑排序输出结束后所余下的顶点都有前驱, 则说明了只得到了部分顶点的拓扑有序序列, 图中存在回路。所以选项Ⅲ正确。
2． 若串S ＝'software'%其子串的数目是（ ）。
A.8
B.37
C.36
D.9
【答案】B
【解析】子串的定义是:串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为n(n＞0) ，长为n 的子串有1个，长为n ﹣1的子串有2个，长为n ﹣2的子串有3个，...... ，长为1的子串有n 个。由于空串是任何串的子串，所以本题的答案为:8*(8＋1)/2十1＝37。故选B 。
3． 已知有向图G=(V，E) , 其中
G 的拓扑序列是（ ）。 A.
B.
C.
,
D.
【答案】A
能被称为
必须排【解析】设G=(V，E) 是一个具有n 个顶点的有向图，V 中顶点序列拓扑序列的条件:若
在顶
点是图中的边(即从顶点。
4． 4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7 B.
C.15
D.16
【答案】C
【解析】Hanoi 问题总移动次数为:2M 次。
5． 假设栈初始为空, 将中缀表达式
当扫描到f 时, 栈中的元素依次是（ ） A.
B.
C.
D.
【答案】B
【解析】中缀表达式转后缀表达式遵循以下原则:
(1)遇到操作数, 直接输出;
(2)栈为空时, 遇到运算符, 入栈;
(3)遇到左括号, 将其入栈; 到有一条路径) ，则在序列中顶点之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列
是转换为等价后缀表达式的过程中, (4)遇到右括号, 执行出栈操作, 并将出栈的元素输出, 直到弹出栈的是左括号, 左括号不输出;
(5)遇到其他运算符
符入栈;
(6)最终将栈中的元素依次出桟, 输出。
所以扫描到‟/‟, 入栈„描到‟+‟, 由于‟+‟优先级比‟/'低, 所以将‟/‟弹出, ‟+‟入栈; 扫描到‟*,, 优先级比‟+‟高, 入栈; 扫描到‟(„, 入栈; 扫描到‟一„, 将栈中优先级更高的‟*‟弹出, „一, 入栈; 扫描到‟*‟, 优先级比‟一„高, 入栈。所以扫描至“f的时候, 栈中元素为:+(一*
6． 某机器有一个标志寄存器, 其中有进位/借位标志CF 、零标志ZF 、符号标志SF 和溢出标志OF , 条件转移指令bgt(无符号整数比较大于时转移) 的转移条件是（ ）。
A.CF+OF=0
B.SF+ZF=0
时, 弹出所有优先级大于或等于该运算符的栈顶元素, 然后将该运算
C.CF+ZF=0
D.CF+SF=0
【答案】C
【解析】判断无符号整数A>B成立, 满足的条件是结果不等于0, 即零标志ZF=0, 且不发生进位, 即进位/借位标志CF=0。所以正确选项为C 。其余选项中用到了符号标志SF 和溢出标志OF , 显然可以排除掉。
7． 处理外部中断时, 应该由操作系统保存的是（ ）。
A. 程序计数器(PC)的内容
B. 通用寄存器的内容
C. 快表(TLB)的内容
D.Cache 中的内容
【答案】B
【解析】外部中断处理过程首先要保护现场, 使得中断处理完后能够恢复程序的状态继续执行。保护现场有两个含义:
①由中断隐指令保存程序的断点(程序计数器) ;
②由中断服务程序保存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。
8． 下列叙述中，不符合m 阶B 树定义要求的是（ ）.
A. 根结点最多有m 棵子树
B. 所有叶结点都在同一层上
C. 各结点内关键字均升序或降序排列
D. 叶结点之间通过指针链接
【答案】D
【解析】B 树就是指树.
根据树的定义，m
阶树中每个结点最多有m 个分支，因此，
树根结点最多有m 棵子树，A 项正确；树中所有叶结点都在最底层，位于同一层，B 项正确；结点内各关键字互不相等且有序排列，C 项正确. 但是，所有叶子结点之间通过指针链接，是
的定义，而树中没有. 因此，D 项是错误的.
9． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。
A.4
B.5
C.6
D.7
【答案】C
【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个(n＞0) 结点的完全二叉树的高度为或由完全二叉树类推到完全三叉树可知，n 个结点的完
相关内容
相关标签