1、数据结构三要素

逻辑结构：逻辑结构是指数据元素之间的逻辑关系，它与存储无关，是独立于计算机的，数据的逻辑结构分为线性结构和非线性结构。线性表是典型线性结构。

非线性结构包括集合，树，图。

（1）集合结构：数据结构中的数据元素除了同属于一个集合的关系外，无任何其他的关系

（2）线性结构：数据结构中的数据元素存在着一对一的线性关系

（3）树形结构：数据结构中的数据元素之间存在一对多的层次关系

（4）图形结构或网状结构：数据结构中的数据元素之间存在多对多的任意关系

2、数据的存储结构：

（1）顺序存储结构：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

优点：可以实现随机存储，每个元素占用最少的存储空间。

缺点：只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片；插入删除操作不方便。

（2）链式存储结构：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。

优点：不会出现碎片的现象，能充方利用所有存储单元。

缺点：每个元素因存储指针而占用额外的存储空间，且只能实现顺序存储。

（3）索引存储结构：在存储元素信息的同时，还建立附加的索引表，索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。

优点：检索速度快。

缺点：附加的索引表额外占用存储空间。另外，增加和删除数据也要修改修改索引表，因而会花费较多的时间。

（4）散列存储结构：根据元素的关键字直接计算出该元素的存储地址，又称为哈希（Hash）存储。

优点：检索、增加和删除结点的操作都很快。

缺点：若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

3、比较顺序存储和链式存储的优缺点

（1）顺序存储时，相邻数据元素的存放地址也相邻(逻辑与物理统一)，要求内存中可用存储单元的地址必须是连续的。

优点：① 存储密度大(＝1)，存储空间利用率高；

② 可随机存取表中的任一元素，查找元素方便。

缺点：① 插入或删除元素时不方便，须移动大量元素，效率较低；

② 存在预分配空间问题。

（2）链式存储时，相邻数据元素可随意存放，但所占存储空间分为两个部分，一部分存放结点值，另一部分存放表示结点间关系的指针。

优点：① 插入或删除元素时很方便，使用灵活；

② 支持动态分配空间。

缺点：① 存储密度小(<1)，存储空间利用率低；

② 查找元素不方便。

4、顺序存储结构和链式存储结构的特点

顺序存储结构：

（1）存储单元中只存放数据元素本身的信息，无附加内容

（2）只要知道第一个数据元素的地址，就可以通过计算直接确定结构中第i个元素的地址，从而直接存取第i个数据元素

（3）由于可根据公式直接确定第i个节点的地址而直接存取第i个元素，所以数据元素存取操作速度较快

（4）插入删除数据元素时，由于需要保持数据元素之间的逻辑关系，必须移动大量元素，因此实现起来较慢

（5）顺序存储结构有两种方式分配空间，一种是静态结构，另一种是动态结构，当用静态结构时，存储空间一旦分配完成，其大小就难以改变。因此，当表中元素个数难以估计时，分配的空间大小也就难以确定。预分配的空间太大会造成浪费，空间太小，有可能出现存放不下的溢出现象。

链式存储结构：

（1）结点中除存放数据元素本身的信息外，还需存放附加的指针

（2）不能直接确定第i个结点的储存位置。要存放第i个结点的信息，必须从第1个节点开始查找，沿指针顺序取出第i-1个结点的指针域，再取出第i个结点的信息，存取速度较慢

（3）链式存储结构的一个优点是插入、删除元素时不必移动其他元素，速度较快。因此当数据元素个数变动较大，插入删除操作频繁时可用链式存储结构来实现

（4）链式存储是一种动态存储结构，当元素数量增加时可随时申请所需的空间，删除时无用的空间可归还给系统，故空间利用率较高，也不存在预分配空间的问题

5、怎样选择顺序存储结构和链式存储结构？

考虑依据有两个：一个是考虑数据结构上要执行的主要操作速度，另一个是对数据元素数目的估计。若执行的主要操作是插入或删除，则最好用链式存储结构，否则应用顺序存储结构；若预先可以估计出元素的个数，则可以用顺序存储结构，否则宜用链式存储结构

6、数据的运算：

施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能。运算的实现是针对物理结构的，指出运算的具体操作步骤。

7、算法的五大特征：

（1）有穷性：一个算法必须总在执行又穷步骤后结束，且每一步都在有穷时间内完成

（2）确定性：每条指令都必须有明确的含义，对于相同的输入必须有相同的输出，不可二义性

（3）可行性：算法描述的操作都可以通过已经实现的基本运算执行有穷次实现

（4）输入：零个或多个数据输入

（5）输出：至少有一个或多个数据输出

8、好的算法包括：

正确性：算法应该正确的解决问题

可读性：算法应该方便人们阅读

健壮性：当输入数据不合法时，算法也能做出相应的反应，而不会产生莫名其妙的结果。

高效率与低存储需求：效率是指算法的执行时间，存储量需求是指算法执行过程中所需要最大存储空间，这两者都与问题规模有关

9、复杂度

时间复杂度：算法的执行时间与原操作的执行次数之和成正比

