数据结构教学资料数据结构计划.doc

《数据结构教学资料数据结构计划.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2001～2002年度《数据结构》教学计划周大课习题安排次教学内容笔做题上机题思考题1绪论；1.41.91.71.11.2数组的概念；顺序表1.82稀疏矩阵；字符串及其操作的实现；2.12.32.22.52.10模式匹配2.72.92.133单链表；循环链表；双向链表；2.153.22.143.32.173.1稀疏矩阵；虚函数和动态联编(自学)3.63.83.104栈；队列；优先级队列3.94.24.33.124.124.133.104.44.94.105递归的概念；迷宫问题(自学)；递归4.155.35

2、.15.55.45.7过程与递归工作栈；广义表5.65.86树与森林的概念；二叉树及其表示；6.16.56.96.46.7二叉树遍历6.106.87线索化二叉树；堆；森林及其遍历；6.146.166.126.186.116.17霍夫曼树6.196.208集合及其表示；等价类和并查集6.217.26.226.237.97.49期中测验；7.87.137.117.107.12静态搜索结构10二叉搜索树；最佳二叉搜索树；7.187.217.207.167.17AVL树7.227.197.2411图的概念；图的存

3、储表示；8.88.118.98.28.4图的遍历与连通性8.158.712最小生成树；活动网络；8.238.248.178.288.258.26排序概述；插入排序8.2713交换排序；选择排序；归并排序9.69.99.119.179.89.129.149.199.1514基数排序；外排序9.239.259.199.219.249.269.2715静态索引结构；动态索引结构10.410.510.1010.1110.1310.210.710.910.1210.1416散列表及其分析10.1710.1810.2

4、310.1910.22【主教材】清华大学计算机系列教材数据结构（用面向对象方法和C++描述），殷人昆，陶永雷，谢若阳等，清华大学出版社，1999年7月【参考教材】CliffordA.Shaffer,APracticalIntroductiontoDataStructuresandAlgorithmAnalysis,1997byPretice-Hall,Inc.,电子工业出版社中译版,中译名《数据结构与算法分析》,张铭,刘晓丹译,1998年教学要求1.数据结构基本概念及简单的算法分析了解数据结构基本概念及数

5、据结构的抽象层次；了解抽象数据类型及面向对象概念；了解算法的定义及算法的特性；掌握算法的性能分析与度量方法。2.数组了解作为抽象数据类型的数组的定义；熟练掌握顺序表的数组定义方式及实现；熟练掌握：字符串的定义及实现。3.链表熟练掌握单链表、循环链表及双向链表的定义及实现。4.栈和队列熟练掌握栈的定义及实现；熟练掌握队列的定义及实现；掌握优先级队列的定义及链表实现。5.递归掌握递归的概念；掌握递归过程的机制与利用递归工作栈实现递归的方法；了解利用栈如何实现迷宫问题的非递归解法；掌握广义表的定义及其实现方法；

6、掌握广义表的递归算法。6.树与森林了解树和森林的概念；掌握二叉树的概念、性质及二叉树的表示；掌握线索化二叉树的特性及寻找某结点的前驱和后继的方法；熟练掌握堆的定义及其实现的方法，以及用来实现优先级队列的方法；掌握树与森林的实现和遍历方法；掌握二叉树的计数方法及从二叉树遍历结果得到二叉树的方法；掌握霍夫曼树的实现方法及霍夫曼编码的概念。7.集合与搜索掌握集合及其表示方法；掌握等价类的链表实现与利用并查集实现的方法；熟练掌握静态搜索表的顺序搜索和折半搜索方法；熟练掌握二叉搜索树的表示、搜索、插入、删除算法及其

7、性能分析方法；掌握AVL树的构造、性能分析方法。8.图掌握图的基本概念和图的存储表示；熟练掌握图的两种遍历方法与求解连通性问题的方法；掌握构造最小生成树的Prim和Kruskal方法；熟练掌握活动网络的拓扑排序方法；掌握求解关键路径的方法。9.排序掌握排序的基本概念和性能分析方法；掌握插入排序、交换排序、选择排序、归并排序等内排序的方法及其性能分析方法；了解基数排序方法及其性能分析方法；掌握多路平衡归并等外排序方法及败者树构造方法；掌握生成初始归并段及败者树构造方法；最佳归并树的建立方法。10.索引与散列

8、结构熟练掌握静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法；熟练掌握动态索引结构，包括B_树、B+树的搜索和构造方法；熟练掌握散列法，包括散列函数的构造、解决冲突的方法。