一、树和森林的概念 二、二叉树 (Binary Tree) 三、二叉树的表示 四、二叉树遍历 (Binary Tree Traversal) 五、线索化二叉树 (Threaded Binary Tree) 六、堆 ( Heap ) 七、树与森林 (Tree & Forest) 八、二叉树的计数 九、霍夫曼树 (Huffman Tree)

8.1 图的基本概念 8.2 图的存储表示 8.3 图的遍历 8.4 图的连通性 8.5 最小生成树 8.6 最短路径 8.7 有向无环图及其应用

顺序查找是一种最基本和最简单的查找方法。它 的思路是,从表中的第一个元素开始,将给定 的值与表中逐个元素的关键字进行比较,直到 两者相符,查到所要找的元素为止。否则就是 表中没有要找的元素,查找不成功。对于表中 记录的关键字是无序的表,只能采用这种方法 。描述顺序查找的算法见框图8-1其中n是表r 的长度,k是要查的元素的关键字,i查到的元 素的序号

3.1 排序的基本概念 3.2 简单的排序方法 3.2.1 插入排序 3.2.2 起泡排序 3.3 先进的排序方法 3.3.1 快速排序 3.3.2 归并排序 3.3.3 堆排序 3.4 基数排序 3.4 各种排序方法的综合比较

1.排列问题(归入第10章中的回溯法一并介绍,此处略) 2.组合问题(同上处理) 3.外排序及广义斐波那契(FIBONACCI)数 4.传递闭包及Warshall算法(学生参考《数据结构》部分的 Floyd算法自学) 课时分配:第3节讲授三个学时、上机三个学时

1999年试题答案: 1. void MergeList_(LinkList &La, LinkList &Lb, LinkList &Lc) /已知单链线性表La和Lb的元素按值非递减排列 /归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列

4.1串类型的定义 4.2串的表示和实现 1定长顺序存储表示 2堆分配存储表示 3串的块链存储表示 4.3串的模式匹配算法 4.4串操作应用举例

9-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的? 【解答】 9-2 设待排序的关键码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次关键码比较

◼ 分治算法的原理 ◼ 大整数乘法 ◼ 矩阵乘法 ◼ 求第k小元素问题 ◼ 寻找最近点对 ◼ 快速傅立叶变换 ◼ 寻找凸包

8-1 画出 1 个顶点、2 个顶点、3 个顶点、4 个顶点和 5 个顶点的无向完全图。试证明在 n 个顶点的无向完全图中，边的条数为 n(n-1)/2。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示