空间复杂度：如果输入数据所占空间只取决于问题本身，而与算法无关，只需要分析除了输入和程序之外的辅助变量所占用的空间即可。

10、数据结构与物理结构关系:

答：数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。

11、用循环比递归的效率高吗？

循环和递归两者是可以互换的，不能决定性的说循环的效率比递归高。

递归的优点：代码简洁清晰，容易检查正确性；缺点是：当递归调用的次数较多时，要增加额外的堆栈处理，有可能产生堆栈溢出的情况，对执行效率有一定的影响。

循环的优点：结构简单，速度快；缺点是：它并不能解决全部问题，有的问题适合于用递归来解决不适合用循环。

12、贪心算法、动态规划以及分治法的区别？

（1）贪心算法顾名思义就是做出在当前看来是最好的结果，它不从整体上加以考虑，也就是局部最优解。贪心算法从上往下，从顶部一步一步最优，得到最后的结果，它不能保证全局最优解，与贪心策略的选择有关。

（2）动态规划是把问题分解成子问题，这些子问题可能有重复，可以记录下前面子问题的结果防止重复计算。动态规划解决子问题，前一个子问题的解对后一个子问题产生一定的影响。在求解子问题的过程中保留哪些有可能得到最优的局部解，丢弃其他局部解，直到解决最后一个问题时也就是初始问题的解。动态规划是从下到上，一步一步找到全局最优解。（各子问题重叠）

（3）分治法（divide-and-conquer）：将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解，例如归并排序。

（各子问题独立）分治模式在每一层递归上都有三个步骤：

①分解（Divide）：将原问题分解成一系列子问题；

②解决（conquer）：递归地解各个子问题。若子问题足够小，则直接求解；

③合并（Combine）：将子问题的结果合并成原问题的解。

13、顺序表和链表的比较

（1）存取（读写）方法

顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。例如在第i个位置上执行存或取的操作，顺序表仅需一次访问，而链表则需从表头开始依次访问i次

（2）逻辑结构与物理结构

采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置则不一定相邻，对应的逻辑关系是通过指针链接来表示的。

14、查找、插入和删除操作

对于按值查找，顺序表无序时，两者的时间复杂度均为O(n); 顺序表有序时，可采用折半查找，此时的时间复杂度为O(log2n) 。

对于按序号查找，顺序表支持随机访问，时间复杂度仅为0(1), 而链表的平均时间复杂度为O(n) 。顺序表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作，只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大。

15、空间分配

顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。

16、数组和链表的区别

（1）数组

优点：① 随机访问性强

② 查找速度快

缺点：① 插入和删除效率低

② 可能浪费内存

③ 大小固定，不能动态拓展

（2）链表

优点：① 插入和删除效率高

② 内存利用率高，不会浪费内存

③ 大小没有固定，拓展很灵活

缺点：不能随机查找，必须从第一个开始遍历，查找效率低

17、单链表与双链表的区别？

单链表：只能向后访问，不能逆向访问

双链表：在单链表的基础上添加一个指向前驱节点的指针域，实现双向遍历

18、单链表 双链表 循环链表的区别？

（1）单向链表（单链表）

单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向表中的下一个节点，而最后一个节点则 指向一个空值NULL。

单向链表只可向一个方向遍历。

查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。也可以提前把一个节点的位置另外保存起来，然后直接访问。

（2）双向链表（双链表）

双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。第一个节点的"前连接"指向NULL，最后一个节点的"后连接"指向NULL，当这两个指针域互相指向对方节点时，就形成了双向循环链表。

这样可以从任何一个节点访问前一个节点，也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。

（3）循环链表

循环链表是单链表的另一种形式，他是首尾相接的链表。它的特点是表中最后一个结点的指针域指向头节点或线性表中的第一个节点，从而使整个链表形成一个环就得到了单链形式的循环链表。

在循环链表中，从表中任意的结点出发都能找到表中的其他结点。在循环链表中设置尾指针而不设立头指针会使某些操作简化。

19、判断一个链表是否有环，如何找到这个环？环的长度？连接点？链表长度？

题问：给定一个单链表，只给出头指针h：

1）如果判断是否存在环？

对于判断一个单链表是否存在环，可以利用追赶的方式，设立两个指针slow、fast，从头指针开始，每次分别前进一步和两步，如果存在环，则两者相遇；如果没有环，fast遇到NULL退出。

2）如何知道环的长度？

在slow和fast相遇的地方标记，再次相遇所走过的操作数就是环的长度。

3）如何找出环的连接点在哪里？

分别从相遇点和头指针开始走，再次相遇的那个点就是连接点。

4）带环链表的长度是多少？

连接点距离头指针的长度，加上环的长度，即为链表长度。

20、链表头节点的作用？

（1）由于第一个数据节点的位置被存放在头节点的指针域中，因此链表的第一个位置上的操作和在表的其他位置的操作一致，无需进行特殊处理（保证每一个结点都有前驱结点，使得插入和删除结点的处理统一）

（2）无论链表是否为空，其头指针都指向头节点的非空指针，因此空表与非空表的处理也得到了统一（带头结点的链表，在表空时存在头结点，使得空表和非空表的处理统一）

