b. One can reverse the order of the elements in a linked list in time O(n). (4%)

c. Returning the maximum element in a max-heap (but not deleting it from the heap) can be done in time O(1). (4%)

d. One can implement a stack (of unbounded size) based on an array so that each individual push/pop operation is time O(1). (4%)

e. One can implement a stack based on a linked list so that each individual push/pop operation is time O(1). (4%)

4. Kruskal’s algorithm builds a minimum cost spanning tree T by adding edges to T one at a time. The following is Kruskal’s algorithm and the original graph with weighted values. Show the minimum cost spanning tree T by means of Kruskal’s algorithm. (10%)

5. For the digraph shown in the right hand side: (20%) a. Obtain its adjacency-matrix

b. Obtain its adjacency-list representation

c. Obtain its inverse adjacency-list representation.

d. Obtain its adjacency-multilist representation

6. The pseudo program is shown in the following. (20%) void program (item a[], item b[]) #define MAX_TERMS 100 int n,i,j,temp; typedef struct { n = a[0].valueC; int valueA; b[0].valueA = a[0].valueB; int valueB; b[0].valueB = a[0].valueA; int valueC; b[0].valueC = n; } item; if (n > 0) item a[MAX_TERMS], temp = 1; b[MAX_TERMS]; for (i = 0; i < a[0].valueB; i++) for (j = 1; j

b. Give the time complexity of the program in terms of big oh.

115年 - 115 國立嘉義大學_碩士班招生考試試題_資訊工程學系：資料結構#143912

114年 - 114 國立嘉義大學_碩士班招生考試試題_資訊工程學系：資料結構#144138

110年 - 110 國立臺灣科技大學_碩士班招生試題_電子工程系：資料結構#112844

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

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

110年 - 110 國立中山大學_碩士暨碩士專班招生考試_資管系/乙組:資料結構#105545

110年 - 110台灣聯合大學系統_碩士班招生考試_電機類:資料結構#104954

110年 - 110 國立中央大學_碩士班招生考試_資訊管理暨大數據分析類:資料結構#103860

110年 - 110 國立政治大學_碩士班招生考試_資訊管理學系/科技組:資料結構#102881

110年 - 110 國立臺灣大學_碩士班招生考試_生物機電工程學研究所丙組:資料結構(C)#100901