数据结构原理与分析013434189

18、读书是易事，思索是难事，但两者缺一，便全无用处——富兰克林
课程名称：数据结构原理与分析 课程代码：01343
第一部分 课程性质与目标

一、 课程的性质与特点：
《数据结构》是信息技术专业、计算机应用技术专业的一门重要的专业基础课，用计算机解决任何实际问题都离不开数据表示和数据处理，而数据的表示和处理的核心问题之一数据结构及其实现正是数据结构课程的基本内容，在计算机软件的各个领域中均会使用到该课程的有关知识
从这个意义上说数据结构课程在知识学习和技能培养两个方面都处于关键性地位；本课程的目的和任务是学生较全面地掌握各种常用的数据结构，为学习后续软件课程提供必要的基础，提高运用数据结构解决实际问题的能力

本课程不仅为数据库及其应用操作系统概论面向对象程序设计软件工程等后继软件课程提供了必要的知识基础、也为计算机及应用的专业人员提供了必要的技能训练

课程特点
《数据结构》是实践性很强的课程,不仅要注重学习基本理论知识,更要注重上机实践,通过上机实践验证算法的正确性,掌握和巩固所学理论知识

二、 课程目标与基本要求：
通过本课程的学习，使学生能够：
1、掌握常用数据结构的基本概念；
2、掌握四种常用逻辑结构的特点和数据组织方法；
3、掌握线性表的存储结构及其算法的实现；
4、掌握各种查找及排序的方法和算法实现；
5、掌握树、图的存储结构；了解这两章的相关算法

6、学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法

7、通过对本课程算法设计和上机实践的训练，还要注重培养学生的数据抽象能力和基本程序设计的能力

三、 与本专业其他课程的关系
　本课程的先修课程为离散数学和高级语言程序设计（C语言和C++语言），后续课程为操作系统、数据库原理等

　数据结构中存储结构及基本运算的实现需要程序设计的基本知识和编程的经验及能力，本课程的大部分实例均是用C语言（或C++）实现的，故要求较熟练地掌握C语言（或C++）

【课程修读对象】
第二部分 考核内容与考核目标

第一章 绪论
一、学习目的和要求
通过本章学习，学生需要掌握常用的基本概念，了解本书涉及的逻辑结构和存储结构，对本教材的体系有一个大致的了解

二、考核知识点与考核目标
（一）基本概念和术语（重点）
数据的相关概念：数据,数据项,数据元素

数据结构的相关概念：数据结构,数据的逻辑结构与物理

结构,逻辑结构与物理结构间的关系

数据类型的相关内容：数据类型、抽象数据类型、数据抽象和信息隐蔽原则，了解什么是面向对象


1、 识记：数据和数据结构的相关概念

2、 理解：数据结构的相关概念，区分逻辑结构与物理结构的关系


（二）算法的描述和分析（一般）
算法的相关内容：算法的定义、算法的特性、算法的时间代价、算法的空间代价

描述算法的方法：类C语言，能够使用C语言编写程序

C语言中函数的定义和调用


1、 识记：描述算法的方法

2、 应用：分析算法的时间和空间复杂度


第二章 线性表
一、学习目的和要求
通过本章学习，学生需要了解两种存储方法各自的优缺点，以便针对不同的需求运用合适的存储方式，掌握线性表的逻辑结构的特点、线性表在内存中的两种存储方法，熟练掌握并理解链式存储方法，会针对数据在不同存储方法时的处理以及相应算法的描述，如果有条件还应通过上机来实现算法

二、考核知识点与考核目标
（一）线性表的逻辑结构（次重点）
线性表的概念、线性表的逻辑结构的特征；
　常见的线性表的基本运算（有六种）：线性表的初始化、求表长、读取线性表中的元素、在线性表中查找某个元素、在线性表中插入元素、在线性表中删除元素

　
1、 识记：线性表的概念

2、 理解：逻辑结构的特征


（二）线性表的顺序存储结构（重点）
顺序存储结构的实现方法：用一维数组实现

顺序存储结构中任意元素的地址的计算方法

顺序存储结构的定义

基于顺序存储结构的算法描述：插入元素、删除元素的算法描述及应用


1、识记：线性表顺序存储的实现方法

2、理解：顺序存储结构中任意元素的地址的计算方法、存储结构的定义方法

