《数据结构与算法:Python语言描述 》课后习题

1）这本书为什么值得看：

• Python语言描述，如果学的Python用这本书学数据结构更合适
• 2016年出版，内容较新
• 作者裘宗燕，北大教授，质量有保证
  2）这本书为什么不值得看：
• 这本书从第七章开始分别是‘图’,‘字典与集合’,‘排序’，这三章在数据结构中属于较难部分，但到这里却能明显感受到作者已经开始着急完本了，明显的越写越不走心，出现了好多错误，讲解的也不像前几章详细了。

第三章、线性表

---

1.复习下面概念

• 线性表：某类元素的集合，元素之间可能存在某种关系。
• 基本元素集合：
• 元素集合和序列：序列就是元素排列有顺序。
• 下标：序列中的元素在表中有一个确定的位置，称为这个元素的下标。
• 空表：没有元素的表。
• 表的长度：表中元素的个数。
• 顺序关系（线性关系）：表元素之间有一个基本关系，叫做下一个关系，下一个关系就是顺序关系（线性关系）。
• 首元素：表的第一个元素。
• 前驱和后继：表中每个元素（除首元素）都有一个前驱元素；表中每个元素（除尾元素）都有一个后驱元素。
• 数据抽象的实现者和使用者：实现；使用。
• 顺序表和链接表：表元素顺序的放在一块连续的存储区里；表元素存放在通过链接构造起来的一系列存储块里。
• 顺序表的元素布局：一种是元素大小相同，在表里等距安排同样大小的存储位置；一种是元素大小不同，实际数据元素另行存储，在顺序表里各单位位置保存对应元素的引用信息（链接）。
• 索引和索引结构：不存放实际数据元素，只存放找到实际数据的线索的顺序表叫做索引。这也是最简单的索引结构。
• 容量：表的存储量大小。
• 元素遍历：完全的访问（可能有操作）一遍表中元素。
• 查找（检索）： 查找给定元素（第一次出现）的位置。
• 定位：表的元素的编号。
• 加入和删除元素：加入删除。
• 尾部加入和删除：在表的已有元素之后插入元素；删除表的已有元素的最后一个。
• 保存插入和删除：在位置i处插入元素；删除位置i的元素。
• 表的一体式实现和分离式实现：存储表信息的单元和元素存储区已连续的方式安排在一块存储区里；表对象只存放表信息，实际数据元素独立存储，通过链接关联。
• 动态顺序表：表的容量在使用中能扩充。方式是：申请一块更大的存储区，把实际数据元素复制到这块存储区，修改表对象和元素存储区的链接。
• 元素存储区的增长策略（线性增长，加倍增长）：当表容量填满时，要更换一块更大的存储区，存储容量的增大量每次都为一个常量n，就叫做线性增长（其实就是加法）；存储量的增加每次都是原容量的某倍，叫做加倍增长（乘法）。
• 元素反转和排序：元素排列顺序进行反转；元素按照某种顺序进行排列。
• 链接结构：链接表中元素存放在一批小块存储区中，用显式的链接将它们连成一串，形成链接结构。
• 单链表（单向链接表）：每个表结点记录着下一个表元素的结点的标识（引用/链接）。
• 链接：引用，指向。
• 表头变量（表头指针）：保存着一个表的首结点的引用（标识/链接）的变量。
• 空链接：结点不存放下一个表元素的引用，在Python中就是系统常量None。
• 链表处理的扫描模式：由于单链表只有一个方向的链接，开始情况下只有表头变量在掌控中，所以对表内容的一切检查都只能从表头变量开始，沿着表中链接逐步进行。这种操作过程称为链表的扫描。
• 汇集对象：把线性表一类的对象称为汇集对象，他们本身是对象，又包含着一组元素对象。
• 尾结点引用：为提高表的后端插入操作的效率，给表对象增加一个表尾结点的引用域，这样，在表尾插入新结点只需O(1)时间。
• 循环单链表：表的尾结点的next域不用None，而是记录着首结点的引用，单链表就形成了一个圈。
• 双向链接表（双链表）：表的每个结点不仅记录着下一个结点的引用，还记录着上一个结点的引用，这样两段插入和删除操作都能高效进行。
• 循环双链表：表尾结点的next域记录着首结点的引用，首结点的prey域记录着尾结点的引用。
• 链表反转：结点顺序反转，可以不断从表的首端取下结点，将其放到另一个空表的首端，就形成了一个反转过程。
• Josephus问题:n个人坐成一圈，从第k个人开始报数，报到第m个数的人退出。然后从下一个人开始继续报数并按相同规则退出，知道所有人退出。
• 随机存取：顺序表中元素顺序存放在一大块存储区中，要存取下表为i的元素，可以用简单的公式计算出元素位置，在O(1)时间直接存取。
• 顺序存取：链接表中元素存放在一批小块存储区中，用显式的链接将它们连成一串，形成链接结构。
• 访问的局部性：顺序表的表元素顺序映射到内存中连续的单元里，下一个元素的实际存储位置与当前元素很近，由于当前计算机体系结构的特点，顺序访问内存中相近位置的效率较高，而真正的随机访问（比如链接表访问下一个结点）效率较低。
• 类定义的内在一致性：再设计一个类时，需要考虑一套统一的规则。类初始化方法建立起的对象应满足这套规则，操作也不能破坏规则，这样定义的类才是有效的。

---

2.那些事物适合用线性表存储和管理?并说明原因。

顺序表优点：随机存取，在O(1)时间进行；缺点：插入和删除都可能需要移动很多元素，操作代价很高（尾端插入、删除除外）。

• 书架上的一排书。
• 计算机桌面上的图标以及相关信息。
• 计算机的文件、文件夹（目录）。

3.

• 尾端，尾端插入和删除不需要移动其他元素，时间复杂度为O(1)。
• 哪端都可以，时间复杂度都是O(1)。

4.

• 顺序表，条件中的几种操作在顺序表中时间复杂度都是O(1)。

5.

• 表对象记录着表首结点引用、尾结点引用。要在尾端插入删除，为提高效率，应增加一个尾结点指针。

6.

• 插入和删除都可能需要移动很多元素，操作代价很高（尾端插入、删除除外）；能避免。
• 存取元素是顺序存取，效率很低。能避免。

7.

淘宝的购物车，用户需要首端加入和随机删除，用链接表合适。

8.

• 选择使用顺序表的情况：频繁随机存取元素、尾端插入和删除新元素，不常用插入和删除元素。
• 选择使用链接表的情况：相反情况。

9.

设计一个程序，对两个排序序列L1和L2进行归并，要求时间复杂度为O(max(m,n)),m和n是两个排序序列的元素个数。
def guibing(L1,L2):
for x in L1:
for y in L2:
while x<y:

10.比较带尾结点指针的单链表和循环单链表。

• 带尾结点指针的单链表：支持高效的后端操作，包括表元素访问和新元素插入，但不包括删除。在需要频繁两端插入的情况下适用。
• 循环单链表：表的每一个结点都可以作为首结点，也是支持高效的后端操作，包括表元素访问和新元素插入，但不包括删除。

11.比较循环单链表和双链表的特点。

• 循环单链表：表的每一个结点都可以作为首结点，也是支持高效的后端操作，包括表元素访问和新元素插入，但不包括删除。
• 双链表：可以向前访问，也可以向后访问。增加一种数据访问顺序，使表中间结点的操作更加方便。实现两端的高效插入和删除。

---

---

第四章、字符串

1.复习下面概念

