第一篇：2014年春季数据结构课程实习
专业认知型课程实习题目及要求
[选好题目]：
每人必须从下面5题中任意选一题作为设计，独立思考，认真完成，课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。
[课程实习报告]:
(保存在word 文档中,文件名要求 按照“班级_姓名_学号_课程实习报告”起名,如文件名为“12信科2张三_001_课程实习报告”.doc)按照课程实习的具体要求建立的功能模块,每个模块要求按照如下几个内容认真完成;
(1)需求分析：
在该部分中叙述每个模块的功能要求
(2)概要设计
在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明(如果指定存储结构请写出该存储结构的定义)。
(3)详细设计
各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。
(4)调试分析
测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。
[课程实习总结]：
（保存在word 文档中）总结可以包括 : 课程实习过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程实习过程中对《数据结构》课程的认识等内容。
[课程实习提交]:
提交内容：课程实习报告（具体格式见题目后附录），统一采用A4纸双面打印输出。报告电子版和程序由学委收齐后发教师邮箱。
提交时间: 第17周星期5前（6月13日），无故迟交无成绩！检查时间: 第17周星期5（6月13日）下午3点在机房。注意事项：1：请同学们注意课程实习报告的提交时间。
2：请按照附件提供的格式组织课程实习，并附上自评分。
【课程实习题目】：
1、利用随机函数产生两列(每列个数均为200且每个数均不小于10)的随机整数,对这两列整数写一个程序实现如下功能操作：
(1)两列整数在顺序存储方式中，(a)找出这两列数中的素数；(b)把两列数中相同的数转化为二进制数输出。
(2)两列整数在链表存储方式中，(a)统计两链表中相同元素的个数；(b)合并这两个链表为一个；(c)分别删除第一链表中能被2整除的结点和第二个链表中能被3整除的结点。
2、利用随机函数产生127个(不大于200且各不相同的)随机整数，用这些整数来生成一棵二树：
(1)分别对二叉树进行先序遍历，中序遍历和后序列遍历输出树中结点元素序列。注意：先序遍历输出要求采用非递归来实现。
(2)输出二叉树中从根到叶子结点间整数和最小的结点路径序列。
3、题目：校园导游图
设计一个校园导游程序，随着华农大校园建设越来越漂亮，春季来赏花的游客逐年攀升，请为来访客人提供各种信息查询任务。
基本要求：
(1)设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介信息，以边表示路权，存放路径长度等相关信息。
(2)为来访客人提供图中任意景点相关信息的查询（如景点简介，相关交通信息等）
(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
4、用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”
字符A B C D E F G H I J K L M频度 64 13 22 32 103 21 15 47 57 1 5 32 20 字符N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16、农夫，狼，羊和菜过河问题
问题描述：有一个农夫带有一条狼，一只羊和一筐菜，想从河的左边乘船去右边，但是由于船太小，每次农夫只能带一样东西过河，而且，如果没有农夫看，则狼会吃羊，羊会吃菜。问农夫怎样过河才能把每样东西安全送过河。
要求：
(1)将上面问题用图表示出来；
(2)选择图的一种存储结构，编写一个自动生成图的算法。
(3)在(2)的基础上编写求解问题算法的程序。
××××××××××××××××××××××××××××× ×××××××××课程实习报告格式要求×××××××××× ××××××××××××××××××××××××××××× • A4打印，按统一封面装订，附页码;
• 报告正文部分主要内容包括：
（1）选题内容
（4）详细设计
（7）总结（2）需求分析（5）调试分析（8）参考文献（3）概要设计（6）系统运行效果图
• 课程设计提交内容：课程设计报告（打印稿和电子稿）和源程序代码
• 完成截止时间：第17周星期五前(6月13日)
• 检查：教师随机抽8位同学检查其完成情况，时间是6月13日下午3点，参加演示的同学视完成情况加2～5分，抽到不来扣3分，其名额可由其他同学代替。
• 课程实习提交内容：课程实习报告（打印稿和电子稿）以及源程序代码。由学习委员收齐后，纸质版报告在检查时提交；电子稿及源程序按姓名学号整理压缩后发到邮箱liang_ru_bing@163.com.• 注：课程实习报告着重说明个人所做工作、成果和体会，报告不得与他人雷同，否则影响自己与他人成绩，严重者无成绩！请认真对待！
第二篇：课程感想-数据结构
转眼间半学期已经过去了，接触数据结构这门课已经八周了。在这一段时间的学习中，我对这门课从刚开始的一窍不通到现在已经可以运用所学的知识解决一定的问题，大致知道了数据结构的思想和作用。
首先对于数据结构，我的认识一直在发生改变，一开始的时候连逻辑结构和物理结构都分不清，到最后能将总表上的内容熟记于心，并加以运用，这样的进步离不开老师的细心教导和同学们的热心帮助。在我的认识中，计算机技术早已经成为新世纪的必修技能。很庆幸我选的专业可以在计算机上有所进阶，为自己在日后的竞争中多添一份筹码。“数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已经成为其他理工专业的热门选修课。
在这门课程里，我首先认识了什么是数据、什么是数据结构以及抽象数据类型这些基本的概念，然后开始学习数据结构的抽象数据的部分。线性表是学习的第一站，我逐渐发现，每开启一个新的逻辑结构，就会相应的讲它的存储结构以及相应的运算。在学习线性表的过程中，我弄明白了很多东西，发现了数据结构已经比c语言高出一个高度了更加宏观地去用c语言，c语言就像是处理数据结构的其中一种工具一样。学习完线性表之后，就像有了一个模板，之后的栈和队列是进出的方式有所修改各有特色了。学到树的时候，眼前一亮，觉得这样的类比方式很有意思，有点像高中生物遗传学上的系谱图。二叉树的遍历让我觉得就像小时候玩智力游戏一样，还有二叉树中例如求深度这样的高度提炼规律又是需要我去努力思考认真总结的„„这门课让我第一次觉得大学还真的有题要想的这么费脑子。
老师上课的方式也很有效率。刚开始的时候我被一大堆概念搞晕了，但是想着就是一堆概念而已课下也就没再去细细研究。结果上课老师提问的时候果然没有答上来，之后每次课前课后都要争取做到预习复习，巩固课上学的知识。不过学知识当然也不是为了应付老师的提问，既然选择了智能，以后这条路要走的顺畅，还少不了数据结构的知识。
结课的时候老师布置了几道编程的题目，一开始看到书上题目里直接有代码，就赶紧往c语言的软件里敲，结果发现运行不成，和同学们交流了之后才知道，可能是调取数据库的问题，书上的函数编译器无法识别，于是我发现我们的主要任务是集中火力把书上提供的功能函数的功能写出来，换言之，就是构造出这些个函数然后再使用它们去实现功能。在编程的过程中出现了很多的问题，比如指针本来就是c语言中的灵魂，难点中的难点，在数据结构的编程中几乎全部都要用到指针，让我不得不又翻开c语言的教材去复习指针的相关知识。另外，编出来的程序有时候自己看不出来错误但是编译器就是报错，又请教了班里一些已经完成的同学，在他们的意见指导下，改进自己的代码最终运行成功实现功能了。尤其是二叉树的那道题，因为书上没有讲如何输入二叉树，我就在思考无果之后去查资料，才了解c语言是这样和二叉树联系在一起的。当年创造出数据结构的人真的是非常厉害。经过这次的编程，我觉得自己不仅捡起来了上学期学的c语言，也加深了对数据结构和c语言的理解。我们现在掌握的数据结构的知识，就如同我偶然在图书馆看到数据结构的书架一样，只是这个庞大、精深体系中的冰山一角而已，就像老师说的，编程类的知识，老师只是把你带进门，想要真正掌握还是要自己下很多功夫的。
转眼间数据结构这门课已经接近尾声，很多人都说编程是一条孤独的、枯燥的路，其实我感觉编程还挺好玩，每编一个程序都像是一场斗智斗勇的冒险，一头扎进去就是好几个小时，也会经常和同学分享一下自己的思路或者见解，越学越觉得智慧殿堂无穷无尽。有时候我以为我自己设计的已经比较简洁比较巧妙了，听了别人的更是醍醐灌顶，觉得自己傻透了。
在这一段时间的学习里，我们同学之前互相沟通交流，互相帮助过得也很愉快，和刘老师相处的也非常融洽，希望老师在日后的生活教学中多注意身体，老师在教我们之前生了一场病，如果不是这样，老师上课的风采应该更甚。在以后的学习中，我也会继续探究数据结构的奇妙世界，学无止境，争取在数据的道路上更上一层楼！
第三篇：数据结构课程教学大纲
数据结构课程教学大纲
一、课程基本概况
课程名称：数据结构
课程名称（英文）： Data Structures
课程编号：B09042
课程总学时：60（其中，讲课48，实验12）
课程学分：3
课程分类：专业选修课
开设学期：4
适用专业：计算机网络工程本科
先修课程：集合论，图论，高级语言（结构或记录，指针）
后续课程：数据库，编译原理，操作系统等
二、课程的性质、目的和任务
数据结构是计算机专业的一门核心专业课程，是软件课程中非常重要的一门课程，在整个专业教学中占有十分重要的地位，是一门理论性非常强的课程。通过课堂教学、课外练习和上机实习，使学生了解数据对象的特性，数据组织的基本方法，并初步具备分析和解决现实世界问题在计算机中如何表示和处理的能力以及培养良好的程序设计技能，为后续课程的学习和科研工作的参与打下良好的基础。
三、主要内容、重点及深度
本门课程共60学时，其中理论教学48学时，实验教学12学时。其中，理论教学部分：
第一章
绪论
（一）目的要求
了解数据结构的意义与发展过程、数据结构在计算机科学中的作用、学习本课程的目的、任务及要求。理解数据结构的基本概念；算法设计；掌握算法的时间和空间复杂度。
（二）教学内容 本章知识点：
1.相关的基本概念(掌握)；
2.算法五大要素(掌握)；
3.计算语句频度和估算算法时间复杂度的方法（掌握）。
（三）重点与难点
重点：数据结构的定义；算法的描述方法。
难点：数据结构的定义；算法与程序的区别；时间复杂度及其计算。
第二章
线性表
（一）目的要求
掌握线性表的逻辑结构；线性表的存储结构及操作的实现；理解一元多项式的表示；
（二）教学内容 本章知识点：
1.线性表的逻辑结构(掌握)；2.线性表的存储结构(掌握)；
3.线性表在顺序结构和链式结构上实现基本操作的方法(掌握)；
4.从时间和空间复杂度的角度比较线性表两种存储结构的不同特点及其适用场合(掌握)。
（三）重点与难点
重点：线性表的概念；线性表的顺序存储结构、链式存储结构及其常用算法。难点：链式存储结构及其常用算法；双向循环链表。
第三章 栈和队列
（一）目的要求
掌握栈的定义，表示及实现；表达式求值；栈与递归过程；队列的定义、表示及实现。
（二）教学内容 本章知识点： 1.栈和队列的特点(掌握)；
2.在两种存储结构上栈的基本操作的实现(掌握)； 3.循环队列和链队列的基本运算(熟练掌握)； 4.递归算法执行过程中栈状态的变化过程(掌握)。
（三）重点与难点
重点：堆栈和队列的概念；递归的定义；循环队列和链队列的基本运算。难点：递归的编程实现；循环队列和链队列的基本运算。
第四章 串
（一）目的要求
了解串的逻辑结构，存储结构；掌握串操作的实现(重点难点BF和KMP算法)串的应用。
（二）教学内容 本章知识点：
1.串的七种基本运算的定义（了解）；
2.利用这些基本运算来实现串的其它各种运算的方法(掌握)； 3.在顺序存储结构上实现串的各种操作的方法(掌握)；
4.KMP算法，熟悉NEXT函数和改进NEXT函数的定义和计算(掌握)； 5.串名的存储映象和在堆存储结构实现串操作的方法(理解)。
（三）重点与难点 重点：串定义和存储方法；串的操作 难点：串操作实现方法
第五章 数组和广义表
（一）目的要求
掌握数组的存储结构；稀疏矩阵的表示及操作的实现；广义表的定义和存储结构；广义表的递归算法。
（二）教学内容 本章知识点：1.数组在以行为主的存储结构中的地址计算方法(掌握)； 2.矩阵实现压缩存储时的下标变换(掌握)；
3.理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵时进行运算采用的处理方法(掌握)；
4.广义表的定义及其存储结构，学会广义表的表头，表尾分析方法(掌握)； 5.学习编制广义表的递归算法(掌握)。
（三）重点与难点
重点：多维数组元素存储地址的计算；稀疏矩阵的三元组表示；广义表的存储定义、操作。难点：稀疏矩阵的三元组表示；广义表的存储定义、操作。
第六章 树和二叉树
（一）目的要求
了解树的基本概念；理解二叉树的性质和存储结构；遍历二叉树和线索二叉树；理解树的存储结构和遍历；集合的一种表示方法；掌握哈夫曼树及其应用；
（二）教学内容 本章知识点： 1.二叉树的结构特点(理解)；
2.二叉树的各种存储结构的特点及适用范围(掌握)； 3.按各种次序遍历二叉树的递归和非递归算法(掌握)；
4.二叉树的线索化，在中序线索树上找给定结点的前驱和后继的方法(掌握)； 5.树的各种存储结构及其特点(掌握)； 6.编写树的各种运算的算法(掌握)；
7.建立最优二叉树和哈夫曼编码的方法(掌握)。
（三）重点与难点 重点：二叉树的概念、性质；二叉树的遍历方式；构造二叉排序树。难点：二叉树的遍历方式；二叉排序树的构造方法；二叉树的线索化。
第七章 图
（一）目的要求
理解图的基本概念；图的存储结构；掌握图的遍历及应用{最小生成树，最短路径等}；拓扑排序和关键路径。
（二）教学内容 本章知识点： 1.熟悉图的各种存储结构；
2.了解实际问题与采用何种存储结构和算法有密切联系(掌握)； 3.遍历图的递归和非递归算法(掌握)；
4.应用图的遍历算法求各种简单路径问题（比如，最小生成树、最短路径、拓扑排序、关键路径等）(掌握)。
（三）重点与难点
重点：图的存储结构；图的遍历 难点：图遍历的算法；
第八章
动态存储管理
（一）目的要求
了解边界标识法和伙伴系统；无用单元收集和紧缩；
（二）教学内容 本章知识点：
1.存储器分配策略和算法（了解）；
2.无用单元收集时的标志算法（了解）。
（三）重点与难点
存储器分配策略和算法、无用单元收集时的标志算法
第九章
查找
（一）目的要求
了解静态查找表(顺序表，有序表，索引顺序表)；动态查找表(二叉排序树，平衡二叉树，B-树和B+树)的建立和查找；掌握哈希表的建立，查找及分析；
（二）教学内容 本章知识点：
1.顺序查找、折半查找和索引查找的方法、应用(掌握)；
2.二叉排序树的构造方法(掌握)；
3.二叉平衡树的建立方法(掌握)；
4.B-树，B+树和键树的特点以及它们的建立过程（理解）；
5.哈希表的构造方法(掌握)；
6.按定义计算各种查找方法在等概率情况下查找成功时和失败时的平均查找长度；
7.哈希表在查找不成功时的平均查找长度的计算方法(掌握)。
（三）重点与难点
重点：二叉排序树的构造方法、二叉平衡树的建立方法；哈希表的构造、应用；
难点：二叉排序树的构造及应用；哈希表的构造方法；查找的平均长度。
第十章
内部排序
（一）目的要求
掌握插入排序、交换排序(起泡排序，快速排序)、选择排序(简单选择，树形选择，堆)、归并排序、基数排序等算法。
（二）教学内容 本章知识点：
1.各种排序方法的特点并能灵活应用(掌握)； 2.各种方法的排序过程(掌握)；
3.各种排序方法的时间复杂度分析(掌握)。
（三）重点与难点
重点：各种排序方法的特点及其应用；实现排序的各种算法。难点：各种排序算法的时间复杂度分析。
十一章
外部排序
（一）目的要求
理解外部排序的基本方法；掌握败者树和多路平衡归并的实现；置换--选择排序；最佳归并树。
（二）教学内容 本章知识点：
1.外部排序的两个过程(理解)；
2.外排过程中所需进行外存读/写次数的计算方法(掌握)；
3.败者树的建立过程(掌握)；
4.实现多路归并的算法(掌握)；
5.置换-选择排序的过程(掌握)；
6.最佳归并树的构造方法（熟悉）；
7.按最佳归并树的归并方案进行平衡归并时，外存读/写次数的计算方法(掌握)。
（三）重点与难点
重点：外部排序过程和实现方法；多路并归算法及其实现； 难点：最佳并归树的构造方法及其应用。
实践教学部分：上机实验分4个专题，每个专题可提供2~4个难度不等的题目供选。
实验一
停车场管理系统
（一）实验内容 以栈模拟车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。栈以顺序结构实现，队列以链表结构实现。
（二）实验过程 编程实现实验内容。
（三）实验教学基本要求
通过实例，使学生掌握栈和队列两种特殊的线性结构，掌握栈和队列的特点。实验后学生提交实验报告。
（四）实验设备和材料 计算机。
（五）实验学时 4学时
实验二
教学计划编制问题
（一）实验内容
假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。编制一个教学计划程序。
（二）实验过程编程实现实验内容。
（三）实验教学基本要求
通过实例，使学生熟悉图的各种存储结构的特性，掌握如何应用图结构解决具体问题。实验后学生提交实验报告。
（四）实验设备和材料 计算机。
（五）实验学时 2学时
实验三
最小生成树问题
（一）实验内容
利用克鲁斯卡尔算法求最小生成树。以文本形式输出树中各条边以及他们的权值。
（二）实验过程 编程实现实验内容
（三）实验教学基本要求
通过实例，使学生熟悉图的各种存储结构的特性，掌握如何应用图结构解决具体问题。实验后学生提交实验报告。
（四）实验设备和材料 计算机。
（五）实验学时 2学时
实验四
哈希表设计
（一）实验内容
假设人名为中国人的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。
（二）实验过程 编程实现实验内容
（三）实验教学基本要求 掌握索引技术的使用。
（四）实验设备和材料 计算机
（五）实验学时 4学时
五、课程教学的基本要求和主要环节
本课程可采用课堂讲授、课堂讨论、习题课等进行课堂教学;条件允许可采用CAI、电子教案、幻灯片、参观等进行辅助教学;每章布置3~6道习题以巩固教学;在课程后半程，安排3~4个上机实验，让学生应用数据结构的理论、方法，分组设计几个较大的软件，使理论与实际相结合。
考试采用闭卷方式。总成绩由平时成绩和考试成绩组成。平时成绩占30%，考试成绩占70%。
六、本课程与其它课程的联系与分工
先修课包括：集合论，图论，高级语言（结构或记录，指针）；
后续课包括：数据库，编译原理，操作系统等。
七、建议教材与参考教材
《数据结构》（C语言版）
严蔚敏等
清华大学出版社
1997 《数据结构题集》
严蔚敏等
清华大学出版社
1999
《数据结构习题与解析》
李春葆
清华大学出版社
2004
八、负责人
撰稿人：刘景汇、李玉香
审稿人：
系（院）领导：
第四篇：《数据结构》课程教学大纲
《数据结构》课程教学大纲
Data Structure 执笔人：
编写日期：
一、课程基本信息
1.课程编号：
2.课程性质/类别： 必修课 / 专业主干课
3.学时/学分： 48 学时（另实验16学时）/ 4 学分
4.适用专业：计算机科学与技术、软件工程、网络工程、信息管理与信息系统等专业
二、课程教学目标及学生应达到的能力
数据结构课程是计算机相关专业的专业基础课、必修课程，主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。通过本课程的学习，要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和编写质量高、风格好的应用程序的能力，培养学生分析问题、解决问题的能力，并为后续课程的学习打下良好的理论基础和实践基础。
三、课程教学内容与基本要求
（一）绪论（3 学时）1．主要内容：
（1）介绍什么是数据结构；
（2）基本概念和术语: 数据、数据元素、数据对象，以及数据结构的定义、逻辑结构、物理结构（理解）数据类型、抽象数据类型；
（3）抽象数据类型的表示与实现；
（4）算法和算法分析: 算法的概念、算法设计的要求以及算法效率的度量。2．基本要求
（1）了解学习数据结构的重要性；
（2）掌握数据结构的定义及相关概念和术语；（3）了解抽象数据类型的定义、表示与实现方法；（4）理解算法的概念、特点并掌握度量其效率的基本方法。3．自学内容：
类C语言的书写规范。
（二）线性表（6 学时）1．主要内容：
（1）线性表的抽象数据类型定义和相关概念：数据项、记录、文件等；（2）线性表顺序存储表示和基本操作的实现；（3）线性表的链式存储表示和基本操作的实现；
（4）稀疏多项式的抽象数据类型定义、表示和加法的实现。2．基本要求
（1）掌握线性表的定义和特点；
（2）熟练掌握线性表的顺序存储表示和插入、删除、查找等实现算法；
（3）熟练掌握单链表、循环链表、双向链表三种链表的表示，以及单链表的查找、插入、删除、创建等实现算法。
3．自学内容：
静态链表。
（三）栈和队列（5 学时）1．主要内容：
（1）栈和队列的结构特性和抽象数据类型定义；（2）栈和队列的顺序存储表示和实现；（3）栈和队列的链式存储表示和实现；（4）栈和队列在程序设计中的应用。2．基本要求
（1）掌握栈和队列两种抽象数据类型的特点；
（2）掌握栈的两种存储表示和实现，特别注意栈满栈空的条件；（3）掌握队列的两种存储表示和实现，特别注意队满队空的条件；（4）了解递归算法与栈的关系。3．自学内容：
链栈，离散事件模拟
（四）串（3 学时）1．主要内容：
（1）串的抽象数据类型定义；
（2）串的表示和实现: 定长顺序存储结构和堆分配存储结构；（3）串的各种基本操作的实现及其应用；（4）串的模式匹配操作。2．基本要求
（1）熟悉串的一些基本操作的定义，并能利用基本操作实现串的其它操作；（2）掌握串的定长顺序存储结构以及基本操作的实现；（3）掌握串的堆分配存储结构以及基本操作的实现；（4）掌握串的简单模式匹配算法，理解KMP算法。3．自学内容：
串操作的应用实例。
（五）数组和广义表（4 学时）1．主要内容：
（1）数组的抽象数据类型定义及其顺序表示和实现；（2）特殊矩阵和稀疏矩阵的压缩存储；（3）广义表的抽象数据类型定义和存储结构。2．基本要求
（1）了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；（2）掌握对特殊矩阵进行压缩存储时的下标变换公式；
（3）熟悉稀疏矩阵的三元组顺序表存储结构下的一般转置和快速转置算法；了解十字链表等存储结构；
（4）掌握广义表的结构特点、取表头表尾操作，及其存储表示方法。3．自学内容：
采用十字链表存储结构创建稀疏矩阵。
（六）树和二叉树（10 学时）1．主要内容：
（1）树的抽象数据类型定义和基本术语；
（2）二叉树的抽象数据类型定义、性质和存储结构；（3）二叉树的遍历；
（4）线索二叉树的定义、遍历及线索化二叉树；
（5）树的存储结构、树和森林的遍历以及与二叉树的转换；（6）Huffman树及其应用。2．基本要求
（1）掌握树型结构的特点和基本术语；
（2）熟练掌握二叉树的性质，了解相应的证明方法；
（3）了解二叉树的顺序存储结构和链式存储结构，熟练掌握二叉链表存储结构；（4）熟练掌握二叉树三种遍历的递归算法和中序遍历非递归算法，能灵活运用遍历算法实现二叉树的其他操作；
（5）熟练掌握二叉树的线索化过程，以及在中序线索二叉树上找结点的前驱与后继的方法；
（6）熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法；（7）了解Huffman树的特性，掌握建立Huffman树和Huffman编码的方法。3．自学内容：
先序、后序遍历二叉树非递归算法，层次遍历二叉树算法。
（七）图（9 学时）1．主要内容：（1）图的定义和术语；
（2）图的四种存储结构：数组表示法（邻接矩阵）、邻接表、十字链表和邻接多重表；（3）图的两种遍历策略：深度优先遍历和广度优先遍历；（4）图的连通性和最小生成树；
（5）有向无环图及其应用：拓扑排序和关键路径；（6）最短路径问题。2．基本要求
（1）熟悉图的定义和术语；
（2）了解图的存储结构，熟练掌握数组表示法（邻接矩阵）和邻接表存储表示；（3）熟练掌握图的深度优先遍历和广度优先遍历算法；（4）掌握无向连通带权图的最小生成树求解算法；
（5）了解有向无环图、AOV网、AOE网及其在实际中的应用，熟悉拓扑排序算法和关键路径算法；
（6）熟悉两种最短路径问题求解算法。3．自学内容：
树的先根遍历算法与图的深度优先遍历算法比较；
树的层次遍历算法与图的广度优先遍历算法比较。
（八）查找（4 学时）1．主要内容：
（1）查找的基本概念和相关术语；
（2）静态查找表：顺序查找、折半查找和索引顺序表查找；（3）动态查找表：二叉排序树的查找、插入和删除；（4）哈希表。2．基本要求
（1）了解查找的作用，熟悉相关术语；
（2）熟练掌握顺序查找、折半查找和索引顺序表查找；（3）熟练掌握二叉排序树的特性、构造和查找方法；
（4）熟练掌握哈希表的构造方法，特别是哈希函数和处理冲突方法的选取；（5）通过分析等概率下的平均查找长度来衡量各种查找方法的效率。3．自学内容：
平衡二叉树。
（九）内部排序（4 学时）1．主要内容：
（1）排序的基本概念和相关术语；
（2）插入排序：直接插入排序、折半插入排序和希尔排序；（3）交换排序：起泡排序和快速排序；（4）选择排序：简单选择排序和堆排序；（5）归并排序：二路归并排序；（6）基数排序：链式基数排序；（7）各种内部排序方法的比较讨论。2．基本要求
（1）了解排序作用，熟悉相关术语；
（2）掌握多种排序的基本思想、算法特点和排序过程，分析它们的时间复杂度、空间复杂度和稳定性。
3．自学内容：
二路插入排序、表插入排序和树形选择排序。
四、教学安排建议
1.作业练习 完成每章的教学后进行布置习题，使用教材配套的《数据结构题集（C语言版）》。尽量选择基础的并且加注了标记的题，应注重于精，而不要求多。要求积极独立完成所布置的习题，建议安排至少六次。
2.案例分析
可参考选择以下一些案例：（1）学生通讯录管理系统，（2）表达式求值问题（3）交通咨询系统，等。3.专题研讨
可参考选择以下一些：（1）最小生成树问题（2）航班信息查询与检索系统，（3）内部排序算法比较，等。
4.实验安排
为了达到理论与实际应用的结合，让学生能将所学知识应用于实际问题的求解中，培养学生的实际动手能力，从而加深对概念及所学知识的理解，灵活、牢固掌握教材内容，提高程序设计及解决实际问题的能力，实验环节的安排非常重要。
建议实验安排为八次，共16学时，分别如下：
实验1 线性表的顺序存储结构的实现(2学时)
实验2 线性表的链式存储结构的实现(2学时)
实验3 栈的算法实现(2学时)
实验4 队列的算法实现(2学时)
实验5 串类型及操作(2学时)
实验6 二叉树的建立与遍历(2学时)
实验7 图的建立与遍历(2学时)
实验8 查找与排序(2学时)注：教师可根据教学实际情况（如：学生情况及学时情况等），适当调整实践教学内容及学时分配。
五、课程考核
1.考核形式及成绩评定办法
本课程考核形式为：平时成绩占40%，期末考试成绩占60%。其中平时成绩的结构分包括：课堂表现10%、平时作业10%和实验20%，期末考试为闭卷笔试考试：120分钟，卷面分满分100分。期末考试成绩低于50分者，本课程成绩按不及格论处。
2.本课程考核的基本要求
课堂表现10%：包括课堂考勤和课堂提问，如果缺课课时达到本课程教学时数的1/3，则取消考试资格。
平时作业10%：根据上交次数及完成情况进行评定。
实验20%：根据各次实验完成情况及实验报告成绩进行评定。
期末考试60%：本课程的期末考试考核内容主要包括线性表、栈与队列、串、数组与广义表、树与二叉树、图、查找和内部排序。其中，线性表、二叉树、图、查找和内部排序内容为考核的重点。
六、本课程与其它课程的先行后续关系
先行课程：《高级程序设计语言》、《离散数学》
后续课程：《操作系统》、《编译原理》、《数据库理论》、《算法分析与设计》等
七、建议教材及教学参考书
1.教材：
严蔚敏，吴伟民编著，《数据结构（C语言版）》，清华大学出版，2012.5 严蔚敏，吴伟民编著，《数据结构题集（C语言版）》，清华大学出版，2012.5 2.参考书：
[1] 许卓群，张乃孝，杨冬青，唐世渭，《数据结构》，高等教育出版社，2004.[2] 徐孝凯，《数据结构简明教程》，清华大学出版社，1995 [3] 陈文博，朱青，《数据结构与算法》，机械工业出版社，1996 [4] 李云清，杨庆红，揭安全编著，《数据结构》（C语言版），人民邮电出版社，2007.[5] 杨秀金主编，《数据结构》，西安电子科技大学出版社，2002.[6] 李廉治，姜文清，郭福顺，《数据结构》，大连理工大学出版社，1989
[7] Aho A V, Hopcroft J E, Ullman J D.Data Structures and Algorithms.Addison-Wesley Publishing Company,Inc.,1983
[8] Baron R J, Shapiro L G.Data Structures and their Implementation.Van Nostrand Reinhold Company, 1980
[9] Esakov J, Weiss T.Data Structures: An Advanced Approach Using C.Prentice-Hall, Inc.,1989
[10] [美]S巴斯《计算机算法：设计和分析引论》朱洪等译，复旦大学出版社，1985
第五篇：“数据结构”课程总结
“数据结构”课程总结
计算机科学与技术专业从1994年开始为我校专科生开设“数据结构”课程，2004年开始为本科生开设这门课程。由于本门课程的教学从教材、讲授、实验指导都体现了先进的教育理念，该课程的教学体系科学、完整，教学手段与方法先进，课程特色鲜明，2006年被评为赤峰学院本科层次精品课。几年来，数据结构课题组成员从以下几个方面对本门课程进行了建设和改革。
一、课程建设指导思想、定位和特色 1．学科地位
“数据结构”是计算机科学与技术专业的一门学科基础课，是本专业和相关专业必修课。本课程的教学目标是培养学生通过理解、分析和研究计算机处理的数据对象的特性，从而选择适当的数据结构、存储结构和相应的算法，并熟练掌握算法的时间分析和空间分析技巧。“数据结构”还是计算机科学与技术专业部分专业课的先导课，如“数据库原理与应用”、“计算机操作系统”、“计算机编译原理”和“面向对象的程序设计”等。所以本课程的教学效果将直接影响到学生对其它后续专业课的学习，因此，该课程在专业建设的地位十分重要。
“数据结构”是一门应用性很强的课程，本课程要求学生在掌握各种数据结构，特别是存储结构和有关算法的基础上，通过大量的上机实例把难以理解的、抽象的概念转化为计算机能够正确运行的程序，从而提高学生运用所学知识解决实际问题的能力。2．课程特色
根据课程建设的规划和我系实际，我们针对《数据结构》课程教学开展讨论，并就实验、图书资料等方面进行建设。在不断的教学实践中，我们按照精品课建设要求，积极探索，积累了丰富的教学经验。
采用国内经典教材，结合前沿的研究领域和最新科研动态，丰富教学内容，让学生了解数据结构的实际应用价值。
采用课堂教学与大作业相结合，上机实践为补充的教学模式，培养学生的创业创新素质和团队协作精神。
二、教师队伍建设
1．良好的学缘结构
任课教师的业务水平和教学水平是影响课程建设质量的重要因素。为此，我们不断加强师资队伍建设，特别注重青年教师和实验指导教师的培养。在担任该课程教学任务的5名教师中，教授1名、副教授2名、讲师2名，学历结构为硕士4人、学士1人，45岁以下3人，35岁以下2人。本教师梯队学历层次较高，职称、年龄结构合理，便于本门课程的建设和发展。
2．加强学术交流，不断提高团队整体教学和科研水平
在教学过程中，我们采取了互相听课，举行公开课、观摩课等方式，经常交流教书育人和教学改革方面的经验，不断提高任课教师的教学水平和学术水平。
以范体贵教授为学科带头人的教学研究梯队，具有丰富的教学经验和高昂的教学热情，同时具备较高的教学研究和科学研究水平。教学梯队成员在搞好教学的同时，积极申报承担各级各类教学研究和科学研究课题，并参加国内外相关学科的科研、教学等方面的学术交流活动。选派范体贵、门爱华两位老师参加全国计算机年会和全国数据库学术会议，与国内其他高校著名学者进行了教学、科研等方面的交流，学到许多宝贵的经验和方法。
注重与其他高校的合作和交流，学习其他院校好的教学经验和方法。选派主讲教师门爱华老师到清华大学计算机系做访问学者，访学期间门老师听取了本课程的讲授，经常与讲授本门课程的资深教授严蔚敏老师、殷仁昆老师进行交流、学习。二位老师都给予了具体的指导和建议，为我校本门课程的改革和发展提供了有利的帮助。请国内著名高校学者来我系讲学传授经验，在教学、科研等方面给予具体的指导。2008年10月清华大学著名数据库专家冯建华教授来我系讲学，课题组成员与冯教授进行了深入的交流，在教学和科研方面都有很大的收获。
3．开展科学研究，积极申请科研立项
数据结构课题小组成员积极进行相关领域的科学研究，几年来发表相关论文30余篇，承担自治区级科研项目四个，赤峰市科技局科研项目一个，院级项目一个，其中3个项目已经完成并通过验收。目前在研的一个科研项目是与清华大学合作申请的计算机前沿领域研究课题，相信通过该项目的研究和合作，对我系的科研工作会起到极大的促进作用，同时能够使我系科研水平上一个新的台阶。课题组成员经过几年的努力，在各方面都取得了一些成绩。范体贵、门爱华、张国祥、王玉红四位教师分别获得“赤峰学院课堂教学质量优秀奖”，范体贵、门爱华两位教师多次获得“赤峰学院科研成果优秀奖”的奖励。王玉红老师获得“毕业实习优秀指导教师“称号，门爱华老师2007年、2008年连续获得“毕业论文优秀指导教师”奖励。
建立了良好的人才培养制度，在学校和系里的大力支持下，鼓励现有教师提高学历与引进高学历教师相结合，经过几年的建设，已经形成了一支以中青年为主的学科梯队。积极鼓励中青年教师到国内名校进修或攻读硕士、博士学位，门爱华、董洁、王玉红分别考取了东北大学和辽宁工程技术大学的硕士研究生，已圆满完成学业并获得硕士学位。
三、教学内容、教材建设
1．理论环节教学内容及学时分配
“数据结构”是计算机科学课程体系中核心课程之首，作为学科的专业基础课，具有承上启下的重要作用。对应于学科中问题求解的理论、抽象和设计的方法论，本课程内容体系结构分为概念表述、构建数据模型、设计算法三个层面，突出数据组织方法与处理技术，贯穿程序设计和软件工程新思想和新观点。理论学时设置为72学时。
2.实践环节教学内容及学时分配
上机实践和课程设计重在培养学生软件设计的综合能力。在基本的课程实习基础上,自2001年起开设了数据结构课程设计，使课程的实践环节总学时数增加到60学时。提出了课程设计的规范要求，突出关键技术要点，贯穿基本技能训练主线，加强实践能力培养。
通过课程设计的训练，突出构造性思维训练的特征，提高了学生组织数据与进行编写大型程序能力，使学生更好地理解和掌握了算法设计所需的技术，为专业学习打下良好的基础。课程设计题目（动态更新、完善）：航空客运订票系统；电梯模拟；简单行编辑程序；工资管理系统；医院排队看病活动的模拟；学籍管理系统；图书管理系统等。3．教材建设
教材建设是课程建设的重要环节。为此，根据教学大纲和本课程的发展需要，在本课程教材的选用上注重教材的先进性和科学性，我们选用了清华大学出版社严蔚敏教授等编写的《数据结构》（C语言版）作为教材，本书内容丰富、体系结构严谨、概念清晰、易学易懂，也是多所院校指定的考研参考教材，完全适合我系计算机科学与技术、信息与计算科学专业学生的需要。任课教师则多方面参考相关教材，选择部分编写精彩的内容充实到教案中。任课教师们广泛阅读相关文献，了解该领域前沿知识，并且在授课过程中介绍给学生，以开阔学生的视野，拓宽学生的知识面。同时，根据教材内容和实际教学要求，编写了《数据结构上机指导与习题就解答》，并正式出版了《数据结构实验教程》一书，该书作为自治区教育厅统编教材已在各高校广泛使用。
四、教学方法和教学手段
1．教学方法
在教学方法上，讲课、讨论和专题讲座等多种形式并用，以科学、生动灵活的讲授方式传授知识，培养学生的创造思维。教师在认真组织课堂讲授，注意各环节正常运行的同时，还针对不同的教学内容采取不同的方法进行讲解，做到课程内容既条理清晰、深入浅出，又重点突出、特色鲜明。教学内容灵活，既有必讲的内容，也有针对不同专业需要和特点选讲的内容。
通过布置适量的课后习题，使学生能够进一步巩固和提高对课上所学知识的领悟和应用能力。我们在选择习题时，一方面注重三基（基本理论，基本方法，基本技能）知识的掌握，另一方面也充分考虑知识的灵活应用，使学生能多角度、多方法地解决问题，既锻炼他们的系统性思维，又提高分析解决问题的能力。每两周安排一次习题课，由指导教师集中解决同学课上课下遇到的问题。
上机实践是学生对本门课程所学知识的一种全面、综合的能力训练，是与课堂听讲、自学和练习相辅相成必不可少的一个教学环节，也是对课堂教学效果的一种检验。通常，实习题中的问题比平时的习题复杂得多，也更接近实际。实习题注重原理与应用的结合，目的让学生学会如何把书上学到的知识运用于解决实际问题的过程中去，培养从事软件开发设计工作所必需的基本技能。同时，通过实践能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的作用。平时的练习较偏重于如何编写功能单一的“小”算法，而实习题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，可以多人合作，有利于一整套软件工程规范的训练和科学作风的培养。此外，实践环节中有很重要的一点，就是机器是比任何教师都严格的主考官。
2．教学手段
为了适应现代化教学的需求，我们在传统教学的基础上，充分利用现代科学技术，广泛应用多媒体教学课件和教学软件。将授课内容制作成了图文并茂的多媒体课件，利用多媒体技术对数据结构辅之以形象的动画，动态演示抽象的复杂数据结构的变化，用板书补充某些推导过程并完成和学生互动的内容，改变了以前课堂教学单调的弊病，激发了学生的学习兴趣。使用多媒体技术还可以直接在课堂上演示算法的实现过程，让学生熟悉算法实现的环境和方法，增强了该门课的实践性，提高了课堂授课效率和教学质量，取得了满意的教学效果。教师们为了更好地适应社会的发展和改革的需要，本着强化算法的思想，在现有数据结构内容的基础上，补充了新的算法，拓宽了学生的知识面。
五、课程建设取得的成果
1．教学科研论文
1）The Boundary Element Analysis for The Thermal Conduction of The Thermal Equipment。Proceedings of International Conference on Computational Physics, Rinton Press, US,(2005)199-202（SCI）
2）基于访问控制列表的路由器防火墙在网络安全中的应用研究。计算机与网络 24,(2004)52-53(核刊)3）信息系统在企业现代化管理中的应用。《商场现代化（学术版）》，2005.2 25-26(核刊)4）可信网络基本概念与基本属性研究。《赤峰学院学报 》2007.5 5）基于包过滤技术路由器防火墙在网络安全中的研究。《计算机应用研究》,2007,vol23 6）Research on The Architecture of Tru-Network。2008 International Symposium on Information science and Engineering 7）路由器防火墙对冲击波、震荡波病毒的过滤研究。《赤峰学院学报》 2005.1 67-68 8）菲涅耳圆孔衍射的数值模拟。《赤峰学院学报》 2006.1 9）复杂轴承流体动力学特性的边界元分析。《润滑与密封》 2006.3(核刊 EI核心刊源)10）三叶轴承流体动力学特性的边界元分析。《润滑与密封》 2006.5(核刊 EI核心刊源)11）164-182Hf核的低能谱和电磁跃迁的相互作用玻色子模型。《高能物理与核物理》 28(12),(2004)119-122(核刊, SCI收录)12）基于访问控制列表的路由器防火墙在网络安全中的应用研究。《计算机与网络》 2004.24 13）赤峰学院校园网路由器、交换机的选型及远程登录。《赤峰教育学院学报》2004.5 81-82 14）《XML数据库存储策略综述》 《计算机科学》 2005年9月（核刊）15）《XML数据库结构连接算法之研究》《计算机科学》 2007年6月（核刊）16）《XML中XPath包含关系判定算法》《内蒙古大学学报》2008年10月（核刊）17）《基于关系数据库的XML数据的存储研究》《赤峰学院学报》 2006年 3 月 18）《XML数据库模式匹配算法研究》 《赤峰学院学报》 2007年 5月 19）《Internet蠕虫的分析与研究》 《赤峰学院学报》 2005年 4月 20）《如何防止外部网络的攻击》 《赤峰学院学报》 2004年2月 21）《射频IC卡消费系统的设计与实现》 《赤峰学院学报》 2008年10月 22）《XPath片断的分析与研究》 《赤峰学院学报》 2008年1月 23）《一种基于层次结构的XML编码技术》 中国教育信息化》 2009年4月（核刊）24）《VC++实现图形、数据库应用系统的思路》赤峰教育学院学报 2002年第2月 25）《基于IP组播的多媒体会议系统的设计》 赤峰教育学院学报 2002年6月 26）论文《个性化WINDOWS系统“开始”菜单》赤峰教育学院学报 2003年4月 27）浅谈DEBUG程序的主要命令用法 赤峰学院学报 2007年5月 28）powerpoint技巧在课件制作中的妙用 赤峰学院学报 2006年1月 29）浅谈用MASM运行汇编程序 赤峰学院学报 2005年 1月 30）XML数字签名浅析 赤峰学院学报 2008年 5月 31）《网络层的静态路由选择综述》 赤峰学院学报 2005年3月 32）《离散数学在计算机教学中的作业》 赤峰学院学报 2008年1月 33）《基于模拟退火算法的油井工矿数据挖掘的应用研究》
赤峰学院学报2009年1月
2.教研课题
1）赤峰学院校园网项目 赤峰学院 2002年-2003年（已验收）2）基于IP网QOS动态控制研究 内蒙教育厅 2005年-2007年（已结题）3）基于结构索引XML模式匹配方法研究 内蒙教育厅 2005年—2007年（已结题）4）XML数据库研究 赤峰学院 2006年—2008年（已结题）5）CAI系统中知识个性化组织与导航研究 内蒙教育厅 2003年-2005年（已结题）6）XML安全数据发布关键问题研究 内蒙教育厅 2009年—2010年（在研）3.教学获奖
1）范体贵、门爱华、张国祥、王玉红分别获赤峰学院2005、2006年、2007年、2008年“课堂教学质量优秀奖”；
2）门爱华2007年、2008年连续获的“毕业论文优秀指导教师”奖励； 3）王玉红2007年获院级“毕业实习优秀实习指导教师”奖励；
4）2009年《数据结构课程教学和实践》课题”获赤峰学院“优秀教学成果二等奖”。
数据结构课程组 2009年5月14日
点击咨询 