110年 - 110 國立高雄科技大學_碩士班招生考試_電腦與通訊工程系：資料結構(乙組)#110488

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

試卷資訊

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

選擇題 (10)

1.需要設計程式來處理稀疏矩陣問題時,如要減少儲存空間的需求,下列哪一種資料結構最為適合? (A)陣列(B)鏈結事列(C)堆疊(D)佇列

2.陣列是一组變數的集合,而對於這些變數,以下何者正確? (A)具有不同的資料型態,並且分散儲存於記憶體空間。 (B)具有相同的資料型態,並且分散儲存於記憶體空間。 (C)具有不同的資料型態,並且線性相鄰地儲存於記憶體空間。 (D)具有相同的資料型態,並且線性相鄰地儲存於記憶體空間。

3.哪種資料结構常用於作業系統處理程序的執行? (A)樹(B)堆疊(C)佇列(D)陣列

4.將A+BXC-D+E/F轉成後序式: (A) AB+C×D–EF/ (B) ABC×+D–EF/+ (C) AB+C×–DEF/+ (D) AB+CD+E×F/–

5.给定一個8x20的二维陣列A,在以列(row)為主的排列方式儲存在記憶體內。若陣列第一個資料A[0，0]存放的位置為120，且陣列每個元素佔2個記憶體單位。請問A[4,10]這個資料會被存放在哪一個位址? (A) 204 (B) 210 (C) 300 (D) 400

6.在一單向鏈結串列上,若要插入一個節點,則下列何者為真? (A)須更改從插入點到串列尾端的所有節點的指標。 (B)最多只需更改兩個指標。 (C)最多只需更改一個指標。 (D)須更改串列中所有篩點的指標。

7.在一個二元樹(binarytree)中，root為第一層,則第i層的節(node)數最多為: (A) 2ⁱ(B)(C)(D)

8.Heapsort最差的計算時間複雜度為何? (A)O(n)(B)O(n2) (C) O(log n) (D) O(n log(n))

9.排序處理過程中,以下何者需要最多的額外記憶體空間? (A)泡沫排序(B)合併排序(C)堆積排序(D)插入排序

10.下列哪個演算法與最小花費生成樹無關? (A) Kruskal (B) Dijkastra (C) Prim (D) Sollin

申論題 (7)

1.請將演算法、料結構分別填入以下空格處:

2.二元樹有55個nodcs,其中dgree為1之nodes有24個,米葉節點的個數?

3.請完成以下程式碼:(請用row和col回答)

4.上圖為環狀佇列滿的狀況,最多允許有MAX_QUEUE_SIZE-1元素,請完成以下程式碼:

5.以中序走訪下圖之二元樹,其輸出結果為何?

(三)問答題(每题10分,共20分)
1針對以下之graph结構,若以V2為起點使用DFS(Depth-first Search)方式所有node 進行逐一訪,則哪個node之訪順序會在V7之前一位?(請寫出尋訪過程)

2.單向鏈結串列,從x節點後插入一個新節點,請完成以下程式碼: