2003 Data Structure Test (120 minutes) Class: Student Number: Name:1.Single-Choice(20 points)(1) The Linked List is designed for conveniently b data item.a. gettingb. insertingc. findingd.locating(2) Assume a sequence list as 1,2,3,4,5,6 passes a stack, an impossible output sequence listIs c .a. 2,4,3,5,1,6b.3,2,5,6,4,1c.1,5,4,6,2,3d.4,5,3,6,2,1(3) A queue is a structure not implementing b .a. first-in/first-outb. first-in/last-outc. last-in/last-outd. first-come/first-serve(4) Removing the data item at index i from a sequential list with n items, d items needto be shifted left one position.a. n-ib. n-i+1c. id. n-i-1(5) There is an algorithm with inserting an item to a ordered SeqList and still keeping theSeqList ordered. The computational efficiency of this inserting algorithm is c .a. O(log2n)b. O(1)c. O(n)d.(n2)(6) The addresses which store Linked List d .a. must be sequentialb. must be partly sequentialc. must be no sequentiald. can be sequential or discontiguous(7) According the definition of Binary Tree, there will be b different Binary Treeswith 5 nodes.a. 6b. 5c. 4d. 3(8) In the following 4 Binary Trees, c is not the complete Binary Tree.a b c d(9) A Binary Tree will have a nodes on its level i at most.a.2ib. 2ic.2i+1d.2i-1(10) If the Binary Tree T2 is transformed from the Tree T1, then the postorder of T1 is theb of T2.a. preorderb. inorderc. postorderd. level order(11) In the following sorting algorithm, c is an unstable algorithm.a. the insertion sortb. the bubble sortc. quicksortd. mergesort(12) Assume there is a ordered list consisting of 100 data items, using binary search to find aspecial item, the maximum comparisons is d .a. 25b.1c. 10d.7(13) The result from scanning a Binary Search Tree in inorder traversal is in c order.a. descending or ascendingb. descendingc. ascendingd. out of order(14) The d case is worst for quicksort.a. the data which will be sorted is too larger.b. there are many same item in the data which will be sorted .c. the data will be sorted is out of orderd. the data will be sorted is already in a sequential order.(15) In a Binary Tree with n nodes, there is a non-empty pointers.a. n-1b. n+1c. 2n-1d.2n+1(16) In a undirected graph with n vertexs, the maximum edges is b .a. n(n+1)/2b. n(n-1)/2c. n(n-1)d.n2(17) The priority queue is a structure implementing c .a. inserting item only at the rear of the priority queue.b. inserting item only at the front of the priority queue.c. deleting item according to the priority of the item.d. first in/first out(18) The output from scanning a minimum heap with level traversal algorithm c .a. must be an ascending sequence.b. must be descending sequencec. must have a minimum item at the head position.d. must have a minimum item at the rear position.(19) Assume the preorder of T is ABEGFCDH, the inorder of T is EGBFADHC, then thepostorder of T will be a .a. GEFBHDCAb. EGFBDHCAc. GEFBDHCAd. GEBFDHCA(20) When a recursive algorithm is transformed into a no recursive algorithm, a structureb is generally used.a. SeqListb. Stackc. Queued. Binary Tree2. Please convert the following infix expression (a*(b+c))+(b/d-e)*a into postfix expression,in the converting process, please draw the change of operator stack and the change of the output. (10 points)3. Assume a list is {xal, wan, wil, zol, yo, xul, yum, wen, wim, zi, xem, zom}, please insert these items to an empty Binary Search Tree and then construct the AVL tree. Please draw the whole processes including inserting an item, or rotate nodes to restore height balance.(10 points)4. Assume a list is {48,35,64,92,77,13, 29,44}, firstly insert these items to an empty complete Binary Tree according to the sequence one by one, then please heapify the complete Binary Tree and implement the heap sort. Please draw the whole heapigying process and sorting process. (10 points)5. For the following directed graph, give the adjacency matrix and adjacency list. Then according your adjacency list, please scan the graph using the depth-first search and the breadth-first search and give the corresponding result. (10 points)6. Assume a list is 35,25,47,13,66,41,22,57, please sorting the list with quicksort algorithm. Please write every sorting pass result (no programming).(10 points)7. Assume keys={32,13,49,55,22,39,20}, Hash function is h(key)=key%7. The linear probe open addressing is used to resolve collisions. Please try to calculate the value of Hash for each key and give the final hash table. (10 points)8. Programming (All methods have been declared in textbook can be used directly, or you can rewrite them if they are not same in your answer) (20 points)(1) Assume there are two ascending ordered lists L1 and L2, please merge L1 and L2 into a new list L3. There will be no duplicate items in L3. Then please reverse the L3 into a descending ordered list.(10 points)(2) Please give the complete declaration of Queue in circle model, then write the insert algorithm and delete algorithm. (10 points)。