計概16-05雜湊－公職試題

【選擇題】

【B】01.一個具有十個空間(Entries)的雜湊表(Hash Table)，已知資料的鍵值(Keys)為24、37、54、66、97、124、224，透過「除以10取餘數」的方法作為雜湊函數，且以分別鏈結法(Separate Chaining)處理碰撞(Collision)，此雜湊表進行上述資料的存放時，將發生幾次碰撞？ (A)3 (B)4 (C)5 (D)6。[109地方四等資處]

h(24) = 24 mod 10 = 4

h(37) = 37 mod 10 = 7

h(54) = 54 mod 10 = 4

h(66) = 66 mod 10 = 6

h(97) = 97 mod 10 = 7

h(124) = 124 mod 10 = 4

h(144) = 144 mod 10 = 4

54、124、224各碰撞24一次，97碰撞37一次，共碰撞4次。

 

【A】02.有關密碼學的雜湊函數(Hash Function)，下列敘述何者正確？ (A)安全的雜湊函數具有單向函數(One-way Function)特性，且能抵抗碰撞攻擊(Collision Resistance) (B)AES與SHA都是密碼學上的安全雜湊函數，而AES安全度更高 (C)是具有金鑰(Key)的一種密碼元件 (D)是一種能夠具備驗證資料來源能力的密碼技術。[110地方四等電子]

(B)AES是對稱式加密法。(C)雜湊函數不需密鑰。(D)雜湊不可反逆，無法由輸出反推輸入值。

 

【B】03.如果要儲存約10000個數字供後續搜尋，下列那種資料結構的平均搜尋速度最快？ (A)二元搜尋樹(binary search tree) (B)雜湊表(hash table) (C)佇列(queue) (D)堆疊(stack)。[110身心四等]

雜湊搜尋法：應用資料中某欄位之值代入事先設計之雜湊函數，計算資料儲存位置，應用時以資料鍵值(key value)轉換。

 

【D】04.使用雜湊函式可隨機存取檔案中的一筆紀錄，但可能產生相同位址，導致碰撞。下列何者不能解決位址碰撞的問題？ (A)當產生相同位址時，可將後來發生的位址之紀錄移到另一個未被占據的位址處 (B)當產生相同位址時，可利用鏈結串列解決法 (C)當產生相同位址時，可利用雜湊桶解決法 (D)當產生相同位址時，可將後來發生的位址之紀錄覆蓋到原來被占據的位址處。[110國安五等]

不能直接覆蓋，否則原來的資料會消失。

 

【C】05.關於雜湊演算法(Hash function)的性質，下列何者正確？ (A)RC4為一種雜湊演算法 (B)雜湊演算法可加密資料，提供保密性 (C)給定SHA3雜湊演算法的輸出值，目前尚無有效率的方法反推其輸入值 (D)目前尚無有效率的方法，找到兩個不同的輸入有相同的MD5值。[110普考電子]

雜湊演算法之不可反逆特性，無法由輸出反推輸入值。

 

【C】06.保護資料完整性最基本的方式就是使用密碼學的雜湊函數。請問下列關於雜湊函數的描述，何者錯誤？ (A)修改輸入中的任一字元都可以得到完全不相干的輸出 (B)雜湊函數是不可逆的函數 (C)不同的輸入一定可以得到不同的輸出 (D)相同的輸入一定可以得到相同的輸出。[111身心五等]

不同的輸入不一定可以得到不同的輸出

 

【D】07.下列那一個結構，採取空間換取時間的策略，藉以提昇在該結構中搜尋資料、新增、刪除的時間複雜度？ (A)二元搜尋樹(Binary Search Tree) (B)紅黑樹(Red-Black Tree) (C)有序鏈結串列(Sorted Linked List) (D)雜湊表(Hash Table)。[113原民四等]

雜湊表(Hash table)是將鍵(Key)值透過雜湊函式(hash function)映射(map)到其在表中的對應位置，加快搜尋速度。

 

