I Single Choice(10 points)1. ( a )For the following program fragment the running time(Big-Oh) is .i = 0;s = 0;while(s ( 5*n*n + 2) i+; s = s + i;a. O(n) b. O(n2) c. O(n1/2) d. O(n3)2. ( c )Which is non-linear data structure_.a. queue b.stack c. tree d. sequence list3.( b )The worst-time for removing an element from a sequence list (Big-Oh) is . a. O(1) b. O(n) c. O(n2) d. O(n3)4.( d )In a circular queue we can distinguish(区分) empty queues from full queues by .a. using a gap in the array b. incrementing queue positions by 2 instead of 1 c.keeping a count of the number of elements d. a and c 5. ( b )A recursive function can cause an infinite sequence of function calls if .a. the problem size is halved at each step b. the termination condition is missing c. no useful incremental computation is done in each step d. the problem size is positive 6( c )The full binary tree with height 4 has nodes. a. 15 b. 16 c.31 d.32 7. ( b )Searching in an unsorted list can be made faster by using .a. binary search b. a sentinel（哨兵） at the end of the list c. linked list to store the elements d. a and c 8.（ b ）Suppose there are 3 edges in an undirected graph G, If we represent graph G with a adjacency matrix, How many “1”s are there in the matrix? a. 3 b. 6 c. 1 d. 99. ( d ) Construct a Huffman tree by four leaf whose weights are 9, 2, 5, 7 respectively. The weighted path length is_.a. 29 b. 37 c. 46 d.4410. Consider the following weighted graph. Consider Dijkstras algorithm on this graph to find the shortest paths with s as a starting vertex. Which are the first four vertices extracted from the priority queue by the algorithm (listed in the order they are extracted) ? a. s, y, t, x b. s, y, x, z c. s, t, y, x d. s, y, x, tFig. 111. Here is an array of ten integers:5 3 8 9 1 7 0 2 6 4Suppose we partition this array using quicksorts partition function and using 5 for the pivot. Which shows the array after partition finishes:a. 5 3 4 2 1 0 7 9 6 8b. 0 3 4 2 1 5 7 9 6 8c. 3 1 0 2 4 5 8 9 6 7d. 3 1 0 2 4 5 8 9 7 6e. None of the aboveII Fill in Blank (10 points)1. For the following program fragment the running time(Big-Oh) is O(n2) . for ( int i = 0; i n; i+ ) for ( int j = 0; j =i; j+) s; /s为某种基本操作2. We store a 44 symmetric matrix A into an array B with row major order, Store the lower triangle only. the index of element a23 in B is 6 .3 We can use 3 vector type to store value and of non-zero elements in a sparse matrix.4. A_stack_ is a list where removal and addition occur at the same end . Frequently known a LIFO (Last-In-First-Out) structure. 5. T( n ) = 2T( n/2 )+ cn, T(n)=O(logn) T(n) = T( n-1)+cn, T( n ) = O(_n_)6. There is a binary tree whose elements are characters. Preorder list of the binary tree is “ABECDFGHIJ” and inorder list of the binary tree is “EBCDAFHIGJ”. Postorder traversal sequence of the binary tree is EDCBIHJGFA . 7There are (n+1)/2 leaf nodes in a full binary tree with n nodes.8When the input has been sorted ,the running time of insertion sort(Big-Oh) is O(n) .9We sort the sequence（43，02，80，48，26，57，15，73，21，24，66）with shell sort for increment 3, the result is _ (15 02 21 24 26 57 43 66 80 48 73) _ .10、In a circular queue, “front” and “rear” are the front pointer and rear pointer respectively. Queue size is “maxsize”. When insert an element in the queue, rear = _ (rear+1)%maxsize_ 11. A _B树_ is an example of a search tree which is multiway (allows more than two children).12. A tree in which every node is no smaller than its children is termed _大顶堆_.III Application of Algorithms （35 points）1.Graph G shown in Fig 2 is a directed graph, please describe G with adjacency matrix and write the orders of breadth first traversal and depth first traversal. Fig.2 A B C D E A 0 1 0 1 0B 0 0 1 1 0C 0 0 0 0 1D 0 0 0 0 1E 0 0 0 0 0Dft:ABCEDBft:ABDCE2The sequence of input keys is shown below: 19，1，23，14，55，20，84，27，68，11，10，17A fixed table size of 19 and a hash function H(key)=key%13，with linear probing(线性探测), fill the table below and compute the average length of successful search.3. Show the results of inserting 53,17,78,09,45,65,87 each , one at a time, in a initially empty max heap（大根堆） 4. write the sequence of preorder,postorder traversals and add inorder threads in the tree.