3、应用：在存储结构定义的基础上用类C语言描述算法，并能写出标准的C语言程序上机实现


（三）线性表的链式存储结构（重点）
1）采用链表存储的实现方法；链式存储结构的定义；单链表中结点的表示方法；
2）单链表的相关概念：头结点、头指针、尾结点；
3）单链表算法中常用的C语言的函数：malloc( ),free( )的格式、功能、返回值以及调用方法；
4）指针的定义和使用；
5）链表可分为动态链表和静态链表，主要是对动态链表的理解

6）单链表的结构、特点

7）带表头结点的单链表和类定义及相应操作的实现

8）单链表的类定义、构造函数、单链表的插入与删除算法及其应用

9）循环链表的特点，循环链表的类定义，以及用循环链表解决问

题的方法

10）双向链表的特点，双向链表的类定义及相关操作的实现，用双向链表解决问题的方法


1、识记：线性表链式存储的实现方法、实现所用的函数以及相关概念

2、理解：链表中存储结构的定义，单链表、双向链表和循环链表的构成，单链表上运算的实现

3、应用：能用类C语言编写相关算法


（三）顺序表和链表的比较（一般）
1）基于空间的考虑：从数据的存储密度上考虑

2）基于时间的考虑：从运算所需要的时间上进行考虑


1、识记：顺序表和链表各自的优缺点

2、应用：能针对数据的不同的使用目的为数据选择合适的存储方法


第三章 栈和队列
一、学习目的和要求
通过本章学习，学生需要掌握栈和队列的特征，栈和队列的顺序存储方式以及在顺序存储方式上的各种操作，并能读懂相关的算法，了解栈和队列的链式存储结构以及栈和队列的简单应用

二、考核知识点与考核目标
（一）栈（重点）
1）栈的定义、栈的特征

2）栈的基本运算定义：六种基本运算函数的应用

3）栈的顺序存储：顺序栈的类型定义和六种基本运算的实现方法和具体算法

4）顺序栈中掌握栈空和栈满的条件

5）栈的链式存储

6) 栈的应用


1、识记：栈的定义和特征，六种基本运算函数

2、理解：顺序栈上的六种基本运算

3、应用：通过掌握栈的特征来读懂栈的相关的算法，可以不要求写算法


（二）队列（重点）
1）队列的定义、队列的特征

2）队列的基本运算定义：六种基本运算函数的函数名、参数、返回值和调用方法

3）队列的顺序存储：一般顺序存储的队列和循环队列，循环队列主要解决的问题

4）在循环队列中六种基本运算的实现方法和具体算法

4）循环队列中掌握队列空和队列满的条件

5）队列的链式存储

6）队列的应用


1、识记：队列的定义和特征，六种基本运算函数

2、理解：循环队列上的六种基本运算

3、应用：通过掌握循环的特征来读懂队列的相关的算法


第四章 串
一、学习目的和要求
通过本章学习，学生需要了解串的基本概念及串的基本操作，掌握串的顺序存储结构和顺序串的各种运算的实现，了解串的链式存储结构

二、考核知识点与考核目标
（一）串及其运算（重点）
1）串的基本概念：串、串名、串值、串长

2）区别下列概念：空串和空格串
3）理解一下概念：子串、主串、串相等、子串在主串中的位置

4）串的运算有：赋值运算、判相等运算、求串

长运算、插入运算、删除运算、连接运算、替换运算、取子串运算

5）掌握以上各种运算的函数的写法、函数参数的含义和各函数的返回值、函数的调用方式


1、识记：串的相关概念、串的基本运算函数的原型

2、理解：串的各种有关的概念、串的基本运算函数的参数

3、应用：串的概念在实际例子中的应用、能够用串的基本函数对给出的字符串进行处理


（二）串的存储结构（一般）
1）串的顺序存储结构

2）串的链式存储结构


1、理解：串顺序存储结构


第五章 数组和广义表
一、学习目的和要求
通过本章学习，学生需要了解数组的逻辑定义和基本运算；熟练掌握数组的两种顺序存储方式；掌握特殊矩阵和稀疏矩阵的压缩存储；了解广义表的基本概念及其操作

