中国科学技术大学 - 数据结构 教学大纲

课程名称    数 据 结 构 IjPtJwW`A  
英文名称    Data Structures gfXit$s  
课程编号    不填    总学时    60    学 分    不填 UWgPQ%}  
预修课程    C语言    开课学期    不填 1A7(s0J8 :  
大纲撰写人    黄刘生 "f!H[F1~  
一、教学目标和基本要求 jjoyMg95  
    目的：使学生较全面地掌握各种常用的数据结构，提高其数据抽象和程序设计能力,为学习后续软件课程提供坚实的基础。 R4f_Kio  
    基本要求：使学生能够从逻辑结构、存储结构和数据的运算三个方面去掌握各种数据结构的特性, 对算法的时、空复杂性有一定的分析能力，使之能够针对具体的应用问题， 选择合适的数据结构及设计结构清晰、正确有效的算法解决之。 I~M@v59C  
二、课程简介 X5)].[d  
  数据结构是计算机学科一门重要的专业基础课，该课程系统地讨论各种常用的数据结构及其应用，以及查找和排序的各种方法及其综合分析比较，培养学生数据抽象和程序设计的能力，算法时、空复杂性的分析能力。 |r`0< `  
三、教学重点、难点 J.,7d ,  
1．    概论：重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及其相互关系，难点是抽象数据类型和算法复杂度的分析方法。 yD^Q&1   
2．    线性表：重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用所学到的基本知识设计有效算法解决与线性表相关的应用问题。 ;3O=
lo:$~  
3．    栈和队列：重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。 rV/! VJ6x  
4．    串：重点是掌握串上实现的模式匹配算法，这也是本章的难点。 H3|x  
5．    树：重点掌握二叉树的遍历算法及其有关应用，难点是使用本章所学到的有关知识设计出有效算法解决与树或二叉树相关的应用问题。 /kFw(l_.  
6．    图：重点掌握图在邻接矩阵与邻近表上实现的遍历算法。难点是求图的最小生成树、最短路径、拓扑排序等应用算法及其时间性能分析。  4V 5  
7．    动态存储管理: 重点是内存空间的分配与回收算法，以及可利用空间表的结构。本章难点是无用单元收集算法的理解与掌握。 x1.yi-  
8．    查找：重点掌握顺序查找、二分查找、二叉查找树上查找以及散列表上查找的基本思想和算法实现。本章难点是二叉查找树的删除算法及B-树上的插入和删除算法。 \avgXndI  
9．    文件：本章重点是介绍存储在外存上的数据絇OST http://www.freekaobo.com/post.php? HTTP/1.0 w"FBJULzn9  
Pro和更新操作。 wn>?r ?KIB  
\ci[<CP  
lT-LOu|  
四、教材名称及主要参考书 7,D6RP(b  
《数据结构C语言版》严蔚敏、吴伟民，清华大学出版社，2000。 AI*1k xR  
《数据结构第2版》黄刘生、唐策善，中国科技大学出版社，2001。 II}3w#r4  
"Data Structures with C++" Williaw Ford et al., Prentice Hall Inc., 1996. |D[4G6&  
"Data Structures & Program Design in C, 2nd Ed." Robert Kruse et al., Prentice Hall Inc., 1997. I(
0 *cWO  
五、课程章节主要内容及学时分配 y[~w2a&+  
@]:GT rs  
第一章 概 论（3学时） D"GQlR  
第一节 基本概念和术语 y(Ck j"  
第二节    学习数据结构的意义  ood ,k{  
第三节    抽象数据类型 L=-v >YL+  
第四节    算法的描述和分析 0r'<aA`=I  
第二章 线性表（6学时） KIHr%  
第一节 线性表的逻辑结构 &-M}:'
  
第二节 线性表的顺序存贮结构 
/UPe@  
第三节 线性表的链式存贮结构 CUZ ;<Pn  
第四节 顺序表和链表的比较 z+qrsT/?L  
第三章 栈和队列（6学时） }E](NvCq  
第一节 栈 zQyt1&!  
第二节    队列 `l`)Cs;a  
第三节    栈与队列的应用实例 Ny)N  
第四章 串（4学时） -_ "6jU  
第一节 串及其运算 `_5{: 9N$  
第二节    串的存贮结构 3YOYlb %j  
第三节    串的模式匹配 ?*2Uw{~}  
第六章 树（10学时） UU"'  
第一节 树的概念 }2~$"L,_  
第二节 二叉树 "3X~BdH&J  
第三节    二叉树的遍历  Oa/#2C~  
第四节    线索二叉树 GYK&QYi,  
第五节    树和森林 SdQ"S-H  
第六节    哈夫曼树及其应用    第七节    树与等价问题、树的计数 4vb
tB2  
第六章 图（10学时） /#xx,?~xx0  
第一节 图的概念 y?@(%PTp  
第二节 图的存贮结构 lzup! `g  
第三节 图的遍历 hqVxvS"  
第四节 图的连通性问题 9s@$P7N5B  
第五节 最短路径 2u?k;"]V  
第六节    有向无环图及其应用 U>=& 2Z2?  
第七章 动态存储管理（5学时） X|Z2"*;b`  
第一节 概述 oVYW'~OID  
第二节    可利用空间表及分配算法 |v31weD8  
第三节    边界标识法 6A,-?W'\  
第四节    伙伴系统 Tq*K =^  
第五节    无用单元收集 pZaOd;t  
第八章 查找（8学时） T?Y/0znB*  
第一节 基本概念 }{(J*T  
第二节 静态查找 ?'I pR  
第三节 动态查找 G~N$bF^R)  
第四节 散列查找 i]M:ntB"  
第九章 文件简介（2学时） 99tKs  
第一节    文件基本概念 TM2pE/P  
第二节    顺序文件与索引文件 rVF7!|&  
第三节 ISAM和VSAM文件 l11+sqg  
第四节 散列文件 CZ4Nw]dtR  
六、系教学委员会意见 (f `zd.  
u#r[JF9LP  
I' TprT  
n0rAO
kW  
K! I]0!:  
组长签字：       年 月 日 |E5\_Z  
七、系主任意见 \PJpy^i  
WO]9\"|y  
Lk>o`<*  
(dgBI}Za  
K 0Gm ?(  
系主任签字：       年 月 日