19. Let A(r) be the area of a circle with a radius r. Assume that the worst-case time T(n) to execute a given program with input of size n is T(n) =n x A(n) = O(f(n)). What is the function of f(n)?
(A)n；
(B)n²,
(C)n³,
(D)n⁴.

1.The following graph shows the circuit, called D-latch, where a small circle means "not." Then what are the values of x and y when a = O and b = 1?   (A)x=0,y=0；(B)x=0,y=1；(C)x=1,y=0；(D)x=1,y=1

2.Given an integer n 2 0 , the Fibonacci number F(n) is defined as follows.  Whether the problem of finding a Fibonacci number F(n) is NP-complete? (A) Yes, because there exists a recursive program whose running time (in units of instruction) is at least 1.618", (B) No, because we can use an iterative approach to derive F(n) such that the running time (in units of instruction) is about n +1； (C) Yes, because we can use an iterative approach to derive F(n) such that the running time (in units of instruction) is about n+1； (D) No, because there exists a recursive program whose running time (in units of instruction) is at least 1.618"

3.The following shows a function written by C programming language. Please tell us the returned value of f (4) ? (A)35:(B)46:(C)48(D)31. F(n)=

4.Which two addresses should a computer have in order to access the Internet? (A) DHCP address and IP address； (B) MAC address and IP address； (C) IP address and TCP address； (D) DHCP address and ARP address.

5.Assume that a multi-programming operating system uses the paging scheme to allocate memory. Assume that the available memory is 60 M bytes and divided into 12 frames； besides, each frame size is 5 M bytes. Now, suppose that we want to execute two programs, the first one needs 23 M bytes and the second one needs 11 M bytes. Then how many frames are needed in order to execute these two programs? (A) 6 frames； (B) 7 frames； (C) 8 frames； (D) 9 frames.

6.Let's continue to consider the above question. How much memory is wasted? In other words, how much memory is not used by those two programs and cannot be used by other programs? (A) 6 M bytes； (B) 1 M bytes； (C) 26 M bytes； (D) 20 M bytes.

7.Assume that a machine cycle consists of three phase: fetch, decode, and execute； besides, the time to execute each phase is T. Then how long do we need to execute n instructions when using the pipelining technique? Note that we assume that these n instructions are independent. (A) 3nT, (B) nT, (C) n +2T, (D) (n + 2)T.

8.The following shows a program written by C language. Please tell us the value of sum when the for loop terminates.   (A) 110； (B) 120； (C) 130； (D) 140.

9. Which one is not the necessary condition for processes to result in a deadlock in an operating system? (A) hold and wait； (B) circular wait； (C) mutual exclusion； (D) preemption.

10. Which one of the following protocols will be executed when we want to automatically obtain an IP address? (A) DHCP, (B) DNS； (C) ARP； (D) TCP.

104年 - 104 國立中山大學_碩士班招生考試_電機系(丙組)：計算機概論#110053