二、考核知识点与考核目标
（一）数组的定义和运算（重点）
1）一维数组、二维数组的定义；
2）一维数组的顺序存储以及在顺序存储中求任意一个元素的首地址

3）二维数组的顺序存储：行主序、列主序
4）在二维数组的两种顺序存储方式中分别求任意一个元素的首地址


1、识记：数组的定义

2、理解：二维数组的两种存储方式

3、应用：能计算一维、二维数组中各元素的首地址


（二）矩阵的压缩存储（重点）
1）特殊矩阵：对称矩阵、三角矩阵、对角矩阵、稀疏矩阵

2）压缩存储的意义

3）各种特殊矩阵的压缩存储方式

4）在压缩存储中元素与存储下标的关系

5）稀疏矩阵的特殊存储


1、识记：特殊矩阵的压缩存储方式

2、应用：能计算在压缩存储中元素与存储下标的关系


（三）广义表（一般）
1）广义表的概念和它的定义方式、表头和表尾的定义

2）广义表的性质

3）广义表的存储结构

4）广义表的基本操作


1、识记：广义表的概念，表头和表尾的表示

2、理解：广义表的基本操作即对给定的广义表分离出表头和表尾


第六章 树和二叉树
一、学习目的和要求
通过本章学习，学生需要了解树的定义及基本术语；熟练掌握二叉树的性质，了解其性质的证明方法；熟练掌握二叉树的存储结构和各种遍历方法；了解二叉树的线索化的方法；熟练掌握哈夫曼树的构造方法及应用；熟练掌握树的各种存储结构及特点；掌握树和森林与二叉树的相互转换方法

二、考核知识点与考核目标
（一）树的概念和基本术语（次重点）
1）树的定义：掌握其定义的递归性

2）树的基本术语：结点的度、分支

结点、叶结点以及树的家族关系的描述方法

3）森林的概念


1、识记：树的概念及基本术语


（二）二叉树（重点）
1）二叉树的定义；
2）二叉树的五种基本形态；
3）注意树和二叉树的区别和联系

4）二叉树的性质：五个基本性质的定义、证明、应用

5）两种特殊的二叉树：满二叉树和完全二叉树


1、识记：二叉树的定义；二叉树与树的关系；二叉树的五个基本性质；完全二叉树的概念

2、理解：二叉树的基本性质和完全二叉树

3、应用：能利用二叉树的五个性质解决各种相关的问题


(三) 二叉树的存储结构（一般）
1）顺序存储结构：主要解决满二叉树和完全二叉树的存储

2）链式存储结构：结点的组成和存储方式


1、识记：二叉树的二叉链表存储


（四）二叉树的遍历（重点）
1）先序遍历方法

2）中序遍历方法

3）后序遍历方法

4）层次遍历方法

5）线索二叉树的概念

6）对二叉树线索化的方法


1、识记：二叉树的三种遍历方法

2、理解：二叉树的三种遍历方法以及二叉树的线索化的方法

3、应用：能根据画出的二叉树写出遍历结果；已知中序和先序遍历结果或中序和后序遍历结果画出二叉树；并能画出线索树


（五）哈夫曼树及其应用（重点）
1）哈夫曼树的定义以及相关术语：路径长度、权值等

2）加权路径长度的计算方法

3）构造哈夫曼树的方法

4）哈夫曼树的应用


1、识记：哈夫曼树的定义及相关概念

2、理解：哈夫曼树的构造方法

3、应用：能构造哈夫曼树以及完成哈夫曼编码


（六）树与森林（次重点）
1）树的存储结构：双亲表示法；孩子表示法；孩子兄弟表示法

2）树、森林转换成二叉树的方法

3）二叉树转换成树、森林的方法


1、识记：树的孩子兄弟存储法

2、理解：树、森林与二叉树的相互转换

3、应用：能完成树、森林与二叉树的相互转换


第七章 图
一、学习目的和要求
通过本章学习，学生需要了解图的基本概念和相关术语；熟练掌握图的邻接矩阵和邻接表以及图的深度遍历和广度遍历方法；能够用Prim和Kruscal方法构造最小生成树

二、考核知识点与考核目标
（一）图的概念和基本操作（次重点）
1）图的定义

2）图的相关概念：无向图、有向图、无向完全图、有向完全图、子图、邻接、路径、路径长度、简单路径、回路或环、定点的度、连通、连通图哈强连通图等

