1、Fi nal Exam in ati on Paper on Data Structures(A)I、Fill Vacant Position (Tx 10=10)1、 is the name for the case when a function invokes itself or invokes a sequenee of other functions,one of which eventually invokes the agai n.2、In adata structure, all insertions and deletions of entries are made aton

2、e en d. It is particularly useful in applicatio ns involving.3、 In c+ , we useoperator to implement the circular queues.4、In processing a contiguous list with n entries: insert and remove require timeapproximately to. And clear, empty, full, size operate in time.5、One of method of searching isthat r

3、equires ordered list.6、The time complexity of the quicksort is.7、Onlygraph has topological order.II、Multiple choice (2 x 10=20)1、 In a tree,are vertices with the same pare nt.()A. childre nB. sibli ng C. adjace ntD. leaf2、A queue is a version of ()A. linked list B. LIFO listC. sequential list D. FIF

4、O list3、How many shapes of binary trees with four no des are there ()A. 12B.15C. 14D. 134、Among sorting algorithms, which kind of algorithm is divide-and-conquer sorting()A. shell sort B. heap sort C. merge sortD. inserting sort5、For the following graph, one of results of depth_first traversal is ()

5、A. abcdefghi B. abcdeighf C. acbdieghf D.abdeighfc6、In a binary tree, if the result of traversing under preorder is the same as that underino rder,the n()A. It is only a binary tree with one nodeB. It is either empty, or the left subtree of any node of the tree is emptyC. It is on ly an empty bi nar

6、y treeD. It is either empty, or the right subtree of an node of the tree is empty7、 There aresolutions to the problem of placing four queens on aX4 board.()A. 2B. 3C. 6D. 48、Which function is smallest order of magnitude?()A. 2 nB. n + Ign C.n 0.1D.100009、The time requirement of retrieving a given ta

7、rget in hash table with n entries is()A. 0( n) B. O(log2 n) C. 0(1)D.0( nl og2 n)10、For the followi ng bi nary tree, the result of travers ing un der postorder is ()A. abcdefghi B. dgbechfia C. gdbaehifc D. gdbehifcaIII、Analyze and Calculate ( 10 )Let A be a upper tria ngular matrix andUg ilo 1023-0

8、.il 13d ,n-i11-1,11-1Suppose that(a) Elements of A are stored in row-major ordering(b) Each eleme nt occupies m memory locatio ns(c) In dex ing begi ns at 0Please give the calculat ing formula of loc(aij)(address of the eleme nt aij)IV、Comprehensive Problem(7 x 6=42)1、Draw a diagram to illustrate th

9、e con figurati on of lin ked no des that is created by the following statement.Node *p0=new Node (a);Node *p仁pO n ext=new Node(b);Node *p2=p1 next=new Node(c,p1);2、Briefing the idea of Shellsort .3、By hand, trace the action of heap_sort on the following lists. Draw the initial tree towhich the list

10、corresp on ds, show how it is conv erted into a heap, and show the resulting heap as each entry is removed from the top and the new entry inserted. 25 3136 281912 224、Suppose that(a) A hash table contains hash_size=16 positi on in dexed from 0 to 15(b) A hash function H(key)=(key*3)%13(c) The follow

11、ing keys are to be mapped into the table:10 120 33 45 58 26 3 27 200 400 2Draw the hash table with the collision resolution oflinear probing.5、Con struct a mi ni mal spa nning tree ofthe followi ng conn ected n etwork.6、Given a sequenee of keys:A ,乙 B,Y, C, X, D, W, E, V, FInsert the keys in the ord

12、er shown above, to build them into an A VL tree (draw the prin cipal AVL tree).V、Develop Algorithm(18 )For linked implementation of binary trees, we have the following class specifications: template struct Binary_node Entry data;Binary_node *left;Binary_node *right; ;template class Bi nary_treeprote

13、cted:Binary_no de*root;int recursive_height (Binary_no de *sub_root);public:int height(); /other fun cti on; ;template int Bin ary_tree:height() recursive_height(root); _Write the fun ctio n recursive_height to computethe height ofa binary tree.An swer of Final Exam in ati on Paper On Data Structure

14、s (A)I. 1、Recurs ionfirst function2、stack revers ing3、modulus ( or % or mod)4、O(n) O(1) (or constant)5、binary search6、O(n log2n)7、directed with no cycleII. 1、B2、D3、A 4、C5、D6、B7、A 8、D9、C 10、DLoc佃滬III.Loc 歸)+(i(2n亠 l)/2+ji)*mWjLoc(a(in)+n(n+l)*m/2 , ij(不寫不扣分)IV. 1、2、Repeat(1) Choosethe in creme nt di

15、satsifies the followi ngs(a) d1 n, di+1 1)、3、1235 、3122121919? 22,12卩 2?.,25 28 31 3625 28 31 3625 28 31 注19 25 362831(120) =7 H(33) =6 H22Z / 712 19 2822 /12 193131/、 22 21 / 12 125 / 82512 28 31 364、 H (10) =2 H25/、茨2812 19 3136(45) =3 H (58) =30123456789101112H(26)=11H(3)=7H(27)=1H(200)=0 H(400)=2 H(2)=