• 字符：基本文字符号。
• 字符集：有穷的一组字符构成的集合。
• 字符串（串）：字符的序列。
• ASCII：由127个字符组成的、基于拉丁字母的一套电脑编码系统。
• Unicode：国际通用编码。
• 字符序：字符集里的字符定义的一种顺序。
• 字符串长度：串中字符的个数。
• 空串：串中字符个数为零。
• 下标（字符位置）：串中字符顺序排列，每个字符都有确定的位置，本书中用从零开始的自然数表示下标。
• 字符串相等：两个串的长度相等，对应下标的字符也一一对应相同。
• 字典序：字符串上的一种序关系，基于字符串定义。
• 拼接：两个字符串通过拼接得到一个字符串，在Python中用+表示字符串拼接。
• 子串：一个串和另一个串的一个连续片段相同，就说是它的子串。
• 子串的出现位置：在母串(?)中跟子串相同的字符段的首字符的下标。
• 前缀、后缀：一个串的前缀就是该串开头的任意一段字符构成的子串。后缀同理。
• 串的幂：一个串的n次幂就是n个这个串的拼接。
• 串替换：把一个串里的一些串替换为另一些串得到的结果。
• 子串检索（子串匹配）：同字符串匹配。
• Python的str类型：可以看作抽象的字符串概念的一个实现。str是不变类型。str对象采用第三章线性表里提到过的，一体式顺序表形式实现。（元素有数字有子母，大小不同，表元素外置）
• 字符串匹配：
• 模式匹配：
• 模式串：
• 目标串：
• 朴素匹配算法：
• KMP算法（无回溯串匹配）：
• 模式：
• 模式语言：
• 描述能力和匹配算法的复杂性：
• 通配符：
• 正则表达式：
• 正则表达式匹配：
• Python标准库re包：
• Python原始字符串：
• 元字符：
• 常规字符：
• 顺序组合（拼接）：
• 字符组：
• 重复模式:
• 选择模式：
• 组概念：

---

2.

3.

4.

---

---

第五章、栈和队列

---

1.复习下面概念

• 容器：一个容器结构里总包含一组其他类型的数据对象，称其为元素，支持对这些元素的存储、管理、使用。
• 元素：容器中包含的数据对象。
• 容器数据结构：能保证存入的元素被保存在容器中，尚未明确删除的元素总可以访问，而取出并删除的元素就不能存在于容器中了。
• 栈（堆栈）：保存数据的容器，主要用于在计算过程中保存临时数据，栈是保证元素后进先出关系的结构，简称为LIFO结构。
• 队列（队）：队列是保证元素先进先出关系的结构，简称为FIFO结构。
• 缓冲存储（缓存）：工作中产生的中间数据暂时不用或者用不完，就有必要把当时不能立即用掉的数据存起来，如果需要存储的数据项数不能事先确定，就不能用设置变量的方法来存储了，就需要采用更复杂的机制存储和管理。这样的存储机制叫做缓冲机制或者缓存。
• 后进先出（LIFO，后进先出表）：按照数据生成的顺序，较后生成并保存的数据需要先行使用和处理。（支持这种顺序使用元素的缓存数据结构就叫做栈）
• 先进先出（FIFO）：按照先后顺序处理，先生成的数据先处理。
• 实现结构：实现其功能所用的结构。
• 入栈：把元素压入栈中。
• 出栈：从栈中弹出元素并返回。
• 栈顶：执行插入和删除元素操作的一端。
• 栈底：栈的另一端。
• 括号匹配问题：在许多正文中都有括号，特别是程序、数学表达式的正文片段中，括号应该正确的嵌套并分别配对。
• 表达式的中缀表示、前缀表示、后缀表示：二元运算符写在两个运算对象中间，这种写法叫做中缀表示；函数符号写在运算对象前面的写法叫做前缀表示；运算符写在运算对象之后的写法叫做后缀表示。
• 波兰表达式：前缀表达式的另一种叫法。
• 逆波兰表达式：后缀表达式的另一种叫法。
• 表达式求值：表达式的运算求得结果过程。
• 表达式形式转换：中缀表达式在计算机中情况很复杂，求值不好处理，所以可以把它转换为后缀表达式来处理。
• 运算符栈：表达式型式转换中，存放运算符的栈。
• 数据栈：表达式型式转换中，存放数据对象的栈。
• 函数的递归定义：在一个定义中引用了被定义的函数本身，这种定义就叫递归定义。
• 递归结构：在一种数据结构里的某个或某几个部分具有与整体同样的结构，就叫做递归结构。
• 递归调用：在Python中定义一个函数时，允许在函数的定义体中出现对这个函数自身的调用。
• 运行栈：要支持递归函数的实现，需要一个栈保存递归函数执行时每层调用的局部信息，留待函数调用返回后继续使用，这个栈叫做运行栈。
• 函数帧（帧）：递归函数执行中的局部信息包括函数的形参、局部变量以及保存的数据，这些信息用一个运行栈保存。运行栈对递归函数的每个调用都在这个栈上给它开辟一块区域，叫做一个函数帧（帧）。
• 入队：把一个元素放入队列。
• 出队：从队列中删除一个元素并返回它。
• 循环顺序表：顺序表的变形。其最后存储位置之后是最前的位置，形成一个环形结构。
• 数据不变式：实现一种数据结构里的操作时，最基本的问题就是这些操作需要维护对象属性间的正确关系。这样一套关系被称为数据结构的数据不变式。
• 消息：windows系统里，各种活动（窗口界面操作、各种输入输出、程序活动）都可能产生各种消息，要求某些系统程序或者用户程序对他们做出响应。
• 消息驱动的系统：消息要求某些系统程序或者用户程序对他们做出响应。
• 消息队列：保存系统从各种活动中接收到各种消息。系统消息分发机制检查消息队列中的消息，根据情况把它们分发给相应程序。
• 离散时间系统和模拟：离散时间系统是真实世界中许多实际系统的抽象。模拟是人们通过计算机程序的运行，来模拟真实系统的活动情况。帮助理解真实世界实际运行中的行为，或者是为计划中的实际系统的设计和实现方式做一些准备。
• 迷宫问题：给一个迷宫图，图上有一个入点，一个出点，要求找到一条可以通过的从入点到出点的路径。
• 当前位置：。
• 探查：检查当前位置是否能通行。
• 回溯法：后退并考虑其他可能性的动作叫做回溯。回溯法通常总是用一个栈作为辅助结构，保存工作中发现的回溯点，以便后续考虑其他可能性时使用。
• 搜索：
• 状态空间搜索（路径搜索）：以迷宫问题为代表的一类问题叫做状态空间搜索。这类问题的基本特征是存在位置、情况等状态；有一个初始状态，一个或者几个结束状态（或者是有判断结束的方法）；每个状态都有neighbor(x)表示跟这个状态x相邻的一组状态；有一个判断函数来判断一个状态是否可行；问题：从x出发，设法找到一个或者全部的解。
• 通用问题求解方法：
• 深度优先搜索：基于栈的搜索称为~，进入一个局部区域，只有穷尽了哪里的状态并发现无法到达目标后才退出来。
• 宽度优先搜索：基于队列的搜索称为~，从入点开始，只有检查完所有与入口同样距离的位置之后，才往前进一步。
• 最优解：在迷宫问题中，就是长度最短的那个路径。
• 双端队列（deque）：允许两段插入、删除元素的缓存结构。

---

2.

• 栈只能栈顶插入、删除元素。
  d,c,b,a ？？？

3.

• a,b,c,d ？？？

4.

• a2=k-1;a(i+1)=k-1 ？？？

5.

• ai>aj>ak

6.中缀形式-->前缀形式

• • a b * - c d
• • 2 + / / a b c d

7.后缀形式-->中缀形式

• a-[b/c-f*d/(3+r)]
• (2+a)/b/[(c-d)-e*f]

8.中缀形式-->前缀形式、后缀形式

• 前缀形式： / + 1 - * 2 3 5 4 ; 后缀形式： 1 2 3 5 - * 4 + /
• 前缀形式： + * + 7 4 - / 6 3 4 ；后缀形式： 7 4 + 2 6 3 - / 4 * /