21、头节点，头指针和首元节点的区别

（1）头指针是指向链表第一个结点的指针，是链表存在的标志

（2）首元结点是链表中存储线性表的第一个结点

（3）头结点是首元结点的前一个结点，是为了使得对链表的处理统一而设置的结点

22、头指针和头结点的区别？

头指针：

• • 是链表指向第一个结点的指针，若链表有头节点，则是指向头节点的指针
  • 是必需的
  • 具有标识作用

头节点：

• 头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前
• 不是必需的，为了方便操作
• 对于插入和删除第一个结点，和其他结点操作统一

23、栈与队列的区别

栈是一种限定性线性表，只能在表的一端进行插入和删除操作的线性表。对于插入到栈的元素按“后进先出”的规则处理，插入和删除操作都在栈顶进行，一般用定长数组存储栈元素。

队列是一种操作受限的线性表，允许在一段进行插入另一端进行删除的线性表。队列顾名思义就像排队一样，对于进入队列的元素按“先进先出”的规则处理。

（1）相同点：

• 栈和队列都是线性结构，是两种特殊的线性表即受限的线性表，都对插入和删除操作加以限制；
• 栈和队列在插入时都是在表尾进行
• 都是逻辑结构的概念,，栈和队列都可以用顺序存储结构和链式存储结构
• 栈和队列插入和删除操作的时间复杂度和空间复杂度是一样的

（2）不同点：

• 栈只允许在一端进行插入和删除，因而是后进先出表；队列只允许在一端进行插入，另一端进行删除，因而是先进先出表。
• 用链表存储时可以实现多栈空间共享，队列不行

24、栈和队列的应用？

栈可用于函数调用和递归，括号匹配，后缀表达式求值；

队列常用于计算机各种资源的管理，消息缓冲器的管理和广度有限搜索算法等

25、栈在括号匹配的算法思想

遍历表达式，缝左括号就入栈，遇到右括号则检查栈是否为空，为空则表明不匹配，不为空则将左括号出栈；表达式遍历完成后栈为空则表明匹配，若栈中还有左括号表明不匹配

26、栈在后缀表达式求值的思想

（1）是操作数则进栈

（2）是运算符则将两个元素出栈并将得到的结果进栈

（3）表达式扫描完成后，栈顶元素为所求结果

27、栈在递归中的应用？

递归是一种重要的程序设计方法。简单地说，若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。

它通常把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算，大大减少了程序的代码量。但在通常情况下，它的效率并不是太高。

将递归算法转换为非递归算法，通常需要借助栈来实现这种转换。

28、队列在层次遍历中的作用？

在信息处理中有一大类问题需要逐层或逐行处理。这类问题的解决方法往往是在处理当前层或当前行时就对下一层或下一行做预处理，把处理顺序安排好，待当前层或当前行处理完毕，就可以处理下一层或下一行。使用队列是为了保存下一步的处理顺序。下面用二叉树层次遍历的例子，说明队列的应用。

29、队列在计算机系统中的应用？

队列在计算机系统中的应用非常广泛，以下仅从两个方面来简述队列在计算机系统中的作用：

第一个方面是解决主机与外部设备之间速度不匹配的问题，第二个方面是解决由多用户引起的资源竞争问题。

（1）对于第一个方面，仅以主机和打印机之间速度不匹配的问题为例做简要说明。主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，由于速度不匹配，若直接把输出的数据送给打印机打印显然是不行的。解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。这样做既保证了打印数据的正确，又使主机提高了效率。由此可见，打印数据缓冲区中所存储的数据就是一个队列。

