110年 - 110 國立政治大學_碩士班暨碩士在職專班招生考試_資訊科學系:資料結構及演算法#105973

科目：研究所、轉學考(插大)◆資料結構及演算法 | 年份：110年 | 選擇題數：0 | 申論題數：11

試卷資訊

所屬科目：研究所、轉學考(插大)◆資料結構及演算法

選擇題 (0)

申論題 (11)

a. (5%) The time complexity of any sorting algorithm is 0(n2).

b. (5%) The best-case time complexity of insertion sort is θ(n logn).
a. (5%) If a problem is in NP-hard, then the problem is in NP.
b. (5%) If a problem is in NP, then the problem is in NP-complete.
3.(15%) Use an example to explain why Dijkstra's shortest path algorithm cannot be applied to graphs with negative edge weights. In your example graph, please highlight the source and the destination.
4. (10%) Give two advantages of red black trees over hash tables.

5. (15%) An independent set I of an undirected graph G = (V,E) is a subset of V such that for any two vertices u and v in I, u and o are not adjacent,i.e.,61f25ba81199b.jpg. Design a dynamic program to find the largest independent set in a tree.
***Please explain the high-level idea of your answer in English or Chinese. ***

6. (15%) Consider an n-node sorted singly linked list L, where the first node (ie., the head) stores the smallest data, the last node (i.e., the tail) stores the largest data, and the61f25be687b58.jpgnode stores the 61f25be687b58.jpg smallest data. Given the address of L's head and a key, is it possible to search for the key in L in O(logn) time? Please explain your answer.
7. (15%) Design a polynomial-time algorithm for the following problem.
 Input: An n-node undirected graph G. 
Output:
 "'Yes', if there is a cycle of length at most n/2 (i.e., a cycle that has at most n/2 nodes) in G;
 "No", otherwise.
***Please give the high-level idea of your algorithm and explain why it has polynomial running time. ***
a. (5%) How to find p's key in Arr?
b. (5%) Does u have a left child node in the binary heap? Please explain your answer.