24-25-2-数据结构-期末

一、填空题（每题1分，共10分）

二、单项选择题（每题2分，共20分）

7. 由34，92，23，34，52，17，4组成的二叉排序树，则这个二叉排序树最下面两层的结点数 ( )

1

2

3

4

检查

10. 用9，2，3，5，7构造哈夫曼树，求这个哈夫曼树的带权路径长度 ( )

23

32

44

45

检查

三、判断题（每题1分，共10分）

四、简答题（每题10分，共40分）

1.

这是一个逆转链表的代码，请补全空处代码

......

while(Old_Head)
{
    Old_Head=______________；
    _______________________；

    New_Head=
}
_______________________；
return L;

3.

现有在表长11的表中填入以下九个数字：

H(key)=key%11;

采用线性探测法解决冲突，填写下表并写出查找成功和查找失败的ASL

4.

写出以下序列使用直接插入排序和快速排序的前三趟结果，并分析是否是稳定算法，分析算法的时间复杂度

五、算法设计题（每题10分，共20分）

1.

1. 编写判断二叉排序树的代码（包含必要的注释）
2. 设T是一棵二叉排序树，请编写寻找二叉树最小结点的代码 BiNode* FindMin(BiTree T)（包含必要的注释）

2.

1. 写出链栈的类型定义；
2. 链栈的判空、出栈、入栈的代码

要求：

• 简述算法思路，包括函数名、传入参数、返回值
• C/C++实现
• 分析每种算法的时间复杂度