102年 - [無官方正解]102 國立嘉義大學_碩士班(乙組)招生考試試題_資訊管理學系：資料結構#146330

1. 以下哪些敘述是對的？
(A) Quick sort 在Worst case時，不只時間複雜度變大，連空間複雜度也變大為O(n)。
(B) Merge sort適用在大量(多筆)資料的排序。
(C) Insertion sort適合少量資料的排序，因為程式碼很簡短、且只需要O(1)的記憶體空間。
(D) Table sort可以避免過多的資料搬移，因此適合每筆資料都很大的狀況下使用。
(E) Heap sort雖然比Merge sort速度稍慢，但好處是耗費記憶體較少。 (5分)

1.請利用Stack將之轉換為Postfix格式。(請使用底下的表格範例作答) (10分)

2.請利用Binary tree將上述Infix表示式轉換為沒有括號的Prefix格式。(請先畫出對應的Binary tree T，再寫出T的Preorder traversal結果即是) (5分)

1.C 語言函式 strcat(x, y) 是將 y 字串內容接到 x 字串後面，若有字串宣告如下：

char s1[10]={ " dog" }, s2[]={ " dog" }, s3[]={ "house" };
請問 strcat(s1, s3) 與 strcat(s2, s3) 的結果各是什麼？有無問題？為什麼？(5 分)

2. 已知C語言變數宣告：int a, b, c;
請問if( !(a<=100) || !(a>200) ) b = c; 這個程式片段有何特點？會造成哪些問題？ (5分)

三、 給定一個具有100個Node的Binary search tree，為了測試你的搜尋程式的效能，你可隨機產生一個整數、輸入搜尋程式，並量測搜尋時間。同時，為了提高測量的精確度，你需要重複「產生亂數值、然後搜尋」非常多次，最後取平均值。但是，事實上這個作法算出來的並不是你的搜尋程式的Average case的效能，請問為什麼？ (5分)

1.請列出右邊這個AOV network所有可能的Topological order。(5 分)

2.以實際例子解釋Topological order 對於AOV的意義為何？
(需先解釋如何解讀你的AOV network)(5分)

1. 請畫出這個Binary search tree。(5分)

2. 針對這個Tree做Postorder traversal的輸出結果是？(5分)

3. 如果從1.這個Tree刪除掉F，請畫出新的Binary trees。(有兩種可能)(5分)

4. 如果建立Binary search tree的過程採用AVL Tree的作法，請問1. 的答案變成什麼？(10分)

2. 請利用Quick sort來排序{40, 35, 20, 10, 60, 45, 55, 30, 70, 15}這些資料。假設每次都從待排序的序列中的最前、中間、及最後一個Key值中選出第二大的當作Pivot，則上述序列中的Pivot是哪一個？並寫出依此Pivot排序後的結果。(5分)

3. 以下這些排序方法：Insertion sort、Quick sort、Merge sort、Radix sort、Heap sort、以及Bubble sort，哪些是Stable的？請舉例說明什麼情況下 “stable sorting” 是選擇排序方法時的重要特質？ (5分)

七、 寫出A, B, C三個字母的所有Stack Permutation的「過程」與結果。(5分)

八、 請完成底下的LSD Radix sort。(假設radix = 2，並在答案卷按題目格式重繪每個Sorting pass後的結果)(5分)

九、 一個Undirected graph有10個Vertex以及8個Edge，請問這個Graph是否有Spanning tree？若有，請舉例說明。若無，請證明。(5分)

十、 如果有一個Column-major array A[n][m]，已知A[4][10]、A[5][5]以及A[6][8]的記憶體位址分別是200, 210, 和 236(以上為十進位)，請問該Array每個Element的大小是多少Byte？(需寫出詳細計算過程) (5 分)