9.

while 支线上还有车厢：
    for 车厢=硬座：
        连接到车头上
    else：
        进入另一条支线
把另一条支线上的车厢连接到硬座车厢后面

10.

• 24
• 120

第六章、二叉树和树

---

1.复习下面概念

• 树形结构：也是由结点(结点中的逻辑单元，可用于保存数据)和结点之间的连接关系(一种后继关系)构成，但其结构和线性结构不同，最重要的特征包括：结构不为空时，都有且仅有一个起始结点，叫做树根；按结点间的连接关系，树根外的结点都有且仅有一个前驱，但可以有0个或者多个后继(不同点)。
• 树根：树形结构中，除结构为空外，都存在着的有且仅有一个的起始结点，叫做树根。
• 前驱：存在前一个结点。
• 后继： 存在后一个结点。
• 二叉树： 最简单的树形结构，特点是：树中每个结点最多关联到两个后继结点；关联的后继结点分左右，或为左关联结点，或为右关联结点。
• 左子树、右子树：左关联结点就是左子树；右_就是右。
• 空树：树中结点个数为零。
• 单点树：只有一个结点—根。
• 父节点、子节点：一棵二叉树的根结点称为该树的子树根结点的父结点；子树的根结点称为二叉树树根结点的子结点。
• 左/右子结点：左/右后继结点
• 父子关系：父结点到子结点的边形成的一种单方向的父/子结点关系。
• 祖先/子孙结点：基于父子关系可以定义其传递关系，称为~。
• 树叶：两棵子树都空，没有子结点的结点叫做~。
• 分支节点：树中除树叶外的其余结点叫做~。
• 结点的度数：一个结点的子结点的个数就是它的度数。
• 路径：根据祖先/子孙关系，从一个祖先结点到它的任何子孙结点都存在一系列的边，形成了两者的联系。这一系列首尾相连的边称为树中的一条路径。每个结点到它的子结点的有一条长度为1路径；到它自身路径长度为0.
• 路径长度：一条路径包含的多少条数。
• 结点的层数：从根开始，根的层数为0，往下子结点为下一层，层数+1.
• 树的高度（深度）：树中结点的最大层数就是高度。
• 满二叉树：所有分直结点的度数都是2.
• 扩充二叉树：加入足够多的新叶结点，使得原有结点度数都变为2.
• 内部结点、外部结点：扩充二叉树中，原有结点就是内部结点，新增的新叶结点就是外部结点。
• 内部路径长度、外部路径长度：从树根到树中各内部结点的路径长度的和；_{到树中的外部结点的}和。
• 完全二叉树：对于一棵高度为h的二叉树，从0_{h-1层的结点度数都为2（结点都满），如果最下的那一层结点不满，则所有结点都在最左边连续排列，空位在右边，这样的二叉树就叫做}。
• 二叉树的遍历：按照某种系统化的方式，访问二叉树的每个结点一次（可能会操作结点的数据）。
• 深度优先遍历：顺着二叉树的一条路径走，直到检查完一个叶结点，往下没有结点了，才回溯继续。
• 先根序(先序)遍历：按照DLR顺序，先访问根结点，再访问左子结点，最后右子结点。
• 中根序(对称序/中序)遍历：LDR
• 后根序(后序)遍历：LRD
• 先根序列：按照先根序遍历得到的结点访问序列。
• 对称(中根)序列：按照中根序~。
• 后根序列：按照后根序~。
• 宽度优先遍历(按层次顺序遍历)：在所有路径上齐头并进。
• 层次序列：按照宽度优先遍历得到的结点序列。
• 表达式树：二叉树中结点与子树的关系可用于表示运算符和运算对象的作用关系。
• 二元表达式：只包含二元运算符的表达式。
• 算术表达式：二元表达式中的运算对象都是数。
• 表达式求值：对表达式化简，把能计算的都计算出来。
• 优先队列：基于队列，特点是存入其中的数据都附有一个数值，叫做优先级，用来表示这个项的优先程度。优先队列要保证任何时候，访问或者弹出的都是这个优先队列中元素的优先级最高的元素。
• 优先关系：集合中元素之间的关系为有序的，靠前的就是更优先的。
• 优先级：项的优先程度。
• 堆：结点里存储数据的完全二叉树就是堆，堆中的数据的存储要满足一种关系，任何一个结点里所存的数据，它按规定的优先关系都要先用或者等于其子结点里的数据。
• 堆序：任何一个结点里所存的数据按规定的优先关系都要先用或者等于其子结点里的数据。
• 小顶堆：数据小的优先构造出来的堆就是小顶堆。
• 大顶堆：数据大的优先构造出来的堆就是大顶堆。
• 筛选(向下筛选、向上筛选)（以小顶堆为例）：把元素和它的父结点的数据相比较，小的话交换两个元素的位置，不断进行这样的操作，直到不小于父结点的数据，或者是到达根结点，才停止。
• 堆排序：如果一个连续表里存储的数据是一个小顶堆，按照优先队列的操作方式反复弹出元素，就能得到一个递增序列。
• 离散事件模拟：前面讲过。被模拟系统的行为可以抽象为一些离散事件的发生，所发生事件可以引发新的时间等。人们希望通过计算机模拟理解系统行为，评价和涉及真实世界中实际的或者所需的系统。
• 模拟框架：模拟按照事件的发生时间为顺序来处理，在模拟系统里用一个优先队列保存，已知在将来某些特定时刻发生的事件，系统的运行就是不断从优先队列里取出等待事件，一个个的处理，直到模拟结束(或者没有事件了，队列为空)。要注意的是，一些时间在处理时，可能会引发新的事件。
• 事件队列：一个保存模拟中缓存的事件的优先队列。
• 宿主系统：事件有一个host参数，用于表示该事件的发生所在的模拟系统。事件执行时，可能会访问宿主系统。
• 二叉树的链接实现：用一个数据单元表示一个二叉树结点，通过子结点的链接（指针）建立结点间的联系。（与连续表的链接实现类似）。
• 二叉树结点类：结点类的构造函数接受三个参数，分别为它的结点数据、左子结点链接、右子结点链接（默认值为None，使用默认值时构造的就是叶结点）。
• 非递归的二叉树遍历算法：循环、生成器
• 非递归后序遍历：这种遍历方法比较麻烦，因为一个根结点要经过三次，第一次经过去处理左子结点，第二次经过是从左子结点返回来去处理右子结点，最后返回来才去处理根结点。对非递归先根序遍历算法进行修改就能得到。
• 下行循环：循环体中的内层循环，目标是找到下一个应该访问的结点。
• 二叉树类：（为什么已经有了二叉树结点类，还要定义一个二叉树类呢？直接基于结点类构造的二叉树具有递归的结构，可以很方便地递归处理，但这样的"二叉树结构"有不统一之处：用None表示空树，但是None的类型并不是BinTNode。此外还有一个原因是，基于二叉树结点类构造的结构不是一种封装良好的抽象数据类型。）
• 带权扩充二叉树：给扩充二叉树的每个外部结点标一个数值，用来表示与该叶有关的某种性质，称为这个结点的权。进而得到的就是~，其外部路径长度是WPL=i从0到m，wili之和。
• 哈夫曼树(最优二叉树)：设有实数集W={w0，w1，...，wm-1}，T是一颗扩充二叉树，它的m个外部结点分别以wi（i=0,1,2...n-1）为权，而且T的带权外部路径长度WPL在所有的这样的扩充二叉树中达到最小，那么，T就被称为数据集W的最优二叉树或者哈夫曼树。
• 哈夫曼算法：就是构造哈夫曼树的算法 。算法的输入为实数集W={w0，w1，...，wm-1}，F是一个包含k棵二叉树的集合，开始时k=m，F={T0，T1...Tm-1},其中的每个Ti都是一棵只包含权威Wi的根结点的单点二叉树。重复以下步骤,直到集合F中只剩下一棵树，这棵二叉树就是集合W上的哈夫曼树(注意最后得到的哈夫曼树不唯一)：1.构造一个新二叉树，它的左右子二叉树是从集合F中选取的两棵权值最小的二叉树，构造出的这棵新二叉树的权值设置为那两棵二叉树的权值之和。2.将那两棵二叉树从集合F中删掉，把新构造出的这棵二叉树加入到集合F中。
• 哈夫曼编码：把哈夫曼算法中的集合F定义为需要编码的字符集合，实数集W定义为各个字符在实际信息传输或储存中出现的频率，构造出一棵哈夫曼树，树中的每个分支结点到它的左子结点的边上标0，到它的右子结点的边上标1，以从根节点到一个外部结点的路径上的0/1序列，作为这个外部结点的标记字符的编码，这样得到的就是哈夫曼编码。
• 最优编码：哈夫曼编码是给定字符集（出现频率确定）的最优编码。存储传输时平均开销最小；对任意一对字符Ci和Cj，字符Ci的编码不是Cj编码的前缀。
• 有序树和无序树：根据子树排列顺序有无意义，可把树分为有序树和无序树。由于计算机表示时存在自然的顺序，所以数据结构中主要考虑有序树，下面默认树是有序树。
• 树和树林：树和二叉树差不多，不同的地方有:树的分支结点的度数没有限制，可以有任意的子结点；二叉树的子结点有左右之分，而在树中没有这个概念，但是因为树的子结点是有序的，所以可以说第一个子树，下一个子树...；树林就是树的集合。
• 树根：非空树中，有且仅有一个的起始结点就是树根。
• 有序树林和无序树林：根据树林中的树排列顺序有无意义，可分为~~，有序树林可以说第一棵树，下一棵树...
• 搜索树：前面提过。在一般的状态搜索问题里，搜索过程中经历的状态(结点)和状态之间的转移关系(边)形成了一棵树，称为‘搜索树’。
• 子结点引用表示法：子指针表示法。用一个数据单元表示结点，通过结点间的链接表示树结构，可以用list表示每个结点。（由于树的结点的度数不定，所以要给结点引用域设置一个值，度数超过这个值的树不支持）（缺点：会出现大量空闲的节点引用域，造成浪费）
• 父结点引用表示法：为克服子结点引用表示法空间浪费的缺点，又提出了父结点引用表示法。在树中，除了根结点外，每个分支结点都有且仅有一个父结点。所以，每个结点（根结点除外）可以只用一个引用域来保存父结点的引用。方法：用一个顺序表表示一棵树，每个表元素对应于一个结点，记录结点数据和父结点引用。（优点：空间开销小。缺点：要访问一个结点的子结点，需要通过查找，复杂度是O(n)）
• 长子-兄弟表示法：树的二叉树表示。二叉树的左子结点表示树结点的第一个子结点，右子结点表示结点的下一个子结点。（这样只适用于结点度数小于等于2的树。）

