USTC-算法基础课-2013-第一次习题课.ppt

9.3-6： 如果 k == 1 ，return i = k / 2 ……O(1) 将数组 a 划分成两部分 A 和 B，使得 A 中所有元素不大于 B，且 A 中元素的个数为 tmpSize = (n / k) * i。 ……O(n)? 在 A 中找第 i 分位数 ……规模减小为 k / 2 输出a[tmpSize - 1] ……O(1) 在 B 中找第 k - i 分位数 ……规模减小为 k / 2 由上面的分析，这个算法的时间复杂度满足题设要求O(n lg k)。? 如果 n/k 不是刚好整除（假设 x = n%k，x != 0），那么我们定义k分位数的分组为：? 前 x 组每组的元素个数为?n/k? + 1，后 k - x 组每组元素个数为?n/k?。? 比如15个元素分为4组，则每组为 4 4 4 3 个元素。? 对应的，将tmpSize更改为 (n / k) * i + (n % k i ? n % k : i)? （ PS：若 k==n ，这实际上是一个O(n lg n)的排序算法。） 9.3-8设X[1..n]和Y[1..n]为两个数组，每个都包含n个已排好序的数。给出一个求数组X和Y中所有2n个元素的中位数的，O(lgn)时间的算法。 假设中位数m在X中，为X[k]，则X中的k个元素小于等于m，n-k个元素大于等于m。若两个数组合并，则必有n个元素小于等于n，n个元素大于等于m。所以Y中有n-k个元素小于m，k个元素大于等于m。 9.3-8分治法 先分别求出X和Y的中位数 比较两个数的大小，如果相等就返回，如果不等的话，去掉较大中位数所在的那个数组的较大的一半，去掉较小的中位数所在的数组的较小的一半， 在规模减半的两个数组上递归调用， 如果一直没有遇到正好相等的情况，那么递归到最后剩下四个数，则返回第二个数。因为这两个数组都是有n个元素，所以最终返回的必然是2n个数中的下中位数。 12.2-1 二叉查找树应满足： 左子树中的节点值都不大于当前节点的值。 右子树中的节点值都不小于当前节点的值。 查找过程应满足： 若当前节点的值等于待查找的值，返回。 若当前节点的值大于待查找的值，那么接下来应该找当前节点的左子结点。 都不满足，接下来查找当前节点的右子结点。 由这两点易知，c，e不满足。 12.3-4 假设另一种数据结构中包含指向二叉树中某结点y的指针，并假设用过程TREE-DELETE来删除y的前驱z。这样做会出现哪些问题？如何改写TREE-DELETE来解决这些问题？ 12.3-6 当TREE-DELETE中的结点z有两个子结点时，可以将其前驱（而不是后继）拼接掉，有些人提出了一种公平的策略，即为前驱和后继结点赋予相同的优先级，从而可以得到更好的经验性能。那么，应如何修改TREE-DELETE来实现这样一种公平的策略？ 生成一个随机数，从而决定是删除后继节点还是前驱。 自己定义一个priority，可以是左右子树的高、左右子树的大小或者等概率随机选择一个。 很多人没有考虑a=0的情况，还有要包括C[a] * 6.2-4 对iheap-size[A]/2，调用MAX-HEAPIFY(A,i)的结果怎样？ 堆中的元素不需要调整 6.2-5 MAX-HEAPIFY的代码效率较高，但第10行中的递归调用可能例外，它可能使某些编译程序产生低效的代码。请用迭代的控制结构(循环)取代递归结构，从而写一个更为高效的MAX-HEAPIFY。 MAX-HEAPIFY(A,i,n) while i≤n/2 do l←left(i);r←right(i) if l≤n and A[l]A[i] then largest←l else largest←i if r≤n and A[r]A[largest] then largest←r if largest≠i exchange(A[i],A[largest]) else break 6.3-2在BUILD-MAX-HEAP的第2行代码中，为什么希望循环下标i从