五、算法设计题(25分)
1． 已知一棵二叉树采用二叉链表存放，写一算法，要求统计出二叉树中叶子结点个数并输
出二叉树中非终端结点（输出无顺序要求）。
2．编写算法，判断带头结点的双循环链表L是否对称。
对称是指：设各元素值a1,a2,...,an, 则有ai=an-i+1 即指：a1= an，a2= an-1 。。。。。。 结点结构为
prior
data next
《数据结构》期中卷（2002）
一、简答题（10分，每小题5分）
1．顺序存储结构和链式存储结构各有哪些优缺点？
2．简述栈和队列的共同点和不同点。它们与线性表有什么关系？
二、判断题（10分，每小题2分）正确在括号内打√，错误打×
( )（1）顺序存储结构只能用来存放线性结构，链式存储结构只能用来存放非线性结构。
( )（2）三元组表相当于一个由若干三元组构成的顺序表。
( )（3）广义表的表头是表中第一个元素，表尾是表中最后一个元素。
( )（4）将一棵树转换为二叉树表示后,该二叉树的根结点一定没有右子树。 ( )（5）哈夫曼树中没有度为1的结点。
三、单项选择题（10分, 每小题2分）
1．下面关于串的叙述中，哪一个是不正确的？
A. 串是字符的有限序列 B. 空串是由空格构成的串
C. 模式匹配是串的重要运算 D. 串既可顺序存储，也可采用链式存储
2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为： A. 98 B. 99 C. 50 D. 48
3．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈,
问下列哪一个序列是可能的出栈序列？
A. E、D、C、B、A、F B. B、C、E、F、A、D C. C、B、E、D、A、F D. A、D、F、E、B、C
4．有一个含头结点的单链表，头指针为head, 则判断其是否为空的条件为： A. head==NULL B. Head->next==NULL C. head->next==head D. Head!=NULL
5．在下列存储形式中，哪一个不是树的存储形式？ A. 双亲表示法 B. 孩子链表表示法 C. 孩子兄弟表示法 D. 顺序存储表示法
四、填空题（15分）
填空完成下面中序遍历二叉树的非递归算法： void InOrder（BiTree root） {
InitStack ( &S ); p = _________ ;
while ( _____________ || ! IsEmpty(S)) {
while (p!=NULL)
{
Push(&S, _____ ) ; p = ______________ ;
}
if ( _______________ ) {
Pop(&S, _______ ) ; Visit ( p -> data );
p = _______________ ;
}
} }
五、构造题（15 分, 每小题5分）
1. 已知一棵树如图1所示,请将该树转化为二叉树。
2002级《数据结构》试卷A参考答案与评分标准
一、简答题（15分，每小题3分）
1. 算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。
2. 主要与哈希函数、装填因子α有关。如果用哈希函数计算的地址分布均匀，则冲突的
可能性较小，如果装填因子α较小，则哈希表较稀疏，发生冲突的可能性较小。 3. 图中结点可能有多个前驱，设置访问标志数组主要是为了避免重复访问同一个结点。 4. 头指针指向头结点，头结点的后继域指向首元素结点。
5. 当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，因
此叫假溢出。解决的方法是采用循环队列，即令最后一个单元的后继是第一个单元。
二、判断题（10分，每小题1分）
（1）(√) （2）(×) （3）(×) （4）(√) （5）(×) （6）(√) （7）(×) （8）(√) （9）(×) （10）(×)
三、单项选择题（10分, 每小题1分）
1． D） 2． B） 3． C） 4. C） 5. B） 6. A) 7． C) 8． D) 9． C） 10．C）
四、填空题（10分，每空1分）
1． high low low high 2. S->next=R->next ； R->next=S ； 3． 时间 空间 4． A[2, 3] 5． 2h-1
五、构造题（20 分）
1．（4分）
2．（6分）
0 1 2 3 4 5
SUN MON THU FRI WED TUE
ASLsucc = ( 1×4 + 2×2 + 3 ) / 7 = 11 / 7
6 SAT
7
8
9
3.（6分）
4．（4分）已知权值集合为：{ 5，7，2，3，6，9 }，要求给出哈夫曼树，并计算其带权路径长度WPL。
WPL = 2×( 9 + 6 + 7 ) + 3×5 + 4×( 2 + 3 ) = 79
六、算法分析题（10分）
解：
（1） 在二叉排序树中插入关键字为K的结点
（2） h = log2 ( n+1 ) 或 h = [ log2 n ] + 1 （方括号表示向下取整） （3） O ( log2 ( n+1 ) ) 或 O ( log2 n )
七、算法设计题（25分）
（答案略）
试卷成绩分析表
填表日期： 年 月 日 课程名称 数据结构 课程类型 必修 院系、年级、专业、班级 命题人及所在 院系 阅卷人及所在 院系 计算科学系2002级 计算科学与技术专业 1、2、3、4班 审批人 阅卷方式 试卷结果分析：（包含试题知识点覆盖程度、难易分布程度、学生成绩分布情况等） 1. 知识点覆盖程度 试题涉及的知识点包括：数据结构基本概念；顺序表、循环单链表、双向循环链表的特点和基本操作，单链表的操作与应用；循环队列的特性与链队列的基本操作；数组的存储结构与存取特性，广义表的基本操作；二叉树的性质与存储结构，二叉树的创建，由遍历序列确定二叉树，哈夫曼树的性质与构造；图的存储结构与基本操作，图的连通性与图的遍历；折半查找的基本过程，二叉排序树的非递归插入算法，构造哈希表；冒泡排序，快速排序，堆排序，基数排序等。知识点覆盖比较全面，重点比较突出。 2. 难易分布程度 较简单的题目有：2个简答题、4个判断题、4个选择题、2个填空题，1个构造题，1个算法设计题。较难的题目有：1个简答题、2个判断题、2个选择题、1个填空题，1个构造题，1个算法设计题。中等难度的题目有：2个简答题、4个判断题、4个选择题、2个填空题， 2个构造题，1个算法分析题，1个算法设计题。难易分布合理，总体难度适中。 3. 学生成绩分布情况 90—100：6人，80—89：26人，70—79：35人，60—69：25人，＜60：11人 成绩分布比较合理，说明试题具有良好的区分度。 试卷中存在的问题和建议： （1） 判断题、选择题偏多，建议压缩判断题、选择题数目。 （2） 算法填空题、算法分析题偏少，建议适当增加算法填空题和算法分析题。
阅卷人签字：