110年 - 110學士後_醫學系︰計算機概論與程式設計#100246

選擇題 (30)

1. Hashing is used to create a hash table for integer keys. Let the hash table be a vector indexed from 0 to 6, the hash function be f(x) = x%7 where x denotes an integer key and % is the modulo operator, and collision be solved with the linear open addressing strategy. Suppose the four integer keys: 19, 33, 8, and 54, are processed sequentially. Where is 33 placed in the hash table? (A) The position indexed 2 (B) The position indexed 3 (C) The position indexed 4 (D) The position indexed 5 (E) The position indexed 6

2. Suppose a computer has a RAM of 1 GB. Let one addressable word consist of 4 bytes. How many address bits are required to access all the words in the RAM? (A) 28 (B) 29 (C) 30 (D) 31 (E) 32

3. Let x=00001111 and y=11111011 be two 8-bit 2’s complement binary numbers. What happens for x + y? (A) The result is -12 in decimal representation. (B) The result is 12 in decimal representation. (C) The result is -10 in decimal representation. (D) The result is 10 in decimal representation. (E) Overflow occurs.

4. What is bootstrap? (A) an I/O device (B) a memory device (C) an interrupt handler (D) a processor (E) a small initiation program to start up computers

5. CPU scheduler selects the next process for execution. There are several basic scheduling methods, such as first-in-first-out (FIFO), shortest job first (SJF), and round-robin (RR). Regarding to these methods, which of the following comments is INCORRECT? (A) With FIFO, the waiting time of a process may depend on the arriving order of the processes. (B) Starvation won’t occur with FIFO. (C) Theoretically, SJF is an optimal scheduling algorithm in terms of average waiting time. (D) Starvation won’t occur with SJF. (E) RR is a preemptive scheduling algorithm.

6. Virtual Memory is a storage allocation scheme in which secondary memory can be addressed as though it were part of main memory. Virtual memory can be implemented using Demand Paging. Several steps are performed in the demand paging scheme:
Step 1: Operating system (OS) puts the process in the blocking state.
Step 2: CPU is notified and the interrupted process is put in the ready state.
Step 3: The required page is brought into the memory with the page replacement algorithm.
Step 4: CPU generates an interrupt, indicating a page fault.
Step 5: Page table is updated accordingly. Which of the following is the CORRECT sequence of steps performed by demand paging? (A) 1, 2, 3, 4, 5 (B) 2, 4, 3, 1, 5 (C) 3, 2, 5, 1, 4 (D) 4, 1, 3, 5, 2 (E) 5, 3, 1, 2, 4

7. Assume there are four frames in main memory. Consider the following page reference string: 2, 1, 6, 4, 1, 2, 5, 3, 1, 2, 1, 6, 7, 3, 6, 1, 2, 1, 6, 3. How many page faults occur for the OPT (Optimal Page-replacement Algorithm) replacement? Notes: All frames are initially empty, so the first unique pages will all cost one fault. (A) 7 (B) 8 (C) 9 (D) 10 (E) 11

8. Consider the execution of the following set of processes on a single-core processor.
Assume we use preemptive SJF (Shortest-Job-First) scheduling. What is the average waiting time? (A) 10 (B) 12 (C) 14 (D) 16 (E) 18

9. Suppose computers A and B have IP addresses 10.105.1.113 and 10.105.1.91, respectively, and they both use the same netmask N. Which of the values of N given below should be used if A and B belong to the same network? (A) 255.255.255.255 (B) 255.255.255.250 (C) 255.255.255.240 (D) 255.255.255.224 (E) 255.255.255.192

10. Assume a network device sends out data at the rate of 4,000 bps. How long does it cost to send a file of 100,000 characters? (A) 100 seconds (B) 200 seconds (C) 300 seconds (D) 400 seconds (E) 50 seconds

11. The following code snippets have security flaws. Which of the choices below can be used as id to achieve the SQL Injection attack? (A) (B) (C) (D) (E)

