Please answer the question:

1. When designing a Dictionary structure, we usually use the concept of

value> pair, please explain what key here means?

2. Based on the data structures learned in the course, which data structure is the

best choice for top-k search, e.g., find the top-k biggest numbers from a sequence

of numbers? Explain the reason.

3. Based on the definitions of big-Oh and , derive the upper and lower bounds for

the following expressions:

4. Given the following array to be sorted: A=[36,20,17,13], if we use mergesort,

what is the recursive depth mergesort needs? And how the numbers are arranged

in the array A after the first recursive call for mergesort (the detailed explanation

should be described)?

5. The Bubble Sort implementation has the following inner for loop:

Consider the effect of replacing this with the following statement:Would the new implementation work correctly?

Would the change affect the

asymptotic complexity of the algorithm? How would the change affect the running

time of the algorithm?

6. Given following traversal results for a binary tree: (1) preorder: GDAFEMHZ;

(2) inorder: ADEFGHMZ. Answer following two questions

a) Restore and draw the binary tree.

b) What is its postorder traversal result?

7. Given following binary node implementation, how the inorder traversal can be

implemented? The function header traverse() is given, please write out its codes.

8. Following code fragment is an optimized implementation of mergesort, answer

following two questions:

(1)What is the strategy of Mergesort and how to analyze its time complexity?

(2)What does the function inssort() in the red rectangle refer to? Write out the

detailed implementation of inssort().

9. Present the max-heap shape and its array representation after running builtHeap

on the following values stored in an array.

13,62,15,15,50,58,16,40,30

10.

Design a (logn) search method that can return the position of an element in

the array (with size n) with value K.

(a) cin (b) can3 + c3 (c) can log n + c5n (d) c62+ cyn for (int j=n-1; j>i; j--) for (int j=n-1; j>0; j--) // Node implementation with simple inheritance class VarBinNode { // Node abstract base class { public: virtual "VarBinNode() () virtual bool isLeaf () = 0; // Subclasses must implement }; class LeafNode : public VarBinNode { // Leaf node private: Operand var; // Operand value public: LeafNode (const Operanda val) { var = val; } // Constructor bool isLeaf () { return true; } // Version for LeafNode Operand value() { return var; } // Return node value ); class Int 1Node : public VarBinNode { // Internal node private: VarBinNode+ left; // Left child VarBinNode* right; // Right child Operator opx; 1/ Operator value public: IntiNode (const Operator& op, VarBinNode* 1, VarBinNode+ r) { opx - op; left = 1; right = r; } // Constructor bool isLeaf ( { return false; } 1/ Version for IntlNode ) VarBinNode* leftchild() { return left; } // Left child VarBinNode* right child() { return right; } // Right child Operator value() { return opx; } // Value }; The function header: void traverse (VarBinNode *root) template void mercesort (E AIL. E templ. int left. int right) { if ((right-left) (&A[left], right-left+1); return; } int i, j, k, mid = (left+right) 72; mergesort (A, temp, left, mid); mergesort (A, temp, mid+1, right); // Do the merge operation. First, copy 2 halves to temp. for (i=mid; i>=left; i--) temp[i] = A[i]; for (j=1; j