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

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

試卷資訊

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

選擇題 (0)

申論題 (16)

(a) Use pseudo-code or C code to describe a string matching algorithm that has time complexity of O(NP*Ns), where Np and Ns are the lengths of P and S, respectively.
(5%) (b) The Knuch-Morris-Pratt (KMP) algorithm is a string matching algorithm designed to reduce redundant symbol comparisons in string matching. What is the big-O time complexity, in terms of NP and Ns, of the KMP algorithm?

2. (10%) The C structures of a singly linked list and its list items are given below:
61baeda32033d.jpg
that moves the item with the smallest va lue to the front of the list, and leave the relative orders of the other list items unchanged.
3. (10%) Given a non-empty queue Q and a stack T, use pseudo-code to describe an algorithm to reverse the order of the elements in Q using T. For both Q and T, you can only use their push and pop operations.
(3%) (a) Describe the advantage of using available-space lists.
(3%) (b) Describe in pseudo-code of how to implement the function clear, which should run in O(1) time complexity. This function clears the content of a list so that its size becomes zero.
(4%) (c) Describe in pseudo-code of how to implement the function add_space (N), where N is a positive integer. This function adds N items to the available-space list. It should use memory allocation call only once.
(3%) (a) What is the purpose of using a stack?
(3%) (b) If using a stack, what information should be pushed onto the stack when moving to a new cell?
(4%) (c) Can you use recursion to solve the same problem? Explain.
6. (10%) Briefly describe "binary search" and "searching on a binary search tree", and make a comparison between them in terms of data structure constraints and time complexity.
7. (10%) Explain why a heap is always implemented in an array rather than linked list.
(5%) (a) Propose two graph storage structures for the graph in Figure I and explain the pros and cons for those two structures.
(5%) (b) Develop a minimal spanning tree of the graph.

9. (10%) The binary search tree in Figure 2 was created by starting with a null tree and entering data from the keyboard. In what sequence were the data entered? If there is more than one possible sequence, identify the alternatives.
61baee72c57bc.jpg

10. (10%) The shell sort algorithm is an improved version of the straight insertion sort. In the shell sort, a list of N elements is divided into K segments, where K is known as the increment. For example, in Figure 3, K is 3. The first, fourth, seventh, and tenth elements make up segment 1. For each pass, the data in each segment are sorted in Insertion Sort. Thus, after insertion sort, there are three different ordered lists. After each pass through the data, the increment is divided by two (K/2) until, in the final pass, it is 1. Please prove (explain) the time complexity of Shell sort is close to O(N log N).
61baeeb53f252.jpg