QuickSort的averagetimecomplexity为O(nlogn)，但是它的worstcase.doc

試畫出下列代數式(algebraic expression)所對應的expression tree (a) (7 + (6 – 2)) – (x – (y – 4)) (b) 3 – (x + (6 ( (4 ( (2 – 3))) (c) ((2 + x) - (2 ( x)) – (x - 2) (d) (3 – ( 2 – (11 – (9 – 4)))) ( (2 + (3 + (4 + 7))) (e) ((2 ( x) + (3 – (4 ( x))) + (x – ( 3 ( 11)) 試求出下列代數式(algebraic expression)的值為何？ (a) ( - + 3 4 – 7 2 ( 12 ( 3 – 6 4 (b) 4 3 2 ( - 5 ( 4 2 ( 5 ( 3 ( ( (c) 3 7 ( 4 - 9 ( 6 5 ( 2 + ( (d) ( - ( 3 x ( 4 y + 15 ( 2 - 6 y，假設x = 2, y = 3 (e) x 2 - 3 + 2 3 y + - w 3 - ( (，假設x = 7, y = 2, w = 1 試利用下列的Huffman tree轉換對應的訊息 (a) 將1111101110轉換為明文 (b) 將1100101110轉換為明文 (c) 將11101011110轉換為明文 (d) 將1101111101110轉換為明文 (e) 將CARE轉換為二進位碼 (f) 將SEA轉換為二進位碼 (g) 將ACE轉換為二進位碼 (h) 將CASE轉換為二進位碼 假設字母A, B, C, …之出現頻率分別如下，則對應的Huffman tree和編碼為 (a) 2, 4, 6, 8, 10 (b) 4, 6, 8, 14, 15 (c) 1, 4, 9, 16, 25, 26 (d) 10, 12, 13, 16, 17, 17 假設數個排序好的串列(list) A, B, C, …的大小分別如下，想要利用合併排序法(merge sort)來排序這些資料，試問其排序的順序和需要多少次的比較才能完成？ (a) 20, 30, 40, 50 (b) 15, 25, 35, 40, 50 (c) 20, 40, 60, 70, 80, 120 (d) 10, 30, 40, 50, 50, 50, 70 試利用下列的二元樹回答下列的問題： (a) 求出中序(inorder or infix)走訪的順序 (b) 求出前序(preorder, prefix, or Polish form)走訪的順序 (c) 求出後序(postorder, postfix, or reverse Polish)走訪的順序 (i) (ii) (iii) (iv) 假設輸入資料的順序如下，試建構出對應的二元搜尋樹(binary search tree) (a) list, static, or, char, this, endl, heap, do, parameter, else (b) object, char, variable, string, pointer, function, virtual, Boolean, parse, global, template, class, range, array (c) 14, 17, 3, 6, 15, 1, 20, 2, 5, 10, 18, 7, 16 (d) 18, 9, 27, 20, 30, 15, 4, 13, 25, 31, 2, 19, 7, 5, 28 試以二項式定理(binomial theorem)求解下列各題 (a) (x – y)9中的x4y5的係數 (b) (x + 2y)10中的x6y4的係數 試求巴斯卡三角形(Pascal’s Triangle)第七列的值為何？ 試以二項式定理(binomial theorem)求解下列各題 (a) C(n, 0) + C(n, 1) + … + C(n, n) = 2n (b) C(n, 0) - C(n, 1) + C(n, 2) - C(n, 3) +… + (-1)n C(n, n) = 0 (c) 20 C(n, 0) + 21 C(n, 1) + … + 2n C(n, n) = 3n 一個袋子中裝有紅、黃、藍、白顏色的球，試問至少要抽出幾顆球，才能保證可以得到三顆同顏色的球？。 試問你們的班級至少要有多少學生，才能保證至少有5個同學是同一個月出生的？ 6個人想要湊錢買禮物，發現他們一共只有2,161元，試證明他們至少有