1: Please choose the best answer from four choices A), B), C) and D) to the questions. (18 pts) 1) Here is the definition of Fibonacci number: { if no if n =1 if n > 1 fib(n) = fib 1) + fib(n - 2) So the value of fib (6) is (A) 5 (B) 8 (C) 13 (D) 10 2) Orders of growth can be used to measure the efficiency of algorithm. Which one of following orders of growth is most efficient? (A) logan (B) n? (C) n (D) n! 3) Which one of following statements is NOT advantages of Brute Force algorithm? (A) wide applicability (B) very efficient (C) yields reasonable algorithms for some important problems (D) simplicity 4) Data structure _will be used when BFS (Breadth First Search) is applied in graph traversals. (A) Stack (B) Queue (C) Hash Table (D) Array 5) For a complete binary tree heap with n nodes is represented sequentially, then for node with index i (assuming it has parent and children), the index of parent is the index of LEFT child is (A) floor(1/2) (B) 2i (C) 2i+1 (D) 21-1 6) Given there is a bill looks like "1XX5" (X denotes missing digit). How many possible values of your bill can be list if we use brute force algorithm to find the two missing digits (A) 2 (B) 50 (C) 100 (D) 1000 7) Which sorting algorithm below requires extra memory? (A) Bubble sort (B) Quick sort (C)Selection sort (D) Merge sort 8) We call occurs when we hash two non-identical identifiers into the same bucket, i.e. f(11)=f(12) when ii = 11 (A) An Overflow (B) A Collision (C) A Mapping (D) A Sorting