2023年数据结构读书笔记.docx

《2023年数据结构读书笔记.docx》由会员分享，可在线阅读，更多相关《2023年数据结构读书笔记.docx（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023年数据结构读书笔记 第一篇：数据结构读书笔记 0913011037信息管理与信息系统李二勇 数据结构读书笔记 第一章是绪论部分，因为大家都是刚刚接触这门课，所以还有很多不是很多的了解，随着计算机的快速进展，计算机的应用领域已经不再只是科学计算领域，而更多的应用于限制管理以及数据处理等非数值计算的处理工作，与此对应，计算机加工处理的对象由纯粹的数值进展到字符，表格和图像等各种具有确定结构的数据，这就给程序设计带来了一些新的问题，为了编写出一个好的程序，必需分析待处理的对象的特性以及各处理对象之间存在的关系。所以在这种环境下，数据结构这门课就诞生了。 其次章.线性表的相关基本概念，如:前驱

2、、后继、表长、空表、首元结点，头结点，头指针等概念。 2.线性表的结构特点，主要是指:除第一及最终一个元素外，每个结点都只有一个前趋和只有一个后继。 3.线性表的依次存储方式及其在具体语言环境下的两种不同实现:表空间的静态支配和动态支配。静态链表与依次表的相像及不同之处 4.线性表的链式存储方式及以下几种常用链表的特点和运算:单链表、循环链表，双向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查 方式。此外，近年来在不少学校中还多次出现要求用递归算法实现单链表输出可能是依次也可能是倒序的问题。 5.线性表的依次存储及链式

3、存储状况下，其不同的优缺点比较，即其 各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。 第三章本章主要重点是1.栈、队列的定义及其相关数据结构的概念，包括:依次栈，链栈，共享栈循环队列，链队等。栈与队列存取数据请留意包括:存和取两部分的特点。 2.递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法 :n!阶乘问题，fib数列问题，hanoi问题，背包问题，3.栈的应用:数值表达式的求解，括号的配对等的原理 4.循环队列中判队空、队满条件，循环队列中入队与出队算法。 第四章1.串的基本概念，串与线性表的关系串是其元素均为字符型数据的

4、特殊线 性表，空串与空格串的区分，串相等的条件 2.串的基本操作，以及这些基本函数的运用，包括:取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。 3.依次串与链串及块链串的区分和联系，实现方式。 4.KMP算法思想。KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的缺乏，明确next数组需要改良之外。其中，理解算法是核心，会求数组是得分点。 查方式是:求next和nextval数组值，根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。 第五章广义表的概念，是数据结构里第一次出现的。它是线性表

5、或表元素的有限序列，构成该结构的每个子表或元素也是线性结构 1.多维数组中某数组元素的position求解。一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。 2.明确按行存储和按列存储的区分和联系 3.将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括:对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟识稀疏矩阵的三种不同存储方式:三元组，带帮助行向量的二元组，十字链表存储。驾驭将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。 4.广义表的概念，特别应当明确表头与表尾的定义。这一点，是理解整个广义表一节算法的基

6、础。 5.与广义表有关的递归算法。由于广义表的定义就是递归的，所以，与广义表有关的算法也常是递归形式的。比方:求表深度，复制广义表等。这种题 目，可以根据不同角度广义表的表现形式运用两种不同的方式解答:一是把一个广义表看作是表头和表尾两部分，分别对表头和表尾进行操作；二是把一个广义表看作是若干个子表，分别对每个子表进行操作。第六章1.二叉树的概念、性质和存储结构 考查方法可有:干脆考查二叉树的定义，让你说明二叉树与一般双分支树的区分；考查满二叉树和完全二叉树的性质，一般二叉树的五特性质:第i层的最多结点数，深度为k的二叉树的最多结点数，n0=n2+ 1的性质，n个结点的完全二叉树的深度，依次存