---

2.

• 5*6=30 （默认构造出的树是一棵。）

3.

• 1+1+2+1=5 （默认有序树。）

4.

• n0=n2+1=11

5.

• 全部结点至少=n2=n0-1

6.

• 高度至少为5

7.

• 归纳总结法 ？？？

8.

• ???

9.

• a) 先根序：ABDGI EHJK CF ; 中根序：DGI B E JHK A FC；后根序：IGD JKHE B FC A
• b)转换成了一个包含五个树的树林，树林怎么便利？？？
• c）

10.

• n=15,I=n-1=14,E=I+2*n=44

11.

• • A * B C - / D E

12.

• 不能。证明：假设一个结点的度数为1，仅从先根序列和后根序列不能判断出这个结点的子树是左还是右。

13.

• a) 没有左子结点
• b)没有右子结点
• c)没有左子结点
• d)没有子结点 （或者abcd都是空树）

14.

• 没有左子结点

15.

• ？？？

16.

• 前缀编码：在一个字符集中，任意一个字符都不和其他字符的前缀相同。
• 哈夫曼编码得到的二进制编码不会出现前缀编码。
• 论文查重？

17.

• a)是，10和10111
• b)是 ，10和101
• c)不是
• d)不是

18.

• a: 00000
• b: 1000
• c: 00001
• d: 010
• e: 101
• f: 1001
• g: 011
• h: 110
• i: 001
• j: 111
• k: 0001

19.

• 跟18类似，略

20.

• 结构归纳法

21.

• 叶结点个数=m+k-1

22.

• ???

23.

• ???

24.

• 宽度优先遍历（树，断言一个结点的度数不为1）
• 用一个变量记录当前层数，变量小于高度-2时，proc为断言一个结点的度数为2；等于高度-1时，？？？

25.

def proc(t):
    x=t.left
    y=t.right
    t.left=y
    t.right=x
def preorder(t,proc):
    if t is None:
        return
    proc(t)
    preorder(t.left)
    preorder(t.right)

---

---

第七章、图

1.复习下面概念

