数据结构豪华精简版

1、认真看完，想挂都很难！1·填空 8空8分2·名词解释 2题6分 第一章3·计算 3题12分 第一章4·多选 5题10分 第二章5·问答 7题56分6·编程 8分 左右二叉树插入删除P177-179第一章 绪论1·数据结构的基本概念（1）数据结构（DS）：相互之间存在一种或多种特定关系的数据元素的集合。（2）数据：是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所作的抽象描述。（3）数据元素：表示一个事物的一组数据。（4）数据项：构成数据元素的数据。例如:一本书的信息：由书名、作者、出版社和分类号等数据项

2、组成。（5）C定义的方法：typedef int DataType;或typedef StudentType DataType（6）数据结构包括：数据的逻辑结构和存储结构。2·DS的三要素：数据的逻辑结构、数据的存储结构、数据的操作。3·数据的逻辑结构主要分为哪4种？a、线性结构：除第一个和最后一个数据元素外，每个数据元素只有一个唯一的前驱和后继数据元素。b、树形结构：除根节点外，每个数据元素只有一个唯一的前驱数据元素，可有零个或若干个后继数据元素。c、图形结构：每个数据元素可有零个或若干个前驱数据元素和零个或若干个后继数据元素。d、集合注：a、树形结构和图形结构称为非线性

3、结构。一对一挂关系的结构称作线性结构。b、数据元素之间的相互联系方式称为数据的逻辑结构。4·数据的存储方法有四种： 顺序存储方法 、 链式存储方法 、 索引存储方法和散列存储方法 。 注：a、数据元素在计算机中的存储方式称为数据的存储结构。b、有两种基本形式：顺序存储结构和链式存储结构。c、顺序存储结构：把数据元素存储在一块连续地址空间的内存中，特点是逻辑上相邻的数据元素在物理上也相邻。d、链式存储结构：用指针把相互直接关联的结点（直接前驱结点或直接后继结点）连接起来，特点是：逻辑上相邻的数据元素在物理上（内存存储位置上）不一定相邻，数据间的逻辑关系表现在结点的连接关系上。e、指针是

4、指向物理存储单元地址的变量。由数据元素域和指针域组成的一个结构体称为一个结点。5·算法的特性：有穷性、确定性、可行性、有零个或多个输入、有一个或多个输出。注：a、算法的定义：描述求解问题方法的操作步骤集合。算法的实现：文字形式、伪代码、程序设计与语言。b、算法的设计目标：正确性、可读性、健壮性、高时间效率、高空间效率。6·计算题（算法的时间效率分析）：算法的耗时与算法所处理数据个数N的函数关系的分析，也称作算法的时间复杂度分析。注：时间频度：一个算法中的语句执行次数称为语句频度或时间频度。记为f(n)。 时间复杂度：对算法各基本操作的频度求和，便可得算法的时间复杂度。一般情