（2）对于第二个方面， CPU (即中央处理器，它包括运算器和控制器）资源的竞争就是一个典型的例子。在一个带有多终端的计算机系统上，有多个用户需要CPU 各自运行自己的程序，它们分别通过各自的终端向操作系统提出占用CPU 的请求。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU 分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把CPU 分配给新的队首请求的用户使用。这样既能满足每个用户的请求，又使CPU 能够正常运行。

30、队列的溢出现象？如何解决

下溢现象：队列为空时出队产生的现象；是正常现象；

真上溢现象：队列满时继续往进队；建立一个足够大的存储空间来解决；

假上溢现象：队列未满而无法继续进队；采用循环队列来解决；

31、两个栈实现一个队列：

先将数据存在到第一个栈里，在将第一个栈里的元素全部出栈到第二个栈，第二个栈出栈，即可达到先进先出。

32、两个队列实现一个栈：

先将数据存到第一个队列里面，然后数据出队一直出队到第二个队列里面，直到第一个队列里面剩余一个数据，这个时候出队，即可达到先进后出的特性。

33、共享栈

共享栈：利用栈底位置相对不变、栈顶位置动态变化的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。这样能够更有效的利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。

34、双端队列

双端队列：限定插入、删除在表的两端进行的队列。

输出受限的双端队列：允许一端进行插入和删除，但在另一端只允许插入的双端队列。

输出受限的双端队列：允许一端进行插入和删除，但在另一端只允许删除的双端队列。

若限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈。

35、如何区分循环队列是队空还是队满？

普通情况下，循环队列队空和队满的判定条件是一样的，都是Q.front == Q.rear。

队头指针指向第一个数；队尾指针指向最后一个数的下一个位置，即将要入队的位置。

方法一：牺牲一个单元来区分队空和队满，这个时候(Q.rear+1)%MaxSize == Q.front才是队满标志 。

方法二：类型中增设一个标志量，以此区别队列是空还是满，表示元素个数的数据成员。这样，队空的条件为Q.size == 0;队满的条件为Q.size == MaxSize。

第四章 串

36、串的基本概念

串是字符组成的线性有限集合，记作a=“a1,a2,…ai,…an”（n>=0）

子串：串中任意多个连续的字符组成的子序列称为该串的子串

主串：包含子串的串称为主串

子串在主串中的位置：某个字符在串中的序号称为该字符在串中的位置；子串在主串中的位置以子串的第一个字符在主串中的位置来表示。

当两个串的长度相等且每个对应位置的字符都相等，称这两个串是相等的

由一个或多个空格（空格是特殊字符）组成的串称为空格串，其长度为串中空格字符的个数。

37、串的存储结构

（1）顺序存储结构：串的字符依次存放在一组连续的储存空间中，静态结构类型

（2）堆存储结构：以一组地址连续的存储单元存放串的字符序列，但存储空间在程序执行的过程中动态分配

（3）块链存储结构：链式存储，链表中每个结点即可以存放一个字符，也可以存放多个字符，因此有时也称每个结点为块，链表中结点大小为数据域中存放字符的个数

38、模式匹配（其中n和m分别为主串和模式串的长度）

简单模式匹配算法：最坏的时间复杂度为O（mn）

KMP算法：时间复杂度是O（m＋n）

第五章 数组

39、矩阵的压缩存储

数据结构中，提供针对某些特殊矩阵的压缩存储结构。这里所说的特殊矩阵，主要分为以下两类：

含有大量相同数据元素的矩阵，比如对称矩阵；

含有大量 0 元素的矩阵，比如稀疏矩阵、上（下）三角矩阵；

针对以上两类矩阵，数据结构的压缩存储思想是：矩阵中的相同数据元素（包括元素 0）只存储一个。

第六章 树与二叉树

40、二叉树与度为2树的区别？

度为2的树至少有三个节点，而二叉树可以为空。

度为2的有序树的孩子的左右次序是相对与另一孩子而言的，若某个节点只有一个孩子，则这个孩子就无需区分左右次序，而二叉树无论其孩子数是否为2，均需要确定孩子的左右次序，即二叉树的节点次序不是相对另一节点而言的，是固定的。

41、什么是树？

树是一种非线性的数据结构，其元素之间有明显的层次关系，由结点和边组成且不存在环；在树的结构中，每个结点都只有一个前件称为父结点，没有前件的结点为树的根结点，简称为树的根；每个结点可以有多个后件成为结点的子结点，没有后件的结点称为叶子结点。

42、什么是二叉树？

二叉树：是n (n >=0) 个结点的有限集合，其特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。与树相似，二叉树也以递归的形式定义。

1)或者为空二叉树，即n=0 。

2)或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。

43、遍历二叉树和二叉线索树

遍历二叉树：以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的某种遍历的线性序列，如先序序列、中序序列、后序序列。

二叉线索树：是比根节点大的放在右子数，比根节点小的放在左子树，对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

44、什么是满二叉树？

一颗高度为h，且含有2^h-1个节点的二叉树称为满二叉树。即树中的每一层都有最多的节点。满二叉树的叶子节点都集中在最后一层，并且除了叶子节点以外每个节点度数都为2.

可以对满二叉树进行编号：约定编号从根节点起，自上而下，自左到右，这样每个节点对应一个编号，对于编号为i的节点，如果有双亲，则双亲为[i/2].如果有左孩子，左孩子为2i,如果有有孩子，右孩子为2i+1.

45、完全二叉树：

高度为h，n个节点的二叉树，当且仅当每个节点都与高度为h的满二叉树中编号1-n的节点一一对应时，叫做完全二叉树。即完全二叉树是指除了最后一层外，其他任何一层的节点数均达到最大值，且最后一层也只是在最右侧缺少节点。

46、二叉排序树：

左子树上所有节点的关键之均小于根节点的关键字，右子树上的所有节点的关键字均大于根节点的关键字，左子树和右子树又各是一颗二叉排序树

47、平衡二叉树：

树上任意节点的左子树和右子树的深度之差不超过1

48、二叉树的存储：

二叉树可以用链式存储结构来存储，满二叉树和完全二叉树可以用顺序存储结构来存储。

二叉树的顺序存储是指用一组地址连续的存储单元自上而下，自左到右存储完全二叉树上的节点，即将完全二叉树上的编号为i的节点元素存储在数组下标为i-1的分量中。

依据二叉树的性质，完全二叉树满二叉树比较适合顺序存储，树中节点的序号可以唯一地反映节点之间的逻辑关系，这样既可以最大节省存储空间，又能利用数组元素的下标值确定节点在二叉树中的位置，以及节点之间的关系。

