108年 - 桃園高中 108 學年度第 1 次教師甄選資訊科#75927

選擇題 (30)

1. 以下函數 b 的時間複雜度是(A) O(nlg_n)；(B) O(n)；(C) O(n²(D)O(2ⁿ )。

2. 以下用不同基數表達的數值中，哪一個的值和其他三者不同？ (A)(01BA)₁₆；(B) (670)₈；(C) (442)₁₀；(D) (110111010)₂。

3. 在下面這段 python 程式執行後，b 中的元素依序為何？ (A) 9,7,5,3,1；(B) 10,8,6,4,2；(C) 0,1,2,3,4,5,6,7,8,8；(D) -1,1,2,3,4,5,6,7,8,9,10,-2。

4. A,B,C,D,E,F 依序 push 到一個堆疊裡，期間可任意插入 pop 指令輸出堆疊頂端的資料，下列何者不可能為其輸出結果？(輸出順序為由左至右) (A) ABCDEF；(B) CDEBFA；(C) ACEDBF；(D) BECFDA。

5. 以下是在學校 WWW 伺服器上所列出目前的連線狀況，若管理員僅會由校內 private IP 來源的電腦來對它進行管理維護，則目前哪個 IP 最可能是入侵者？ (A) 127.0.0.1；(B) 64.233.188.188；(C) 162.125.34.129；(D) 117.18.232.200。

6. 這段 C++ 程式執行後，畫面上會出現幾個 * ？(A)10；(B) 12；(C) 16；(D) 18。

7. 我們在一個電腦系統中使用 8 個位元採二補數方式來儲存一個整數，請以二進位來表示這個系統中整數的最小值。 (A) 10000000；(B) 11111111；(C) 11000000；(D) 10000001。

8. 我們被分配到一個 class C 的 IP 範圍使用權，為了讓各部門都可以有自己的一個 subnet 可用，使用了 255.255.255.224 做為網路遮罩，則每個部門最多只有個 IP 可使用？ (A) 18；(B) 30；(C) 32；(D) 62。

9. 以下這段 python 程式運行後，c 的值何？ (A) 3；(B) 100；(C) 1000；(D) 程式有誤，執行到途中會停下來。

10. 若我們的加密演算法為將明文與金鑰做 XOR 運算，當金鑰為 0xB7 且加密後密文為 0xCD 時，請問明文為何？ (A) 0x7A；(B) 0x85；(C) 0xFF；(D) 0x7F。

11. What is the output of the following program : (A) 1 (B) 2 (C) 3 (D) 4

12. What is the output of the following program: (A) 1,2,3 (B) 1,3,0 (C) 5,3,0 (D) 0,3,5

13. The following function return true when ____________.(A) s is string with same char. (B) s is a palindrome. (C) s is empty. (D) all of the above.

14. Given the following functions for Stack operation, please fill the blanks with correct statements.

(A) code1: s[top++] , code2: s[top--] (B) code1: s[++top] , code2: s[--top] (C) code1: s[top++] , code2: s[--top] (D) code1: s[++top] , code2: s[top--]

15. Suppose p is a pointer of node points to the rear of a circular linked list. Initially, p = null.The following program codes will insert a node pointed by pointer q at the front of the circuler list. Please fill in the blanks. (A) code1: p , code2: q (B) code1: p , code2: q-＞link (C) code1: p-＞link , code2: q (D) code1: p-＞link , code2: q-＞link

16. Suppose p is a pointer of node points to the rear of a circular linked list. Initially, p = null. Suppose we have another linked list pointed by avail which links the unused space together. The following program will erase the circular list into the single linked list pointed by avail. Please fill the blanks.(A) code1: p-＞link-＞link, code2: p (B) code1: p , code2: p-＞link-＞link (C) code1: temp , code2: avail (D) code1: avail , code2: temp

17. Let T be a binary search tree with left and right pointers as usual.What does the function M(T) compute? (A) The height of T. (B) 1 + the height of T. (C) The number of keys in T. (D) The number of nodes in the extended version of T.

18. Consider we have n disks with size of S1,S2,...Sn to build RAID system with. Which of the following statements is NOT true? (A) For RAID 0, the capacity = Sum(S1,S2,...Sn),no fault tolerance. (B) For RAID 1, the capacity = Min(S1,S2,...Sn),fault tolerance = n-1. (C) For RAID 5, the capacity = (N-1)*Min(S1,S2,...Sn),fault tolerance = 1. (D) For RAID 10, the capacity = (N-2)*Min(S1,S2,...Sn),fault tolerance = 2.

19. How many of the following errors can NOT be detected during program compiling? (A)4 (B)5 (C)6 (D)7

20. Amdahl's law is often used in parallel computing to predict the theoretical speedup when using multiple processors. Assume we have a program that is 80% parallelizable, What is the theoretical speedup gained by running on Quad-Core machine relative to a Single-Core machine ? (A)2.5 (B)4 (C)0.8 (D)3.2

21. Which of the following statements about Hamilton Path/Circuit is True? (A) A Hamiltonian path is a path in an undirected or directed graph that visits each edge exactly once. (B) Determining whether Hamiltonian paths and cycles exist in graphs is polynomial. (C) A simple graph with n vertices (n ＞= 3) is Hamiltonian if every vertex has degree n / 2 or greater. (D) A graph with n vertices (n ＞= 3) is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is n/2 or greater.

22. Which of the following statements is(are) true? 1.Queue is useful in CPU scheduling and Disk Scheduling. 2.Stack is useful while checking for balanced parentheses in an expression. 3.Queue is useful while converting infix to Postfix/Prefix. 4.Stack is useful while Breadth First Search in a graph. 5.When data is transferred asynchronously between two processes. Stack is used for synchronization. Examples : IO Buffers, pipes, file IO, etc. (A)1,2 (B)2,3,4 (C)2,3,4,5 (D) 1,2,5

23. Which of the following sort algorithms is stable and has average time complexity O(NlogN) ? (A) QuickSort (B) HeapSort (C) MergeSort (D) Insertion Sort

24. Suppose that Bob and Alice want to send information to each other with the RSA algorithm. Which of the following statements are correct? 1.Bob must know Alice's public key to encrypt the message. 2.Alice must use her private key to decrypt the encrypted message from Bob. 3.Alice can use her own private key to send a signed message to Bob with a signature. 4.Bob can verify the signature with Alice's public key. 5.If someone has Alice's public key, he can forge Alice's sigature. (A) 1,2,3,4,5 (B)1,2,3,4 (C)3,4 (D)1,2,5

25. Given two switches A,B which are interconnected via port a1 and b2. switch A has following configs: (A) a1: trunk mode, b2: access mode. (B) a1: access mode, b2: trunk mode. (C) a1: trunk mode, b2: trunk mode. (D) a1: access mode, b2: access mode.

26. Which of followings is not the main features of Object-oriented Programming? (A) Encapsulation (B) Modularity (C) Inheritance (D) Polymorphism

27. What is the time complexity of following code?

(A) O(n³) (B) O(n²) (C) O(nlog2 n) (D) O(n² logn)

28. Which of the following recurrence relation and asymptotic notation is NOT true? (A) T(n) = 8T(n/2) + 1000n² , T(n) = θ(n³) (B) T(n) = 2T(n/2) + 10n, T(n) = θ(nlogn) (C) T(n) = 2T(n/2) + n² , T(n) = θ(n² ) (D) T(n) = 2T(n/4) + ,T(n) = θ( log )

29. Which of the following statements is true? (A)UDP uses a three-way handshake to establish a reliable connection. (B)ICMP is used to discover the MAC address associated with a give IP address. (C)Time-sensitive applications(Streaming media,VoIP) use TCP that emphasizes low latency. (D)DHCP,DNS use UDP; FTP,HTTP use TCP; Ping,Treceroute use ICMP.

30. Given the follow DNS records, which statement is NOT correct？ $ORIGIN tyc.edu.tw. tysh IN SOA zeus.tysh.tyc.edu.tw. admin.tysh.tyc.edu.tw. (A) The authoritative name server for domain tyc.edu.tw is zeus. (B) The IP address of the mail server for user@tysh.tyc.edu.tw is 210.50.90.2. (C) mail is the aliase of host hermes. (D) admin@tysh.tyc.edu.tw is responsible for the domain tysh.tyc.edu.tw.