Examination Paper on Data StructureⅠ Fill Vacant Position ()1.In a ________ data structure, all insertions and deletions of entries are made atone end. It is particularly useful in application involving________.2.In processing a sequential list with n entries: insert and remove require timeapproximately to ________.3.One of method of searching is ________ that requires ordered list.4.The time complexity of the quicksort is ________.5.Only ________ ________ graph has topological order.6.According the definition of Binary Tree, there will be ________ differentBinary Trees with 5 nodes.ⅡSingle choice ()1.The Linked List is designed for conveniently ________data item.a. gettingb. insertingc. findingd. locating2.Assume a sequence list as 1,2,3,4,5,6 passes a stack, an impossible outputsequence list Is ________ .a. 2,4,3,5,1,6b.3,2,5,6,4,1c.1,5,4,6,2,3d.4,5,3,6,2,13. A queue is a structure not implementing ________.a. first-in/first-outb. first-in/last-outc. last-in/last-outd. first-come/first-serve4.Removing the data item at index i from a sequential list with nitems, ________ items need to be shifted left one position.a. n-ib. n-i+1c. id. n-i-15.The addresses which store Linked List ________ .a. must be sequentialb. must be partly sequentialc. must be no sequentiald. can be sequential or discontiguous6.The time requirement of retrieving a given target in hash table with n entriesis _______a. O(n)b. O(log2n)c. O(1)d. O(nlog2n)7.If the Binary Tree T2 is transformed from the Tree T1, then the postorder ofT1 is the ________ of T2.a. preorderb. inorderc. postorderd. level order8.In the following sorting algorithm, ________ is an unstable algorithm.a. the insertion sortb. the bubble sortc. quicksortd. mergesort9.Assume there is a ordered list consisting of 100 data items, using binarysearch to find a special item, the maximum comparisons is ________ .a. 25b.1c. 10d.710.The result from scanning a Binary Search Tree in inorder traversal isin ________ order.a. descending or ascendingb. descendingc. ascendingd. out of order11.The ________ 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 order12.In a Binary Tree with n nodes, there is ________ non-empty pointers.a. n-1b. n+1c. 2n-1d.2n+113.In a undirected graph with n vertexs, the maximum edges is _______.a. n(n+1)/2b. n(n-1)/2c. n(n-1)d.n/214.The output from scanning a minimum heap with level traversalalgorithm _______.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.15.Assume the preorder of T is ABEGFCDH, the inorder of T is EGBFADHC,then the postorder of T will be _______.a. GEFBHDCAb. EGFBDHCAc. GEFBDHCAd. GEBFDHCA16.When a recursive algorithm is transformed into a no recursive algorithm, astructure _______ is generally used.a. SeqListb. Stackc. Queued. Binary Tree17.Among sorting algorithms, _______ kind of algorithm is divide-and–conquer sorting.a. shell sortb. heap sortc. merge sortd. inserting sortⅢcomprehensive problem( )1. For the following binary tree, give the result of traversing under postorder2.Assume a list is {48,35,64,92,77,13, 29,44}, firstly insert these items to an emptycomplete 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.3. 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.4. Suppose that(a ) A hash table contains hash_size = 16 position indexed from 0 to 15(b) A hash function H(key)=(key * 3) % 13(c) The following keys are to be mapped into the table:10 120 33 45 58 26 3 27 200 400 2 Draw the hash table with the collision resolution of linear probing.5. Construct a minimal spanning tree of the following connected network.Ⅳ Programming.1. Assume there are two ascending ordered linked lists L1 and L2, please merge L1 and L2 into a new link list L3. There will be no duplicate items in L3. Then please reverse the L3 into a descending ordered list.For linked list, we have the following class specifications:Template<class Entry>struct Linknode{Elemtype data;Linknode< Elemtype > *next;};Template<class Entry>class Linklist{public: A B H E G C D Fvoid Mergelist(const Linknode <Elemtype> &A, const Linknode< Elemtype > &B, Linknode < Elemtype > &C );private:Linknode< Elemtype > *head;};Write the function Mergelist;2 .For linked implementation of binary trees, we have the following class specifications: template<class Entry>Struct Binary_node{Entry data;Binary_node<Entry > * lchild;Binary_node<Entry > *rchild;};Class Binary_tree{Protected:Binary_node<Entry > *root;int recursive_heght( Binary_node<Entry > *sub_root);Public:int height();};Template <class Entry >int Binary_tree<Entry > :: height(){recursive_height(root);}Write the function recursive_height to compute height of a binary tree.。