09－10第二学期期末考试试卷
试卷代码：18335C 授课课时：96 考试用时：150分钟 课程名称：数据结构与算法（软件） 适用对象：软件工程选课班
试卷命题人 邓庆山 试卷审核人 一、填空题（每空2分，共20分）
1. 栈与队列和一般线性表的区别体现在_____________。 2. 向一个长度为n的顺序线性表删除第i个元素（1<=i<=n）,需向前移动______个元素。 3. 在双向链表中，每个结点有两个指针域，一个指向_________，一个指向_________。 4. 在一棵二叉树中，度为0的结点的个数是10，则度为2的结点个数是_________ 5. 一个有n个结点的二叉树的深度最大为___________，最小为__________ 6. n个定点的连通图至少有_______条边。
7. 在无向图G的邻接矩阵A中，若(vi,vj)属于图G的边的集合，则对应元素A[i][j]等于_______，否则等于_________.
二、选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。每小题2分，共10分。）
1.组成数据的基本单位是（ ）
A.数据项 B.数据类型 C.数据元素 D.数据变量 2.链表不具备的特点是 （ ） A. 可随机访问任何一个元素
B. 插入、删除操作不需要移动元素 C. 无需事先估计存储空间大小
D. 所需存储空间与线性表长度成正比
3.head为指向单链表的头结点中的指针，判断该链表的非空条件是（ ）。 A. head==NULL
B. head->link==NULL C. head!=NULL
D. head->link!=NULL
4.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。 A. edcba B. decba C. dceab D. abcde 5.请选出下列说法中唯一正确的一个：（ ）。
A. 判断队列是否为空只能通过头结点的count信息来判断。 B. 除了头结点，队列中的每一个元素都只有一个唯一的前驱。 C. 队列在实现递归算法、表达式求值等方面有较多的应用。 D. 队列是一种典型的后进先出（LIFO）的数据结构。
6.如果一棵二叉树结点的前序序列是A、B、C，后序序列是C、B、A，则该二叉树结
【第 1 页 共 3 页】
点的中序序列（ ）。
A. 必为A、B、C B. 必为A、C、B C. 必为B、C、A D. 不能确定 7.含有15个结点的二叉树的最小高度是（ ）
A. 3 B. 4 C. 5 D. 6 8.具有 n(n>0) 个顶点的无向图最多含有（ ） 条边。 A. n(n-1) B. n(n+1) C. n(n-1)/2 D. n(n+1)/2
9.在线形表中采用折半查找法查找一个数据，线性表应满足（ ）
A. 以数组方式存储。 B. 以链接方式存储
C. 以数组方式存储且结点按关键码有序排列。 D. 以链接方式存储且结点按关键码有序排列 10.快速排序在下列（ ）情况下最易发挥其长处。
A. 被排序的数据中含有多个相同排序码 B. 被排序的数据已基本有序
C. 被排序的数据完全无序 D. 被排序的数据中的最大值和最小值相差悬殊 三、简答题（要求写出主要操作步骤及结果。每小题5分,共35分） 1．试写出下列程序段的输出结果（栈的元素类型是char）
void main() { stack S;
char x=’c’,y=’k’; InitStack(S);
Push(S,x);Push(S,’a’);Push(S,y); Pop(S,x);Push(S,’t’);Push(S,x); Pop(S,x);Push(S,’s’); While(!StackEmpty(S)){
Pop(S,y);printf(“%c”,y); }
printf(“%c”,x); }
2. 已知如下的一棵二叉树，写出其先序，中序，后序和层序序列。
A
B C
D E F
H G
I
3. 假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。
【第 2 页 共 3 页】
4．已知一无向图的邻接表如下所示，写出从顶点V1出发的深度和广度优先搜索序列。
5. 求出下图的一棵最小生成树。
3 1 6 4 7 3 5 4 8 5 7 8 4 5 8 6 5 6 6 2 3 6.设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试用希尔排序(增量为5,2,1)排序，写出每趟排序后的结果。
7.设散列表为T[0..12]，哈希函数为H(key)=key%13,给定键值序列是{52,41,95,21,14,28,82,30}，请画出用线性探测再散列方法处理冲突时所构成的散列表，并求出在等概率情况下，查找成功的平均查找长度。
四、证明题（要求写出证明过程。共8分）
证明：在有N个叶子的哈夫曼树上，其结点总数为2N-1。 五、算法设计题（共17分，第1题8分，第2题9分）
1. 试写一个算法，实现在顺序线性表L中第i个位置之前插入新的元素e。 2. 给出二叉树的二叉链表存储结构，计算二叉树中的叶子结点个数。
【第 3 页 共 3 页】
因篇幅问题不能全部显示，请点此查看更多更全内容