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

科目：研究所、轉學考(插大)、學士後-計算機概論 | 年份：110年 | 選擇題數：0 | 申論題數：11

試卷資訊

所屬科目：研究所、轉學考(插大)、學士後-計算機概論

選擇題 (0)

申論題 (11)

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, 612f11d4cf8b5.jpgare balanced parentheses sequence. On the other hand, 612f11f825a6a.jpg 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