数据结构(c语言版)复习资料.doc

数据结构复习资料

一、填空题
1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。
2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。
3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。
4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。
5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
6． 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。
7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。
8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。
9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。
10. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。
11. 一个算法的效率可分为 时间 效率和 空间 效率。
12. 在顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数与 表长和该元素在表中的位置 有关。
13. 线性表中结点的集合是 有限 的，结点间的关系是 一对一 的。
14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。
15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。
16. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。
17. 顺序表中逻辑上相邻的元素的物理位置 必定相邻。单链表中逻辑上相邻的元素的物理位置 不一定 相邻。
18．在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示。
19． 在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。
20. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。
21. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。
22. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
23. 不包含任何字符（长度为0）的串 称为空串； 由一个或多个空格（仅由空格符）组成的串 称为空白串。
24. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。
25. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。
26． 由３个结点所构成的二叉树有 5 种形态。
27. 一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶子。
注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。
28． 一棵具有２５７个结点的完全二叉树，它的深度为 9 。
（ 注：用ë log2(n) û+1= ë 8.xx û+1=9
29．设一棵完全二叉树有700个结点，则共有 350 个叶子结点。
答：最快方法：用叶子数＝[n/2]＝350

30． 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。
答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。 另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.
31．在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
32. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。
33. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。
解：显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不应当按照公式
来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：
全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！
34．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
35. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。
36. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
二、判断正误（在正确的说法后面打勾，反之打叉）
（ × ）1. 链表的每个结点中都恰好包含一个指针。
答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。
（ × ）2. 链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的示意图有序。
（ × ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。错，链表的结点不会移动，只是指针内容改变。
（ × ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。
（ × ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”
（ × ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。
（ × ）7. 线性表在物理存储空间中也一定是连续的。
错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。
（ × ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。
（ × ）9. 顺序存储方式只能用于存储线性结构。
错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍）
（ × ）10. 线性表的逻辑顺序与存储顺序总是一致的。
错，理由同7。链式存储就无需一致。
（ × ）11. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。
（ × ）12. 在表结构中最常用的是线性表，栈和队列不太常用。
错，不一定吧？调用子程序或函数常用，CPU中也用队列。
（ √ ）13. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
（ √ ）14. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。
（ × ）15. 栈和链表是两种不同的数据结构。
错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。
（ × ）16. 栈和队列是一种非线性数据结构。
错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。
（ √ ）17. 栈和队列的存储方式既可是顺序方式，也可是链接方式。
（ √ ）18. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
（ × ）19. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
错，后半句不对。
（ × ）20. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。
错，有可能。
（ √ ）21. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（ × ）22.二叉树中每个结点的两棵子树的高度差等于1。
（ √ ）23.二叉树中每个结点的两棵子树是有序的。
（ × ）24.二叉树中每个结点有两棵非空子树或有两棵空子树。
（ × ）25.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。 （应当是二叉排序树的特点）
（ × ）26.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1）
（ × ）27.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（ × ）28.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）
（ √ ）29.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
（ √ ）30.具有12个结点的完全二叉树有5个度为2的结点。
三、单项选择题
（ B ）1. 非线性结构是数据元素之间存在一种：
A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系
（ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构；
A) 存储 B) 物理 C) 逻辑 D) 物理和存储
（ C ）3. 算法分析的目的是：
A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系
C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性
（ A ）4. 算法分析的两个主要方面是：
A) 空间复杂性和时间复杂性 B) 正确性和简明性
C) 可读性和文档性 D) 数据复杂性和程序复杂性
（ C ）5. 计算机算法指的是：
A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法
（ B ）6. 计算机算法必须具备输入、输出和 等5个特性。
A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性
C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性
（ C ）7．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：
（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构
（ B ）8.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是
（A）110 （B）108 （C）100 （D）120
（ A ）9. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：
（A） 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
（B） 在第i个结点后插入一个新结点（1≤i≤n）
（C） 删除第i个结点（1≤i≤n）
（D） 将n个结点从小到大排序
（ B ）10. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素
（A）8 （B）63.5 （C）63 （D）7
（ A ）11. 链接存储的存储结构所占存储空间：
（A） 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
（B） 只有一部分，存放结点值
(C） 只有一部分，存储表示结点间关系的指针
（D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数
B ）12. 链表是一种采用 存储结构存储的线性表；
（A）顺序 （B）链式 （C）星式 （D）网状
（ D ）13. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:
（A）必须是连续的 （B）部分地址必须是连续的
（C）一定是不连续的 （D）连续或不连续都可以
（ B ）14． 线性表Ｌ在 情况下适用于使用链式结构实现。
（Ａ）需经常修改Ｌ中的结点值 （Ｂ）需不断对Ｌ进行删除插入
（Ｃ）Ｌ中含有大量的结点 （Ｄ）Ｌ中结点结构复杂
（ B ）15.栈中元素的进出原则是
Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出
（ C ）16. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为
Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定
（ B ）17. 判定一个栈ST（最多元素为m0）为空的条件是
Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0
（ C ）18. 在一个图中，所有顶点的度数之和等于图的边数的 倍。
A．1/2 B. 1 C. 2 D. 4 （
B ）19. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。
A．1/2 B. 1 C. 2 D. 4
（ B ）20. 有8个结点的无向图最多有 条边。
A．14 B. 28 C. 56 D. 112
（ C ）21. 有8个结点的有向完全图有 条边。
A．14 B. 28 C. 56 D. 112
（ B ）22．在表长为ｎ的链表中进行线性查找，它的平均查找长度为
Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;
Ｃ. ＡＳＬ＝＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１
（ A ）23．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 比较大小，查找结果是失败。
A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50
（ C ）24．对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。
A．3 B．4 C．5 D． 6
（ A ）25. 链表适用于 查找
A．顺序 B．二分法 C．顺序，也能二分法 D．随机

四、简答题

1.数据结构和数据类型两个概念之间有区别吗？
答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。
2. 简述线性结构与非线性结构的不同点。
答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。
3、分析下面各程序段的时间复杂度

(1.) for (i=0; i<n; i++)
for (j=0; j<m; j++)
A[i][j]=0;
答：O（m*n）
1.
项基本原则

(2.) x=0;
for(i=1; i<n; i++)
for (j=1; j<=n-i; j++)
x++;
解：因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）

4.设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。
刘答：至少有14种。
① 全进之后再出情况，只有1种：4，3，2，1
② 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4
③ 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4
④ 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3
5.给定二叉树的两种遍历序列，分别是：
前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，
试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。
解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。

D
A
C F
E G
B H I
6. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
答：DLR：A B D F J G K C E H I L M
LDR: B F J D G K A C H E L I M
LRD：J F K G D B H L M I E C A

数据结构的概念：数据之间的内在联系。要了解3种数据结构的概念：逻辑结构；物理结构；基本操作。
例如：栈和队的逻辑结构都是线性的，但她们的基本操作不同，就是不同的数据结构。
常见的数据结构的分类：线性关系；集合关系；一对多；多对多（图）；
什么事物理结构（应该有印象）。
算法设计时要用类PASCAL,类C，不要用C++.
算法分析的常用方法：事前分析；事后统计。
时间/空间复杂度的概念。空间是算法运行时资源占用情况。
时间复杂度：最坏，最好，平均。
例如：归并排序都是O（n*logn），最好，最怀，平均都是一样的
   插入排序：最好为O(n) ,最坏为O（n2）
线性表：逻辑关系，各种基本操作，两个有序表的归并。
线性表的顺序存储：线性表的操作在顺序表中的实现。
例如：1。插入与删除和插入的位置与表长有关。
   2．在一个长为n的表中插入一个元素的平均复杂度，要有插入位置的概率分布表达式，即给出此表达式，算平均复杂度。
线性表的链式存储：链表的基本操作：2个有序表的归并。
例如：1。把链表就地逆置：一个指针P指向当前逆置好的一系列节点的最后一个节点，取P的NEXT插入队头。
   2．三色问题：节点红黄蓝在链表上无序排列，把他们按红黄蓝的顺序排好。要求只能从头到尾搜索一遍。设当前指针P，头指针S，S.NEXT为Q，S后接红节点。若P为红，插入S后。若P为黄，插入Q后。若P为兰，不动。然后P向后移，求下个。
注：要了解单链表的插入，删除在什么位置操作。
静态链表（数组表示）：不能象单链表那样不受限增加节点。
循环链表：如果表示队列，用它最好。P指向队尾。好处：用于优先队列中。
双向链表：单链表中只有P指向当前节点，不能删除P。因为无法找到P 的前驱。而双向链表可以。注意指针变化情况。
栈：后进先出。基本操作：出入栈，取栈顶。在顺序表和链表上的实现；出栈序列是否合理？
例如：入栈序列是1，2，，，n，则出栈序列有几种？（即n个节点的二叉树的个数。因为树的先序是1，2，，，n）。
栈与递归：见我给你寄过去的手写体。
队列：先进现出。链队列，循环队列。
例如：1。把从队头开始的第i个元素删除：队列 只有出队入队，不能直接删除。要先将前i-1个出队，入队尾；i出队；i+1以后的出队入队尾。
   2．队列逆置（队头与队尾交互）：出队入栈；后出栈入队。
注意：这些结构的基本操作有什么，不能混。
循环队列：队头指针和队尾指针。记住队空和满的标志。见手写版。
串：1。KMP算法，求NEXT函数值等。时间：O(n+m)。其中，模式匹配为O（n）；预处理为O（m）,要会证明她们。简略证明见手写版。
      2．求两串的最长公共子串，时间为O（n）是不行的，至少要O（n2）。具体证明估计不会考。
17．数组：存储位置与下标对应。特殊数组（对称，上三角等）。
  三元组，稀疏矩阵（求逆）。计数技术，在设计算法中的应用。
   十字链表不考。
   广义表：基本概念，存储结构（二叉链表）。应用不考。
   广义表递归算法了解。
二叉树的性质（熟）。
   存储结构：二叉链表，三叉链表。
   遍历：中，先，后。 按层遍历：用辅助队列。例如求K层有多少节点。
线索二叉树：中序（先后序不考）。线索中的插入删除不考。
树与森林的遍历：树的先根与后根（分别对应相应二叉树的先序，中序）。森林的先序和后序（分别对应相应二叉树的先序，中序）。
树与二叉树一一对应。
由先序中序可以唯一确定二叉树。而由先序后序不能。例子见手写版。
二叉树可以为空，树不能为空（树为有根有序树）。
树与等价：例如：判断一个元素是否属于一个特定的集合，可看这个节点是否在此树上。看两个节点是否在一个强联通分量，看他们是否在一棵树上。求KRUSCAL算法（最小生成树集合）。
哈夫曼：前缀码。它是加权外部路径长度最小的二叉树。它是严格二叉树，无度为1的点。节点个数＝2×叶节点－1。 构造，编码。
扩展：用0，1，2三进制编码：元素个数为奇。N个元素K进制：K-1整除N-1。否则增加概率为零的元素。
注意11。6节的最佳归并。
树的计数：记结论。
N个操作符或N个括号，为操作符加括号的情况数目。
N＋2个顶点的凸多边形，他的不同三角剖分的个数。
a1,a2,,,an, ai=1/-1,任意前k个ai之和大于等于0，求不同组合数。
见手写版。
图：存储结构（针对有向图和无向图）。邻接表中边节点中存储的信息不是顶点内容而是顶点序号。
图的遍历：深度优先借助于栈；广度优先借助于队列。
图的连通：深度优先搜索一次。
有向图的强联通分量（不重要）。
最小生成树：PRIM算法，KRUSCAL算法。写算法，要用到树与等价类。（SEL-UNION算法）。她们的时间复杂度。若用优先队列，时间复杂度降低。
关节点，关键路径：深度优先数。
有向无环图：拓扑排序。用邻接矩阵保存它，则入度为0的列全为0。去掉该节点，必还有节点入度为0，所以调整矩阵，可得上三角矩阵。
DAG图等价为拓扑有序。拓扑排序算法：2个共享链栈，利用空间。
若得逆拓扑序，不用栈而用队列；也可以增加一个栈。也可以用深度优先搜索，找最深得那个节点最先把它输出。
最短路径：单源（有向图，且权值>=0是DIJISTRU算法的适应范围）。对无向图，可看成2个方向权值一样。例子见手写版。
问：DIJISTRU算法能否求图的最小生成树？不能。
打印最短路径，时间O（n2），空间O（n），可以用DIJISTRU算法得到集合的同时，记录每个节点前面那个元素，一个一个向前找。
二部图：一个图是否是二部图？时间是O（n）。用等价类：一个边的两点分属于不用等价类（估计不会考太深）。
伙伴系统，边界标识（要看）。无用单元收集不考。
顺序查找时间（最坏，平均）。有序表查找，二分查找，折半查找（判定树，树的高度，平均检索长度（在成功和不成功时的不同情况））。
静态树表不考，静态次优不考。
索引顺序表：概念。
动态查找：二叉排序树：中序遍历有序，先序无序。给出先（或后）序的次序，写出此树（因为中序是顺序的，已知）。他的插入和删除（删除不一定考）。给定树，求平均查找长度。
查找长度的量级。
平衡二叉树：一定是二叉排序树。树的所有子树都是平衡二叉树。反之不成立。若要执行4种旋转，至少7个节点。
M阶B树：关键字个数的上下限。N个关键字构成树的节点数目层数。
B＋树的概念。  键树。
哈希表：解决冲突的方法。只有链地址法可以解决二次聚集。不是同义词不会竞争同一位置。链地址法是顺序结构和链结构的完美结合。
查找长度：1。探测次数（包括最后一次比较为空的次数）。
       2．关键字比较次数（不包括最后一次为空的）。
37．内部排序：简单插入排序（稳定）；折半（不稳定）；希尔（不稳定）；冒泡（稳定）；快速（不稳定）；选择（不稳定）；堆（不稳定）；归并（稳定）。要记住她们的时间复杂度（最好，平均，最坏）。
  基数排序：给定N个数，范围在（0，n2-1），以O(n)时间排序。记ni=ai*n+bi，按(ai,bi)先以bi为基数排序，再以ai 排。
  基数排序利用关键字本身的值，而其他基于比较。
找最大和最小值的时间[3/2n]-2。见手写版。两两比较，小的方一个数组，大的放一个数组，再找。
找最大和次大值：可以调整堆，也可以记下比较
13

第一章
一、数据结构的四类基本类型：1、集合2、线性结构3、树形结构4、图形结构或网状结构
二、数据元素之间的物理结构有两种：顺序存储结构和链式储存结构
三、算法中基本操作重复的次数是问题规模N的某个函数F（N）算法的时间量度记作T（N）＝O（F（N））它表示随问题规模N的增大，算法执行的时间的增长率和F（N）的增长率相同，称作算法的渐近时间复杂度简称时间复杂度。
第二章　　线性表
一、线性表的建立：
1、建立一个线性链表：
2、插入一个结点：在头部：在中间：在尾部：
3、删除一个结点：头部　中间尾部

二、线性链表原代码如下：
　 include <stdio.h>
typedef　struct node {
　 int data;
　 struct node *next;
}NODE
1、建立一个线性链表：
create_list( )
{　NODE *head,*p;
　 int i,j,k;
　 scanf(“%d”,&i);　  //链表的结点个数
　 head=NULL; 
　 for(j=i;i!=0;i--){
　 scanf(“%d”,&k);
　 if(head==NULL)
　　{
　 head->data=k;
　 p=head;
}
p->next->data=k;
p=p->next;
}
p->next=NULL;
return(head);
　　　　 }
2、插入一个结点：
　 在头部插入一个结点p ： 
　　　　  insert(NODE*head){
　　　　　　 NODE *p ;
　　　　　　 scanf(“%d”,&p->data)；　　  //要插入的结点
　　　　　　 p->next=head;
　　　　　　 head=p;　　　　 
　　　　　　 }　　　 

　 在p与q之间插入结点k：
　　　　insert(NODE * head){
　　　　 NODE  *p,*q,*k;
　　　　 scanf(“%d”,&k->data)；　　　　　 //要插入的结点
　　　　 k->next=q;
　　　　 p->next=k;
　　　　 }

　 在尾部插入一个结点q ：
　　 insert(NODE *head){
　　　　 NODE *p,*q;
　　　　 scanf(“%d”,&q->data)；　　　　　 //要插入的结点
　　　　 for(p=head;p->next!=NULL;p=p->next);　  //到链表的最后一个结点
　　　　 p->next=q;
　　　　 q->next=NULL;
　　　　 }

3、删除一个结点：
在头部删除一个结点p:
　 delete(NODE*head){
　　　　NODE *p;
　　　　p=head;
　　　  head=head->next;
　　　　free(p);
　　　　 }

在p与q之间删除结点k：
　 delete(NODE*head){
　　　 NODE *p,*q,*k;
　　　 p->next=q;
　　　 free(k);
　　　 }

在尾部删除一个结点p:
　 delete(NODE*head){
　　　　 NODE *p,*q;
　　 for(q=p=head;p->next!=NULL;q=p,p=p->next);　  //到链表的最后一个结点
　　　　 q->next=NULL;
　　　　 free(p);
　　　　}

双向链表的操作与单向差不多。
第三章　栈和队列
一、栈是一种先进后出的线性表
　　　进栈相当于在线性链表的头部插一个结点，出栈相当于在线性链表的头部删除一个结点
二、队列是一种和栈相反的线性表，它是先进先出线性表
　　　进队相当于是在线性表的尾部加一结点，出队相当于在线性链表的头部删除一个结点
三、判断循环队列的空满可以用以下两种方法：一是另设一个标志位区别队列是空是满二是少用一个元素空间，约定头指针在队列尾指针的下一位置上作为队满

第四章　串
一、串的机内表示：定长顺序存储表示和堆分配存储表示，两者的思想和区别
二、定长顺序存储表示思想是类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。
三、堆分配存储表示思想是仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是程序执行过程中动态分配而得。
四、两者区别是：定长顺序存储是每个定义的串变量是分配一个固定的长度而堆分配存储是程序执行过程中动态分配而得。
　 串的模式匹配算法：P79
 第五章：数组和广义表
一、疏矩阵的存储方法
　　1、三元组顺序表：
　  压缩存储的概念就是只存储稀疏矩阵的非零元。所以一个三元组（i,j, aij）就可以唯一确定了矩阵的一个非零元。其中i 表示该非零元在稀疏矩阵中的第几行，j 表示非零元在稀疏矩阵中的第几列，aij表示非零元在稀疏矩阵中的值。

快速转置的好处缺点原因
 二、十字链表：在链表中，每个非零元可以用一个含有五个域的结点表示，其是I,j,e三个域分别表示该非零元所在行、列、和非元零的值，向 右域right用以链接同一行下个非零元，用down用以链接同列中下一个非零元，同一行非零元可以通过right域链成一个链表，同一列可以通过 down域链成一个链表，每个非零元既是某行链表中的结点，又是某个列链表的结点整个矩阵就成了一个十字交叉的链表故称十字链表，可以用两个分别存储行链 表的头指针的列链表的头指针的一维数组表示之：
矩阵： 0 0 1 0
1　3　1
2 0 0 4　　　　　　　　　　　　　　　　　　　　　　　 
　　 　　　0 3 5 0　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

3　3　5

3　2　3

2　1　2

2　4　4
 1、广义表的存储结构
 广义表LS=（a1,a2,a3…an）表头是第一个元素a1，其余元素组成的表（a2,a3,…an）是LS的表尾
 第六章　　　 树和二叉树
一、二叉的性质：1、在二叉树的第I层上至多有2I-1个结点（I＞＝1）
　　　　　  2、深度为K的二叉树至多有2K－1个结点
　　　  3、对任何一棵二叉树T，如果其终端结点数不N0，度为2的结点数为N 2则N0＝N2＋1
　　　　　  4、具有N个结点的完全二叉树的深度为LLOG2N」＋1
二、满二叉树的定义：一棵深度为k且有2k-1个结点的二叉树称为~
三、完全二叉树定义：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度k的满二叉树中编号从1到n的结点一一对应时称之为完全二叉树
四、二叉树的存储结构：一、顺序存储结构二、链式存储结构
五、遍历二叉树：
1、前序：是先访问根结点，先序遍历左子树，先序遍历右子树
2、中序：中序遍历左子树，访问根结点，中序遍历右子树
3、后序：后序遍历左子树，后序遍历右子树，访问根结点
例：见书p129页
六、建立一棵二叉树：p131
七、线索二叉树：穿线方法：先按先、中或后序把二叉树遍历，

八、树的存储结构：一、双亲表示法：就是用一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲的结点在数组中位置。特点：找双亲容易，找孩子难（见p135 图6.13）
　二、孩子兄弟表示法（又称二叉树和二叉链表表示法）链表结构中的两个链域分别指向该结点的的第一个孩子结点和下一个兄弟结点。操作容易，破坏了树的层次
（见p137 图6.15）
九、森林的遍历：
1、先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树
2、后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点