5、况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n),称O(f(n) 为算法的渐进时间复杂度，简称时间复杂度。 例：1、for(i=1;i<=n;i+) printf(“i=%dn”,i); 因为f(n)=n               所以 T(n)=O(n )2、f(n)=2n2

6、+n+1 T(n)=n2(就是n的平方)规律：为了方便比较，通常的做法是，从算法选取一种对于所研究的问题（或算法模型）来说是基本运算的操作，以其重复执行的次数作为评价算法时间复杂度的标准。该基本操作多数情况下是由算法最深层环内的语句表示的，基本操作的执行次数实际上就是相应语句的执行次数。例：for（i=1;i<=n; i+）for(j=1;j<=n; j+) c i j =0; for(k=1;k<=n; k+) c i j +=a i k *b k j ; 最深层基本语句执行次数f（n）= n3则该算法的 时间复杂度：T（n）=O（n3）O(1)<O(log2n)&l

7、t;O(n)<O(n*log2n)<O(n2)<O(n3)<O(2n)<O(n!)第2章 线性表1·带头结点单链表和不带头结点单链表插入、删除的比较。注：a、单链表是构成链表的结点只有一个指向直接后继结点的指针域。b、单链表的表示方法：数据域指针域 或Datanextc、data域存放数据元素，next域存放指向下一个结点的指针。d、指向单链表的指针称作头指针，头指针所指的不存放数据元素的第一个结点称作头结点。存放第一个数据元素的结点称作第一个数据元素结点。第一个数据元素结点在带头结点的单链表中是链表中的第二个节点，在不带头结点的单链表中是链表中的第一个

8、结点。例：带头结点的单链表（1） 带头结点单链表的插入删除。 P27（2）不带头结点的单链表的插入删除。P28结论：a、带头结点，无论是在第一个数据元素结点前插入还是在其他数据元素结点前插入，都不会改变头指针的值。删除第一个数据元素结点和删除其他数据元素结点算法的处理方法相同。 b、不带头结点，则在第一个数据元素前插入和在其他数据元素结点前插入算法的处理方法不同。删除第一个数据元素结点和删除其他数据元素结点的算法的处理方法不相同。2·双向链表在双向链表中,由于每个结点既包含有一个指向后继结点的指针,又包含有一个指向前驱结点的指针,所以当访问过一个结点后,既可以依次向后访问每一个结点,

9、也可以依次向前访问每一个结点。双向链表中，每个结点有3个域：prior、data、next，其中prior域为指向前驱结点的指针域。单链表中,进行结点插入和删除时涉及到前后结点的一个指针域的变化。而在双链表中,结点的插入和删除操作涉及到前后结点的两个指针域的变化。插入、删除操作具体看P37-402·线性结构的特点（非重点，了解）A 定义：可以在任意位置进行插入何删除数据元素操作的、有n（n>=0）个相同类型数据元素a0,a1,a2an-1组成的线性结构。B 特点：除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素。3·线性结构的两种存储结

10、构及其对应的特点（非重点，了解）(1) 顺序存储结构特点: a线性表中所有数据元素所占的存储空间是连续的；b 线性表中各数据元素在存储空间上是按逻辑顺序依次存放的。(2) 链式存储结构特点：a用一组任意的存储单元存储线性表的数据元素；b利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素；c每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息第三章 栈1·给出数据元素序列A、B、C、D，给出利用一个栈可以得到的所有数据元素序列和不可以得到的所有数据元素序列（重点）解：可以得到的数据元素序列有：A入，A出，B入，B出，C入，C出，D入，D出，得ABCDA入，A出，B入，B出，C

11、入，D入，D出，C出，得ABDCA入，A出，B入，B出，C入，D入，D出，C出，得ACDBA入，A出，B入，C入，C出，B出，D入，D出，得ACBDA入，A出，B入，C入，D入，D出，C出，B出，得ADCBA入，B入，B出，A出，C入，C出，D入，D出，得BACDA入，B入，B出，A出，C入，D入，D出，C出，得BADCA入，B入，B出，C入，C出，D入，D出，A出，得BCDAA入，B入，B出，C入，C出，A出，D入，C出，得BCADA入，B入，B出，C入，D入，D出，C出，A出，得BDCAA入，B入，C入，C出，B出，D入，D出，A出，得CBDAA入，B入，C入，C出，B出，A出，D入，D出

12、，得CBADA入，B入，C入，C出，D入，D出，B出，A出，得CDBAA入，B入，C入，D入，D出，C出，B出，A出，得DCBA除上述14个不同组合外，尚有ADBC，BDAC，CABD，CADB，CDAB，DABC，DACB，DBAC，DBCA，DCAB组合不能得到。2·栈和队列的概念（非重点，了解）(1)栈：a一种特殊的线性表，栈的数据元素以及数据元素间的逻辑关系和线性表完全相同，差别是：线性表的插入删除不受限制，而栈只能在栈顶插入和删除。 b栈中允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。栈的插入操作通常称为进栈或入栈, 栈的删除操作通常称为退栈或出栈。不含元素的空表称

13、空栈 c每次进栈的数据元素都放在原来当前栈顶元素之前而成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，这样，最后进入栈的数据元素总是最先退出栈，因此，栈也称为后进先出线性表。（2）队列：a一种特殊的线性表，队列的数据元素及数据元素间的逻辑关系和线性表相同，差别是：线性表允许在任意位置插入删除，队列只允许在队尾插入，队头删除。b 每次入队列的数据元素都放在原来的队尾数据元素之后成为新的队尾元素，每次出队列的数据元素都是原来的队头元素。这样，最先入队列的数据元素总是最先出队列，多以队列是先进先出线性表。3·栈和队列进行数据修改的原则（非重点，了解）栈：后进先出 队列：先进先出第4

14、章 串1·KMP算法例： 0 1 2 3 4 5 6 7a b a a b c a cnextj -1 0 0 1 1 2 0 1nextvalj -1 0 -1 1 0 2 -1 1以下为神将庞武锦解题破解：（1） nextj方法：a、0对应的a为-1,1对应的b为0。.神将说固定的！结果可从下面做法推出。b、2对应的a前面的b的前面木有与之相同对应的b，所以2对应a的nextj为0。.c、3对应的a前面的a的前面有0对应的a，所以3对应的a的nextj为0对应的a的退一格为1对应的b，即nextj为1。d、4对应的b前面的a有0对应的a（神将说找对应的只能找最前面的，所以2对应的

15、a跳过，但是有种情况是前面一排的是否形成对称，对称则取中间。如P105），所以退一格为1对应的b，即nextj为1。同理，可得出后面结果。总结：做法是先找X（07）对应下字母（a、b、c）前面字母Y1的前面有木有与之对应相同的字母Y2，没有与之对应相同的nextj为0，有对应相同的则nextj为退一格的字母上的X（07）。（2） nextvalj方法：a、0对应的a为-1,1对应的b为0。不要问为什么了！b、2对应的a的nextj为0与0对应的a有相同的a，则2对应的a的nextvalj为0对应的a的nextj为-1，即2对应的a的nextvalj为-1。c、3对应的a的nextj为1与1对应

16、的b，a和b不同。则3对应的a的nextvalj等于3对应的a的nextj为1。同理，可得出后面的答案。总结：做法是先找X（07）对应下的（a、b、c）的nextj为Y，再找到Y和X相等的对应，再看Y和X对应下的字母（a、b、c）是否相同。相同的，则nextvalj为X对应下的nextj；不相同的，则nextvalj为对应下的nextj。（不知道有木有讲清楚。）2·空格串、空串的概念（非重点，了解）空格串: 由一个或多个空格组成的串 称为空格串，它的长度为串中空格字符的个数。空串:就是神马都没有。3·串相等的判断条件（非重点，了解）当且仅当两个串的值完全相等。第七章 广义表

17、利用广义表的GetHead和GetTail操作写出函数表达式，将原子banana分别从下列广义表中分离出来（1）L1=(apple, pear, banana, orange)（2）L2=(apple, pear), (banana, orange)（3）L3=(apple), (pear), (banana), (orange)（4）L4=(apple, (pear), (banana), (orange)（5）L5=(apple), (pear), (banana), orange)（6）L6=(apple), pear), banana), orange)（7）L7=(apple, (p

18、ear, (banana), orange)解：（1）gethead(gettail(gettail(L1)（2）gethead(gethead(gettail(L2)（3）gethead(gethead(gettail(gettail(gethead(L3)（4）gethead (gethead (gethead(gettail(gettail(L4)（5）gethead(gethead(gettail(gettail(L5)（6）gethead(gettail(gettail(gethead(L6)（7）gethead(gethead(gettail(gethead(gettail(L7)

19、注：取表头：取第一个元素，后面的元素舍去。（去括号）取表尾：除第一个元素以外的元素。（留括号）GetHead(p, h, w) PGetTail(b, k, p, h) （K，P，h） GetHead(a, b), (c, d) (a,b)GetTail(a, b), (c, d) (c,d)2·广义表的概念（非重点，了解）定义：n>=0个数据元素组成的序列，每个数据元素或但个数据元素简称原子，或依然是一个广义表。广义表的长度：最外层包含的元素个数。广义表的深度：所有原子数据元素到达根结点的最大值。注：当广义表为原子元素时深度为0；为空表时深度为1；其他情况的子表的最大深度+1

20、.（1）A = () （2）B = (e) （3）C = (a, (b, c, d)（4）D = (A, B, C)=(), (e), (a, (b, c, d)（5）E = (a, (a, b), (a, b), c)第八章 树和二叉树1·二叉树的性质性质1：在一棵非空二叉树的第i层上至多有2i个节点（i >= 0）性质2：深度为k的二叉树至多有2k+1 - 1个节点(k >= -1)性质3：对于一棵非空二叉树，若度为2的节点有n2个，叶子节点有n0个，则有n0 = n2 + 1性质4：有n个节点的完全二叉树的深度k为 log2n性质5：若对一棵有n个节点的完全二叉树的

21、节点按层的顺序编号，则对任一节点i (0 <= i < n)有：a） 若i = 0，则节点i为根节点，无双亲若i > 0，则i的双亲节点为(i - 1) / 2b)若2i + 1 < n，则节点i的左孩子为2i + 1若2i + 1 >= n，该节点为叶子节点c)若2i + 2< n，则节点i的右孩子为2i+2若2i + 2 >= n，则无右孩子d)节点i所在层数为 log2i+1 例：一棵完全二叉树有1000个节点有 500 个叶子节点有 499 个度为2的节点具有n个节点的完全二叉树中有én/2ù叶子节点，有én/2&

22、#249; - 1个度为2的节点具有n0个叶子节点的完全二叉树中共有2n0个节点或2n0 - 1个节点2·二叉树遍历前序遍历：根结点左子树右子树中序遍历：左子树根结点右子树后序遍历：左子树右子树根结点例1：画出满足下列条件的二叉树：a该二叉树中序遍历DCBGEAHFIJK；b该二叉树后序遍历DCEGBFHKJIA。解：a由后序遍历最后一个A得出为根结点。b在中序找到A，A左边为左子树，右边为右子树。（DCBGE）A（HFIJK）。c后序中前5个DCEGB为左子树，后5个FHKJI为右子树。(DCEGB)(FHKJI)Ad后序左子树、右子树的最后一个B、I为根结点A的左右子树。(DC)

23、B(GE)A(HF)I(JK)e中序B左DC为结点B的左子树，右边GE为结点B的右子树；同理I的左子树为HF，右子树为JK。f后序DC的C在后，C为根；EG的G在后，G为根。g中序遍历：左根右 后序遍历：左右根则二叉树图自己画 例2：已知一棵二叉树的中序序列： BDCEAFHG 后序序列： DECBHGFA请画出这棵二叉树分析a由后序遍历特征，根节点必在后序序列尾部b由中序遍历特征，根节点必在其中间，而且其左部必全部是左子树的子孙，其c右部必全部是右子树的子孙d子树依此类推3·树转换为二叉树、森林转换为二叉树（1）树转换为二叉树a兄弟相连:将同一双亲节点的兄弟节点相连b长兄为父:保留

24、节点的最左孩子连线，删除其它孩子连线c长子靠左，弟弟靠右: 特点：根节点没有右孩子节点的最左孩子为左孩子，节点的右兄弟为右孩子（2）二叉树转换为树：将所有右孩子变为兄弟（3）森林转换为二叉树: 首树根为根，余根变兄弟（4）二叉树转换为森林：把根的右子树变为森林，其余右子树变为兄弟 具体看课件，P207 8-134·理解： （1）树：由n(n>=0)个结点构成的集合。n=0的树为空树 n=1的树只有一个结点，对n>1的树T有：A有一个特殊的结点为根节点，根节点没有前驱结点B除根结点外，其余结点被分成m（m>0）个互不相交的集合T1，T2，。Tm，其中每个集合Ti(1&

25、lt;=i<=m)本身又是一棵结构与树类同的子树。（2）结点：包括一个数据元素及若干指向其子树的分支。 结点的度：结点所拥有的子树的个数。 叶结点：度为0的结点。 分支结点：度不为0的结点。也称非终端结点。 孩子结点：树中一个结点的子树的根结点称作这个结点的孩子结点。也称后继结点。 双亲结点：若树中某结点有孩子结点，则这个结点称作它的孩子结点的双亲结点。也称直接前驱结点。 兄弟结点：具有相同的双亲结点的结点。（3）树的度：树中所有结点的度得最大值。 结点的层次：从根结点到树中某结点所经路径上的分支数称为该结点的层次。 树的深度：树中所有结点的层次的最大值。 有序树如果树中各结点的各子树从

26、左至右是有序排列，不可互换的，则称该树为有序树，反之为无序树。 森林：m(m>=0)棵数的集合。（4）二叉树：n(n>=0)个有限结点构成的集合。n=0的树称为空二叉树；n=1的树只有一个根结点；n>1的二叉树由一个根结点和至多两个互不相交的、分别称作左子树和右子树的子二叉树构成。满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层，则为满二叉树。完全二叉树：如果一棵具有n个结点的二叉树的结构与满二叉树的前n个结点的结构相同，称为完全二叉树。5·掌握哈夫曼树和哈夫曼编码的构造（1）在二叉树中，从树中一个结点到另一个结点之间的分支

27、构成这两个结点之间的路径。 路径上的分支数目称做结点到结点的路径长度。 树的路径长度是从树根到所有结点的路径长度之和。 （2）树的带权路径长度（WPL）：从二叉树根节点到所有叶子节点的路径长度与相应叶子节点权值的乘积之和。例： WPL=1*2+2*3+3*3+4*1=21例：一棵有n0个叶子节点的Huffman树，有 个节点n = n0 + n1 + n2 = 2n0 - 1Huffman树构造算法：P194 结合课件看例题：密文。P208 8-26 重点第9章 图1·图的遍历（深度优先和广度优先）（1） 深度优先a从图中某个初始顶点v出发，访问初始顶点vb选择一个与顶点v相邻且没被

28、访问过的顶点w为初始顶点，再从w出发进行深度优先搜索c直到图中与当前顶点v邻接的所有顶点都被访问过为止（2） 广度优先a访问初始点vi b访问vi的所有未被访问过的邻接点vi1,vi2,vit c按vi1,vi2,vit的次序，访问每一个顶点的所有未被访问过的邻接点d依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止2·最小生成树定义：带权无向连通图的所有生成树中边的权值总和最小的生成树构造最小生成树的准则：1. 必须包括n个顶点2. 必须使用且仅使用图中的n-1条边来连接图中的n个顶点3. 不能产生回路注：普利姆算法、克鲁斯卡尔算法见书本P229、P234和课件题目。

29、3·最短路径a从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，将路径长度最短(即经过的边数最少)的那条路径称为最短路径，其路径长度称为最短路径长度或最短距离b考虑路径上各边上的权值，则通常把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径长度c考虑路径上各边上的权值，则通常把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径长度注：重点看课件和书P235以后。4·拓扑排序 结合课件例题看设G=(V, E)是一个具有n个顶点的有向图V中顶点序列v1, v2, , vn称为一个拓扑序列，当且仅当该顶点序列满足下列条件：

30、若<vi, vj>是图中的边，则在序列中顶点vi必须排在顶点vj之前在一个有向图中找一个拓扑序列的过程称为拓扑排序拓扑排序方法1. 从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它2. 从网中删去该顶点，并且删去从该顶点发出的全部有向边3. 重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止5·理解：a有n(n-1) 条边的无向图称为完全图,有 n(n-1) 条弧的有向图称为有向完全图。 b连通图和强连通图：无向图G，如果从顶点 vi 到顶点 vj 有路径，则称 vi 和 vj 是连通的。 如果对于无向图 G 中任意两个顶点 vi , vj V, vi 和 v

31、j 都是连通的，则称 G 是连通图。 在有向图中，若如果对于每一对 vi, vj V，vivj ，从 vi 到 vj 和 从 vj 到 vi 都存在路径，则称 G 是强连通图。c在图G=(V,E)中，若从结点vi出发有一组边(或弧)可到达结点vj，则称结点vi到vj的结点序列为从结点vi到vj的路径。d回路在路径中，第一个结点和最后一个结点相重合的路径叫回路或叫环 e简单路径在路径中，序列中各结点不重复出现的路径叫简单路径f简单回路除了第一个结点和最后一个结点外，其余结点都不重复出现的回路叫简单回路（或简单环） g如果无向连通图是一个带权图，那么他所有生成树必有一棵边得权值总和最小的生成树，我

32、们称这棵树为最小生成树。第十章 排序 结合课件看以下排序的例题（1）希尔排序1. 把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序2. 小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后排序过程结束3. 小组的构成不是简单地“逐段分割”，而是将相隔某个增量span的记录组成一个小组，让增量span逐趟缩短（如依次取5, 3, 1），直到span = 1为止（2）堆排序设有n个数据元素的序列 k0, k1, , kn-1，当且仅当满足下述关系之一时，称之为堆 ki k2i+1且ki k2i+2（小根堆） ki k2i+1且ki k2i+2（大根堆） i = 0, 2, (n-1)/2如果让满足以上条件的元素序列 (k0, k1, , kn-1)顺次排成一棵完全二叉树，则此树的特点是： 树中所有节点的值均大于（或小于）其左右孩子，此树的根节点