2008～2009学年第 二 学期
《数据结构与算法》课程考试试卷(A卷) (开卷)
班级___________________学号____________________ 姓名_________________ 考试日期: 2009年4月26日 考试时间: 15:00-17:30
题号 得分 得 分 评卷人 解答内容不得超过装订线 一 二 三 四 五 六 七 八 九 十 总分 一. (30分)名词解释及举例。
1. 设表中的元素类型为int型, 用C语言定义一个顺序存储的线性表, 并画出内存分配图。
2. 设结点中的数据部分的类型为int型, 用C语言定义一个单向线性链表, 并画图表示之。
3. 设栈中元素类型为int型, 用C语言定义一个顺序存储的栈, 画出栈在初始状态、某中间状态和结束状态时的示意图, 并给出某中间状态下一个push、pop操作后栈的变化。
4. 设队列中元素类型为int型, 用C语言定义一个顺序存储的队列, 画出队列在初始状态、某中间状态和结束状态时的示意图, 并给出某中间状态下进队列、出队列操作后队列的变化图。
1
5. 给出树的定义, 并用图形方式举一例子。
6. 给出二叉树的定义, 并画一棵二叉树。
7. 什么是完全二叉树, 并画一棵完全二叉树。
8. 设结点中数据部分的类型为int型, 给出用链式存储结构存储二叉树时结点的C语言结构类型定义, 并用二叉链画一棵二叉树。
9. 给出B_树的定义
10. 给出图的定义, 并画一个边上带权的有向图。
2
得 分 评卷人 二. ( 6 分) 设元素类型为int型, 编写一个函数原型为
void Insert( int A[], int n, int idx, int x );
的插入函数, 完成A中下标idx之前插入元素x的功能, 其中n为A中
已有元素个数。 王五;44,赵六;分别画出这4个学生记录的按学号从小到大顺序链接的 评卷人 带头结点的线性单向链表和带头结点的双向循环链表.
2. 设有另一个学号为25,姓名为刘七的学生记录,画出分别插入到
以上单向链表和双向循环链表后得到的仍是按学号从小到大链接的新的链表,图示插入过程, 并写出指针赋值语句. 得 分 三. (10分) 1.设有4个学生,学号和姓名依次为11,张三;22,李四;33,
3
得 分 评卷人 得 分 评卷人 四. (6分)设有C语言算术表达式 5+4*(3-9/2*6)+8, 画出用栈计算这
一表达式的每步过程。
五. (6分) 设有如下递归函数
int Fib(int i)
{ if(i==0) return 0; if(i==1) return 1;
return (Fib(i-1)+Fib(i-2));}, 给出Fib(3)的递归调用过程。
得 分 评卷人 六. (8分) 对下图所示二叉树, 给出其顺序存储结构及先序遍历、中序遍
历、后序遍历得到的结点序列。
+ － / d * `
a
e b c 4
得 分 评卷人 得 分 评卷人 ;
七．(10分) 设用于通讯的电文仅由5个字母{A,B,C,D,E }组成，字母在
电文中出现的次数分别为2, 12, 4, 5, 8, 构造哈夫曼树并为这5个字母设计哈夫曼编码。
八．(12分) 如图所示,
1. 分别给出此图的邻接矩阵和邻接表.
2. 给出从顶点V1出发的用深度优先算法遍历的每步过程和结果. 3. 给出从顶点V1出发的用广度优先算法遍历的每步过程和结果.
V1 V2 V6 V3 V4 V5 5
得 分 评卷人 得 分 评卷人
九．(6分) 设数据元素的类型为int型, 编写一个针对从小到大有序
的顺序存储线性表进行二分查找的C语言函数(要求用非递归算法)。
十．(6分) 设有关键字序列 11, 22, 25, 18, 15, 60, 40, 31, 设Hash
表的长度为6, Hash函数为取余数法,冲突解决用链表法, 对上述序列给出所建Hash表。
6
