阿摩線上測驗 登入

110年 - 110 國立高雄科技大學_碩士班招生考試_資訊工程系：資料結構#110422

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

試卷資訊

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

選擇題 (0)

申論題 (21)

1. (10%) A lower triangular array A is an n-by-n array in which A[]0]== 0, if i <j. Assume that A is stored in one-dimensional array B sequentially, i.e, B[0] = A[0[0], B[1]=A[I][O], B[2] =AI] [1],B[B3]=A[2][0], B[4]=A[2][1], B[S]=A[2][2]J.... Write the addressing formula for the element A[/]U] stored in B[k] in the lower triangular part.
(a) (2%) 5n2 + 10000
(b) (2%) n32m + 10m23m
(c) (2%) Kruskal's algorithm for a graph of V vertices and E edges
(d) (2%) Bubble sort for n numbers
(e) (2%) Binary scarch in a sorted array
(a) (5%) Use linear probing to handle the overflow (draw the hash table).
(b) (5%) Use chaining to handle the overflow (draw the hash table).
4. (10%) Use Dijkstra's algorithm to find the shortest paths from nodc A to other nodes. Show your steps.
(a) (5%) Create a max beap tree according to the input order of data: 3, 5, 1, 9, 6, 4, 8, 7, 2.
(b) (5%) What is the result after delete 1 from the above max heap tree?
(a) (5%) perform a selection sort (detail needed, show each step).
(b) (5%) perform a merge sort (detail needed, show each step).
(a) (5%) Convert the following expression into postfix form (no detail needed).
((10-2)/3)+6-5*2
(b) (5%) Use a stack to evaluate your postfix form (detail needed, show each step).
(a) (5%) Construct a binary search tree.
(b) (5%) Show the pre-order traversal of the above tree.
(c) (5%) Show the tree after deleting "20"
(a) (5%) To check whether the queue is full.
(b) (5%) To check whether the queue is empty.
(c) (5%) If we want to usc all n slots, what do we need to do?