7、储二叉树时孩子结点与父结点之间的换算关系左为:2*i，右为:2*i+1。 2.二叉树的三种遍历算法 二叉树的遍历算法有三种:先序，中序和后序。其划分的根据是视其每个算法中对根结点数据的访问依次而定。不仅要娴熟驾驭三种遍历的递归算法，理解其执行的实际步骤，并且应当娴熟驾驭三种遍历的非递归算法。由于二叉树一章的很多算法，可以干脆根据三 种递归算法改造而来比方:求叶子个数，所以，驾驭了三种遍历的非递归算法后，应付诸如:“利用非递归算法求二叉树叶子个数 3.可在三种遍历算法的基础上改造完成的其它二叉树算法: 求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左右子树

8、，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。假如你可以娴熟驾驭二叉树的递归和非递 归遍历算法，那么解决以上问题就是小菜一碟了。 4.线索二叉树: 线索二叉树的引出，是为避开如二叉树遍历时的递归求解。对于线索二叉树，应当驾驭:线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题如:查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题。 5.最优二叉树哈夫曼树: 最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边给予了权值，这样形成的二叉树按权相加之和是最小的。 6.树与森林: 二叉树是一种特殊的树，这

9、种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的特殊之处是在于:二叉树是有序的！即:二叉树的左右孩子是不行交换的，假如交换了就成了另外一棵二叉树，这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树。但是，对于一般的双分支树而言，不具有这种性质。 树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法:先根与后根对于森林而言称作:先序与后序遍历。在难度比较大的考试中，也有基于此种算法的基础上再进行扩展要求你利用这两种算法设计其它算法的，但一般院校很少有这种考法，最多只是要求你根据先根或后根写出他们的遍历序列。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的:先根遍历对应

10、二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。 第七章 图 图这一章的特点是:概念繁多，与离散数学中图的概念联系紧密，算法困难与图两章的学问这一章的重点是:图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，连通图，强连通重量等概念。 2.图的几种存储形式: 图的存储形式包括:邻接矩阵，逆邻接表，十字链表及邻接多重表。 3.图的两种遍历算法:深度遍历和广度遍历 深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比方:“求最长的

11、最短路径问题和“推断两顶点间是否存在长为K的简洁路径问题，就分别用到了广度遍历和深度遍历算法。 4.生成树、最小生成树的概念以及最小生成树的构造RIM算法和KRUSKAL 7.最短路径问题: 最短路径问题分为两种:一是求从某一点动身到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。 主要还是表达在平常做试验的时候，因为做其他课的试验最至少会知道一些基本的做法，但是遇到数据结构就会觉察真的很难，有时真的什么都不会，看也看不懂，感觉很吃力，就感觉数据结构这个模块不简洁，有点困难，总体感觉学不好，但是上次期中考试时候，觉察也不是传闻中的那么难，有些题真的很死，可以用固定的方法去写，但是那种题

12、不多，大部分的题还是要自己去构造一种思想，并用代码实现它！感觉这样的题不好做，有点难度！其实，刚起先讲的时候，因为课下没有预习，上课节奏也没有跟上，所以就失去信念了。 这几天，因为考试在即，所以花了一些功夫复习，自我感觉收获还算不小，最至少了解了一些，学到了一些！但是课程已经结束了，还 是感觉缺少很多，所以自己还是要其他方面多多努力，接下来的复习还是要靠自己理解，假如理解好了以后对做题的关心确实不小，所以说，理解透彻了就好办了！如今大多是自学，相比以前的学习方法，感觉有点不一样，但是我信任假如努力还会有很大的提高的。 其次篇：数据结构 试验：线性表的基本操作 学习驾驭线性表的依次存储结构、链式

13、存储结构的设计与操作。对依次表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。 1.依次表的实践 1)建立4个元素的依次表s=sqlist=1，2，3，4，5，实现依次表建立的基本操作。 2)在sqlist =1，2，3，4，5的元素4和5之间插入一个元素9，实现依次表插入的基本操作。 3)在sqlist =1，2，3，4，9，5中删除指定位置i=5上的元素9，实现依次表的删除的基本操作。2.单链表的实践 3.1)建立一个包括头结点和4个结点的5，4，2，1的单链表，实现单链表建立的基本操作。 2)将该单链表的全部元素显示出来。 3)在已建好的单链表中的指定位置i=3插入一

