108年 - [無官方正解]108 國立嘉義大學_轉學生招生考試試題_資訊工程學系：計算機概論#144308

1. One difference between a compiler and an interpreter is (5%) (A) a compiler is a program (B) a compiler is used to translate high-level language into machine language (C) a compiler is no longer needed after a program is translated (D) a compiler processes source code

2. Approximately how many iterations will binary search need to find a value in a list of 512 items? (5%) (A) 512 (B) 256 (C) 9 (D) 3

3. The recursive Fibonacci function is inefficient because (5%) (A) it does many repeated computations (B) recursion is inherently inefficient compared to iteration (C) calculating Fibonacci numbers is intractable (D) fibbing is morally wrong

4. Which of the following is not true of the halting problem? (5%) (A) It was studied by Alan Turing. (B) It is harder than intractable. (C) Someday a clever algorithm may be found to solve it. (D) It involves a program that analyzes other programs.

5. Explain subnet masking in simple terms, including why a subnet mask is required when an adapter is configured with an IP address. (10%)

6. Place these algorithm classes in order from fastest to slowest: n log n, n, n2 , log n, 2n. (10%)

7. Why is it a good idea to first write out an algorithm in pseudocode rather than jumping immediately to a programming language code? (10%)

(1) X AND Y (3%)

(2) X OR Y (3%)

(3) X XOR Y (3%)

(4) X + Y (3%)

(5) X − Y (3%)

(1) Two’s complement (5%)

(2) One’s complement (5%)

(3) Sign-and-magnitude (5%)

(1) Explain why the search algorithm for a linked list can only be sequential. (5%)

(2) There are a linked list called List with two parts (data part and link part) and two pointers, pre (for previous) and cur (for current). Additionally, search is an algorithm that searches for a node with a specific value in List. If the node is found, it returns true; otherwise, it returns false. When the search stops, no matter whether the target is found, cur points to the node that stops the search and pre points to the previous node. At the beginning of the search, pre pointer is null and cur pointer points to the first node of List. If the flag returned from search is false (i.e., the node is not found), we can insert a node in List. Please show the algorithm that can be used to insert a node in List. (15%)