清华大学模拟试题二
一． 单项选择题（2分/题）
1．一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后，其空链域数为（）。
A.0 B.1 C.2 D.不确定
2．设图G采用邻接表存储，则拓扑排序算法的时间复杂度是（）。
A.O(n) B.O(n+e) C.O(n2) D.O(n*e)
3．下列排序算法中，时间复杂度为O(nlog2n)且占用额外空间最少的是（）。
A.堆排序 B.冒泡排序 C.快速排序 D.SHELL排序
4．已知数据表A中每个元素距其最终位置不远，则采用（）排序算法最节省时间。
A.堆排序 B.插入排序 C.快速排序 D.直接选择排序
5．串是（）。
A.不少于一个字母的序列 B. 任意个字母的序列
C.不少于一个字符的序列 D.有限个字符的序列
二． 判断题（1分/题）
1.（ ）若一个栈的输入序列为123…n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai =n-i+1。(i=1,2,...,n)
2.（ ）二叉树中的叶子结点就是二叉树中没有左右子树的结点。
3.（ ）一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。
4.（ ）删除二叉排序树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。
5.（ ）线性表就是顺序表。
6.（ ）若一棵树中某结点的度为1，则该结点仅有一棵子树。
7.（ ）所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。
8.（ ）AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。
9.（ ）若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反。 10.（ ）在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。
1
二叉排序树操作
一、设计步骤
1）分析课程设计题目的要求
2）写出详细设计说明
3）编写程序代码，调试程序使其能正确运行
4）设计完成的软件要便于操作和使用
5）设计完成后提交课程设计报告
（一）程序功能：
1）创建二叉排序树
2）输出二叉排序树
3）在二叉排序树中插入新结点
4）在二叉排序树中删除给定的值
5）在二叉排序树中查找所给定的值
（二）函数功能：
1） struct BiTnode 定义二叉链表结点类型包含结点的信息
2） class BT 二叉排序树类，以实现二叉排序树的相关操作
3） InitBitree() 构造函数，使根节点指向空
4) ~BT () 析构函数，释放结点空间
5) void InsertBST(&t,key) 实现二叉排序树的插入功能
6) int SearchBST(t,key) 实现二叉排序树的查找功能
7) int DelBST(&t,key) 实现二叉排序树的删除功能
8) void InorderBiTree (t) 实现二叉排序树的排序（输出功能）
9) int main() 主函数，用来完成对二叉排序树类中各个函数的测试
2 二、设计理论分析方法
（一）二叉排序树定义
首先，我们应该明确所谓二叉排序树是指满足下列条件的二叉树：
（1）左子树上的所有结点值均小于根结点值；
（2）右子数上的所有结点值均不小于根结点值；
（3）左、右子数也满足上述两个条件。
根据对上述的理解和分析，我们就可以先创建出一个二叉链表结点的结构体类型（struct BiTNode）和一个二叉排序树类（class BT），以及类中的构造函数、析构函数和其他实现相关功能的函数。
（二）插入函数（void InsertBST(&t,key)）
首先定义一个与BiTNode *BT同一类型的结点p， 并为其申请空间，使p->data=key,p->lchild和p->rchild=NULL。然后通过对int SearchBST(t,key)的返回值，来判断插入的结点是否已存在，若不存在则从根节点开始，按照二叉排序树的定义来寻找存放新结点的位置，已实现插入操作。
习题六 树和二叉树
一、单项选择题
1． 以下说法错误的是 ( )
A．树形结构的特点是一个结点可以有多个直接前趋
B．线性结构中的一个结点至多只有一个直接后继
C．树形结构可以表达(组织)更复杂的数据
D．树(及一切树形结构)是一种"分支层次"结构
E．任何只含一个结点的集合是一棵树
2．下列说法中正确的是 ( )
A．任何一棵二叉树中至少有一个结点的度为2
B．任何一棵二叉树中每个结点的度都为2
C．任何一棵二叉树中的度肯定等于2
D．任何一棵二叉树中的度可以小于2
3．讨论树、森林和二叉树的关系，目的是为了（ ）
A．借助二叉树上的运算方法去实现对树的一些运算
B．将树、森林按二叉树的存储方式进行存储
C．将树、森林转换成二叉树
D．体现一种技巧，没有什么实际意义
4．树最适合用来表示 ( )
A．有序数据元素 B．无序数据元素
C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据
5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A．9 B．11 C．15 D．不确定
6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。
A．M1 B．M1+M2 C．M3 D．M2+M3
7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
A． 250 B． 500 C．254 D．505 E．以上答案都不对
8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )
A．不确定 B．2n C．2n+1 D．2n-1
数据结构PPT教案（清华大学）DS
第一章：引言
1.1 数据结构的概念
数据结构的定义
数据结构的应用场景
数据结构的基本术语
1.2 数据的抽象
抽象数据类型（ADT）
数据结构的表示
数据结构的操作
1.3 算法与数据结构的关系
算法的定义
算法与数据结构的关系
算法分析与评估
第二章：线性表
2.1 线性表的定义
线性表的概念
线性表的抽象数据类型
线性表的表示
2.2 线性表的实现
顺序存储结构
链式存储结构 线性表的扩充操作
2.3 线性表的操作
线性表的插入与删除
线性表的查找与排序
线性表的其他操作
第三章：栈和队列
3.1 栈的定义和应用
栈的概念
栈的抽象数据类型
栈的表示和操作
栈的应用场景
3.2 队列的定义和应用
队列的概念
队列的抽象数据类型
队列的表示和操作
队列的应用场景
3.3 栈和队列的扩展
双向栈和双向队列
栈和队列的链式存储结构
栈和队列的其他操作
第四章：线性表的排序
4.1 排序的基本概念 排序的定义
排序的分类
排序的评价指标
4.2 插入排序
直接插入排序
希尔排序
插入排序的性能分析
4.3 选择排序
简单选择排序
堆排序
选择排序的性能分析
4.4 交换排序
冒泡排序
快速排序
交换排序的性能分析
第五章：查找
5.1 查找的基本概念
查找的定义
查找的评价指标
查找的方法分类
5.2 顺序查找
线性表的顺序查找 有序表的顺序查找
顺序查找的性能分析
5.3 二分查找
二分查找的原理
二分查找的实现
二分查找的性能分析
5.4 哈希查找
哈希查找的原理
哈希函数的设计
哈希查找的性能分析
第六章：树和二叉树
6.1 树的基本概念
树的定义
树的抽象数据类型
树的基本术语
树的性质
6.2 二叉树
二叉树的定义
二叉树的基本性质
二叉树的遍历
二叉树的类型
6.3 线索二叉树 线索二叉树的概念
线索二叉树的遍历
线索二叉树的存储结构
6.4 树的应用