14、个结点3，实现单链表插入的基本操作。 4)在一个包括头结点和5个结点的5，4，3，2，1的单链表的指定位置如i=2删除一个结点，实现单链表删除的基本操作。5)实现单链表的求表长操作。 1.打开VC+。 2.建立工程：点File-New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK-finish。至此工程建立完毕。 3.创建源文件或头文件：点File-New，选File标签，在列表里选C+ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4写好代码 5编

15、译链接调试 线性是我们学习数据结构中，遇到的第一个数据结构。学习线性表的重点驾驭依次表和单链表的各种算法和时间性能分析。线性表右两种存储方式即依次存储结构和链式存储结构。通过学习我知道了对线性表进行建立、插入、删除，同时单链表也是进行建立、插入、删除。而对于依次表的插入删除运算，其平均时间困难度均为0n.通过这次的学习，驾驭的太娴熟，主要是课本上的学问点没有彻底的理解，回去我会多看书，理解重要的概念。总之，这次试验我找到了自己的缺乏之处，以后会努力的。 试验二：栈的表示与实现及栈的应用 1驾驭栈的依次存储结构及其基本操作的实现。2驾驭栈后进先出的特点，并利用其特性在解决实际问题中的应用。3驾驭

16、用递归算法来解决一些问题。 1.编写程序，对于输入的随便一个非负十进制整数，输出与其等值的八进制数。 2.编写递归程序，实现N！的求解。3.编写递归程序，实现以下函数的求解。 n,n=0,1Fib(n)= Fib(n-1)+Fib(n-2),n1 4.编写程序，实现Hanoi塔问题。 1.打开VC+。 2.建立工程：点File-New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK-finish。至此工程建立完毕。 3.创建源文件或头文件：点File-New，选File标签，在列表里选C+ Source Fil

17、e。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4写好代码 5编译链接调试 通过这次的学习我驾驭了栈这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；总的来说，栈是操作受限的线性表，是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶top，相应地，表头端称为栈底botton；栈又称为后进先出Last In First Out的线性表,简称LIFO结构，因为它的修改是按后进先出的原则进行的。 加上这个试验，我已经学了线性表依次表，单链表和栈，知道它们都是线性表，而且对以后的学习有很大的作用，可以说这是学习以后学问的

18、总要基础。 试验三：二叉树的建立及遍历 1驾驭利用先序序列建立二叉树的二叉链表的过程。2驾驭二叉树的先序、中序和后序遍历算法。 1.编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。如：输入先序序列abc#de#，则建立如下列图所示的二叉树。 并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 1.打开VC+。 2.建立工程：点File-New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK-finish。至此工程建立完毕。 3.创建源文件或头文件：点File-New，选Fil

19、e标签，在列表里选C+ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4写好代码 5编译链接调试 这次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历，在这次试验中我按先序方式建立二叉树的，而遍历方式则相对要多一些，有递归的先序、中序、后序遍历，和非递归的先序、中序、后序遍历，此外还有层次遍历.二叉树高度和叶子个数的计算和遍历相差不大，只是加些推断条件，总体来说，本次试验不太好做，期间出现了很多规律错误，变量初始化的问题等，不过经过细致排查最终都一一解决了。 试验四：查找与排序 1驾驭折半查找算法的实现。2驾驭冒泡排序算法的实现。

20、 1.编写折半查找程序，对以下数据查找37所在的位置。5，13，19，21，37，56，64，75，80，88，92 2.编写冒泡排序程序，对以下数据进行排序。49，38，65，97，76，13，27，49 1.打开VC+。 2.建立工程：点File-New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK-finish。至此工程建立完毕。 3.创建源文件或头文件：点File-New，选File标签，在列表里选C+ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程

21、之中。 4写好代码 5编译链接调试 1查找算法的代码如下所示： #include “stdio.h #include “malloc.h #define OVERFLOW-1 #define OK 1 #define MAXNUM 100 #define N 10 typedef int Elemtype;typedef int Status;typedef struct Elemtype *elem; int length;SSTable;Status InitList(SSTable &ST) int i,n; ST.elem = (Elemtype*) malloc(Elemtype);