对于一般的二叉树来言，若想让数组下标反应树中结点之间的逻辑关系，需要添加并不存在的空结点。这样造成了存储空间的浪费。空间利用率低，因此一般二叉树都采用链式存储结构。用链表节点来存储二叉树中的每个结点。二叉树中，结点通常包括数据域，左指针域，右指针域。

49、二叉树的遍历：

二叉树有先序遍历（根左右），中序遍历（左根右）和后续遍历（左右根）；还有层次遍历，需要借助一个队列。

三种遍历算法中，递归遍历左右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是O(n) 。在递归遍历中，递归工作栈的栈深为树的深度，所以在最坏情况下，二叉树是有n 个结点且深度为n 的单支树，遍历算法的空间复杂度为O(n) 。

50、树的存储方式

（1）双亲表示法：

这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。

该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快得到每个结点的双亲结点，但求结点的孩子时需要遍历整个结构。

（假设以一组连续向量空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在向量中的位置

利用了每个结点有唯一的双亲的性质，根结点无双亲可以用空（0）表示。以双亲表示法为存储结构时，Parent（T,X）操作方便实现。从某点开始找结点的双亲，反复判断双亲结点，双亲的双亲，直到双亲为空，就可以找到树的根，这就是ROOT（x）操作。在这种表示法中，求结点的孩子结点时需要遍历整个向量）

（2）孩子表示法：

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n 个结点就有n 个孩子链表（叶子结点的孩子链表为空表），这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

（①由于树中的每个结点可能有多棵子树，可用多重链表，即每个结点有多个指针域，其每个指针指向一棵子树的根结点。在一棵有n个结点，度为k的树中必有n（k-1）+1个空链域，空间浪费较大，如果在结点中增加一个域表示结点的度，就可以减少空间浪费，但实现时操作不方便。

②把每个结点的孩子结点排列起来，使之成为一个线性表，以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空表）。而n个头指针又组成一个线性表。

孩子表示法便于查找孩子操作的实现。）

（3）孩子兄弟表示法：

孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）

这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便。

（以二叉链表作为树的存储结构，链表中结点的两个链域分别指向该点的第一个孩子结点和下一个兄弟结点

与二叉树的链式表示相同，孩子兄弟表示法也缺乏结点的前驱，所以查找双亲较麻烦。）

51、什么是哈夫曼树？

从树的根到任意结点的路径长度与该结点上权值的乘积，称为该结点的带权路径长度。

树中所有叶子的带权路径长度之和为该树的带权路径长度。

在含有n个带权叶节点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也称最优二叉树。

52、如何构造哈夫曼树？

从集合中选取根结点权值最小的两棵树（集合中的树一开始都是结点）组成一颗新树，新树的权值为左右子树权值之和，删除集合选取的两个结点，增加新树的结点，重复上述操作；

（1）权值越大的结点距离根节点越近

（2）树中没有度为1的结点

固定长度编码、可变长度编码、前缀编码

在数据通信中,若对每个字符用相等长度的二进制位表示，称这种编码方式为固定长度编码。

若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。

可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。（哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码）

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。

53、哈夫曼编码

利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根结点到每个叶子结点都有一条路径，对路径上的各分支规定，指向左子树的分支表示“0”，指向右子树的分支表示“1”，取每条路径上“0”和“1”的序列作为各个叶子结点对应的字符编码，即哈夫曼编码。

对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。

54、图的存储结构

（1）邻接矩阵法：

邻接矩阵是表示顶点之间相邻关系的矩阵，用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系。适合稠密图。

在无向图中，若两顶点之间是连通的，则用1表示，否则用0表示。

在有向图中，若A能够到B，则A到B表示1，没有方向连接的用∞表示。

（2）邻接表法：

当一个图为稀疏图时，使用邻接矩阵法显然要浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。

邻接表是指对图G 中的每个顶点Vi建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图则是以顶点vi为尾的弧），这个单链表就称为顶点vi的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点。

逆邻接表：对每个顶点Vi建立一个以顶点Vi为弧头的边链表

（3）十字链表法：

十字链表法是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。

（4）邻接多重表：

邻接多重表是无向图的另一种链式存储结构。

在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低。

55、邻接矩阵与邻接表的区别？

邻接表：（链式存储结构）由单链表的表头形成的顶点表，和单链表其余节点形成的边表两部分组成；一般顶点表存放顶点信息和指向第一个边节点的指针。适合用于稀疏图。

邻接矩阵：（顺序存储结构）用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。适合用于稠密图。

56、图的遍历

图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可视为一种特殊的图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

图的遍历比树的遍历要复杂得多，因为图的任一顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组visited[ ]来标记顶点是否被访问过。图的遍历算法主要有两种：广度优先搜索和深度优先搜索。

（1）广度优先搜索(Breadth-First-Search, BFS)：

（2）深度优先搜索（Depth-First-Search, DFS):

57、最小生成树性质:

①最小生成树不是唯一的，即最小生成树的树形不唯一，R中可能有多个最小生成树。当图

