100年 - 100 樹德科技大學_碩士班暨碩士在職專班入學考試筆試試題_資訊工程系碩士班：資料結構#104286

科目：研究所、轉學考(插大)-資料結構 | 年份：100年 | 選擇題數：10 | 申論題數：10

試卷資訊

所屬科目：研究所、轉學考(插大)-資料結構

選擇題 (10)

(1) quick sort 及 insertion sort 的 worst case 之時間複雜度均為 O(n²)。(A)O(B)X

(2)堆疊對資料的新增與刪除都在同一端，其操作具有 FIFO 的特點。(A)O(B)X

(3 ) insertion sort 是一種穩定的排序法，而 quick sort 是一種不穩定的排序法。(A)O(B)X

(4)一個深度(depth)為 6 的二元樹，期最多的節點數為 63 個。(A)O(B)X

(5)分支度(degree)是指樹(tree)中每個節點所有子樹(subtree)的個數。(A)O(B)X

(6)串列(list)必頇用指標(pointer)來表示。(A)O(B)X

(7)陣列 A 中，由小而大存放 1，4，8，11，15，21，34，45 等 8 個數值，以二元搜尋法(binary search) 來找尋數值 4，頇比較 3 次。(A)O(B)X

(8)如圖所示，請依字母順序作頂點之選擇其從頂點 A 開始之深度優先搜尋(Depth First Search)之順序為 ABCDEFGHI。
(A)O(B)X

(9)要將四個訊息加以編碼，其權重分別為 2,3,7,9。假設左分支為 0，右分支為 1，則經赫夫曼編碼(Huffman Codes)後，可得到 00、01、000、001 等編碼。?(A)O(B)X

(10)雜湊搜尋(Hashing search)是將搜尋鍵值直接經過函數的計算轉換成表格位址，搜尋效率可達到 O(1) 。(A)O(B)X

申論題 (10)

(1)前序式(prefix)

(2)後序式(postfix)

2. 簡答題 (1)若用一個大小為 8 的陣列來執行環狀佇列，且當 front 和 rear 的值分別為 7 和 3，當從佇列中刪除二個元素，再加入一個元素之後，請問 front 的值與 rear 的值分別為何？(6%)

(2)有一個 300 個節點(node)的二元樹(binary tree)，其最小高度為多少? (4%)

(1)該矩陣 A 是以 row-major 方式或以 column-major 方式儲存？(5%)

(2)每個元素的 size 為多少個位置(Byte)？(5%)

(3)A[5][3]之位置為何？(10%)

(1)利用 Prim’s Method (10%)

(2)利用 Kruskal’s Method (10%)

6. 有一數列為 1, 2, 5, 12, 29, 70….，從第三項起存在有一與前二項之特定關係：f(n)=2*f(n-1)+f(n-2)，請用遞迴方法寫出 JAVA 或 C 語言之程式。(10%)