2017年浙江师范大学数理与信息工程学院885数据结构与程序设计考研题库
● 摘要
一、填空题
1． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
2． 栈是_____的线性表，其运算遵循_____的原则。
；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）
3． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。
【答案】n （n-l ）/2
【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。
4． 阅读下列程序说明和裎序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：
（1）把根结点放入堆栈。
（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。
存放还没有转换过的结点，它的栈顶指针为
。
（1）
{（2）
If （ （3） ）
}
}}
【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。
5． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
6． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若则
则
的地址为
若
的地址为将代入得33。
7． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
8． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
9． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
10．A 是一个任意给定的整数。free_tree设T 是一棵结点值为整数的二叉排序树，在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
，）则 的地址为_____。
【答案】
二、选择题
11． 对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（ ）。
A. 排序的总趟数 B. 元素的移动次数 C. 使用辅助空间的数量 D. 元素之间的比较次数 【答案】D 。
【解析】折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，
而记录的移动次数不变。折半插入排序的时间复杂度仍为
所以两者之间的不同只可能是元素之间的比较次数。
12．以下与数据的存储结构无关的术语是（ ）。
A. 循环队列 B. 链表 C. 哈希表 D. 栈 【答案】D
【解析】循环队列体现线性表是以顺序存储。用散列法存储的线性表称散列表。链表说明线性表是以链式结构存储的。栈不能体现出是顺序还是链式存储结构。
13．一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A.107 B.108 C.214 D.215
【答案】B
【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有以
14．下列选项中，能缩短程序执行时间的措施是（ ）。
I. 提高CPU 时钟频率 II. 优化数据通路结构 III. 对程序进行编译优化
所
也就是说若对其进行哈夫曼编码，共能得到108个码字。