12. Suppose we have two tables, named TABLE-A and TABLE-B, respectively, as shown below.

(A) The result is a table of 7 records. (B) There are 5 columns in the resulting table. (C) Green appears in three records of the resulting table. (D) Eight appears in two records of the resulting table. (E) JOIN cannot be performed for these two tables.

13. In a 3-level memory hierarchy system, the hit time for each level is

T1 = 5 ns (L1-cache)

T2 = 200 ns (L2-cache)

T3 = 600 ns (Main memory)

The local hit rate in each level is H1 = 0.9 (L1-cache), H2 = 0.8 (L2-cache), and H3 = 1 (It is assumed that we can always find the data in main memory). If the average access time (ns) of this memory is K. What is the value of “{Round(K*123)} mod 5” ? (A) 0 (B) 1 (C) 2 (D) 3 (E) 4

14. Let AB*CD-/E+ be an postfix expression. If A=6, B=3, C=4, D=5, and E=8. What is the result of this postfix expression after evaluation? (A) -10 (B) -8 (C) 8 (D) 9 (E) 10

15. Let the height of a tree be the number of nodes along the longest path from the root node to the leaf nodes. Consider the integers 30, 41, 25, 29, 94, 37, 70, 23, 65, 75 in the specified order to develop a binary search tree. Which of the following is TRUE? (A) The node for 37 is an internal node. (B) The root node is 41. (C) The node for 70 has only one child. (D) The height of the tree is 5. (E) The node for 75 is a child of the node for 94.

16. What will be the output of the following C code ? (A) 2 (B) 3 (C) 4 (D) 5 (E) None of the above

17. Consider the following instruction mix for a processor:

ALU operations: 40%, uses 4 cycles.

Branch opera tions: 30%, uses 4 cycles.

Memory references: 30%, uses 5 cycles.

The un-pipelined processor has a clock cycle time of 1 ns. The pipelined processor has a clock cycle time of 1.2 ns. Suppose that we ignore any latency and hazards, and assume that the pipelined processor has an ideal CPI (cycles per instruction) of 1. How much speedup can be achieved when comparing the un-pipelined processor and the pipelined processor? (A) 3.28 (B) 3.35 (C) 3.58 (D) 3.86 (E) 3.98

18. Perform a DFS (Depth-First Search) traversal of this graph by starting at node 1 and going in the order of numbers in Arabic when picking which neighbor to visit first. Which of the following is the CORRECT traversal order?
(A) 1, 2, 6, 4, 5, 3, 7 (B) 1, 2, 4, 6, 5, 3, 7 (C) 1, 2, 4, 5, 6, 3, 7 (D) 1, 2, 4, 3, 7, 5, 6 (E) 1, 2, 4, 5, 3, 7, 6

19. Consider the following C code:
When the code is executed, what is the final value of x? (A) 20 (B) 24 (C) 28 (D) 32 (E) 36

20. What will be the output of the following C code?
(A) 36 (B) 39 (C) 93 (D) 63 (E) 96

21. In machine learning, one of the most common problems that will occur when we are training a model is overfitting. There are some techniques that could ease or even solve this problem. Which of the following technique does NOT alleviate overfitting problem? (A) Adding dropout between layers. (B) Increasing training epochs. (C) Data augmentation. (D) Early stopping while training model. (E) Using L1/L2 regularization.

22. Consider the following C program code and statements (1)~(5). (1) node[1].num = 0
(2) node[1].num = 1
(3) node[2].ptr-＞num = 9
(4) node[9].ptr-＞ptr-＞num = 121
(5) node[9].ptr-＞num = 100
Which of the following statements is CORRECT?
(A) (1)(3)(4)(5) (B) (1)(3) (C) (2)(3) (D) (2)(3)(4)(5) (E) (4)(5)

