賺批幣的時間又到了… 這次拖了一陣子才翻，該不會大家都已經寫出來了吧（想必不太可能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)