• 图：在计算机的数据结构领域，图被看作是一类复杂数据结构，可用于表示各种复杂联系的数据集合。定义：一个图是一个二元组，G=(V,E),V是图的顶点集合，E是图的边的集合。
• 二元关系：两个集合，他们的元素互相之间有某种联系，这两个集合就是二元关系。
• 拓扑结构：把实体抽象成与其大小、形状无关的“点”，而把连接实体的线路抽象成“线”，进而以图的形式来表示这些点与线之间关系的方法，其目的在于研究这些点、线之间的相连关系。
• 图论：数学领域里的一个研究分支，专门研究图这种拓扑结构。
• 图算法：研究图的算法。
• 顶点和边：图中的基本个体，用来表示任何讨论中需要关心的实体。
• 有向图、无向图：有向图的边有方向，是顶点的有序对；无序图的边没有方向，是顶点的无序对。
• 有向边及其始点和终点：用尖括号形式表示，例如<v,v'>表示从顶点v到顶点v'的有向边，v是边的始点，v'是边的终点。
• 无向边：用圆括号表示，例如(v,v')。
• 邻接(顶)点：对于图G=(E,V)，如果边<vi,vj>属于E，就称vj是vi的邻接顶点或者邻接点，也称这条边是和顶点vi相关联的边，或者vi的邻接边。
• 邻接边：上面有
• 邻接关系：边集合E表示的是顶点之间的邻接关系。
• 完全图：任何两个顶点之间都有边的图就是完全图。
• 顶点的度：和这个顶点邻接的边的条数。
• 入度、出度：以这个顶点为终点边的条数；以这个顶点为始点的边的条数。
• 路径：对于图G=(E,V)，如果存在顶点序列Vi0，Vi1，...,Vim，使得(Vi0，Vi1)，(Vi1，Vi2)...(Vim-1，Vim)都属于E，就说从顶点Vi0到Vim存在路径，<Vi0，Vi1，...,Vim>就是从顶点Vi0到Vim的一条路径。
• 路径的长度：路径上边的条数。
• 回路(环)：起点、终点是同一个顶点的路径。
• 简单回路：一个环路除了起点和终点相同外，其他顶点都不相同，就称这个环路是~。
• 简单路径：'内部'没有回路的路径。换句话说，就是起点终点可能相同，但其他顶点都不相同。（所以，简单回路属于简单路径。）
• 有根图：如果在有向图G中存在一个顶点v,从v到图中的其他顶点都有路径，就说顶点v是图G的一个根。(可能不唯一)。
• 连通：如果在无向图G中，存在从vi到vj的路径，就说vi，vj之间连通。
• 连通无向图(连通图)：如果一个无向图中任意两个顶点之间都连通，就说这个无向图是~。
• 强连通有向图：如果一个有向图中的任意两个顶点vi，vj，从vi到vj连通，从vj到vi也连通，就说这个有向图是~。
• 最小连通图：一个连通图，去掉任一个边就不再是连通图，就说这个连通图是_{。（包含n个顶点的}恰有n-1个边）
• 最小有根图：一个连通图，去掉任一条边就不再是有根图，就说这个有根图是_{。（包含n个顶点的}恰有n-1个边）
• 无向树：满足‘包含n个顶点的最小连通图恰有n-1个边’这个性质的图G称为无向树。（从无向树的任意一个顶点出发都能到达任何其他顶点。）
• 有向树：满足‘包含n个顶点的最小有根图恰有n-1个边’这个性质的图G称为有向图。（这个有根图的根可以看做树根。）
• 子图：对于图G'(V',E'),G(V,E),如果V'包含于V，E'包含于E，就说G'是G的子图。子图就是原图的一部分，而且满足图的基本定义。
• 无向图的连通子图：一个无向图可能不是无向连通图，但是它的子图可能是连通的，这种子图就称为原图的~。
• 有向图的强连通子图：一个有向图可能不是强连通的，但是它的子图可能是强连通的，这种子图就称为原图的~。
• 极大连通子图(连通分量)：如果有向图G'是G的一个连通子图，并且，G'不‘真包含于’G，就说G'是G的极大连通子图。（就是说G'的V'和E'都是极大的，不能扩充的。）
• 极大强连通子图(强连通分量)：与极大连通分量的定义类似。（这个要注意##看书的例子）
• 带权图：图G的每条边都被赋予一个权值，就称G是带权图。
• 网络：就是带权的连通无向图。
• 邻接矩阵：是图的最基本表示方法。邻接矩阵是表示图中顶点间邻接关系的方阵。对于有n个顶点的图G(V，E)，它的邻接矩阵是一个n*n方阵，图中的每个顶点按顺序对应于矩阵里的一行(或者一列)，矩阵元素表示图中的邻接关系。
• 邻接表表示法：为图中每个顶点关联一个表，用来记录这个顶点的所有邻接表。
• 顶点表：顶点是图中最基本的成分，通常有标识，也可以顺序编号，顺序编号后就可以通过编号'随机访问'。图中顶点通常不变，所以可以用一个顺序表来实现。（每个顶点还要关联一个表示它的邻接边表的链表。）
• 图的遍历(周游)：按照某种方式系统的访问图中每个顶点而且是仅访问一次的过程。也叫做周游。
• 可达顶点：从一个顶点v出发，如果到一个另外的顶点v'有路径，v'就是v的可达顶点。
• 深度优先遍历：1.假定从顶点v出发，先访问顶点v并将其标为'已访问'，检查v的邻接顶点，从中选择一个'未访问'的，从它出发继续进行~(这里调用递归)，直到这条路径上的终点没有邻接顶点时进行回溯；2.反复进行上述操作(这里是调用递归)，直到v的可达顶点都是'已访问'；3.检查图中是否还有'未访问'的顶点，如果有，说明这个图不是连通的，这时就要另选出一个'未访问'顶点，从它出发重复前面的过程，直到它的可达顶点都已访问，也直到图的所有顶点都已访问。
• 宽度优先遍历: 1.假定从顶点v出发，首先访问v并将其标为'已访问'，再检查v的未访问的邻接顶点（假设为v0,v1，...，vm），依次全部访问并标为已访问；2.再检查v0,v1，...，vm的邻接顶点......如此的进行下去，知道v所有可达顶点都已访问；3.检查图中是否还有'未访问'的顶点，如果有，说明这个图不是连通的，这时就要另选出一个'未访问'顶点，从它出发重复前面的过程，直到它的可达顶点都已访问，也直到图的所有顶点都已访问。
• 深度优先搜索(DFS)序列：就是用深度优先遍历得到的序列。
• 宽度优先搜索(BFS)序列：就是用宽度优先遍历得到的序列。
• 生成树：性质：对于一个连通无向图/强连通有向图G(或者是有跟有向图G')，从G的任一顶点v0出发(或者是从有根有向图G'的根v0'出发)，到图中的其他顶点都存在路径。如果图G有n个顶点，必然可以找到G中的一个包含n-1条边的集合且这个集合包含了从v0出发到其余所有顶点的路径(这里是不是用包含不合适，边集合能包含路径吗？组成？？)。 对于无向图，满足这个性质的子图就是它的一个最小连通子图；对于强连通有向图或者是有根有向图，满足这个性质的子图T'就是它的一个最小有根子图，也叫做G'的一棵生成树。
• DFS生成树：跟'搜索树'类似。按照深度优先遍历方式，在遍历中记录访问的所有顶点和边，就得到原图的DFS生成树。
• BFS生成树：按照宽度优先遍历方式，在遍历中记录访问的所有顶点和边，就得到原图的BFS生成树。
• (网络的)最小生成树：网络就是带权连通无向图。假定G是一个网络，G的一个生成树的所有边的权值之和就是这个生成树的权。G可能有不止一个生成树，这些生成树中权值最小的一个叫做G的最小生成树。
• Kruskal算法：一种构建最小生成树的简单算法。是基于简单连通分量的最低代价互联。简单说就是不停从边集E中找一条在T'=(V',{})中的两个端点是两个不同连通分量的边e,把这条边加入T'(这次操作使T'少了一个连通分量)。
• 连通分量的代表元：在Kruskal算法实现中有一个问题，怎么判断两个顶点在T'中是两个不同连通分量呢？一种有效方法就是为每个连通分量确定一个代表元，代表元相等就是互相连通，就是同一个连通分量。
• Prim算法：构建最小生成树的另一种算法，基于最小生成树的一种重要性质-MST性质。
• MST性质：设G=(V,E)是一个网络，U是V任意一个真子集，设边e=(u,v)属于E，其中u属于U，v属于V-U，（也就是说，边e的一个顶点u在U中，另一个不在），设满足e的边的集合是E1，边e'是E1中权值最小的一个，那么G必定有一棵包含边e'的最小生成树。
• 最短路径问题：对于带权有向图和网络(带权无向图)，从顶点v到v'的所有路径中长度最短的那条就是最短路径。找到最短路径的问题就是~。
• 带权图上的路径长度：边上附有权，路径长度就是路径上的所有边的权值之和。
• Dijkstra算法：求单源点最短路径，即从一个顶点出发到其余顶点的最短路径问题。(具体算法书上有，太多不打了。)
• Floyd算法：求任意顶点间的最短路径，即计算出各对顶点间的最短路径及其长度。（这个算法操作机械繁琐，缺乏直观，不适合人工操作，我不甚理解）(具体算法书上有，太多不打了。)
• AOV网：AOV网就是有向图的顶点表示活动，边表示活动先后顺序。
• 拓扑排序和拓扑序列：对于给定的AOV网N,如果N中的'所有'顶点能排出一个满足“若N中存在从顶端vi到vj的路径，那么在S里vi就排在vj之前”的线性序列S=vi0,vi1...,vin-1，就说S是N的一个拓扑序列，这个操作就是拓扑排序。(具体的拓扑排序算法书上有，太多了不打了。)
• 制约关系：一个活动发生了，另一个活动才能发生，这个关系就是~。
• AOE网(一类带权有向图)：AOE网就是带权有向图的顶点表示事件，边表示活动，边的权表示活动持续时间。
• 关键路径：完成整个工程的最短时间，就是从开始顶点到结束顶点的最长路径的长度。（这个算法我不甚理解）

---

2.

• 图略
• 图略
• 图略
• 不是，顶点b，e和它们之间的两个边

