计算机系 2009级 专科教学大纲
4. ISAM文件和VSAM文件 5. 直接存取文件 6. 多关键字文件 教学重点：
顺序文件；索引文件 教学难点：
多关键字文件 教学要求：
1. 掌握：顺序文件；索引文件； 2. 了解：多关键字文件等。 三、课程教学基本内容和学时分配
章 1 绪论 2 线性表 3 栈 4 队列 5 串 6 数组和广义表 教学内容 什么是数据结构、数据的逻辑结构、存储结构、算法和算法分析 线性表的定义与运算、顺序存储 线性表的链式存储 栈的定义和运算、栈的存储和实现、栈的应用举例 队列的定义和运算、队列的存储和实现、队列的应用举例 串的定义和运算、串的表示和实现、串的基本运算 数组的定义、数组的顺序表示和实现、广义表的定义等 树的定义和术语、二叉树 7 二叉树 遍历二叉树和线索二叉树 二叉树的转换、二叉树的应用 哈夫曼树及其应用 图的定义和术语、图的存储表示 8 图 9 查找 图的遍历 图的连通性、最短路径 查找的基本概念、静态查找表 动态查找表 哈希表 概述、插入排序 10 排序 *11 系统开发 12 文件 小计 合计 快速排序、选择排序 归并排序、各种排序方法的比较 系统设计的要求、文件的包含处理、课程设计任务书 概念、顺序文件、索引文件、ISAM和VSAM文件、散列文件等 课时 分配 2 2 2 6 6 4 4 2 4 4 6 4 6 6 2 2 2 2 2 2 不讲 2 72 90 18 3 2 3 4 2 2 选做 2 实验 实训 四、课程各教学环节要求
26
计算机系 2009级 专科教学大纲
本课程是计算机专业学生必修的一门专业基础课和主干课 , 理论性较强。课程包括课堂教学与实践教学两大部分，课堂教学在方法上，采用课堂讲授，课后自学，课堂讨论等教学形式，实践教学部分主要是实验。
1．课堂讲授
课堂教学主要介绍数据结构中基本内容：线性表的基本操作，实现方式，实际应用；栈的基本操作，实现方式，应用举例；队列的基本操作，实现方式，应用举例；树及二叉树的基本操作，实现方式，应用举例；图的基本操作，实现方式，应用举例等等，其中重点为栈、队列、树型结构及图型结构的基本操作及实现方式和基本方法。在教学内容组织方式上尽量采用实际的操作系统与传统教学内容融合并重的形式，并将实验环节贯穿课程教学的过程，加强学生对数据结构的理解，培养学生分析问题、解决问题和实际动手能力。
2．课后自学
为了培养学生整理归纳，综合分析和解决问题的能力，每章都安排一部分内容作为自学，课上教师只给出自学提纲，课后由学生根据参考网站和参考书自学。
3．课堂讨论及习题课
教师应精选论题，认真组织课堂讨论，安排重点发言(可在讨论前让学生先到网上查资料准备），充分调动每一位学生的积极性，并做好总结。习题课以典型例题分析及综合性的练习为主。（课时已包括在前述学时分配中）。
4．课外作业
课外作业的内容选择基于对基本理论、基本原理和基本方法的理解和巩固，每章都应选择一定的题目让学生练习，另外，可增加一些综合练习题，培养学生的分析问题和综合能力。
5．平时测验
为及时了解教学情况，可适当安排平时课堂测验，但每次测验不超过 30分钟。 6．实验
本课程开设16个实验课，总共32个学时。实验内容为数据结构中各章典型算法。要求学生一定要先了解实验目的、内容、要求以及注意事项；实验过程中要求学生仔细观察做好记录；实验结束后交实验报告。本课程的实验内容自始至终贯彻课程中所介绍的程序设计风格，养成良好的编程习惯。学生在上机做实验前，应事先将程序、调试数据、上机操作顺序准备好，并提前使用这些调试数据人工执行过。
7．课程设计
27
计算机系 2009级 专科教学大纲
在最后要求每位学生完成一个综合课程设计，要求对需要完成的任务进行任务分解，对程序体系结构和模块结构设计、采用的调试数据、上机操作过程进行描述，事后进行整理，以电子版形式提交课程设计。
除学校提供的时间外，要求课外学生利用自己可能拥有的计算机条件，完成更多的练习，不通过大量的实践，能力和知识水平得不到有效得提高。
8．课程考核
（1）成绩的组成：本课程属于考试课，成绩采用百分制，包括平时成绩、期末成绩，分别占总评成绩的20%、80%。
（2）考试的形式：闭卷。 五、本课程与其它课程的联系
本课程是在程序设计语言基础上讲授的，要求前续课程对图、集合等基本概念和基本理论详细讲解，应掌握一门高级程序设计语言如C语言等。
六、教材及教学参考书
1．《实用数据结构基础》，陈元春，张亮，王勇编著，北京：中国铁道出版社，2003.8 2．《数据结构（C语言描述）》，马秋菊著，北京：中国水利水电出版社，2006 3．《数据结构》（第二版），严蔚敏，吴伟民编著，北京：清华大学出版社，1999 4．《数据结构题集》，严蔚敏，吴伟民编著，北京：清华大学出版社，1999 七、其它说明
任课教师有权根据学生的具体情况自行调整授课内容的先后顺序，根据实际情况补充一些预备知识。（注：章节后有*的表示有难度的章节，可以根据情况选讲，甚至可以删去不讲。）
28
计算机系 2009级 专科教学大纲
课程编号：11013023
《数据结构实验/实习》教学大纲
（Data Structure）
适用专业：计算机信息管理,计算机应用技术
总学时：18 实验/实习周数：18
制定单位：计算机系 执笔者：白凤凤 审核人：王三虎 编写日期：2009年10月9日
一、实验（实习）的目的与任务
通过理论与实际应用相结合，让学生根据所学内容，利用数据结构解决各种实际问题。通过上机实习，增强学生的编程能力和分析问题的能力，训练学生进行复杂程序设计的技能，培养良好程序设计的习惯和学生实际动手能力，达到学以致用目的。
二、实验（实习）教学的基本要求 实验一：复习C语言结构体的用法
主要内容：有5个学生，每个学生的数据包括学号、姓名、三门课的成绩、平均分，要求从键盘依次输入5个学生的学号、姓名、三门课成绩，自动计算三门课的平均分数，并将5个学生的数据在屏幕上输出）
要求：通过实验程序，分析它们的时间复杂度，认识算法时间复杂度，掌握其分析的基本方法。
实验二：线性表子系统
主要内容：用结构体描述一个字符型的单链表；创建线性表；在线性表中插入元素、删除元素、显示线性表中所有元素；用if语句设计一个选择式菜单。
要求：掌握线性表的特点，线性表顺序存储结构和链式存储结构的基本运算，掌握线性表的创建、插入、删除和显示线性表中元素等基本操作。
实验三：栈子系统
主要内容：设计一个字符型的链栈；编写进栈、出栈、显示栈中全部元素的程序；编写一个把十进制整数转换成二进制数的应用程序（选做）；编写一个把中缀表达式转换成后缀表达式（逆波兰式）的应用程序（选做）；设计一个选择式菜单。
要求：掌握栈的特点及其描述方法；掌握用链式存储结构实现一个栈；掌握建栈的各种等基本操作；掌握栈的几个典型应用的算法。
实验四：队列子系统
主要内容：设计一个字符型的链队列；编写队列的进队、出队、读队头元素、显示
29
计算机系 2009级 专科教学大纲
队列中全部元素程序；设计一个选择式菜单，以菜单方式选择队列的各种基本操作。
要求：掌握队列的特点及其描述方法；用链式结构实现一个队列；掌握队列的各种基本操作；掌握队列的简单应用程序。
实验五：串子系统
主要内容：由用户通过键盘输入建立一个字符串；编写插入、删除、查找、比较、取子字符串、连接字符串、显示、模式匹配（选做）等程序；设计一个选择式菜单，以菜单方式选择上述操作。
要求：掌握串的特点及顺序定长存储的方式；掌握串的创建、连接、插入、删除、显示等操作；掌握串的查找、取子字符串、比较串大小的操作；掌握模式匹配的基本思想及其算法。
实验六：树和二叉树子系统
主要内容：按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构（选做）；编写前序遍历、中序遍历、后序遍历、层次遍历程序；求二叉树的叶结点数、总结点数和深度；设计一个选择式菜单，以菜单方式选择下列操作。
要求：掌握二叉树的特点及其存储的方式；掌握二叉树的创建和显示方法；复习二叉树遍历的概念，掌握二叉树遍历的基本方法；掌握求二叉树的叶结点数、总结点数和深度等基本算法。
实验七：图子系统
主要内容：编写按键盘输入的数据建立图的邻接矩阵存储；图的深度优先遍历程序和图的广度优先遍历程序（二选一）；设计一个选择式菜单。
要求：掌握图邻接矩阵的存储方法；掌握图深度优先遍历的基本思想；掌握图广度优先遍历的基本思想。
实验八：查找子系统
主要内容：编写顺序查找、二分查找程序（二选一）；编写建立二叉排序树的程序；编写在二叉排序树上的查找、插入、删除结点的程序；编写二叉排序树中序输出的程序（选做）；设计一个选择式菜单。
要求：通过查找实验理解查找的基本算法；熟悉各种查找方法的适用场合及平均查找长度；掌握静态查找和动态查找的区别；掌握顺序查找、二分查找的基本思想及其算法；掌握二叉排序树基本思想及其算法。
实验九：排序子系统
主要内容：编写直接插入排序、希尔排序、冒泡排序、快速排序、选择排序。
30