【C】08.若一個具有10個空間的雜湊表(Hash Table)tb，透過「除以10取餘數」的方法作為雜湊函數，且以線性探測法(Linear Probing)處理碰撞(Collision)，將資料鍵值(Key)32、14、72、53、95、64、86依序儲存至雜湊表tb，則資料鍵值86儲存的位址為何？ (A)tb[6] (B)tb[7] (C)tb[8] (D)tb[9]。[113關務四等]

32 % 10=2 → 存tb[2]

14 % 10=4 → 存tb[4]

72 % 10=2 → 存tb[2] → 和32碰撞，位址+1存tb[3]

53 % 10=3 → 存tb[3] → 和72碰撞，位址+1存tb[4] → 和14碰撞，位址+1存tb[5]

95 % 10=5 → 存tb[5] → 和53碰撞，位址+1存tb[6]

64 % 10=4 → 存tb[4] → 和14碰撞，位址+1存tb[5] → 和53碰撞，位址+1存tb[6] → 和95碰撞，位址+1存tb[7]

86 % 10=6 → 存tb[6] → 和95碰撞，位址+1存tb[7] → 和64碰撞，位址+1存tb[8]

tb[0]=空，tb[1]=空，tb[2]=32，tb[3]=72，tb[4]=14，tb[5]=53，tb[6]=95，tb[7]=64，tb[8]=86，tb[9]=空

留言

張貼留言

這個網誌中的熱門文章

計概16-09後序－公職試題