3.

• 假设有n个顶点，n-1<=边的个数<=n*(n-1)
• 可能有，可能没有
• 出度范围为[0,n-1]
• 入度范围为[0,n-1]

4.

• (n^2)/2,n*(n-1)

5.

• 答案和4一样

6.

• 环路是起点终点相同的无向图，要求的问题信息不足，最少是n个

7.

• 9

---

注意：在下面几道题，顶点我都用下标来表示，比如顶点v2，就用2来表示。

---

8.

• 0149
• 023149
• 02349
• 025649
• 02375649

9.

10.

• 图略
• 图略
• 014687523
• 0125 34678
• 用（一个顶点的下标，下一顶点的下标，两个顶点之间边的权）形式表示:（1,4,3）（3,6,4）（3,1,6）（2,5,6）（5,6,7）（7,8,8）（6,7,9）（2,0,9）
• （1,4,3）（1,3,6）（3,6,4）（6,5,7）（5,2,6）（6,7,9）（7,8,8）（2,0,9）

11.

• （0,2,5）（2,3,9）（0,5,9）（3，7，11）（3,1,12）（3,4,15）（4,9,19）（5,6,20）（9,8,32）

12.

• 0124 3765 89
• 0421 7368 59

13.

14.

15.

16.

17.

---

---

第八章、字典和集合

1.复习下面概念

• 数据存储和访问：~是计算机最基本的功能。
• 检索（检查）：找到数据的存储位置。知道了数据保存在哪里，只需要常量时间就可以得到它。
• 检索码（关键码）：检索时提供的信息。
• 关联数据：数据项由两部分组成，一是关键码，二是与关键码相关联的实际数据。
• 字典（查找表、映射、关联表）：支持基于关键码的数据存储与检索的数据结构。
• 静态字典：字典建立之后，内容和结构不在变化，主要操作只有检索，实现时只需考虑检索效率。（适合用最佳二叉排序树实现）
• 动态字典：字典初始创建之后，内容和结构将一直处于动态变动之中，主要操作有检索、插入、删除，实现时不仅要考虑检索效率，插入、删除效率也要考虑。
• 平均检索长度：在一次完整检索过程中，比较关键码的平均次数就称为~。
• 索引：做基于关键码的索引，就是要实现从关键码到数据存储位置的映射。这种映射就是索引。
• 关联：一个数据项就是一个二元组（关键码、值），称之为关联。
• 有序集合：元素之间存在某种顺序存储的集合。（比如整数的小于等于关系，字符串的字典序）
• 二分法检索：1.从元素范围中取出位置居中的那个数据项，用检索关键码和它比较，如果想等检索结束。如果检索关键码较大，则把检索范围修改为中间项之后的半区间；如果较小，则修改为中间项之前的半区间。2.重复步骤1,如果检索范围中已经没有数据了还没找到相等的关键码，就是检索失败结束。
• 判定树：用二叉树来表示关键码排序的顺序表字典，树中结点所标的数是数据项的关键码。（树中除叶结点外的每个分支结点都是一个关键码范围的居中位置的那个关键码，它的左子树是这个关键码范围的最小值，右子树是最大值）
• 散列表（哈希表）：如果数据项连续存储，而关键码就是存储数据的地址（或下标）。在这种情况下，基于关键码能最快找到所需的数据（O(1)时间）。但是，关键码不一定都是整数，可能是字符串，那就不能作为地址（下标）了。况且，即便关键码是整数，也可能因为取值太大而不适合作为地址（下标）。可以考虑通过一个变换（一个计算）把它们映射为一种下标。这样做，就把基于关键码的检索变为了基于整数下标（存储数据的地址）的直接元素访问，有可能得到一种高效的字典实现技术。
• 散列：散列表的基本思想：如果一种关键码不能或者不合适作为数据存储的下标，可以通过一个变换或者一种计算把它们映射成一种下标。
• 散列函数（哈希函数、杂凑函数）：从可能的关键码集合到一个整数区间（下标区间）的映射就是~。
• 冲突（碰撞）：通常情况下，散列函数h是从一个大集合到一个小集合的映射。这样就必不可免的出现多个不同的关键码被h对应到同一个下标位置的情况，也就是说，必然会出现key1 != key2，但是h(key1) = h(key2)的情况，人们就说这里出现了冲突（碰撞）。
• 同义词：出现key1 != key2，但是h(key1) = h(key2)的情况，人们就说这里出现了冲突（碰撞），也称key1和key2是散列函数h下的同义词。
• 负载因子：负载因子=（散列表中当时的实际数据项数）/（散列表的基本存储区能容纳的元素个数），~越大，越容易出现冲突。
• 数字分析法（仅适用于关键码集合已知）：对于给定的关键码集合，分析关键码中各位数字的出现频率，从中选出分布情况较好的若干数字作为散列函数的值。例子：我们专业的学号统一是 201517040xx ，xx是班级内学号，比如我就是20151704078，那么如果给定的关键码集合是我们这届测控专业的86名学生的学号，那么用数学分析法选取个十位作为散列函数的值，得到的h(k)集合就是{01,02，...，78，...86}。
• 折叠法：将较长的关键码切分为几段，再通过某种运算将他们合并。例如：关键码都是十一位整数，可以先把它们每三位切分为一段，再把得到的三位整数相加并舍弃进位，以得到的结果作为散列函数的值。实例：20 / 151 / 704 / 078，三位整数相加并舍弃进位：20+151+704+078（舍弃进位）= 843，这样就把11位整数映射到[0,999]的区间了。
• 中平方法：先求出关键码的平方，然后取出中间的几位作为散列值。

数学分析法、折叠法、中平方法都是适用于整数关键码的散列方法。对于整数关键码，散列函数的设计有两个追求：1.把较长的整数关键码映射到较小的区间；2.尽可能的消除关键码和映射值之间明显的规律性。通俗的说，散列函数的映射关系越乱越好，越不清晰越好。