G中的各边权值互不相等时，G的最小生成树是唯一的;若无向连通图G的边数比顶点数少1，即G本身是一棵树时，则G的最小生成树就是它本身。

②最小生成树的边的权值之和总是唯一的，虽然最小生成树不唯一，但其对应的边的权值

之和总是唯一的,而且是最小的。

③最小生成树的边数为顶点数减1。

58、最小生成树算法

（1）普利姆算法（Prime）（时间复杂度为O(n^2)，适合用于稠密图）

 Prim（普里姆）：采用了贪心算法的思想

（1）将起始顶点并入生成树

（2）将各顶点到生成树距离最短的那个顶点并入生成树

（3）更新各顶点到生成树的距离（比较第二步并入的顶点到各顶点的距离是否会比原顶点距离短，会的话则更新顶点到生成树的距离）

（4）重复以上三步直到所有顶点并入，此时最小生成树完成

（Prim算法构造最小生成树的过程：初始时从图中任取一顶点（如顶点1)加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都增1。以此类推，直至图中所有的顶点都并入T，得到的T就是最小生成树。此时T中必然有n-1条边。）

（2）克鲁斯卡尔算法（Kruska）（适用于稀疏图）

思路：每次找出候选边中权值最小的边，并入生成树中

算法执行过程：

将连通网中所有的边按照权值大小做升序排序，从权值最小的边开始选择，只要此边不和已选择的边一起构成环路，就可以选择它组成最小生成树。对于 N 个顶点的连通网，挑选出 N-1 条符合条件的边，这些边组成的生成树就是最小生成树。

（Kruskal算法构造最小生成树的过程：初始时为只有n个顶点而无边的非连通图T ={V,0}，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T，否则舍弃此边而选择下一条权值最小的边。以此类推，直至T中所有顶点都在一个连通分量上。）

59、Dijkstra算法（迪杰斯特拉）

从源点出发，每次选择离源点最近的一个顶点前进，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

用于计算图中某一结点到其余顶点的最短路径。

思路：

（1）集合S存放图中一找到最短路径的顶点

（2）集合U存放途中剩余顶点

算法执行过程：

（1）初始时，S只包含原点，即：S={v}，v的距离为0。U包含除v以外的其他顶点。即：U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。

（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v大k的最短路径长度）。

（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

（4）重复步骤（2）和（3）直到所有顶点都包含在S中。

60、Floyd算法（弗洛伊德）

61、Dijkstra算法与Floyd算法的比较

1. Dijkstra算法适用稠密图（邻接矩阵），因为稠密图问题与顶点关系密切；Floyd稠密图、稀疏图都适用；
2. Dijkstra不能处理负权图；Flyod能处理负权图；
3. Dijkstra处理单源最短路径；Flyod处理多源最短路径；

62、AOV网：

一种以顶点表示活动，以边表示活动的先后次序且没有回路的有向图。反映出整个工程中各个活动之间的先后关系的有向图。

63、拓扑排序和逆拓扑排序

拓扑排序的核心过程：

①从AOV网中选择一个没有前驱（入度为0）的顶点输出

②从网中删除该顶点，并且删除以该顶点为起点的有向边

③一直重复① ②操作，直到该AOV网为空或当前网中不存在无前驱的顶点为止，后一种情况说明有向图中必然有环

若图中没有环的时候，还可采用深度优先搜索遍历的方法进行拓扑排序。

对一个AOV 网，如果采用下列步骤进行排序，则称之为逆拓扑排序:

①从AOV网中选择一个没有后继(出度为0）的顶点并输出。

②从网中删除该顶点和所有以它为终点的有向边。

③重复①和②直到当前的AOV 网为空。

用拓扑排序算法处理AOV网时，应注意以下问题:

①入度为零的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶

点所代表的活动开始或继续。

②若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一

个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。

③由于AOV网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成AOV网的新的邻接存储矩阵，这种邻接矩阵可以是三角矩阵；但对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立。

64、AOE网：

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网。

AOE网具有以下两个性质:

①只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始;只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。在AOE网中仅有一个入度为0的顶点，称为开始顶点(源点)，它表示整个工程的开始;网中也仅存在一个出度为0的顶点，称为结束顶点（汇点)，它表示整个工程的结束。

65、AOV和AOE的比较

AOE网和AOV网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，AOE网中的边有权值;而AOV网中的边无权值,仅表示顶点之间的前后关系。

AOV网：顶点表示活动，边表示活动之间的先后关系，一般用来表示活动的制约关系；

AOE网：边表示活动，边的权值表示活动持续时间，顶点用来表示活动的开始，一般用来分析工程最少需要多少时间完成，或者是工程为缩短时间可以加快哪些活动；

66、关键路径的核心算法：

最大路径长度的路径称为关键路径

关键活动：关键路径上的活动为关键活动，关键活动的最早开始时间等于最晚开始时间。

由于AOE网中的某些活动是可以同时发生的，所以完成整个工程的时间应该是从起始点到终点的最大路径长度，关键路径长度即为工程的最短完成时间。

 

 

第八章查找