3）图的存储结构：邻

接矩阵表示法、邻接表表示法

4）图的深度优先遍历

5）图的广度优先遍历


1、识记：图的定义和相关术语、图的存储结构

2、理解：图的两种遍历方法


（二）图的连通性问题
1）无向图的连通分量和生成树

2）有向图的强连通分量

3）最小生成树的概念

4）用普里姆（Prim）算法构造最小生成树

5）用克鲁斯卡尔（Kruscal）算法构造最小生成树


1、识记：最小生成树的概念

2、应用：能用两种算法构造最小生成树


第八章 查找
一、学习目的和要求
通过本章学习，学生需要掌握静态查找表及其查找算法：顺序查找、折半查找、分块查找；了解动态查找表：二叉排序树；掌握哈希表及其查找

二、考核知识点与考核目标
（一）查找的基本概念（一般）
1）查找的概念及查找表

2）静态查找表和动态查找表

3）查找表的存储结构


1、识记：查找的方法；静态查找表


（二）静态查找表（重点）
1）顺序查找的基本思想、算法实现

2）折半查找在有序表中查找的基本思想：折半查找的实现过程和算法实现

3）分块查找的思想、实现过程


1、识记：顺序查找、折半查找、分块查找的基本思想

2、理解：顺序查找、折半查找、分块查找的实现过程

3、应用：顺序查找、折半查找、分块查找的算法实现


（三）动态查找表（一般）
1）二叉排序树的概念

2）二叉排序树的构造

3）在二叉排序树上的查找方法


1、识记：二叉排序树的概念和构造方法


（四）哈希表查找（一般）
1）哈希表的概念：散列、哈希表、哈希函数、冲突

2）构造哈希函数的方法：直接定址法、平方取中法、数字分析法、除留余数法

3）处理冲突的方法：开放定址法、拉链法


1、识记：哈希表的概念

2、理解：哈希表的查找为何会转换到构造哈希函数和处理冲突上来

3、应用：能利用构造哈希函数和处理冲突的方法构造哈希表


第九章 排序
一、学习目的和要求
通过本章学习，学生需要了解各种排序方法的稳定性，掌握排序的基本概念、排序的种类、排序的过程及方法；并会用各种排序方法的算法

二、考核知识点与考核目标
（一）排序的基本概念（一般）
1）排序的概念

2）排序的分类

3）排序稳定性的判断


1、识记：排序的基本概念和分类


（二）插入排序（重点）
1）插入排序的基本思想

2）插入排序的分类：直接插入排序、希尔排序、

3）

两种排序的实现过程

4）直接插入排序的算法实现


1、识记：插入排序的基本思想

2、理解：两种排序的实现过程

3、应用：对给定数据排序的实现


（三）交换排序（重点）
1）交换排序的基本思想

2）交换排序的分类：冒泡排序、快速排序

3）两种排序的实现过程

4）冒泡排序的算法实现


1、识记：交换排序的基本思想

2、理解：两种排序的实现过程

3、应用：对给定数据排序的实现


（四）选择排序（重点）
1）选择排序的基本思想

2）选择排序的分类：直接选择排序、堆排序

3）堆排序的概念以及初始堆的建立
3）两种排序的实现过程

4）直接选择排序的算法实现


1、识记：选择排序的基本思想

2、理解：两种排序的实现过程

3、应用：对给定数据排序的实现


（五）归并排序（一般）
1）归并排序的思想

2）二路归并的实现过程


1、识记：归并排序的基本思想和实现过程



第三部分 实践环节
一、教学目的
试验目的在于更深入的理解和掌握课程教学中的有关基本概念，将知识转化为能力，通过解决实际问题，来提高分析和解决问题的能力
因此明确试验的目的，以保证达到课程所指定的基本要求


实验一 顺序存储的线性表

（一）实验目的：
　1、了解线性表的逻辑结构特征

　2、熟练掌握线性表的顺序存储结构的描述方法及在其上实现各种基本运算的方法

　3、掌握和理解本实验中出现的一些基本的C语言语句

　4、体会算法在程序设计中的重要性

（二）实验内容：
1、将一顺序表中的元素逆置，要求算法仅用一个辅助结点

2、求顺序表中的元素的最大值和次最大值

