赚批币的时间又到了… 这次拖了一阵子才翻，该不会大家都已经写出来了吧（想必不太可能XD） ==== 6.1 排序（Sorting）与杂凑（Hashing） (1) 感谢名沅帮忙翻译这一题 考虑以下修改过的随机挑选基准(pivot)的快速排序法，以寻找第k小的元素。当k被 平均随机挑选时（「平均」指的是每个元素被挑选到的机率是相同的），以C(N)表示使用 此演算法时，预期的比较次数。试导出C(N)的封闭型式(closed-form)解。你可以在你解 答中使用调和级数的和 H(N)=Σ(n=1 to N)1/n, which is O(log N)。 Quick-k(阵列 a, 整数 N, 整数 k) /* 1 <= k <= N */ ‧从a[0]至a[N-1]平均随机选择一个元素作为基准值(pivot) ‧对基准值以外的a[0]至a[N-1]和基准比较（一共比较N-1次）， 比基准值小的随机存到另一个M-1个元素长的阵列left； 比基准值大的随机存到另一个N-M个元素长的阵列right。 如果 k = M 就 回传 基准值 否则如果 k < M 就 回传 Quick-k(left, M-1, k) 否则 回传 Quick-k(right, N-M, k-M) 结束如果 提示：Quick-k参数为N, k时，令其比较次数为 T(N, k)。从此演算法可得 1 k-1 N T(N, k) = --- ( Σ T(N-M, k-M) + Σ T(M-1, k) ) + (N-1) 以及 T(1, 1) = 0 N M=1 M=k+1 1 N 我们的目的是藉由 C(N) = --- Σ T(N, k) 计算 C(N)。 N k=1 关於closed-form，在 http://mathworld.wolfram.com/Closed-FormSolution.html 网页上的解释是这样： An equation is said to be a closed-form solution if it solves a given problem in terms of functions and mathematical operations from a given generally accepted set. For example, an infinite sum would generally not be considered closed-form. However, the choice of what to call closed-form and what not is rather arbitrary since a new "closed-form" function could simply be defined in terms of the infinite sum. 简而言之，就是有限的数学符号组合而成的解。（吧） (2) 在使用比较排序（comparision sort）排序 N 个布林元素的问题当中，请证明 该问题只需要 Ω(N) 次的比较。 译注：布林元素指的是 { True ,False }，也可以想成 { 0, 1 }。 (3) 给予两个长度为 N 且已经排序好的阵列 A 与 B。请用 C 语言或任何的虚拟码 （pseudo-code）来实作出可以找出 A∪B 的中位数且时间复杂度为 O(log N) 的演算法。请简要的解释为何该演算法之时间复杂度为 O(log N)。 (4) 给予一个由 N 个排序过的元素仅接着 M 个没有排序的元素所组成的阵列。对於 下列数种情况，你会怎麽排序这一整个阵列？ (a) M = O(N) (b) M = O(log N) (c) M = O(1) (5) 杂凑函数（hashing function）除了可以用来做出有效率的储存，还可以用来设计 出有效率的演算法。请用任何的搜寻引擎搜寻 "Rabin-Karp String Matching Algorithm" 并比较其与 KMP 演算法的不同之处。请注意你必须以自己的话来完成 这一题，并附上你所学习的网站。 (6) 考虑另一个替代的的二次探测法（quadratic probing）其定义 h_i(key) = (h(key) + 16 * i^2) mod P 其中 P 是一个奇数的质数，i 在 [0, m] 之内。 若 m = (P - 1) / 2，i, j 在 [0, m] 之内且 i =/= j，请证明对於所有可能的 i 与 j， h_i(key) =/= h_j(key)。 (7) 对於下列 32 个 C 语言的关键字，建立一个完美并有效率的的杂凑函数。 auto, break, case, char, const, continue, default, do, double, else, enum, extern, float, for, goto, if, int, long, register, return, short, signed, sizeof, static, struct, switch, typedef, union, unsigned, void, volatile, while 你需要解释你的杂凑函数为何完美且有效率。 6.2 快速排序（Quick Sort） 实作下列排序法中的任两个：希尔排序（shell sort）、堆积排序（heap sort）、 合并排序（merge sort）、内部为计数排序的基数－16排序（radix-16 sort with counting sort）。你可以选择任意程度的实现细节（应该是指可以任意的使用STD 吧）但请附上清楚的说明。然後写一个名为 hw6_2 的程式来比较你实做出来的排序 与 C 当中的 qsort 或是 C++ 中的 std::sort。测试的资料为一由 32 位元的无符 号整数（32-bit unsigned interger）随机组成的阵列。测试当阵列大小为 {16, 64, 255, 1024, 4096, 16384 } 时，你所实作出来的两个排序以及 C 当中的 qsort 或是 C++ 中的 std::sort 的执行时间并将结果画成像课本 372 页中图 7.18 的形式。 简要地说明你的发现。 6.3 二元平衡搜寻树（Balanced Binary Search Trees） libavl （http://www.stanford.edu/~blp/avl/）是一个很好用的二元搜寻树的函 式库。像下面所列出的简短程式码就可以建构一个 16 个整数的 AVL 树（AVL tree） 并将其印出来： #include <stdio.h> #include <stdlib.h> #include "avl.h" void postorder_interger_avl(const struct avl_node *node){ if(node == NULL) return; printf("%d ", *((int *)node->avl_data)); if(node_avl_link[0] != NULL || node_avl_link[1] != NULL){ putchar('('); postorder_integer_avl(node->avl_link[0]); putchar(','); putchar(' '); postorder_integer_avl(node->avl_link[1]); putchar(')'); } } int int_compare(const void *pa, const void *pb, void *param) { int a = *(const int *)pa; int b = *(const int *)pb; if(a < b) return -1; else if(a > b) return +1; else return 0; } int main(){ struct avl_table *tree; tree = avl_crete(int_compare, NULL, NULL); int i; for(i = 0; i < 16; i++){ int *element = (int *)malloc(sizeof(int)); *element = i; void **p = avl_probe(tree, element); } postorder_integer_avl(tree->avl_root); puts(""); return 0; } 请注意 libavl 的使用手册可能难以阅读；上面的程式码修改自 libavl 当中的 avl-test.c。当上面的程式码与 avl.c 编译後，会正确的印出一棵 AVL 树： 7 (3 (1 (0 , 2 ), 5 (4 , 6 )), 11 (9 (8 , 10 ), 13 (12 , 14 (, 15 )))) 在这题当中，你需要下载 libavl 并实作出三种不同的树：高度限制二元搜寻树 （height-bounded binary search tree）、ALV 树以及红黑数（Red-Black tree）， 其分别位於 "bst.c"、"avl.c" 以及 "rb.c" 中。 (1) 写一个名为 hw6_3_1 的程式将 6.1(7) 当中所提供的 C 的关键字依其列出的顺序 插入上述的三种树当中。并以上面的输出格式将这三种树的最後结果印出来。 (2) 写一个名为 hw6_3_2 的程式将 6.1(7) 当中所提供的 C 的关键字随机调换其顺序 後再插入上述的三种树当中。将此步骤重复 10000 次并记录这三种树的最大高度、 最小高度以及平均高度。完成下列的表格并简要的说明你的发现。 +--------------------+----------------+----------------+----------------+ | tree type | maximum height | minimum height | average height | +--------------------+----------------+----------------+----------------+ | height-bounded | | | | | binary search tree | | | | +--------------------+----------------+----------------+----------------+ | AVL tree | | | | +--------------------+----------------+----------------+----------------+ | Red-Black tree | | | | +--------------------+----------------+----------------+----------------+ 如果你在使用或是编译 libavl 上有任何问题，请与 TA 讨论。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.214.43 ※ 编辑: syuusyou 来自: 140.112.214.43 (06/11 23:38)