67、查找

分为静态查找表和动态查找表；

静态查找表包括：顺序查找、折半查找、分块查找；

动态查找包括：二叉排序树和平衡二叉树。

（1）顺序查找：把待查关键字key放入哨兵位置（i=0），再从后往前依次把表中元素和key比较，如果返回值为0则查找失败，表中没有这个key值，如果返回值为元素的位置i（i!=0）则查找成功，设置哨兵的位置是为了加快执行速度。时间效率为O（n），其特点是：结构简单，对顺序结构和连式结构都适用，但是查找效率太低。

（2）折半查找：要求查找表为顺序存储结构并且有序，若关键字在表中则返回关键字的位置，若关键字不在表中时停止查找的典型标志是：查找范围的上界<=查找范围的下界。

（3）分块查找：先把查找表分为若干子表，要求每个子表的元素都要比他后面的子表的元素小，也就是保证块间是有序的（但是子表内不一定有序），把各子表中的最大关键字构成一张索引表，表中还包含各子表的起始地址。特点是：块间有序，块内无序，查找时块间进行索引查找，块内进行顺序查找。

（4）二叉排序树：二叉排序树的定义为：或者是一棵空树，或者是一棵具有如下特点的树：如果该树有左子树，则其左子树的所有节点值小于根的值；若该树有右子树，则其右子树的所有节点值均大于根的值；其左右子树也分别为二叉排序树。在查找时可以进行动态的插入，插入节点要符合二叉排序树的定义，这也是动态查找和静态查找的区别，静态查找不能进行动态插入。

（5）平衡二叉树：平衡二叉树又称为AVL树，它或者是一棵空树或者具有如下特点：他的左子树和右子树的高度差的绝对值不能大于1，且他的左右子树也都是平衡二叉树。

平衡因子：是指左子树的高度减去右子树的高度，它的值只能为1，0，-1

如果再一个平衡二叉树中插入一个节点可能造成失衡，这时就要进行树结构的调整，即平衡旋转。包括4中情况：在左子树的左子树上插入节点时向右进行单向旋转；在右子树的右子树上插入节点时向左进行单向旋转；在左子树的右子树插入节点时先向左旋转再向右旋转；在右子树的左子树插入节点时先向右旋转再向左旋转。

68、B 树，又称多路平衡查找树，

B 树中所有结点的孩子个数的最大值称为B 树的阶，通常用m表示。

一棵m 阶B 树或为空树，或为满足如下特性的m 叉树：

树中每个结点至多有m 棵子树，即至多含有m-1 个关键字。

若根结点不是终端结点，则至少有两棵子树。

除根结点外的所有非叶结点至少有「m/2] 棵子树，即至少含有「m/2]- 1 个关键字。

所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似千折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。

B 树是所有结点的平衡因子均等于0 的多路平衡查找树。

69、B+树

是应数据库所需而出现的一种B 树的变形树。

一棵m 阶的B+树需满足下列条件：

每个分支结点最多有m 棵子树（孩子结点）。

非叶根结点至少有两棵子树，其他每个分支结点至少有「m/2]棵子树。

结点的子树个数与关键字个数相等。

所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。

所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。

70、m 阶的B+树与m 阶的B 树的主要差异如下：

在B+树中，具有n 个关键字的结点只含有n 棵子树，即每个关键字对应一棵子树；而在B 树中，具有n 个关键字的结点含有n+1棵子树。

在B+树中，每个结点（非根内部结点）的关键字个数n 的范围是「m/2]<=n<= m (根结点：1<=n<=m); 在B 树中，每个结点（非根内部结点）的关键字个数n 的范围是「m/2]-1<=n<=m-1 。

在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B 树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

71、散列表又称为哈希表，

是根据关键字而进行直接访问的数据结构。也就是说，散列表建立了关键字和存储地址的一种直接映射关系。

散列表是一种数据结构，它的优点是可以提供快速的查找操作和插入操作。缺点是删除操作慢，散列表是基于数组的，而数组创建后难于扩展，某些散列表被基本填满时，性能下降得非常严重。

散列函数是一个把查找表中的关键字映射成该关键字所对应地址的函数。散列函数可能会把两个或两个以上的不同关键字映射到同一地址，这种情况称为冲突。

散列函数的构造方法包括：直接定址法、除留余数法、数字分析法、平方取中法、折叠法、随机数法。其中，最常用的是除留余数法。

（1）直接定址法：取关键字的某个线性函数值作为散列地址，即

H(key) = a*key+b。

（2）除留余数法：取关键字对p取余的值作为散列地址，其中p通常是小于或等于散列表表长m的质数，即H(key) = key % p

处理冲突的方法包括：开放定址法和拉链法。其中，开放定址法包括：线性探查法，二次探查法，双重散列法。

（1）线性探查法：将散列表T[0…m-1]看成是一个循环向量，若初始探查的地址为d（即h(key)=d），探查时从地址d开始，首先探查T[d]，再探查T[d+1]…直到探查到T[m-1]，此后循环到T[0]，T[1]…直到探查到T[d-1]为止，探查时，如果遇到有空的地址就插入。

