导论

# 6.1 堆及堆的性质 **（二叉）堆**可以看作完全二叉树，其存储结构通常是**数组**，表示堆的数组A中有两个重要属性：$A.length$表示数组元素的个数；$A.heap-size$表示有多少个堆元素在数组中，$0 \le A.heap-size \le A.length$。 ![Figu ......

# 7.1 快速排序的描述 对一个典型的子数组$A[p..r]$进行快速排序的三步分治过程： - **分解**：数组$A[p..r]$被划分为两个（可能为空）的子数组$A[p..q-1]$和$A[q+1..r]$，使得$A[p..q-1]$中的每一个元素都小于等于$A[q]$，而$A[q+1..r] ......

# 前言 此前我们已经学习了几种$\Omicron(n \log n)$的排序算法，这些排序算法都有一个有趣性质，在排序的最终结果中，各元素的次序依赖于它们之间的比较，我们将这类排序称为**比较排序(comparison sort)**。 8.1节将要证明**对包含$n$个元素的输入序列，在最坏情况 ......

一个包含 $n$ 个元素的集合中的第 $i$ 个**顺序统计量**指集合中的第 $i$ 小的元素。**最小值**是第 $1$ 个顺序统计量（$i= 1$），**最大值**是第 $n$ 个顺序统计量（$i = n$）。 9.1节将讨论从集合中找出最小值和最大值的问题。9.2节将分析一个实用的算法，它在 ......

# 三、当元素 A[i] 比其孩子的值都大时，调用 MAX-HEAPIFY(A.i)会有什么结果? ## 文心一言： 当元素 A[i] 比其孩子的的值都大时，调用 MAX-HEAPIFY(A, i) 会将 A[i] 与其孩子中的最小值进行交换，并将 A[i] 视为新的根节点。这个操作会使得以 A[i ......

# 二、参考过程 MAX-HEAPIFY，写出能够维护相应最小堆的 MIN-HEAPIFY(A，i)的伪代码，并比较 MIN-HEAPIFY 与 MAX-HEAPIFY 的运行时间。 ## 文心一言： MIN-HEAPIFY(A, i)的伪代码如下： 1.将节点i及其子树中的最小元素交换到根节点i； ......

# 一、参照图6-2的方法，说明 MAX-HEAPIFY(A，3)在数组 A=(27，17，3，16，13，10，1，5，7，12，4，8，9，0)上的操作过程。 ## 文心一言： 下面是 MAX-HEAPIFY(A, 3) 在数组 A = (27, 17, 3, 16, 13, 10, 1, 5, ......

# 值为的数组是一个最大堆吗? ## 文心一言： 是的，这个数组是一个最大堆。 最大堆是一种特殊的二叉树，它满足以下性质：对于任意节点 x，其子节点 y 的值都小于等于 x 的值。 我们可以使用数组来表示最大堆的节点，其中根节点存储在数组的第一个位置，而其他节点存储在数组的后续位置。在这个最大堆中， ......

# 五、一个已排好序的数组是一个最小堆吗? ## 文心一言： 一个已排好序的数组不一定是一个最小堆。最小堆是一种特殊的二叉树，它满足以下性质：对于任意节点 x，其父节点 y 的值都小于等于 x 的值。而一个已排好序的数组只是一个有序数组，它满足任意的元素都是按从小到大的顺序排列的，但并不一定满足最小 ......

# 四、假设一个最大堆的所有元素都不相同，那么该堆的最小元素应该位于哪里? ## 文心一言： 最大堆的最小元素位于堆的根结点。由于最大堆的性质，根结点是堆中所有元素的最大值，因此它也是堆中所有元素的最小值。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/80b9f ......

# 三、证明:在最大堆的任一子树中，该子树所包含的最大元素在该子树的根结点上。 ## 文心一言： 在最大堆中，根结点是整个堆中最大元素的孩子，因此它包含的最大元素是在该子树的根结点上。 我们可以通过递归的方式证明任意子树中的最大元素都在该子树的根结点上。假设我们已经证明了深度为 d-1 的子树中的最 ......

# 一、在高度为h的堆中，元素个数最多和最少分别是多少? ## 文心一言： 在高度为 h 的二叉搜索树（BST）中，元素个数最多和最少的情况分别如下： 1.最多情况：当每个节点都包含两个子节点时，BST 中的元素个数最多。此时，BST 中的元素个数为 2^(h+1) - 1。 2.最少情况：当 BS ......

# 七、为使特征序列长度的下界变得更精确，请说明在 n 次硬币的公平抛掷中，不出现比Ign - 2lglgn 更长的连续正面特征序列的概率小于 1/n。 ## 文心一言： 在 n 次硬币的公平抛掷中，每个硬币正、反面朝上的概率均为 1/2。让我们考虑一个事件 A，其表示在 n 次抛掷中不出现比连续 ......

# 分段 根据前面介绍到的基址+界限寄存器对的方式，虽然很好的解决了地址转换的问题，但是可以看到，它也带来了一个问题：内存浪费。 根据前面介绍到的那种内存分配处理方式，堆和栈之间会有大量的空闲空间，而前面的介绍中，这些空间都会被一次性装入内存中，那在程序运行的初期，就会有大量没有被使用的内存被强行占 ......

# 六、假设将n个球投人 n 个箱子里，其中每次投球独立，并且每个球等可能落入任何箱子。空箱子的数目期望是多少?正好有一个球的箱子的数目期望是多少? ## 文心一言： 这是一个典型的概率问题。首先，我们可以通过简单的计算来理解问题的背景。假设我们有n个球和n个箱子，每个球被投人到箱子里的概率是相等的 ......

