阿摩線上測驗
登入
首頁
>
研究所、轉學考(插大)-資料結構
> 99年 - 99 淡江大學 轉學考 資料結構#55506
99年 - 99 淡江大學 轉學考 資料結構#55506
科目：
研究所、轉學考(插大)-資料結構 |
年份：
99年 |
選擇題數：
0 |
申論題數：
19
試卷資訊
所屬科目：
研究所、轉學考(插大)-資料結構
選擇題 (0)
申論題 (19)
(a)完成以下 Array List 之 Java 實作。（10%)
(b)比較 Array List 與 Linked List 在 add(index，item), remove(index)與 get(index)等三項操作上的優缺 點石(請分三項條列作答 ＞ 否則不給分 (6%)
(a)完成以下整數堆叠之Java實作。（8%)
【已刪除】(b)參考以下某算術運算式之後置式(postfix expression)，求出其運算結果。(4%)
(-爲減號，％爲求餘數運算符號)
(c)將以下中置式(infix expression)轉換爲後置式。(5%)
(a)將以下鍵値依序加入一MaxHeap ,畫出逐步加入的過程。（6%) 18, 5, 12, 23, 8, 30, 15, 20
(b)在堆積(heap)中，某節點的註標(index)爲k，則其父節點與二個子節點之註標分別爲何?(6%)
(a)依序將以下整麵入一棵空的二元搜繼，畫出此樹最後的外觀 (4%) 18, 9, 13, 10, 25, 20, 33, 22,21
(b)寫出此樹的中序(inorder)與後序(postorder)巡行的次序。(4%)
(c)若用Heap表示此二元樹，共薷耗用多少位置？說明你的答案。（4%)
(a)完整二元樹(complete binary.tree)與全滿二元樹(foil binary tree)有何不同？舉例說明之。（4%)
(b)證明高度爲h的全滿二元樹，共有2
h
-l個節點。（4%)
(c)—棵具有n個節點(公1)的二元樹，存在多少個空的指標欄位？請說明原因。（4%)
(a)分析二元搜尋法(binary search)之最差狀況時間複雜度。
(b)分析Insertion Sort的最纖況時間複雜度。
(c)分析Quick Sort的最差狀況時間複雜度。
(a)將以下鍵値(key瓶序加入一雜湊表(表格大小爲13) ,使用h(key) = key%TableSize做爲雜湊函 數，並採用二次探測(quadratic probing)做爲碰撞排解方法，畫出最後的雜湊表內容 (寫出計算 過程，否則不給分)(8%)
25, 16, 21，142, 30, 43, 12, 95
(b)承(a) ,改用separate chaining做爲碰撞排解方法。（4%)
(c)說明雙雜湊(double hashing)如何改善雜湊表甲的群集(cluster)效應。(4%)
阿摩線上測驗
登入
(-爲減號，％爲求餘數運算符號)