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

1. Factorial function n! is described as follows: \[ n! = \begin{cases} 1 & \text{, if } n=0 \\ n \times (n-1)! & \text{, if } n \ge 1 \end{cases} \]Please write a recursive C function for factorial function n! (10 %)

(a) What is the address of A(4,8)? (10%)

(b) What is the number of rows of A? (5%)

3. Please write the postfix and prefix forms of following expressions：
(A-B) / C*D/(E-F+G * H)-J . (10%)

4. Please write a length function that returns the number of nodes in a double-linked list. (hint: Your answer shall show the number of nodes at least.) (15%)

(a) Write out the inorder, preorder, postorder, and level-order traversals for the binary tree shown below. (10%)

(b) Write a recursive function inorder to accomplish the inorder traversal. (10%)

(a) Which sorting scheme is used here to sort the list? (5%)

(b) Give the average computing time for the function sort. (10%)

(c) Is the function sort a stable sorting scheme? (5%)

(d) Give the status of the list at each call of the function sort. (10%)