数据结构课程实施方案

  • 格式:doc
  • 大小:83.50 KB
  • 文档页数:3

数据结构课程实施方案

一、课程名称:数据结构

二、课程概况

《数据结构》课程是电大计算机科学与技术专业的一门专业基础课。它涉及在计算机中如何有效地表示数据,如何合理地组织数据和处理数据。还涉及初步的算法设计和算法性能分析技术。学好数据结构课程,将为后续的专业课程,如数据库系统、操作系统、编译原理等,打下良好的知识基础,而且还为软件开发和程序设计提供了必要的技能训练。

本课程要求学员对计算机的组成有基本的了解,对程序设计方法有一定基础,对C语言编程,最好是C++语言编程,有一定的经验。对涉及离散数学的知识,如表、树、图、集合等,有初步的了解。事实上,课程讲授中将会简单地补充这些方面的内容。

三、课程教材

《数据结构》

殷人昆编,清华大学出版社,2001年3月出版

四、其它媒体

课堂教学采用计算机电子版教材的投影手段,该教材采用PowerPoint软件编制,目前已在清华大学计算机系本科《数据结构》课教学中试用。在试用的过程中对教学内容进行总结,在学生的参与下对教材中的所有算法进行修改,使其正确性、可读性更好。

可对课堂教学过程采用现场录像的办法以产生音像版教材,也可以以光盘形式提供(带或不带语音)电子版教材。

实验教学(上机实验)在微机(486以上)上即可。要求在开通实验前在所有教学微机上安装C++的编译程序。使用Borland C++ 或 Visual C++ 都可以。前者的系统体积小一些。但同一个源程序在这两个编译器上可能会出现不同的编译信息。

学生交作业时必须说明是在哪一个编译器上哪一个版本下做出来的。

五、教学要求:

课程教学计划总学时数为 72学时,4学分,其中课内学时48,实验24

教 学 内 容 课内学时 实验学时

一、数据结构基本概念及简单的算法分析 2学时

二、数组 4学时 2学时

三、链表 4学时 2学时

四、栈和队列 4学时 2学时

五、递归 4学时 2学时 六、树与森林 7学时 2学时

七、集合与搜索 6学时 2学时

八、图 6学时 2学时

九、排序 6学时 2学时

十、索引与散列结构 5学时 8学时

六、教学进程:

 笔做题共53题,要求交书面作业;上机题共19题,额定用24  30小时完成。习题附在暂用教材《数据结构(用面向对象方法和C++描述)》各章之后。

块 习 题 安 排

名 称 教 学 内 容 笔做题 上机题 思考题

1 基本概念 什么是数据结构

抽象数据类型及面向对象概念

数据结构的抽象层次 1.4 1.1 1.2

2 算法分析 算法定义, 特性及质量要求

性能分析与度量 1.9 1.7 1.8

3 数组 数组

顺序表 2.1 2.3 2.2 2.5 2.10

4 数组 字符串

字符串的模式匹配 2.7 2.9 2.14 2.13

5 链表 单链表

单链表的游标类 2.15 2.16

3.3 2.17 3.1

6 链表 循环链表

多项式的加法

双向链表 3.2 3.7 3.6 3.8 3.10

7 栈和队列 栈

栈的应用:表达式求值 3.9 4.2 3.12 3.10 4.4

8 栈和队列 队列

优先级队列 4.3 4.12 4.13 4.9 4.10

9 递归 递归的概念

递归过程与递归工作栈 4.15 5.3 5.1 5.4 5.7

10 广义表 广义表及其表示

广义表的递归算法 5.6 5.5 5.8

11 树与森林 树和森林的概念

二叉树的概念与性质 6.1 6.5 6.9 6.4 6.7

12 树与森林 二叉树的表示

二叉树遍历 6.10 6.12 6.8 13 树与森林 线索化二叉树 6.13 6.11

14 树与森林 堆

树与森林 6.14 6.16 6.18 6.17

15 树与森林 二叉树的计数

霍夫曼树与霍夫曼编码 6.19 6.21 6.20

16 集合与搜索 集合及其表示

等价类与并查集 7.2 6.22 6.23

17 集合与搜索 简单的搜索结构

二叉搜索树 7.8 7.9 7.4

18 集合与搜索 二叉搜索树(续)

AVL树 7.13 7.18 7.11 7.10 7.12

19 图 图的基本概念

图的存储表示 7.21 7.22 7.20 7.16 7.19

20 图 图的遍历与连通性 8.8 8.11 8.9 7.24 8.2

21 图 最小生成树 8.15 8.17 8.4 8.7

22 图 活动网络 8.23 8.28 8.25 8.26

23 排序 排序概述

插入排序 8.24 8.27

24 排序 交换排序 9.9 9.8 9.12

25 排序 选择排序 9.11 9.14 9.15

26 排序 归并排序

基数排序 9.19 9.17

27 排序 外排序 9.23 9.25 9.21 9.24 9.26

28 索引与散列 静态索引结构 9.27 10.4

29 索引与散列 动态索引结构 10.5 10.9

10.10 10.11 10.2 10.7

10.12 10.14

30 索引与散列 散列 10.13 10.17

10.18 10.23 10.19 10.22

七、成绩考核