• 除余法：关键码key是整数，用key除以某个不大于散列表长度m的整数p，以得到的余数作为散列地址（或者是余数+下标值）。为了存储方便，人们经常将m取为2的幂值，此时p可以取小于m的最大素数（就是m-1，h=key mod p；如果余数+下标值，并且连续表的下标从1开始，h=key mod p + i，i for [1,2,3,...]）。注意p不要取偶数，如果用偶数作为除数，就会出现偶数关键码映射到偶数散列值，奇数关键码映射到基数散列值的明显规律。除余法的缺点：相近的关键码将映射到相近的值。
• 基数转换法：基数转换法既适用于整数关键码，还能用于字符串关键码。 1.对于整数关键码：取一个正整数r，把关键码看做r进制的数，再把它转换为十进制或者二进制数。通常r取素数以减少规律性。例如：取r=13，对于关键码335647，计算得到：335647(13进制) = 713^0+413^1+6*132+513^3+313^4+3*135=6758172 (十进制)，这时的映射值的取值范围可能不合适，可以考虑用除余法、折叠法、或者删除几位数字的方法将其归入所需的下标范围。 2.对于字符串关键码：最常见的是把字符串中的每个字符看做一个整数（怎么看做呢？用字符的编码值，即ASCII码或者Unicode码），再取一个正整数x，把得到的整数关键码看做x进制的整数（建议取素数29或31为基数）。这样，就把字符串转换为了整数（x进制），再用整数关键码的散列方法把结果归入散列表的下标范围（比如除余法）。
• 内消解技术：在用散列技术实现字典时，会出现冲突。内消解方法就是在基本的存储区内部解决冲突问题。内消解的基本方法称为开地址法。开地址法的基本想法是：当准备插入数据却发现冲突时，设法在基本存储区（顺序表）里为需要插入的数据项另行安排一个位置。为此，需要设计一种系统的易于计算的位置安排方式，称为探查方式。探查方式又分为线性探查、双散列探查。（书中用实例详细讲解了两者和其各自优缺点。）（Python的dict、set就是基于散列表技术实现，采用的内消解技术解决冲突。）
• 外消解技术：在用散列技术实现字典时，会出现冲突。外消解方法就是在基本的存储区外部解决冲突问题。1.溢出区方法：另行设置一个溢出存储区，当插入数据项时没发生冲突就直接插入基本存储区，而当发生冲突时，就把相应数据和关键码一起存入溢出存储区。溢出存储区的数据项也是顺序排列。检索、删除操作就是先找到散列位置，如果那里有数据项，但是检索关键码和数据项关键码不匹配，就转到溢出存储区顺序检索，直到找到要找的关键码，或者确定相应数据不存在。缺点：当溢出区的数据越来越多时，字典的性能将会趋于线性（因为溢出区是顺序检索）。 2. 桶散列：散列表的每个元素只是一个引用域，引用着一个保存实际数据的存储桶。设计想法：所有的数据项都不存放在基本存储区中，而是另行存放，在散列表里保存对数据项的引用。桶散列中最简单的是拉链法：在拉链法中一个存储桶就是一个链接的结点表。字典中的数据项不保存在散列表的主存储区，而是存入相应结点表中的结点里，具有同样散列值的数据项都保存在这个散列值对应的链接表中。插入：先找到关键码的散列位置，把数据项插入到链接表的前端。检索：通过散列函数找到相应的结点表，顺序检查相匹配的数据项。删除就是先检索，再删除掉数据项。
• 溢出区方法：上面有
• 桶散列：上面有
• 拉链法：上面有
• 集合与元素：集合主要关注个体与个体的汇集之间的关系。集合是个体的汇集。元素就是个体。在计算机科学领域，具体的数据项就是个体，数据项的汇集就是集合。
• 属于关系：一个个体是一个集合中的元素，就说这个个体属于这个集合。
• 全集：当前的所有元素都包含的集合就是全集。
• 外延表示：明确列出集合中的所有元素。用一对花括号{}，在花括号中列出集合所有的元素，就是~。
• 内涵表示（集合描述式）：给出集合中所有元素应满足的性质。称为~或者描述式。
• 基数：一个集合中元素的个数称为这个集合的~。
• 空集：集合中不包含元素。
• 并集：S并T的元素或者是S的元素，或者是T的元素。
• 交集：S交T包含且仅包含那些既属于S又属于T的元素。
• 补集：S-T包含且仅包含那些属于S但是不属于T的元素。
• 排序线性表：有序集合+二分法
• 位向量：位向量是集合的一种特殊实现技术。如果程序中需要实现、使用的集合都是某个集合U的子集，那么：假设集合U元素个数是n，给集合U的每个元素确定一个编号作为这个元素的下标；对任何一个要考虑的集合S（肯定是U的子集），可以用一个n位的二进制序列vs来表示，方法是：对于集合U的每个元素，如果属于那么在vs中就是取值1，不属于就是取值0。二进制序列s就是位向量。
• 二叉排序树：是一种存储数据（结点存放关键码及关联的数据）的二叉树，把字典的数据存储和查询功能融合在二叉树的结构里。性质：一棵二叉排序树或者是空树，或者满足以下性质：其根结点保存这一个数据项（关键码及关联数据）；如果结点的左子树不空，那么其左子树的所有结点保存的关键码都小于它的关键码的值；如果结点的右子树不空，那么其右子树的所有结点保存的关键码都大于它的关键码的值；非空的左子树或者右子树也是二叉排序树。（递归结构）（~可以直接作为字典，把实际数据存放到结点中；也可以作为索引结构，实际数据另行存储，结点中存放的关键码所关联的是实际数据的存储位置信息。）
• 最佳二叉排序树：是使检索的平均比较次数达到最小的二叉排序树，即使关键码在扩充二叉排序树的平均检索长度E(n)的值达到最小。又分为简单情况（检索概率相同）、一般情况（检索概率不同）。
• 动态规划：在整个计算过程中，逐步建立并维持好一大批子问题的解，在每一部基于这些小的子问题的解构造出更大的子问题的解，最终构造出整个问题的解（对于最佳二叉排序树问题，就是维护较小的最佳二叉排序树）。在设计复杂算法是非常有用。
• 带权路径长度：
• 平衡二叉排序树（AVL树）：实际使用中非常需要既能够维持高效检索，由能够支持动态操作的排序树结构。_{是一类特殊的二叉排序树。}或者是空树，或者满足以下性质：其左右子树都是AVL树（递归结构），其左右子树的高度之差的绝对值不能超过1。
• 平衡因子（BF）：平衡二叉树的每个结点中会记录这个结点的平衡因子。一棵树的~就是其左子树的高度减去其右子树的高度，对平衡二叉树来说，BF取值为1，0，-1。
• 失衡和调整：在插入、删除等动态操作中，会改变树的结构，如果结点的平衡因子大于1或者小于-1，就是失衡。调整就是在发现失衡后，只需要在最小不平衡子树的根结点附近做局部调整，就可以把该子树的根的平衡因子的变为0（或者变为1或者-1就可以了），而且保证这棵子树的高度与插入之前相同且数据排序正确。
• 多分支排序树：一个结点里可能存出多个关键码，需要维持这些关键码和相应子树关键码的排序关系。包括B树、B+树。
• B树：一种动态的多分支排序树，通过多种调整多分支排序树结构的手段，来维护结点分支数，保证树具有良好结构。
• B+树：

---

2.

• 保持唯一性：O(n),O(n),O(n)
• 不~ ：O(n),O(1),O(n)

3.

• s1 : 10010 11110 0010
• s2 : 01100 01110 1011
• s3 : 11010 11100 0001
• 余下的略

4.

• a） 给定一组12个关键码的序列为[46,78,35,99,70,48,121,10,66,54,26,37]，用 k % 17 作为散列函数且采用线性探查法消解冲突，得到关键码相应存储位置的序列为[12,10,1,14,2,15,3,11,16,4,9,5]
• b） 采用h2=k % 5 + 2 的双散列技术消解冲突，得到关键码相应存储位置的序列为[12,10,1,14,2,6,4,3,15,5,9，？]，关键码37用该方法得不到存储位置，因为计算结果是一个循环‘3,5,2,4,6, 3,5...’，循环中的存储位置都已被占用。
• 6种

5.

• 没有第五题

6.

• 取中间位置的数4作为树根，向下递归构建出树。

7.

• 略

8.

• 二叉排序树删除很简单，不用想最佳二叉排序树一样还要考虑负载因子。

9.

• （5+4+3+2+1）*2=30种
• 基本想法：序列要满足：（#表示先于）65#7，65#96，7#43，43#36，43#57，96#74 ；序列一共7位，第一位必须是树根65，而且96#74，所以96不能在序列的首位和末位，其他5位都可以；74必须在96之后，这样就有5+4+3+2+1种序列；36和57的位置可以互换，所以总共有（5+4+3+2+1）*2=30种序列。

10.

• 修改： “采用字典序”我审题出错了，以为是要考字符串关键码的基数转换法...
• 先把字符串关键码转换为整数关键码，代码如下：

def str_hash(s):
    h1=0
    for c in s:
        h1=h1 * 29 + ord(c)
    return h1
L={'JAN' , 'FEB' , 'MAR' , 'APR' , 'MAY' , 'JUN' , 'JUL' , 'AUG' , 'SEP' , 'OCT' , 'NOV' , 'DEC'  }
print([str_hash(s.title()) for s in L])    

结果就是： [58161, 68935, 65737, 58027, 72844, 65735, 65157, 67684, 69426, 60216, 61897, 67691]
后面工作就很简单了，略。