3、设一顺序表中元素值递增有序
试设计一算法，将元素x插入到表中适当的位置上，并保持顺序表的有序性


实验二 单链表

（一）实验目的
1、熟练掌握线性表运用链表存储时的各种运算的算法实现

2、掌握和理解本实验中出现的一些基本的C语言语句

3、体会算法在程序设计中的重要性

（二）实验内容
1、设计一算法，逆置带头结点的动态单链表，要求用原表的结点空间

2、设一链表表中元素值递增有序
试设计一算法，将元素x插入到表中适当的位置上，并保持顺序表的有序性

3、在无表头结点、也无头指针的非空单循环链表中，指针S指向该链表中的任一结点，试写一算法删除结点S的直接前驱结点

4、设有两个按元素值递增有序的单链表A和B，编一程

序将A表和B表归并成一个新的递增有序的单链表C（值相同的元素均保留在C表中），并要求利用原表的空间


实验三 栈和队列

（一）实验目的
1、掌握栈和队列的数据结构的特点

2、熟练掌握在两种存储结构上实现栈和队列的基本运算

3、学会利用栈和队列解决一些实际问题

4、掌握和理解本实验中出现的一些基本的C语言语句

5、体会算法在程序设计中的重要性

（二）实验内容
1、写一算法将一顺序栈中的元素依次取出，并输出元素值

2、写一算法将一链栈中的元素依次取出，并输出元素值

3、写一算法将一顺序队列中的元素依次取出，并输出元素值

4、写一算法将一链队列中的元素依次取出，并输出元素值


实验四 串

（一）实验目的
1、掌握串的顺序和链式存储结构的实现方法

2、了解串的模式匹配算法

（二）实验内容
1、写出取子串运算的算法

2、写出替换运算的算法


实验五 二叉树

（一）实验目的
1、熟悉二叉树的各种存储结构及使用范围

2、掌握建立二叉树的存储结构的方法

3、熟练掌握二叉树的三种遍历方式的递归算法

4、掌握递归的方式

（二）实验内容
1、以二叉链表作存储结构，设计求二叉树高度的算法

2、以二叉链表作存储结构，编写递归的中序遍历算法


实验六 图

(一)实验目的
1、掌握图的两种存储结构的实验方法

2、掌握遍历图的递归算法

（二）实验内容
1、设计算法，构造无向图的邻接链表

2、设计算法，构造无向图的邻接矩阵


实验七 查找

（一）实验目的
1、掌握顺序查找、二分查找的递归和非递归算法

2、掌握散列表上的各种操作

3、了解在二叉排序树上各种操作的实现

（二）实验内容
1、给出顺序表上顺序查找元素的算法

2、给出非递归的二分查找算法


实验八 排序
（一）实验目的
1、熟练掌握在顺序表上实验排序的各种方法

2、深刻理解各种算法的特点并能灵活运用

（二）实验内容
顺利编写各种排序程序，实现对任意无序序列的递增排序操作

第四部分 有关说明与实施要求

一、课程自学考试大纲中有关术语的说明
在各章"基本要求"中，对概念和理论要求的提法是"了解"、"理解"、"深刻理解"；对技能要求的提法是"掌握"、"

熟练掌握"
为使自学者进一步把握自学要求，在各章的考核要求中，提出了"识记"、"理解"、"应用"等三个能力层次，他们之间是递进等级的关系，后者必须建立在前者基础上
它们的含义是："识记"-能知道有关的名词、概念、知识、定律、原理的意义，并能正确认识和表达
"理解"-在了解的基础上，能全面的把握基本概念和原理的区别与联系
"应用"-在理解的基础上，能用学过的一、二个知识点，分析和解决简单的问题，并且在简单应用基础上，能用学过的多个知识点综合分析和解决复杂的问题

二、考核目标的能力层次表述：
识记：能知道记忆有关名词、概念的意义，并能正确认识和表达

理解：在识记的基础上能把握基本概念和原理，能认识到有关概念和原理的区别与联系

应用：在掌握的基础上能用学过的知识点综合分析和解决一般性的问题

三、指定教材：
《数据结构》齐景嘉著东南大学出版社 2006年8月第1版

