数据结构 复习重点.docx
《数据结构 复习重点.docx》由会员分享，可在线阅读，更多相关《数据结构 复习重点.docx（16页珍藏版）》请在冰点文库上搜索。
数据结构复习重点
数据结构复习重点
谁让我找到你们了.
第一章
1.数据是信息的载体,它能够被计算机识别、存储和加工处理。
2.数据元素是数据的基本单位。
有些情况下，数据元素也称为元素、结点、顶点、记录。
3.数据结构指的是数据之间的相互关系，即数据的组织形式。
一般包括三个方面的内容：
①数据元素之间的逻辑关系，也称为数据的逻辑结构；②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构；③数据的运算，即对数据施加的操作。
4.数据类型是一个值的集合以及在这些值上定义的一组操作的总称。
按"值"是否可分解，可将数据类型划分为两类：
①原子类型，其值不可分解；②结构类型，其值可分解为若干个成分。
5.抽象数据类型是指抽象数据的组织和与之相关的操作。
可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。
6.数据的逻辑结构简称为数据结构。
数据的逻辑结构可分为两大类：
①线性结构（~的逻辑特征是若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继）；②非线性结构（~的逻辑特征是一个结点可能有多个直接前趋和直接后继）。
7.数据存储结构可用四种基本的存储方法表示：
①顺序存储方法（该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
由此得到的存储表示称为顺序存储结构）；②链接存储方法（该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。
由此得到的存储表示称为链式存储结构）；③索引存储方法（该方法通常是在存储结点信息的同时，还建立附加的索引表）；④散列存储方法（该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址）。
8.非形式地说，算法是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值为输出。
因此，一个算法是一系列将输入转换为输出的计算步骤。
9.求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢?
选用的算法首先应该是"正确"的。
此外，主要考虑三点：
①执行算法所耗费的时间；②执行算法所耗费的存储空间，其中主要考虑辅助存储空间；③算法应易于理解，易于编码，易于调试等等。
10.性结构反映结点的逻辑关系是一对一的,非线性结构反映结点间的逻辑关系是多对多的。
11.数据的运算最常用的五种，分别是查找、插入、删除、更新、和排序。
12.一个算法的效率可分为时间效率和空间效率。
第二章线性表
1.线性表是由n（n≥0）个数据元素（结点）a1,a2,an组成的有限序列。
其中数据元素的个数n定义为表的长度。
当n=0是称为空表，常常将非空的线性表（n0）记作：
（a1,a2,an）。
2.按顺序存储方法存储的线性表称为顺序表，按链式存储的线性表称为链表。
3.顺序表上实现的基本运算有：
插入、删除。
在顺序表做插入运算，平均要移动表中的一半结点。
当表长n较大时，算法的效率相当低。
虽然EIS（n）中的n的系数较小，但就数量级而言，它仍然是线性阶的，因此算法的平均时间复杂度是0（n）；在顺序表做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是0（n）。
4.线性表中结点集合的元素是有限的，结点间的关系是一对一的。
5.链表的每个结点只有一个链域的链表称为单链表。
建立单链表有两种方法：
头插法建表、尾插法建表。
6.在链表的开始结点之前附加一个结点，称为头结点，会带来以下两个优点：
①由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上操作一致，无须进行特殊处理；②无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理和非空表的处理也就统一了。
7.查找运算分两种：
①按序号查找（链表不是随机存取结构）；②按值查找。
8.循环链表是一种首尾相接的链表。
其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
9.双链表若希望从表中快速确定一个结点的直接前趋，可以在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。
这们形成的链表中有两条方向不同的链，故称之为~。
和单链表类似，双链表一般也是由头指针head惟一确定的，增加头结点也能够使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。
10.顺序表和链表，它们各有所长。
在实际应用中究竟选用哪一种存储结构呢?
答：
这要根据具体问题的要求和性质来决定。
通常从以下几个方面来考虑：
①基于空间的考虑；②基于时间的考虑。
存储密度是指结点数据本身所占的存储量和整个结点结构所占的存储量之比；显然，顺序表的存储密度为1，而链表的存储密度小于1。
当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构；顺序表是由向量实现的，它是一种随机存取结构，对表中任一结点都可在0
（1）时间内直接地存取，而链表中的结点，需从头指针起顺着链扫描才能取得。
因此，若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；对于频繁进行插入和删除的线性表，宜采用链表做存储结构；若表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。
11.存储密度是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。
即：
存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）。
存储密度越大，存储空间的利用率就越高。
显然，顺序表的存储密度为1，而链表的存储密度小于1。
12.顺序表相对于链表的优点有节省存储空间和随机存取。
链表相对于顺序表的优点有插入和删除操作方便。
13.双链表中要删除已知结点*p，其时间复杂度为0
（1）。
14.在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需知道头指针。
第三章和队列
1.栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。
2.栈是限制仅在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端称为栈底。
当表中没有元素时称为空栈。
3.栈的基本运算有六种：
①InitStack（S）构造一个空栈S；②StaclEmpty（S）判栈空。
若S为空栈，则返回TRUE，否则返回FALSE；③StackFull（S）判栈满。
若S为满栈，则返回TRUE，否则返回FALSE。
该运算只适用于栈的顺序存储结构；④Push（S,x）进栈。
若栈S不满，则将元素X插入S的栈顶；⑤Pop（S）退栈。
若栈S非空，则将S的栈顶元素删去并返回该元素；⑥StackTop（S）取栈顶元素。
若栈S非空，则返回栈顶元素，但不改变栈的状态。
4.栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。
5.在顺序栈上实现的六种基本运算：
6.栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行。
7.队列也是一种运算受限的线性表。
队列也称作先进先出的线性表，简称为FIFO表。
它只允许在表的一端进行插入，而在另一端进行删除。
允许删除的一段称为队头，允许插入的一段称为队尾。
8.队列的基本运算有六种：
①InitQueue（Q）置空队。
构造一个空队列Q。
②QueueEmpty（Q）判队空。
若队列Q为空，则返回真值，否则返回假值。
③QueueFull（Q）判队满。
若队列Q为满，则返回真值，否则返回假值。
此操作只适用于队列的顺序存储结构。
④EnQueue（Q,X）若队列Q非满，则将元素X插入Q的队尾。
此操作简称入队。
⑤DeQueue（Q）若队列Q非空，则删去的队头元素，并返回该元素。
此操作简称出他。
⑥QueueFront（Q）若队列Q非空，则返回队头元素，但不改变队列Q的状态。
9.递归是指若在一个函数、过程或者数据结构定义的内部又直接（或间接）出现有定义本身的应用，则称它们是递归的，或者是递归定义的。
10递归算法的设计一般有两步：
①将规模较大的原问题分解一个或多个规模更小、但具有类似于原问题特性的子问题，即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题；②确定一个或多个无须分解、可直接求解的最小子问题。
上述第一步称为递归步骤，第二步中所述的最小子问题称为递归的终止条件。
第四章串
1.串是零个或多个字符组成的有限序列。
一般记为S="a1a2…an"
2.将仅由一个或多个空格组成的串称为空白串；不包括任何字符的串称为空串。
3.串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。
4.通常在程序中使用的串可分为两种：
串变量和串常量。
5.串的顺序存储结构称为顺序串。
子串定位运算又称串的模式匹配或串匹配。
在匹配中，一般将主串称为目标串，子串称为模式串。
第五章多维数组和广义表
1.一般都是采用顺序存储的方法来表示数组。
通常有两种顺序存储方法：
①行优先顺序；②列优先顺序。
按上述两种方式顺序存储的数组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。
2.特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。
有：
①对称矩阵；②三角矩阵；③对角矩阵。
3.稀疏矩阵设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数（即sm﹡n），则称A为稀疏矩阵。
4.若将表示稀疏矩阵的非零元素的三元组按行优先（或列优先）的顺序排列（跳过零元素），则得到一个其结点均是三无组的线性表。
将该线性表的顺序存储结构称为三元组表。
5.广义表（Lists又称列表）是线性表的推广。
6.一个表的"深度"是指表展开后所含括号的层数，例如，表L、A、B、C的深度为分别为1、2、3、4表D的深度为∞。
7.通常把与树对应的广义表称为纯表，它限制了表中万分的共享和递归；把允许结点共享的表称为再入表；而把允许递归的表称为递归表。
8.广义表的两个特殊的基本运算：
取表头head（LS）和取表尾tail（LS）。
9.值得注意的是广义表（）和（（））不同。
前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为1的非空表（只不过该表中惟一的一个元素是空表），对其可进行分解，得到的表头和表尾均是空表（）。
第六章树
1.树（Tree）是n（n≥0）个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：
①有且仅有一个特定的称为根（Root）的结点；②其余的结点可分为m（m≥0）互不相交的子集T1、T2、Tm，其中每个子集本身又是一棵树，并称其为根的子树（Subtree）。
2.一个结点拥有的子树数称为该结点的度。
一棵树的度是指该树中结点的最大度数。
度为零的结点称为叶子或终端结点。
度不为零的结点称为分支结点或非终端结点，除根结点之外的分支结点统称为内部结点，根结点又称为开始结点。
树中某个结点的子树之根称为该结点的孩子或儿子，相应地，该结点称为孩子的双亲或父亲。
3.森林是m（m≥0）棵互不相交的树的集合。
树和森林的概念很相近，删去一棵树的根，就得到一个森林。
反之，加上一个结点作树根，森林就变为一棵树。
4.二叉树是n（n≥0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
5.二叉树具有以下几个重要性质：
①二叉树第I层上的结点数目最多为2i-1（i≥1）；证明：
可用数学归纳法证明（归纳基础：
i=1时，有2i-1=20=1。
因为第一层上只有一个根结点，所以命题成立。
归纳假设：
假设对所有的j（1≤ji）命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。
归纳步骤：
根据归纳假设，第i-1层上至多有2i-2个结点。
由于二叉树的每个结点至多有两个孩子，故第I层上结点数，至多是第i-1层上的最大结点数的2倍，即j=i时,该层上至多有2*2i-1=2j-1个结点，故命题成立。
）②深度为k的二叉树至多有2k-1个对点（k≥1）；证明：
（在肯有相同深度的二叉树中，仅当每一层都含有最大结点数时其树中结点数最多。
因此利用性质1可得，深度为k的二叉树的结点数至多为20+21+2k-1=2k-1故命题正确。
）③在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1；证明：
（因为二叉树中所有结点的度数均不大于2，所以结点总数（记为n）应等于0度结点数，1度结点（记为n1）和2度结点数之和：
n=n0+n1+n2,另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点的总数是n1+2n2，但树中只有根结点不是任何结点的孩子，故二叉树中的结点叫数又可表示为：
n=n1+2n2+1）④具有n个结点的完全二叉树的深度为[lgn]+1（或[lg（n+1）]）。
证明：
（设所求完全二叉树的深度为k，由完全二叉树的定义知道，它的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。
由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数n2k-1-1。
另一方面，由性质2知道n≤2k-1，即：
2k-1-1n≤2k-1由此可推出：
2k-1≤n2k，取对数后有：
k-1≤lgnk），因为k-1和k是相邻的两个整数，故有k-1=[lgn]，由此即得：
k=[lgn]+16.树、森林到二叉树的转换：
①在所有兄弟结点之间加一连线；②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。
7.森林的两种遍历方法：
⑴前序遍历森林，若森林非空，则：
①访问森林中第一棵树的根结点；②前序遍历第一棵树中根结点的各子树所构成的森林；③前序遍历除第一棵树外其它树构成的森林。
⑵后序遍历森林，若森林非空，则：
①后序遍历森林中第一棵树的根结点的各子树所构成的森林；②访问第一棵树的根结点；③后序遍历除第一棵树外其它树构成的森林。
8.树的路径长度是从树根到树中每一结点的路径长度之和。
第七章图
1.对图进得深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列，或DFS序列。
2.深度优先搜索的特点是尽可能先对纵深方向进行搜索。
3.广度优先搜索的特点是尽可能先对横向进行搜索。
4.广度优先遍历图所得的顶点序列，定义为图的广度优先遍历序列，或BFS序列。
5.由深度优先搜索得到的生成树称为深度优先生成树，或DFS生成树。
6.对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得对图中任意一对顶点u和v，若u，v∈E（G），则u在线性序列中出现在v之前。
通常将这样的线性序列称为满足拓扑次序的序列，简称拓扑序列。
第八章排序
1.排序就是要整理文件中的记录，使之按关键字递增（或递减）次序排列起来。
2.排序方法可以按照不同的原则加以分类：
在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。
3.内部排序方法可以分为五类：
插入排序、选择排序、交换排序、归并排序和分配排序。
4.插入排序的基本思想是：
每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。
5.快速排序采用了一种分冶的策略，通常称其为分冶法。
分冶法的基本思想是：
将原问题分解为若干个规模更小但结构与原问题相似的子问题；递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
6.对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是O（n2）；对于n个记录的集合进行归并排序，所需要的附加空间是O（n）。
7.堆排序是一树形选择排序，它的特点是，在排序过程中，将R看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大的记录。
8.在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选取归并排序方法；若只从平均情况下最快考虑，则应选取快速排序方法；若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。
9.大多数排序算法都有两个基本的操作：
比较两个关键字的大小和改变向记录的指针或移动记录本身。
第九章查找
1.查找的定义是：
给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。
2.若在查找的同时对表做修改操作，则相应的表称之为动态查找表，否则称之为静态查找表。
3.和排序类似，查找也有内查找和外查找之分。
若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。
4.二分查找又称折半查找。
5.二叉排序树又称二叉查找（搜索）树，其定义为：
二叉排序树或者是空树，或者是满足如下性质的二叉树。
①若经的左子树非空，则左子树上所有结点的值均小于根结点的值；②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；③左、右子树本身又各是一棵二叉排序树。
6.平衡二叉树是指树中任一结点的左右子树的高度大致相同。
若任一结点的左右子树的高度均相同，则二叉树是完全平衡的。
平衡的二叉排序树是指满足BST性质的平衡二叉树。
第十章文件
1.文件是性质相同的记录的集合。
2.数据项有时也称为字段，或者称为属性。
其值能惟一标识一个记录的数据项或数据项的组合称为主关键安项，其它不能惟一标识一个记录的数据项则称为次关键字项，主关键字项的值称为主关键字。
3.文件上的操作主要有两类：
检索和维护。
4.检索就是在文件中查找满足给定条件的记录，它既可以按记录的逻辑号查找，也可以按关键字查找。
5.文件的基本组织方式有四种：
顺序组织、索引组织、散列组织和链组织。
文件组织的各种方式往往是这四种基本方式的结合。
6.磁道是盘片上同心圆，同一盘组上半径相同的磁道合在一起称为一个柱面。
7.顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。
若顺序文件中的记录按其主关键字有序，则称此顺序文件为顺序有序文件；否则称为顺序无序文件。
8.索引表是用索引的方法组织文件时，通常是在文件本身之外，另外建立一张表，它指明逻辑记录和物理记录之间的一一对应关系，这张表就叫做索引表，它和主文件一起构成的文件称作索引文件。
9.索引表中的每一项称作索引项。
10.对于索引非顺序文凭，由于主文件中记录是无序的，则为每个记录建立一个索引项，这样建立的索引表称为稠密索引。
11.散列文件是利用散列存储方式组织的文件，称为直接存取文件。
12.对于文件来说，磁盘上的文件记录通常是成组存放的，若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶。
13.多重表文件是将索引方法和链接方法相结合的一种组织方式，它对每个需要查询的次着急字建立一个索引，同时将具有相同次关键字的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字，儿为索引表的一个索引项。
例题：
完成下列中序遍历二叉树的算法，注意在遍历中只有一个栈，而不用任何其他变量。
#definemax100typedefstructtnode{
structtnode*lchild,*rchild：
}tnode；
typedefstructstack{
tnode*elem[max]；
inttop；
}stack；
voidindrder（tnode*bt）
{stacks；
s.top=0；s.elem[s.top++]=btdo
{while（s.elem[s.top--1]！
=null）
s.elem[s.top++]=s.elem[s.top-1]！
lchildif（s.top1）
{s.top-
printf[s.top-1]-data）；
s.elem[s.top-1]=elem[s.top-1]-vchild
}
}while（！
（s.top==1&&s.elem[s.top-1]==null））
s.top=0}
2.下列算法的功能是求出指定结点在给定的二叉排序树中所在的层次。
Voidlevel（BSTreeroot.p）；
{
intlevel=0；
if（！
Root）；
return（0）；
else{
level++；
while（root-key！
=p-key）{；
if（root-keyp-key）；
root=root-lchid：
elseroot=root-rchild；
level++；
}
return（level）；
}
}
3.t利用一维数组inta[n]可以对n个整数进行排列，其中一种排列算法的处理思想是将n个整数分别作为数组a的个元素的值，每次（即第I次）从元素a~a[n-1]中找出最小的一个元素a[k]（Ikn）,然后将a与[k]换位。
这样反n次完成排序。
请编写实现上述算法的过程，并分析完成排序所需要的次数。
解：
voidsort（inta[n]）
{
intI,j,t,min,minpos；
for（I=o；In；I++）{
min=a：
minpos=1；
for（j=I+1；In；j++）
if（a[j]min）}
min=a；
minpos=j；
}
if（minpos！
=I）}
t=a；
t=a；
a=a[minpos]
a=a[minpos]；
a[minpos]=t：
}}}
4.设给定的散列存储空间为：
H[0.m],每个H单元可存放一记录，选取的散列函数为H[r_KEY]，其中R_KEY为记录关键字，解决冲突的方法为线性探测法，试编写将某记录R入表H中的算法。
解：
voidbuildhash（keytypeR.key,intI,intj,intn）
{
for（I=0；In；I++）{
j=H（R.key）；
if（H[J]=r_key；
else{
do{
j=（j+1）%（m+1）
}while（H[j]）；
H[j]=r_key；
}}}
5试写出二分查找的递归算法。
解：
intbinsrch（intlow,inthig,keytypek）
{intmid；
if（lowhig）
return（0）；
else
{（mid=（low+hig）/2；
if（k==r[mid].key）
return（mid）
if（kr[mid].keyrerurn（binsrch（mid+1.hig.k））；
if（kr[mid].key）
return（binsrch（low.mid-1,k））；
}}
6.写一个遍历B-树的算法，使输出的关键字序列递增有序。
算法中的读盘操作可假写为DiskRead.
解：
voidinorder（Btreet）
{intI：
if（t）：
{for（I=1；It-keynum；I++）
{diskread（T-son）
printf（"%c",t-key；
diskread（T-son；
inorder（T-son；
}}
1.在双链表中要删除已知结点*p，其时间复杂度为O（1。
）
2.若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是82。
3.在按关键字递增的数组A[20]中，按二分查找方法时行查找时，查找度为5的元素个数为5。
4.在左右子树均不空的先序线索二叉树中，空链域的数目是1。
5.已知数组A[8][8]为对称矩阵，其中每个元素占5个单元。
现将其下三角部分按行优先次序存储在起始地址为100的连续的内存单元中，则元素A[4，5]对应的地址为
升级会员 