11.

• 略

12.

• 四阶B树：树根（10 ）； 树根左子结点（3 5 7），树根右子结点（13 15 18）；树根左子结点的子结点依次为（1 2 ），（4），（6），（8 9），树根右子结点的子结点依次为：（11 12）（14） （16 17）（19 20）
• 四阶B+树：树根（10 11）； 树根左子结点（4 8 10），树根右子结点（14 18 20）；树根左子结点的子结点依次为（1 2 3 4），（5 6 7 8），（9 10），树根右子结点的子结点依次为：（11 12 13 14）（15 16 17 18） （19 20）

13.

• 我的思路：不妨设两个关键码分别为x，y且x>y ；检索关键码x的位置，用变量a记录x的结点位置，并用一个栈保存从树根到a的途径结点；如果a有子结点，对a的两个子树进行对y的检索，若y检索成功，结果就是a的父结点，结束。若a没有子结点或者a有子结点但y检索失败，就往下进行；取栈顶元素并用变量b表示，对b的另一个子树进行对y的检索，若y检索成功，结果就是b，结束。若b只有一个子树或者y检索失败，就继续进行这一步，直到检索成功，得到结果，结束。

---

第九章、排序

1.复习下面概念

• 排序问题：整理数据的序列，使其中元素按特定顺序排列的操作。
• 全序关系：集合S上的一个全序关系，记为≤，是集合S上的一种自反、传递、反对称的关系。对集合中的任意两个元素x，y，都有x≤y，或者y≤x 成立。
• 反对称关系：反对称就是如果a和b满足关系R，那么反个顺序，b和a肯定不满足关系R。R称为反对称关系。举个例子，真包含关系⊂是反对称的，A⊂B则B一定不⊂A；包含关系⊆不是对称也不是反对称的，称为非对称关系，因为A⊆B 不能判断B是否⊆A；相等关系=是对称的，因为A=B可以推出B=A 。
• 等价类：在实际情况中很多时候，需要考虑的序把被排序数据归结为一组(有序的)等价类，同属一类的数据元素都被认为是相等的。
• 排序方法（排序算法）：完成排序工作的方法。
• 堆排序算法：如果一个连续表里存储的数据是一个小顶堆，按照优先队列的操作方式反复弹出元素，就能得到一个递增序列。不难想象，这就形成了一种可用于完成对连续表中元素的排序工作的可行方法。
• 基于关键码比较的排序：就是根据记录中所考虑的那个关键码的序关系整理记录序列，使之成为按关键码排序的序列。
• 排序码：在一次排序中考虑的关键码。
• 内排序：在一次排序工作的执行过程中，如果待排序的记录全部保存在内存，这种工作就称为~。
• 外排序：针对外存（磁盘等）数据的排序工作称为~。
• 外排序算法：有些排序算法特别考虑到外存的特点，因此特别适合外存排序工作，这类算法也被称为外排序算法。
• 归并排序算法：
• 排序中的基本操作（关键码比较、数据记录移动）：确定数据的顺序关系；调整数据的位置 和/或 顺序。
• 最优排序算法：最理想的排序算法是O(n log n)时间，O(1)空间，稳定性，最好还具有适用性（不知道是否存在）。目前，蒂姆排序在实际应用中处于最优地位。
• 原地排序算法：排序工作可以在原序列（表）中完成，只需要几个简单变量作为操作中的临时存储。具有这种性质的算法也被称为~。
• 稳定性：序列中可能会存在排序码相同的记录，如果一个排序算法能够维持序列中所有排序码相同的记录的相对位置，就说这个排序算法是稳定的。
• 适应性：如果排序算法对接近有序的序列工作的更快，就说这种排序算法具有适应性。
• 插入排序：从序列的第二个元素开始，把它和之前的元素逐个比较，直到找到不大于之前的元素的位置，就把它插入到该位置。重复上个操作，直到未排序序列中的记录个数为0。排序完毕。
• 选择排序：每次从未排序序列中选出最小的纪录，把它放到已排序序列的后面。重复上个操作，直到未排序序列中只剩下一个记录。排序完毕。
• 交换排序（起泡排序）：比较序列中相邻记录，发现相邻的逆序对时，进行交换。通过反复的比较、交换，最终完成整个序列的排序工作。详细：起泡排序最多需要做n-1遍，每一遍都是一次完整的扫描，没一次完整扫描的成果是：1）减少了序列中的逆序对。2）把当时最大的记录放到已排序记录前面。（这也是为什么起泡排序能保证最多n-1遍）
• 分配排序（快速排序）：选择一个标准，把被排序序列中的记录跟这个标准进行比较，划分为大小两组，小的组排在前面。采用上个操作，递归的分别去划分得到的两组记录，直到每个记录组中最多包含一个记录时，整个序列的排序完成。

---

• 直接插入排序算法：上面有。
• 二分法插入排序算法：在已排序序列里检索元素的插入位置时，可以使用二分法。
• shell排序算法：采用一种变动间隔的排序技术，其中用简单插入排序作为基础算法，可以得到更高的操作效率。
• 直接选择排序算法：上面有。
• 树形结构：选择排序中，可以改变选择方式以提高排序效率。可以考虑堆排序算法。
• 交换和排序：通过不断交换序列中的逆序记录对，使序列渐渐的接近有序序列。
• 逆序：记录对的序为逆。
• 气泡排序算法：上面有。
• 交错排序算法：快速排序的表实现。很抽象，结合图像去理解。
• 快速排序：上面有。
• 划分：在快速排序中，把被排序序列中的记录和某个标准比较，使划分为两组。
• 归并排序算法：基于归并的思想也可以实现排序，称为归并排序。
• 归并操作：是一种典型的序列操作。其工作是把两个或更多有序序列合并为一个有序序列。
• 二路归并：初始时，把待排序序列中的n个记录看做n个有序的子序列，每个子序列长度为1；把当时序列组里的有效子序列两两归并，完成后，子序列个数减半，每个子序列长度为原来2倍；重复上个操作，最终得到一个长度为n的有序序列。（代码很复杂，仔细推导才能理解）
• 分配排序：重题，上面有。
• 多轮分配和收集：采用元素适合分配排序的‘元组’作为关键码，通过多轮分配和收集，完成以这种元组为关键码的记录的排序工作。
• 高位优先算法：从元组的最高位（最左位）开始考虑关键码元素，称为~。
• 低位优先算法：从元组的最低位（最右位）开始考虑关键码元素，称为~。
• 基数排序：如果每位关键码都是数字，那么关键码元组可以看做是以某种进制表示的一个整数，这样排序过程就是从元组元素的低到高逐位进行收集和分配。这样的处理过程就像是按照技术逐位处理，因此这种多轮分配排序也被称为基数排序。
• 混成排序算法：实际排序中可以采用多种算法的组合，将其称为混成方法。
• 蒂姆排序算法：Python内置的排序函数sort，表list类的对象也有一个sort方法，这两者同用一个排序算法——蒂姆排序，是一种混成排序算法。~ = 插入排序 + 归并排序
• 主关键码：实际应用中，数据记录通常有一个主关键码，例如各种唯一标识符，比如学号、身份证号、手机唯一标识符等。
• 其他关键码：也经常需要把记录中的其他成分作为排序码，比如学生的姓名、性别、成绩等排序。

---

2.

• 蒂姆排序（序列太长，且要求最快找到）

3.

• 简单插入排序（和0比较），n次 。（只是用O(1)空间，O(n)时间）

4.

• 快速排序，划分规则：-10，10 。（线性时间，尽量快速）

5.

• 归并排序，O(n log n) 。（比较次数少于2n-3，也就是说不能用选择排序的思想）

6.

• 快速排序，j=( len(lst)-1 ) / 2 。（找到序列的中位值，线性时间）