四、自学方法指导
1、在全面系统学习的基础上，掌握数据结构的基本概念、几种基本数据结构以及建立在各存储结构上的运算
各章节之间既互相联系，逐层深入，又相对有一定的独立性，自学应考者应先弄清本课程的体系，由浅入深、全面系统地学习各章内容，记忆应当识记的基本概念，读懂、理解线性表、排序和查找等章节程序例题，然后有目的地深入学习各重点章节

2、把学习数据结构的基本理论与上机实习结合起来
这要在C语言的基础上，把类C程序写成标准的C 语言程序，才可以输入到计算机中调试、运行、分析输出结果
有能力的考生应尽可能多地编程上机，以提高自己运用所学C语言知识对所学的数据结构有独立编程的能力

五、对社会助学的要求：
1、社会助学者应根据本大纲规定的考核知识点和基本要求，认真钻研指定教材，明确本课程与其它课程的不同特点与学习要求，对自学应考者进行切实有效地辅导，注意纠正他们自学中的各种偏向，把握社会助学的正确导向

2、要正确处理基础知识和应用能力的关系，努力引导自学应考者将识记、掌握同应用联系起来，把基础知识和理论转化成应用能力，在全面辅导的基础上，着重培养和提高自学应考者的分析问题、解决问题和编写程序的能力

3、要正确处理重点和一般的关系，课程内容有重点和一般之分
但考试内容是全面的，而且重点和一般是相互联系的，不能截然分开
社会助学者应指导自学应考者全面系统地学习教材，掌握全部考试内容和考核知识点，在此基础上再突出重点
总之，要把重点

学习同兼顾一般结合起来，切勿孤立地抓重点把自学应考者引向猜题、押题的错误倾向

4、助学学时：本课程为6学分，助学学时为108学时，分配如下：
章次 理论助学学时 章次 理论助学学时 一 2 八 12 二 28 九 12 三 8 四 4 五 12 六 18 七 12
六、关于命题考试的若干要求：
1、本课程的命题考试，应根据本大纲所规定的考核知识点和基本要求来确定考试范围和考核要求，不要任意扩大或缩小考试范围，提高或降低考核要求
考试命题要覆盖到各章，并适当突出重点章节，体现本课程的内容重点

2、本课程在试题中对不同能力层次要求的分数比例，一般为：识记占15%；理解占35%；应用占50%

3、试题要合理安排难度结构
试题难易度可分为：易、较易、较难、难四个等级
每份试卷中，不同难易度试题的分数比例一般为：易占20%；较易占30%；较难占30%；难占20%
必须注意，试题的难易度与能力层次不是一个概念，在各能力层次中都会存在不同难度的问题，切勿混淆

4、本课程考试试卷采用的题型有：单项选择题、填空题、简答题、程序填空题、计算题、综合应用题

5、考试方式采用闭卷笔试120分钟
采用百分制记分，60分合格

七、题型示例：　
（一）单项选择题：
1、数据元素及其关系在计算机存储器内的表示，称为数据的( )
　A、逻辑结构 B、存储结构 C、线性结构 D、非线性结构
（二）填空题：
1、含有769个结点的二叉树中，共有 个叶子结点

（三）简答题：
1、如右图所示试写出按照普里姆算法从顶点1出发得到最小生成树的过程中，选取的第三条边，并求出最小生成树的权


第三条边为：




权值是：


（四）程序填空题：
1、在有序表r中进行二分查找关键字为K的元素的非递归算法，若查找成功则返回对应元素的下标，否则返回0

相关的结构体定义如下：
typedef struct
{ KeyType key;
}SEQLIST;
int Binsch(SEQLIST *r, int n, KeyType K)
{
int low=1, high=n;
while(low<=high)
{
int mid;
mid= ① ;
if(______②__________) return mid;
else if(Kelse ____③___________;
}
return -1;
}
（五）计算题
1、已知数组A［20］［20］为对称矩阵，其中每个元素占5个单元
现将其下三角部分按行优先次序存储在起始地址为200的连续的内存单元中，求元素A［５，６］、A[15，8]对应的地址

（六）综合应用题
1、 有一组关键字序列（38，19，65，13

，97，49），采用快速排序方法由小到大进行排序，请写出第一趟的排序过程和结果

??

??

??

??

18、读书是易事，思索是难事，但两者缺一，便全无用处——富兰克林