2017年南京航空航天大学计算机科学与技术学院922数据结构与操作系统[专业硕士]之数据结构考研冲刺密押题
● 摘要
一、填空题
1． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
2． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
【答案】
3． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
4． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树 5
．
求REPLACE （S ，V , m ）=_____。
【答案】
6． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
7． 表达式
【答案】
8． 组成串的数据元素只能是_____。
【答案】字符
9． 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m
阶个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；
10．二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
树每个结点至多有_____个儿子，除
根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____
已
知
的后缀表达式是_____。
二、选择题
11．已知三叉树T 中6个叶结点的权分别是2，3, 4, 5，6，7, T的带权（外部）路径长度最小是（ ）
A.27 B.46 C.54 D.56
【答案】B
【解析】利用三叉树的6个叶子结点的权构建最小带权生成树，
最小的带权路径长度为
12．响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（ ）。
I. 开关中断II. 保存通用寄存器的内容III. 形成中断服务程序入口地址并送PC A. 仅I 、II B. 仅 I 、III C. 仅 II 、III D.I 、II 、III 【答案】B 。
【解析】中断隐指令完成的操作有3个：①保存断点；②关中断；③引出中断服务程序（形成中断服务程序入口地址并送PC ）。而保存通用寄存器内容的操作是由软件来实现，不是由中断隐指令实现的。
13．下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）。
A. 时间片轮转调度算法 B. 短进程优先调度算法 C. 先来先服务调度算法 D. 尚响应比优先调度算法 【答案】D
【解析】时间片轮转法和先来先服务算法都是公平的方法，并未考虑进程等待时间和执行时间，而短进程优先考虑的是进程执行时间。最高响应比优先调度算法是最先执行响应比最尚的进程（响应比=1＋等待时间/估计运行时间）。该算法综合了先来先服务（FCFS ）和短作业优先（SJF ）算法，FCFS 只考虑每个作业的等待时间，而未考虑执行时间的长短。SJF 只考虑执行时间的长短，而未考虑等待时间的长短，HRRN 算法则同时考虑执行时间和等待时间。
14．—棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有（ ）个结点。
A.2h
B.
C.
D. 【答案】B 【解析】此树满足哈夫曼树，除根节点外每层有两个节点。
15．在一棵度为4的树T 中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T 的叶结点个数是（ ）。
A.41 B.82 C.113 D.122