二元樹(binary tree)
(1) 有一個二元樹(binary tree)的中序走訪(inorder traversal)順序為
ABCDEFGHI , 它的後序走訪( postorder traversal ) 順序為
BACFEIHGD,其中每個英文字母代表一個節點。請畫出此二元樹。
(2) 上述二元樹的前序走訪(preorder traversal)順序為何?
(3) 在二元搜尋樹(binary search tree)中,那一個走訪順序(前序、中序
或後序)正好為排序好的情況?原因何在?(本小題未寫明原因者,
不給分)
(4) 如何利用線性掃瞄方式,判斷一個前序運算式(prefix expression)是
否合法?
解釋下列名詞:
(1) AVL 樹(AVL tree)
(2) 解釋圖形(graph)名詞:漢米爾頓迴路(Hamiltonian circuit)
(3) 解釋圖形(graph)名詞:廣度優先搜尋(breadth first search)。以程
式實作此搜尋時,該使用那一種資料結構?
(4) C++或JAVA 語言中,protected 之意義
(5) Hanoi towers problem
假設有下列數種排序方法:(A)bubble sort (B)quick sort (C)heap sort
(D)merge sort (E)radix sort (F)insertion sort。回答下列問題時,請分別以
ABCDEF 之代號答之。
(1) 一個排序法,在輸入資料中有多筆相同資料時,於排序前與排序後,
任兩筆相同的資料前後順序不變者,稱之為「穩定排序法」。請問那
些排序法為穩定排序法?
(2) 假設輸入資料有n 個,在最糟情形下,那些排序法的時間複雜度為O
(nlogn)?
(3) 排序程式實作時,那些排序法需要額外的陣列或鏈結串列?
(4) 在程式實作時,一般使用陣列進行排序。有些時候也需要對鏈結串列
進行排序。那些排序法無法對單向鏈結串列(linearly linked list)進行
排序?
在忽略第7 列的情形下,可將上面函式改寫成更有效率的函式如下。
請完成第10~12 列的程式內容。
1 int f(int n)
2 {
3 int i, a,b,c;
4 if (n <= 1)
5 return(n);
6 a=0;
7 b=1;
8 for (i = 2; i <= n; i++)
9 {
10
11
12
13 } // end of for
14 return (c);
15 }
可觀看題目詳解,並提供模擬測驗!(免費會員無法觀看研究所試題解答)