# 第1部分 虚拟化 # 第2部分 并发 **线程和进程的区别**： > [线程与进程，你真得理解了吗](https://blog.csdn.net/mu_wind/article/details/124616643) - **本质区别**：进程是操作系统进行资源分配和调度的基本单位，线程是处理器任 ......

# 五、在大小为n的集合中，一个k字符串构成一个k排列的概率是多少?这个问题和生日悖论有什么关系? ## 文心一言： 在大小为n的集合中，一个k字符串构成一个k排列的概率是1/k!，这是由于排列的总数是k!，而每个字符串被选中的概率是相等的，因此每个字符串构成一个排列的概率是1/k!。 这个问题和生 ......

# 四、一次聚会需要邀请多少人，才能让其中 3 人的生日很可能相同? ## 文心一言： 为了解决这个问题，我们需要先计算出所有可能的生日组合数，然后计算出其中生日相同的组合数。 已知需要邀请的人数为：23人 根据组合数公式，可计算出所有可能的生日组合数： 2.58520167*10^{22} 根据生 ......

# 三、在生日悖论的分析中，要求各人生日彼此独立是否很重要?或者，是否只要两两成对独立就足够了?证明你的答案。 ## 文心一言： 在生日悖论的分析中，要求各人生日彼此独立是非常重要的。这是因为，如果各人生日不是独立的，而是存在一定的相关性，那么就会影响到概率的计算，从而影响到生日悖论的分析结果。 具 ......

# 二、假设我们将球投入到b个箱子里，直到某个箱子中有两个球。每一次投掷都是独立的并且每个球落入任何箱子的机会均等。请问投球次数期望是多少? ## 文心一言： 这是一个典型的鸽巢原理（Pigeonhole Principle）问题。假设每次投球时，每个箱子有1/b的概率被选中。我们设投球次数为x。 ......

# 一、一个屋子里必须要有多少人，才能让某人和你生日相同的概率至少为1/2? 必须要有多少人，才能让至少两个人生日为 7月 4 日的概率大于 1/2? ## 文心一言： 一个屋子里必须要有多少人，才能让某人和你生日相同的概率至少为1/2？ 答案：23人。 证明：假设有n个人，生日都在一年365天当中 ......

# 六、请解释如何实现算法 PERMUTE-BY-SORTING，以处理两个或更多优先级相同的情形。也就是说，即使有两个或更多优先级相同，你的算法也应该产生一个均匀随机排列。 ## 文心一言： 算法 PERMUTE-BY-SORTING 是一种基于排序的随机排列算法，它通过将输入数组中的元素按照优先 ......

# 五、证明:在过程 PERMUTE-BY-SORTING的数组 P中，所有元素都唯一的概率至少是1-1/n。 ## 文心一言： 证明： 在过程PERMUTE-BY-SORTING中，对于输入数组P中的每个元素，其出现次数为1，因此对于每个元素，在排序后的数组中，它出现的位置是唯一的。 假设在排序后 ......

# 一、Marceau 教授不同意引理 5.5 证明中使用的循环不变式。他对第1次送代之前循环不变式是否为真提出质疑。他的理由是，我们可以很容易宣称一个空数组不包含0排列。因此一个空的子数组包含一个0排列的概率应是 0，从而第 1次选代之前循环不变式无效。请重写过程 RANDOMIZE-IN-PLA ......

# 四、利用指示器随机变量来解如下的帽子核对问题(hat-heck problem):n位顾客，他们每个人给餐厅核对帽子的服务生一顶帽子。服务生以随机顺序将帽子归还给顾客。请问拿到自己帽子的客户的期望数是多少? ## 文心一言： 我们可以将这个问题转化为求解在指示器随机变量基础上的期望值。 已知有n ......

# 三、利用指示器随机变量来计算掷n 个骰子之和的期望值。 ## 文心一言： 为了计算掷n个骰子之和的期望值，我们需要先了解一个重要的概念：指示器随机变量。 指示器随机变量是一种特殊的随机变量，它只有两个取值：0和1。通常用I来表示指示器随机变量，它的取值为1表示事件发生，取值为0表示事件未发生。在 ......

## 二、在 HIRE-ASSISTANT 中，假设应聘者以随机顺序出现，你正好雇用两次的概率是多少？ ## 文心一言： 我们可以先计算出在HIRE-ASSISTANT中，雇佣一个应聘者的概率为3/4，然后计算出雇佣两次应聘者的概率为3/4 * 3/4 * 2。 已知在HIRE-ASSISTANT中 ......

# 一、在 HIRE-ASSISTANT 中，假设应聘者以随机顺序出现，你正好雇用一次的概率是多少？正好雇用 n 次的概率是多少? ## 文心一言： ![在这里插入图片描述](https://img-blog.csdnimg.cn/376d65c524dd4dbb9cabc0327d1d9ea7.p ......

# 三、假设你希望以1/2的概率输出0与 1。你可以自由使用一个输出0或1的过程 BIASED-RANDOM。它以某概率 p 输出1，概率 1-p 输出0，其中 0 0.5，则返回 0。 3.如果 p < 0.5，则返回 1。 这种算法是无偏的，因为它不考虑 BIASED-RANDOM 过程的输出， ......

# 二、请描述 RANDOM(a，b)过程的一种实现，它只调用 RANDOM(0，1)。作为a和b的函数，你的过程的期望运行时间是多少? ## 文心一言： 假设我们有一个伪随机数生成器，可以生成在[0,1)范围内的随机数。那么我们可以使用以下算法实现从一个[a, b]范围内的随机数： 1.首先生成一 ......