（2）再哈希法

（3）链地址法：若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组，凡是散列地址为i的结点均插入到头指针为i的单链表中。

与开放定址法相比，链地址法的优点是：

① 链地址法处理冲突简单，且无堆积现象，因此平均查找长度较短；

② 在用链地址法构造的散列表中，删除结点的操作易于实现。

而链地址法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间。

（4）建立一个公共溢出区

第九章 排序

72、排序：

是指把一个任意元素的序列排列成一个按关键字key有序的序列。

内部排序包括：插入排序、选择排序、交换排序、归并排序、基数排序。

其中插入排序包括：直接插入排序、折半插入排序、希尔排序；

选择排序包括：简单选择排序，堆排序；交换排序包括：冒泡排序、快速排序。

（1）直接插入排序（稳定）：基本思想为：将序列分为有序部分和无序部分，从无序部分依次选择元素与有序部分比较找到合适的位置，将原来的元素往后移，将元素插入到相应位置上。时间复杂度为：O（n^2）,空间复杂度为O（1）

（2）折半插入排序（稳定）：基本思想为：设置三个变量low high mid，令mid=(low+high)/2,若a[mid]>key,则令high=mid-1,否则令low=mid+1,直到low>high时停止循环，对序列中的每个元素做以上处理，找到合适位置将其他元素后移进行插入。他的比较次数为O(nlog2n),但是因为要后移，因此时间复杂度为O(n^2),空间复杂度为O(1)。 优点是：比较次数大大减少。

（3）希尔排序（不稳定）：基本思想为：先将序列分为若干个子序列，对各子序列进行直接插入排序，等到序列基本有序时再对整个序列进行一次直接插入排序。优点是：让关键字值小的元素能够很快移动到前面，且序列基本有序时进行直接插入排序时间效率会提升很多，空间复杂度为O（1）。

（4）简单选择排序（不稳定）：基本思想为：将序列分为2部分，每经过一趟就在无序部分找到一个最小值然后与无序部分的第一个元素交换位置。优点是：实现起来特别简单，缺点是：每一趟只能确定一个元素的位置，时间效率低。时间复杂度为O（n^2），空间复杂度为O（1）。

（5）堆排序（不稳定）：设有一个任意序列，k1,k2,…,kn，当满足下面特点时称之为堆：让此序列排列成完全二叉树，该树具有以下特点，该树中任意节点均大于或小于其左右孩子，此树的根节点为最大值或者最小值。优点是：对大文件效率明显提高，但对小文件效率不明显。时间复杂度为O(nlog2n),空间复杂度为O(1)。

（6）冒泡排序（稳定）：基本思路为：每一趟都将元素进行两两比较，并且按照“前小后大”的规则进行交换。优点是：每一趟不仅能找到一个最大的元素放到序列后面，而且还把其他元素理顺，如果下一趟排序没有发生交换则可以提前结束排序。时间复杂度为O（n^2）,空间复杂度为O（1）。

（7）快速排序（不稳定）：基本思路为：在序列中任意选择一个元素作为中心，比它大的元素一律向后移动，比它小的元素一律向前移动，形成左右两个子序列，再把子序列按上述操作进行调整，直到所有的子序列中都只有一个元素时序列即为有序。优点是：每一趟不仅能确定一个元素，时间效率较高。时间复杂度为O(nlog2n),空间复杂度为O（log2n）.

（8）归并排序（稳定）：基本思想为：把两个或者两个以上的有序表合并成一个新的有序表。时间复杂度为O（nlogn）,空间复杂度和待排序的元素个数相同。

（9）基数排序：时间复杂度为：对于n个记录进行链式基数排序的时间复杂度为O（d(n+rd)）,其中每一趟分配的时间复杂度为O(n),回收的时间复杂度为O（rd）。

73、排序方法的比较

直接插入排序、冒泡排序和简单选择排序是基本的排序方法，它们主要用于元素个数n不是很大(n< 10000) 的情形。

对于中等规模的元素序列(n <=1000), 希尔排序是一种很好的选择。

对于元素个数n 很大的情况，可以采用快排、堆排序、归并排序或基数排序，其中快排和堆排序都是不稳定的，而归并排序和基数排序是稳定的排序算法。

74、堆和栈的区别，以及为什么栈要快

（1）堆和栈的区别

① 扩展方向不同：堆是由低地址向高地址扩展；栈是由高地址向低地址扩展。

② 申请方式不同：堆由程序员手动分配和管理；栈由系统自动分配和管理；

③ 效率不同：堆由程序员分配，分配效率较低，可能由于操作不当产生内存碎片；而栈由系统分配，分配效率较高，不会有内存碎片。

④ 程序局部变量使用的是栈空间，new和malloc函数动态申请的内存是堆空间。

（2）栈的效率高的原因

栈是操作系统提供的数据结构，计算机底层对栈提供了一系列支持：分配专门的存储器存储栈的地址，压栈和入栈有专门的指令执行；

而堆是由C和C++函数库提供的，机制复杂，需要一系列分配内存、合并内存和释放内存的算法，因此效率较低。