《数据结构(ⅱ)》教学大纲

《《数据结构(ⅱ)》教学大纲》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、编号：信息管理与信息系统—2005—8公共管理学院本科课程教学大纲《数据结构(Ⅱ)》教学大纲编写人：董凯宁编写时间：2005年10月30日一、课程基本信息课程名称：数据结构(Ⅱ)DataStructure(II)课程号：40128830课程类别：专业课学时：48学分：3二、教学目的及要求数据结构概论，从抽象数据类型的角度讨论线性表、栈、队列，串、数组、广义表，树、二叉树和图等基本类型的数据结构及其应用，抽象数据类型的常用表示方法,操作系统和编译程序中涉及的动态存储管理的基本技术，查找、内部排序，外部排序，置换－选择排序,文件的概念，文件结构,索引顺序存取方法。三、教

2、学内容第1章绪论（共3学时）²1.1什么是数据结构（0.5学时）教学内容：由数学方程无法描述的非数值计算问题引出数据结构表、图、树的3种实例，阐述数据结构的概念，数据结构的内涵和特点，数据结构所处的学科地位，数据结构的学科背景、起源、发展和现状；要求学生掌握数据结构的概念，能辨别数学模型中数学方程和表、图、树等数据结构的区别。²1.2基本概念和术语（1学时）教学内容：阐述本课使用的一些基本概念，包括数据、数据元素、数据项、数据对象、数据结构、集合、结构、线性结构、树形结构、图状结构、网状结构、逻辑结构、物理结构、存储结构、位、元素、结点、数据域、顺序映像、非顺序映像

3、、顺序存储结构、链式存储结构、指针、虚拟存储结构、数据类型、原子类型、结构类型、抽象数据类型、固定聚合类型、可变聚合类型、多形数据类型；要求学生掌握包括数据、数据元素、数据项、数据对象、数据结构、集合、结构、线性结构、树形结构、图状结构、网状结构等在内的所有基本概念。²1.3抽象数据类型的表示与实现（0.5学时）171编号：信息管理与信息系统—2005—8公共管理学院本科课程教学大纲教学内容：阐述在C语言中，抽象数据类型的常用表示方法，包括预定义常量和类型、数据结构的表示用类型定义（typedef）描述、函数表示法、各种赋值语句、选择语句、结束语句、输入和输出语句、

4、基本函数、逻辑运算约定；要求学生了解抽象数据类型的描述语言、构成方法，掌握抽象数据类型的类C语言11种表示方法。²1.4算法与算法分析（1学时）1.4.1算法教学内容：阐述算法的定义，算法的5个重要特征：有穷性、确定性、可行性、输入、输出；要求学生掌握算法的定义，理解算法的5个重要特征。1.4.2算法设计要求教学内容：阐述好算法设计的4个要求——即正确性、可读性、强壮性和效率与低存储量需求；要求学生理解好算法设计的4个要求。1.4.3算法效率的度量教学内容：阐述算法效率的2种度量方法：事前统计的方法和事后分析估算的方法，时间复杂度的概念，频度的概念；要求学生掌握时间

5、复杂度的概念，频度的概念。1.4.4算法的存储空间需求教学内容：阐述空间复杂度的概念，空间复杂度的表示法，算法原地工作的概念；要求学生掌握空间复杂度的概念，了解算法原地工作的概念。第2章线性表（共4学时）²2.1线性表的类型定义（0.5学时）教学内容：阐述线性结构的特点，线性表的抽象数据类型定义，数据项、记录、文件的定义，实例说明线性表的插入、删除、归并等操作方式，并对算法做相应的分析；要求学生掌握线性表的概念和抽象数据类型定义。²2.2线性表的顺序表示和实现（重点）（1.5学时）教学内容：阐述线性表的顺序表示的概念，顺序映像的方式，顺序映像的随机存取特性，实例描述

6、线性表在顺序存储表示时进行插入、删除、合并操作的几种算法；要求学生掌握线性表的顺序表示的概念和顺序映像的方式，理解线性表在顺序存储结构时的插入、删除、合并等操作方法。²2.3线性表的链式表示和实现（重点）（1.5学时）2.3.1线性链表教学内容：阐述线性链表的概念、构成方式，结点、数据域、指针域、指针、链、链表、头指针、头结点和静态链表的概念，线性链的表示法，实例算法说明单链表的插入、删除、合并操作处理算法，静态链表的算法；要求学生掌握线性有序链表的概念、与之相关的名词概念，理解单链表的插入、删除、合并操作算法过程。2.3.2循环链表教学内容：阐述循环链表的概念，循

7、环链表的操作特点；要求学生掌握循环链表的概念。2.3.3双向链表教学内容：阐述双向链表的概念和特点，双向链表的抽象数据类型定义，双向链表的几种操作算法；要求学生掌握双向链表的概念，理解双向链表的抽象数据类型定义，理解双向链表的操作算法。²2.4一元多项式的表示及相加（0.5学时）171编号：信息管理与信息系统—2005—8公共管理学院本科课程教学大纲教学内容：阐述存储高次一元多项式的线性表可以采用每个元素包含2个数据项的方法，利用线性链表的基本操作来实现一元多项式的定义、相加和相乘运算；要求学生掌握利用线性链表的基本操作来实现一元多项式的定义、相加和相乘运算。第