圖片
【選擇題】 【 C 】 01. 以後序 (postorder) 方式走訪下圖中的運算樹，且輸出走訪到的節點內容，下列何者為輸出的字串？ (A)*A+BC (B)A*B+C (C)ABC+* (D)ABC*+ 。 [109 地方四等電子 ] 後序走訪順序：左子樹 → 右子樹 → 根節點。   【 D 】 02. 某二元樹有 3 個節點，經後序走訪 (postorder traversal) 結果輸出 C 、 B 、 A ，該二元樹有幾種可能？ (A)3 (B)9 (C)7 (D)5 。 [109 地方四等電子 ]   【 D 】 03. 將中序運算式 (Infix Expression)1(23/4)*5+- 轉換為後序運算式 (Postfix Expression) 的結果為何？ (A)12+34/5*- (B)12+345*/- (C)123-4/5*+ (D)1234/-5*+ 。 [109 關務四等 ] 1+(2-3/4)*5 → 1+((2-(3/4))*5) → 1234/-5*+ 由右往左，將運算子取代最近的右括號   【 C 】 04. 某一個二元樹的前序 (pre-order) 順序為 ABCDEFGHI ，中序 (in-order) 順序為 BCAEDGHFI ，則其後序 (post-order) 順序為何？ (A)ABDCEFGIH (B)BCADGFIE (C)CBEHGIFDA (D)DHGFEICBA 。 [109 鐵路員級 ] 前序找最前，中序分左右，後序找最後。 前序： ABCDEFGHI ，最前為 (A) 中序： BCAEDGHFI ，以 (A) 為中，分成左 (BC) ，右 (EDGHFI) 後序的順序為 " 左右中 " ， A 放在最後，則左 (BC) 右 (EDGHFI) 中 (A) ，選 (C) 。   【 B 】 05. 如果某一個二元樹的前序與中序表示法為： c, a, b, d, g, e, f 與 b, a, g, d, c, e, f ，則其後序表示法為何？ (A)b, d, g, a, f, e, c (B)b, g, d, a, f, e, c (C)b, g, d, a, e, f, c (D...
閱讀完整內容

計概16-06樹－公職試題

圖片
【選擇題】 【 C 】 01. 下列何種樹狀資料結構，不保證為平衡樹 (Balanced tree) ？ (A) 完整二元樹 (Complete binary tree) (B) 完滿二元樹 (Full binary tree) (C) 二元搜尋樹 (Binary search tree) (D) 最小堆積 (Min heap) 。 [113 地方四等電子 ] 平衡樹的左右子樹高度差不超過 1 。 1 、 2 、 3 、 4 組成的二元搜尋樹，會往右傾斜，左右子樹高度差會超過 1 。   【 B 】 02. 若以廣度優先搜尋 (Breadth-first Search) 走訪下圖 ( 從節點 1 開始 ) ，各節點的走訪順序應為何？ ( 若同時有多個選擇，請優先挑選數字較大的節點 ) (A)123456 (B)143265 (C)146523 (D)146532 。 [113 地方四等電子 ] 廣度優先搜尋 (BFS) ：從根節點開始，沿著樹的寬度搜尋樹的所有節點，直到找到結果為止。   【 C 】 03. 在一個高度為 7 層的二元樹結構中，其總節點數最多為 (A)256 (B)128 (C)127 (D)255 。 [113 身心五等 ] 2 ^ 7 - 1 = 127 個節點   【 C 】 04. 關於 AVL 樹的敘述，下列何者錯誤？ (A)AVL 樹是一種二元搜尋樹 (B) 在 AVL 樹中，任一節點的兩棵子樹的最大高度差為 1 (C) 在一有 n 個節點的 AVL 樹中插入或刪除一個節點資料，平均複雜度為 O(1) (D)AVL 樹可用來進行排序。 [113 身心四等電子 ] AVL 樹為確保搜尋效率，平均情況下，尋找、插入和刪除操作的時間複雜度都是 O(log n) 。   【 C 】 05. 若執行下列 C 語言程式， #include<stdio.h> #include<stdlib.h> struct node {   char data;   struct node *left;   struct node *right; }; void main(){...
閱讀完整內容

計概16-09後序－統測試題

圖片
【二技試題】 【 C 】 01. 中序式 (Infix form) 表示的運算式 B-C+D*E/(F-G) ， 如果轉換成為後序式 (Postfix form) 應為 (A)+-BC/*DE-FG (B)BCDEFG+-*/- (C)BC-DE*FG-/+ (D)GF-E/D*C+B- 。 [91 護理 ]   【 D 】 02. 某個二元樹 (binary tree) 的前序式 (preorder) 為 ABDFGEC ，中序式 (inorder) 為 FDGBAEC ，則其後序式 (postorder) 為何？ (A)FDGBECA (B)FGDBECA (C)FDGBCEA (D)FGDBCEA 。 [92 管理 ]   【 A 】 03. 假設 a = 5, b = 4, c = 3, d = 2 ，則依後序 (postfix) 運算式 ab * cd + / 之計算值為何？ (A)4 (B)11.5 (C)0.25 (D)10.5 。 [92 護理 ]   【 C 】 04. 後序 (postfix) 運算式 6,3,/,3,-,5,2,*,+ 之計算結果為何？ (A)3 (B)6 (C)9 (D)11 。 [95 護理 ]   【 A 】 05. 有一個中序 (infix) 表示式為 (a/(b-c+d)) × e-a × c ，則此式之後序 (postfix) 表示式為何？ (A)abc-d+/e×ac×- (B)ab/c-de×+ac×- (C)abcdeac-+/-×× (D)abcd-+/ea-c×× 。 [96 電機 ]   【 D 】 06. 假設 W = 4, X = 2, Y = 5, Z = 3 ，後序 (posrfix) 運算式為 WX/YZ-+X* 的值為何？ (A)6 (B)7 (C)12 (D)8 。 [97 管理 ]   【 D 】 07. 若有一個中序 (infix) 式為 ((a+b)+c × (p-q))/(r-s/t) ，其後序式應為下列何者？ (A)abc+-p+/q×rst/- (B)ab/c-p+q+rst×-/ (C)ab+cpqrst-+/-×/ (D)ab+cpq-×+rst/-...
閱讀完整內容