22、 if(!ST.elem)return(OVERFLOW); printf(“输入元素个数和各元素的值:); scanf(“%dn,&n); for(i=1;iST.elem) t=ST.elem;= (Elemtype*) malloc (MAXNUM*sizeof ST.elem=ST.elem;ST.elem=t;void display(SSTable ST) int i; for(i=1;inext=HL;HL=p;C.P-next=HL;p=HL;D.P-next=HL-next;HL-next=p;4.两个字符串相等的条件是 A.串的长度相等 B.含有相同的字符集 C.都是非空串

23、 D.串的长度相等且对应的字符相同 5若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是 A.SXSSXXXX B.SXXSXSSX C.SXSXXSSX D.SSSXXSXX 6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为A.0 B.1 C.48 D.49 7.已知用某种排序方法对关键字序列51，35，93，24，13，68，56，42，77进行排序时，前两趟排序的结果为 35，51，24，13，68，56，42，77，93 35，24，13，51，56，42，68，77，93所接受的排序方法是 A.插入排序 B.冒泡排序 C.快速排

24、序 D.归并排序 8.已知散列表的存储空间为T，散列函数Hkey=key%17,并用二次探测法处理冲突。散列表中已插入以下关键字：T=39，T=57和T=7，则下一个关键字23插入的位置是 A.T B.T C.T D.T 9.假如将矩阵Ann的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=(a11,a21,an1),(a12,a22,an2),，a1n,a2n,ann),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是A.head(tail(head(L)B.head(head(head(L)C.tail(head(tail(L)D.head

25、(head(tail(L)10.在一个具有n个顶点的有向图中，全部顶点的出度之和为Dout，则全部顶点的入度之和为 A.Dout B.Dout-1 C.Dout+1 D.n 11从规律关系来看，数据元素的干脆前驱为0个或1个的数据结构只能是A线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构 12栈的插入和删除操作在()进行。 A栈顶 B.栈底 C.随便位置 D指定位置 13由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为A.24 B.71 C.48 D.53 14一个栈的输入序列为1 2 3，则以下序列中不行能是栈的输出序列的是()A.2 3

26、 1 B.3 2 1 C.3 1 2 D.1 2 3 15关于栈和队列的说法中正确的选项是 A栈和队列都是线性结构 B.栈是线性结构，队列不是线性结构 C.栈不是线性结构，队列是线性结构 D.栈和队列都不是线性结构 16关于存储相同数据元素的说法中正确的选项是A依次存储比链式存储少占空间 B.依次存储比链式存储多占空间 C.依次存储和链式存储都要求占用整块存储空间 D.链式存储比依次存储难于扩充空间 17已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行A.qnext=s；pnext=s； B.qnext=s；snext=p； C.

27、qnext=s；qnext=p； D.qnext=s；snext=q； 18设一组记录的关键字key值为62，50，14，27，19，35，47，56，83，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是A.1 B.2 C.3 D.4 19执行下面程序段时，S语句被执行的次数为：for(int i=1;ikey=Key) printf(“已找到n); return; p=(Key key)? p-lchild:p-rchild; printf(“没有找到n); void InsertBST(BSTree *T,KeyType Key) BSTNod

28、e *f,*p; p=(*T); while(p) if(p-key=Key) printf(“树中已有Key不需插入n); return; f=p; p=(Key key)?p-lchild:p-rchild; p=(BSTNode*)malloc(sizeof(BSTNode); p-key=Key; p-lchild=p-rchild=NULL; if(*T)=NULL)(*T)=p; else if(Keykey)f-lchild=p; else f-rchild=p; /*InsertBST*/ void DelBSTNode(BSTree *T,KeyType Key) BSTNo

29、de *parent=NULL, *p, *q,*child; p=*T; while(p) if(p-key=Key)break; parent=p; p=(Key key)?p-lchild:p-rchild; if(!p)printf(“没有找到要删除的结点n);return; q=p; if(q-lchild & q-rchild) for(parent=q,p=q-rchild;p-lchild;parent=p,p=p-lchild);child=(p-lchild)?p-lchild:p-rchild; if(!parent)*T=child; else if(p=parent-

30、lchild) parent-lchild=child; else parent-rchild=child; if(p!=q) q-key=p-key; free(p); void InorderBST(BSTree T) if(T!=NULL) InorderBST(T-lchild);printf(“%5d,T-key);InorderBST(T-rchild); 第五篇：数据结构教学大纲 数据结构与算法教学大纲 课程编号：030816 适用专业：教化技术学 总学时数：64 学 分：4 编制单位：茂名学院理学院教化与信息技术系 编制时间：2023年6月20日 一、课程地位、性质和任务 数据

31、结构与算法课程是计算机相关学科专业的基础课程中的一门重要的核心课程。通过本课程的教学，使学生知道求解非数值类问题的基本模型表、树、图，模型的特点和适用场合，能够根据问题设计和选择好的算法，为学习后续的操作系统、编译原理和软件工程等专业课程，设计应用程序打下基础。 本课程以提高学生的计算机应用实力和综合素养为目标，通过课程教学，为学生构建数据结构与算法方面的学问体系，使学生一方面能够根据问题选择合适的数据结构，设计高效的算法，提高程序设计实力，另一方面，在工程应用中，具有甄别好算法的实力，也就是要从建模、解模和综合等三个方面，提高学生的程序设计实力。 二、与其他课程的关系 先修课：程序设计基础、

32、离散数学、计算机组成原理、计算机文化基础 三、教学内容、课时支配和基本要求 一教学部分 第1章 绪论2学时1.1什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析算法及其设计的要求，算法效率的度量，算法的存储空间需求1.5 问题求解 基本要求： 了解：抽象数据类型，算法设计方法与算法分析。 驾驭：数据与数据结构、算法的基本概念；问题求解的方法与步骤 重点：数据结构和算法的概念，算法的描述形式和评价方法，问题求解的一般步骤 难点：评价算法的标准和评价方法，最坏状况和平均状况的区分。 第2章 线性表8学时2.1 线性表的类型定义 2.2 线性表的依次表

33、示和实现 2.3 线性表的链式表示和实现线性链表，循环链表，双向链表2.4 一元多项式的表示及相加 基本要求： 了解：两种存储结构依次存储结构和链式存储结构及一元多项式的表示及相加。 驾驭：要求娴熟驾驭处理线性表的各种算法。为后继章节的学习打基础。重点：各种算法。难点：链表的理解。 第3章 栈与队列4学时 3.1 栈定义，栈的表示和实现 3.2 栈的应用举例数制转换，括号匹配的检验，行编辑程序，迷宫求解，表达式求值 3.3 栈与递归的实现 3.4 队列及其实现定义，链队列，循环队列3.5 *离散事务模拟 教学要求：娴熟驾驭栈和队列的特性和在不同存储结构前提下的算法实现。栈和队列是表最基本和重要

34、的数据结构，是数据结构课程的基础。 基本要求： 了解： 栈和队列的定义及其实现。 驾驭： 娴熟驾驭栈和队列的特性和在不同存储结构前提下的算法实现。重点： 栈和队列的算法实现。难点： 栈和队列的算法实现。 第4章 串2学时4.1 串类型的定义 4.2 串的表示和实现定长依次存储，堆支配存储，串的块链存储4.3 串的模式匹配算法求子串位置的定位函数，模式匹配的一种改良算法4.4 串操作应用举例文本编辑，建立词索引表 基本要求： 了解：串的基本概念及主要操作和运算。驾驭：驾驭串的基本概念和运算。重点：主要操作和运算。难点：模式匹配及串的应用。 第5章 数组2学时5.1 数组的定义 5.2 数组的依次

35、表示和实现 5.3 矩阵的压缩存储特殊矩阵，稀疏矩阵5.4 广义表的定义 5.5 广义表的存储结构 5.6 m元多项式的表示 5.7 广义表的递归算法求广义表的深度，复制广义表，建立广义表的存储结构 基本要求： 了解：了解作为抽象数据类型的数组和C语言的数组。相识到数组可以作为依次存储结构用于依次表、字符串和稀疏矩阵的实现。也可以接受链式存储结构。 驾驭：驾驭基本概念和算法。重点：算法。 难点：广义表的递归算法。 第6章 树与二叉树15学时6.1 树的定义和基本术语 6.2 二叉树二叉树的定义，二叉树的性质，二叉树的存储结构6.3 遍历二叉树和线索二叉树遍历二叉树，线索二叉树 6.4 树和森林

36、树的存储结构，森林与二叉树的转换，树和森林的遍历6.5 树与等价问题 6.6 赫夫曼树及其应用最优二叉树赫夫曼树，赫夫曼编码6.7 回溯法与树的遍历 6.8 树的计数 基本要求： 了解：理解树与森林的定义与术语。 驾驭：娴熟驾驭二叉树性质和遍历算法，驾驭树与森林的孩子兄弟存储表示和遍历。驾驭哈夫曼树构造的方法和算法。重点： 树的存储结构和遍历算法。难点：哈夫曼树构造的方法和算法 第7章 图11学时7.1 图的定义和术语 7.2 图的存储结构数组表示法，邻接表，十字链表，邻接多重表7.3 图的遍历深度优先搜寻，广度优先搜寻 7.4 图的连通性问题无向图的连通重量和生成树，有向图的强连通重量，最小

37、生成树，关节点和重连通重量 7.5 有向无环图及其应用拓扑排序，关键路径 7.6 最短路径从某个源点到其余各项点的最短路径，每一对顶点之间的最短路径基本要求： 了解：图的基本概念和相关术语。 驾驭：图的两种主要存储结构及遍历算法。驾驭最小生成树、最短路径和活动网算法的思想。 重点：图的两种主要存储结构及遍历算法。难点：图的遍历算法，最短路径算法。 第8章 查找8学时 9.1 静态查找表依次表，有序表，静态树表，索引依次表9.2 动态查找表二叉排序树和平衡二叉树，B_树和B+树，键树9.3 哈希表定义，构造方法，处理冲突的方法，查找及其分析 基本要求： 了解： 各种查找法的基本概念及实现的基本思

38、想。 驾驭：娴熟驾驭搜寻结构的折半查找、二叉搜寻树、平衡二叉树主要搜寻算法。驾驭哈希表查找算法。重点：各种算法的基本思想及实现。难点：哈希表查找算法。 第9章 内部排序8学时10.1 概述 10.2 插入排序干脆插入，其他插入，希尔10.3 交换排序冒泡排序、快速排序10.4 选择排序简洁，树形，堆10.5 归并排序 10.6 基数排序多关键字，链式10.7 排序算法分析 基本要求： 了解：基数排序，排序算法分析方法 驾驭：排序的基本概念，插入排序，交换排序，选择排序，归并排序重点：内部排序算法 难点：基数排序多关键字，链式 第10章 *外部排序2学时11.1 外存信息的存取 11.2 外部排

39、序的方法 11.3 多路平衡归并的实现 11.4 置换-选择排序 11.5 最正确归并树 基本要求： 了解：外部排序的基本概念和相关术语。 驾驭：基本驾驭外排算法的基本思想，不同排序方法的比较。重点：外部排序算法 难点：多路平衡归并的实现 第11章 算法设计的一般方法2学时 1重点 1有效算法的概念，问题固有难度的概念； 2递归法；分治法；平衡原则；贪心法；动态规划的基本原理；3搜寻-回溯法的基本原理和本质.2难点 1问题固有难度的概念； 2递归分治法的效率分析写出时间耗费的递推式，并求解；3动态规划法中的状态转移方程确实定。 二试验、实习部分 课程支配五个类别的试验，试验时数为12课时，其中

40、： 试验 一、线性链表及运算 2课时 试验 二、栈和队列 2课时 试验 三、树和二叉树 4课时 试验 四、图及其应用 2课时 试验 五、查找与排序 2课时 四、课程考核方式 闭卷考试70%、平常作业与试验30% 五、建议教材和教学参考书 参考教材： 1、数据结构C语言描述高等教化出版社 耿国华主编 2、数据结构C语言版清华高校出版社 严蔚敏，吴伟民编者 3、数据结构题集C语言版清华高校出版社 严蔚敏，吴伟民编者 4、数据结构算法实现及解析其次版西安电子科技高校出版社 高一凡 六、说明 1、因课时支配少，教学内容多。建议接受多媒体教学。 2、由于本课程内容较多，在实际教学中可根据大纲内容，进行适当调整。