23. The following is a C program code:
Which one of the following statements is CORRECT? (A) When a=8, b=5, c=6, then A is 81, B is 5. (B) When a=8, b=5, c=6, then A is 81, B is 6. (C) When a=8, b=5, c=6, then A is 17, B is 5. (D) When a=8, b=5, c=6, then A is 17, B is 6. (E) When a=8, b=5, c=6, then A is 16, B is 6.

24. Suppose there are 16 users in the system, and they use symmetric encryption to achieve confidential communication, how many keys need to be managed? (A) 125 (B) 256 (C) 120 (D) 128 (E) 160

25. Let a, b, c be three 8-bit operands to a carry-save adder and their values be a = 00010110, b = 01101101 and c = 01001110. What are carry outputs of this carry-save adder? (A) 01001110 (B) 00110101 (C) 01010110 (D) 00111010 (E) 01101101

26. Which of the following activation functions can avoid the vanishing gradient problem? (A) ReLU (B) tanh (C) Sigmoid (D) ELU (E) None of the above

27. What is the status of a process if the process stops because its time slot is over? (A) Waiting (B) Running (C) Ready (D) Sleeping (E) Terminated

28. In machine learning, a confusion matrix is a table that is often used to describe the performance of a classification model on a set of test data for which the true values are known. One can use the matrix to calculate the evaluation metrics, such as accuracy, precision, recall, and F1 score. Suppose a confusion matrix contains TP (true positive) = 900, FN (false negative) = 100, FP (false positive) = 50, and TN (true negative) = 950. What is the value of precision for the model? (A) 1850/2000 (B) 900/1000 (C) 900/2000 (D) 50/950 (E) 900/950

29. Suppose there is a two-input neuron with weights w1 = 3, w2 = 2, and bias b = 1.2. Let the activation function f be the ReLU (Rectified Linear Unit) function, defined as f(x) = max(0, x). Given the inputs p1 = -5 and p2 = 6. What is the output of this neuron? (A) 0 (B) 1.2 (C) 2.4 (D) -1.5 (E) -1.8

30. For a Generative Adversarial Network (GAN) that can produce images of cars, which of the following statements is TRUE?
(1) The generator aims to learn the distribution of car images.
(2) After training the GAN, the discriminator loss eventually reaches a constant value.
(3) The generator can produce unseen images of cars.
(4) The discriminator can be used to classify images as car vs. non-car. (A) (1) and (2) (B) (2) and (3) (C) (1), (2) and (3) (D) (2), (3) and (4) (E) (1), (2), (3) and (4)

申論題 (6)

1. A binary tree has ten nodes. The inorder and preorder traversals of the binary tree are shown as follows.
Inorder: FKCGJBDEAI
Preorder: GFCKDJBIEA
Draw the tree.

a. Determine the entropy of the data set. (4 points)

b. Determine the average entropy of the resulting subsets obtained by splitting on attribute A. (4 points)

c. How much information gain is obtained if attribute A is selected for the root node of the decision tree? (2 points)
Note: Please use the values: log23 = 1.6 and log25 = 2.3. Hint: Entropy = is distribution for event i

3. To transmit text across a network, an English character is usually encoded in 8 bits in which bits 0~6 are the ASCII code and bit 7 is used for parity checking. Suppose a string of 5 characters, infni, is to be transmitted and odd-parity checking is adopted. Let the ASCII code of i be 1101001, the ASCII code of n be 1101110, and the ASCII code of f be 1100110. What is the sequence of 40 bits encoded for the 5-character string? Please show the sequence in hexadecimal (base 16) form.

4. Suppose we have an array A containing 9 integers: 240, 119, 682, 341, 225, 556, 122, 661, 245, i.e. A = [240, 119, 682, 341, 225, 556, 122, 661, 245] with the first index being 0. Please convert the array A into a maxheap and show the content of A after conversion. Note that the conversion should be done in-place.

110年 - 110學士後_醫學系︰計算機概論與程式設計#100246

試卷資訊

選擇題 (30)

申論題 (6)