数据结构试题(修改).doc

200X年试题 选择题 (1)Suppose 1,2,3,4 is the order which these elements push onto a stack. The sequence obtained is () A.4.1.2.3 B.3.2.4.1 C.3.4.1.2 D.4.3.1.2 (2)Suppose that a linear list contains n=31 nodes, the binary search is applied to the list, the maximum times in searching is () A 4 B 5 C 25-1 D 24-1 (3)In the following sorting algorithms, which is unstable() A Selection sort B Merge sort C Bubble sort D Insertion sort (4)Bubble sort is used for n nodes, the minimum number of comparisons is () A n-1 B n C n(n-1/2) D n(n+1)/2 (5)How many binary trees in different forms can at most be built by three nodes? A 4 B 5 C 6 D 7 填空题 .(1)The stack takes on character of _______________________________ (2)The postfix expression is ‘abcdef*/-*+’. Its infix expression is _____________________ (3)The advantage of circular queues is _____________________ .(4)If the depth of full binary tree is k, then the number of nodes in the tree at least_____________ (5)The selection sort is used to sort n nodes, the number of its comparisons is ______________________ 三．(1) Write a function Deletion in C for linear list. (5 points) (2)Write a function Pop in C for linked stack. (5 points) (3)Write a function in C for binary search. (10 point ) (4)Write some sentences in C which delete the node b in the following figure. (5 point)(附图) (5)Write some sentences in C which insert the node b in the following figure(5pont)(附图) 四． (1) Write a function in C of randex(基数)sort. (10 point ) (2)Write a function in C of quick sort. (10 point ) (3)Suppose that a hash table contains 5 entries indexed from 0 through 4 and that the following keys are to be mapped into the table. 12,19,17,14,10,24,15 Hash function h(k)=k mod 5. (a)Determine the hash addresses and resolute collision by chaining. (b)Write a function in C for search by chaining. (10point) 五. (1)Write a function in C which will in