学院名称 专业班级： 姓名： 学号： 我
密 封 线 内 不 要 答 题
┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ 密
┃┃┃┃┃┃┃┃┃┃┃ 封
┃┃┃┃┃┃┃┃┃┃┃ 线
┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
2012 至 2013 学年第 2 学期
数据结构与算法试卷A 卷
出卷教师： 适应班级：空信1201－1202 考试方式：闭卷 本试卷考试分数占学生总评成绩的 80 %
题号 一 二 三 四 总分 核分人
得分
复查总分 总复查人
一、选择题（本题15分,每小题1分）
请将正确的答案填入下面的表格中：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1. 算法分析的目的是 。
A 、找出数据结构的合理性
B 、研究算法中的输入和输出关系
C 、分析算法的效率以求改进
D 、分析算法的易懂性和文档性
2. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址__ ____。
A 、必须是连续的
B 、部分地址必须是连续的
C 、一定是不连续的
D 、连续或不连续都可以
3. 在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_________。
A 、O(1)
B 、O(n)
C 、O(n 2)
D 、O(nlog 2n) 4. 栈的插入和删除操作在___ ___进行。
A 、栈顶
B 、栈底
C 、任意位置
D 、指定位置 5. 稀疏矩阵一般的压缩存储方法有两种，即____ ___。
A 、二维数组和三维数组 B 、三元组和散列
C 、三元组和十字链表
D 、散列和十字链表
6. 依次在初始为空的队列中插入元素为a,b,c,d 以后，紧接着作了两次删除
操作，此时的队头元素是（ ）
A. a
B. b
C. c
D. d 7. 广义表（（a ））的表尾是____ ___。
A 、a B 、（a ） C 、（ ） D 、（（a ）） 8. 下面4棵二叉树，是平衡二叉树的是____ ___。
A B C D 9. 求字符串T 在字符串S 中首次出现的位置的操作称为 （ ） A. 串的模式匹配 B. 求子串 C. 求串的长度 D. 串的连接 10. 深度为5的二叉树至多有____ ___个结点。
A 、16 B 、32 C 、31 D 、15
11. 对于一个具有n 个顶点的无向图，要连通全部顶点至少需要______条边。
A 、n B 、n+1 C 、n-1 D 、n 2
12. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的( )。
A 、先序遍历 B 、中序遍历 C 、后序遍历 D 、按层遍历 13. 对包含N 个元素的哈希表进行查找，平均查找长度为（ ）。
得分 评卷人
学院名称 专业班级： 姓名： 学号： 密 封 线 内 不 要 答 题
┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ 密
┃┃┃┃┃┃┃┃┃┃┃ 封
┃┃┃┃┃┃┃┃┃┃┃ 线
┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
14. 在所有排序方法中，关键字比较次数与记录的初始排列次序无关的是_________。
A 、希尔排序
B 、冒泡排序
C 、直接插入排序
D 、堆排序 15. 实现堆排序的存储结构是（ ）
A 、二重链表
B 、矩阵
C 、单链表
D 、向量
二、判断题（本题15分,每题1分）
对的打 √,错的打 Χ，请将答案填入下面的表格中：
（ ）1、对任何数据结构链式存储结构一定优于顺序存储结构。
（ ）2、循环队列的引入，目的是为了克服假溢出现象。
（ ）3
、由二叉树的先序序列和中序序列能唯一确定一棵二叉树。
（ ）4、空格串可以被看成空串。
（ ）5、在一个AOE 网络中有几条关键路径，只要通过提高其中一条关键路径上的关键活动速度，就能导致整个工程缩短工期。
（ ）6、完全二叉树的某结点若无左孩子，则它必是叶结点。
( )。
（
）7、当初始记录序列安关键字有序或基本有序时，快速排序时间复杂度是O(n 2)，此时它的性能不如起泡排序好。
（ ）8、存在有偶数个结点的满二叉树。
（ ）9.线性的数据结构可以顺序存储，也可以链接存储。
非线性的数据结构只能链接存储。
（ ）10、图的广度优先生成树唯一。
（ ）11、单链表从任何一个结点出发，都能访问到所有结点。
（
）12、冒泡排序和快速排序都是稳定的。
（ ）13、树转化为二叉树，根结点没有右孩子。
（ ）14、邻接矩阵适合存储稠密图。
（ ）15、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数。
三、简答题（本题 40 分）
1. 写出下面图中二叉树的先序遍历结果，并画出它的先序线索
树。
（7分）
2. 给出用Prim 算法构造下列带权图的最小生成树的过程。
（画出中间步骤，从V 1开始）（6分）
学院名称 专业班级： 姓名： 学号： 我
密 封 线 内 不 要 答 题
┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ 密
┃┃┃┃┃┃┃┃┃┃┃ 封
┃┃┃┃┃┃┃┃┃┃┃ 线
┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
3. 假设用于通信的电文由字符集{a, b, c, d, e, }中的字母构成。
它们在电文中出现的频度分别为{0.3, 0.05, 0.4, 0.15, 0.1 }，为这5个字母设计哈夫曼编码。
（要求画出哈夫曼树和写出编码结果，其中左子树权值小于右子树权值。
编码时左边0，右边1）（7分）
4. 有一组关键字（19, 01, 23, 55,16 ,11, 36），设哈希函数为H （key ）= key % 7，用链地址法解决冲突，请画出哈希表，并计算等概率情况下查找成功的平均查找长度。
（7分）
5、对于下面的稀疏矩阵采用三元组法存储，写出其三元组法存储表示。
(6分)
6. 假定一组记录为(55, 77, 33, 66, 22, 88, 99， 44)，对其进行堆排序，
请写出对它进行初始建大顶堆的过程。
（7分）
学院名称 专业班级： 姓名： 学号：
密 封 线 内 不 要 答 题
┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ 密
┃┃┃┃┃┃┃┃┃┃┃ 封
┃┃┃┃┃┃┃┃┃┃┃ 线
┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
四、编写算法(30分，每题15分）
1．在查找表st 中，折半查找关键字的值为k 的记录。
已知查找表事先已按关键字升序排列，查找表存储结构定义为： typedef struct{ elemtype elem[max];
int length;
}sstable;
2．统计二叉树叶子结点个数，设此二叉树以二叉链表作存储结构，定义如下： typedef struct bitnode{ elemtype data;
struct bitnode *lch,*rch;
} bitnode,*bitree;。