40. Determine the expected search cost of an optimal binary search tree for a set of n = 5 keys with the following probabilities. We assume that all searches are successful.
(A) 2.15
(B)1.15
(C)2.10
(D) 1.10
(E) 2.0

36. For a chain of matrix A1A2A3A4 with their dimensions in the following table, parenthesize the product A1A2A3A4 to minimize the number of scalar multiplications. What is the minimum number of scalar multiplications?(A)82 (B)72 (C)112 (D)99(E)70

37. Assume that quicksort is being used to sort an array A with values 4 2 8 73 1 5 6. After the first invocation to the partition algorithm the array looks like this: 2 3 1 4 7 5 8 6. Which value could have been chosen as the pivot? (A) 4(B)7 (C)1 (D)3 (E)8

38. Professor Chen uses the following algorithm for merging k sorted lists, each having n/k elements. He takes the first list and merges it with the second list using a linear-time algorithm for merging two sorted lists, such as the merging algorithm used in merge sort. Then, he merges the resulting list of 2n/k elements with the third list, merges the list of 3n/k elements that results with the fourth list, and so forth, until she ends up with a single sorted list of all elements. What is the worst-case running time of the professor Chen's algorithm in terms of n and k. (A)θ(log(nk))(B)θ(nk) (C)θ(nlogk) (D)θ(lognlogk) (E)θ(n)

39. A hiker faces the Knapsack problem. There are 7 items to be packed into the knapsack, each with value viand weight wi as shown in the following table. The knapsack, which is initially empty, can hold a maximum weight of 16, so some item(s) must be left behind. The optimality criterion is to maximize the total value of the items that are placed in the knapsack.The hiker fills the knapsack one item at a time. Now consider the following two cases: (a) fractions of items cannot be packed, and (2) fractions of items can be packed. What are the optimal values of the items that are packed in these two cases respectively? Give the answer in the form of (no-fractions-allowed, fractions-allowed). (A)(28,30.5) (B)(37,40)(C)(30,34) (D)(38,40) (E)(34,38.5)

101. _____ , the company’s CEO hasn’t decided whether to fire the manager and his team who handle the publicity and all that business. (A) Even as (B) So far (C) Already (D) A while ago

102. Gabar Restaurant serves freshly cooked dishes in our live cooking stations _____ customers can watch the chefs turn fresh ingredients into delicious meals. (A) which (B) whose (C) what (D) where

103. We will email you a barcode _____ you to get a voucher from a physical store. (A) that will allow (B) will allow (C) which allow (D) which allowing

104. Some senior high school students take _____ for granted that their parents would pay for their tuition fees when they go to university. (A) them (B) theirs (C) all (D) it

105. International students currently residing in the UK are _____ our new internship scheme, which provides the opportunity to achieve paid short-term work experience. (A) immersed in (B) appointed as (C) eligible for (D) exposed to

106. Thank you for your email to show your interest in becoming a volunteer. _____ , as of now, we are overstaffed and there are no openings. (A) Therefore (B) Accordingly (C) Unfortunately (D) Similarly