110年 - 110 國立臺灣大學_碩士班招生考試_工程科學及海洋工程學研究所丁組: 計算機概論(A)#100870

1.(20%) Given a string c consist of"!" and "I" symbols, for every right parenthesis there exists a matching left parenthesis, we said that string is a balanced parentheses sequ quence. For example, are balanced parentheses sequence. On the other hand, are not balanced parentheses sequence. Plcase implement a function balanced_ parenthese (seq) which takes one string seq as the parameter. The function wil return true if the string seg is a balanced parentheses sequence or false otherwise.

a.(10%) According to the sentence "this is an example of a buffman tree", please generate the Huffman code tablc and encode the above sentence with your code table.

b.(10%) Given a string S which consist of space char and lower case letters (i.e.,', 'a', ...,'2), implement a function huffman_code (str) which can output the huffiman code table which is optimized to the input string S and convert the str into a bit pattem according to the generated hufiman code table.

3.(20%) A sum-product number in a given number base b is a natural number that is equal to the product of the sum of its digits and the product of its digits. For example, the number ]44 in base 10 is a sum- -product numbet, because 1 + 4 + 4= 9, (1)(4)(4) = 16, and (9) (16)= 144. Please implement a function is_ sum product_ number (x) to check whether a natural number x is a sum-product number in base 10.

a.(10%) Please implement the heapsort algorithm. heapsort (list, n). list: an array or a list, count: the number of data in the 1 ist that needs to be sort.

b. (5%) Is heapsort a stable sorting algorithm?

c. (5%) What is the time complexity of heapsort in worst case?

a. Coupling and Cohesion

b. Abstract Data Type and Encapsulation

c.Machine Cycle and Pipeline

d. Virtual Memory and Virtual Address

110年 - 110 國立臺灣大學_碩士班招生考試_工程科學及海洋工程學研究所丁組: 計算機概論(A)#100870

試卷資訊

選擇題 (0)

申論題 (11)