教甄資賦優異組

解釋以F名詞:(12%)【題組】(a)stack overflow

【題組】(b) max heap

【題組】(c) perfect hash function

2.遞迴：參考以下java程式片殺冋答問題。（12%)【題組】(a)假設陣列a□的内容如K，呼叫fun()函數返问後，程式的輸出爲何？(4%)

【題組】(b)完成以下遞迴版之輾轉相除法函數gcd()，以求取正整數a,b的最大公因數。(4%)

【題組】(c)完成以下::7C捜尋樹(BinarySearchTree)類別中的遞迴版捜尋函數searchO，其中的key 參數爲欲捜尋的鍵値，函數冋傳値爲此一所在的節點，若無此鍵値，則回傳null。

3.串列(List):(12%)【題組】(a)若一Array List有n個元素，在其中插入一個新元素x，使其成爲第k個元素(l＜k＜n)， 需執行那些動作？ (4%)

【題組】(b)具有dummyhead node的linked list有何優點？舉例說明之。（4%)

【題組】(c)以下averageO函數可求取一鏈結串列list中元素的平均値，但其執行效率不佳，請指 出其中的關鍵處。（4%)

4.堆疊(Stack)and 丨宁列(dueue): (12%)【題組】(a)若堆疊的特質可用"LastIn First Out"來描述，如何以類似的說法來描述Queue特質? (

【題組】(b)有--堆疊S的內容爲(a^cAe)，其屮e在頂端(top)，又有一f宁列Q的內容爲(w,x,y,z)， 其中z在末尾。先在S進行三次pop，再在Q中進行二次dequeue，最後依序將由S

【題組】(c)寫出以下算術運算式F的前置式(prefixexpression)與後置式(postfix expression)。(6%)F= a-(b+c/d-e)*f+g/h*j

5.二元搜尋樹(Binary Search Tree): (12%)【題組】(a)依序將以下鍵値加入一空的二搜尋元樹(鍵値的大小依照字典順序)，畫出最後的樹狀結 構 ° (4%)NYY, KITTY,

【題組】(b)7?〈(a)，寫出此二元樹的中序巡行(inorder traversal)與後序巡行(postorder traversal)結果，假設巡行的目的爲印出節點對應的鍵値。（4%)

【題組】(c)若僅知一棵二元搜尋樹的中序與後序尋行結果，能否唯一決定此二元樹的結構？說明 原因，否則不給分。（4%)

6.排序(Sort):(12%)【題組】(a)某陣列的初始內容爲88,17,45,98, 32，使用Bubble Sort進行由小到大排序，共需幾次的元素互換(swap)?需寫出排序過程，否則不給分。

【題組】(b)在MergeSort中，若需合倂二段已經排好的整數序列(7,19, 33, 35)與(12,15, 23, 31),共需進行多少次的元素比較？需寫出過程，否則不給分。（4%)

【題組】(c)假設使用Quicksort排序一整數序列，若挑選最靠近平均値的元素做爲樞紐(pivot)，可 倉g有利於分割時的平衡性，但此舉是否會對排序的時間複雜度造成影響？說明原因， 否則不給分。（

7.Hashing: (14%)【題組】(a)依序將以下整數鍵値加入一個大小(TableSize)爲11的Hashtable，使用h(key)=key mod TableSize 做爲 Hash fu

【題組】(b)同(a)’但改用double hashing來進行碰撞排解’公式如下，其中hl(key)爲primary hash function: (5%)hi(key) = hl(key)+i*h

【題組】(c)使用linearprobing做爲碰撞排解方法時，容易產生primary clustering的狀況，解釋何 謂 primary clustering。（4%)

8.時間複雜度(timecomplexity)分析：(14%)【題組】(a)請分析以下程式片段的時間複雜度，（5%)

【題組】(b)請分析以下程式片段的時間複雜度，（5%)

【題組】(c)某演算法的時間複雜度爲0(n2)與Ω(n2)，分別代表何意？(4%)

1.Solve the set of equationsy~2y + z = 0 zf-y-2z = 0Subject to the conditions jf(0) = 1 and z(0) = 0

 2935   首頁 上一頁 36 37 38 39 40 41 42 43 44 45 下一頁 尾頁