《数据结构试题答案修改版》由会员分享，可在线阅读，更多相关《数据结构试题答案修改版（8页珍藏版）》请在金锄头文库上搜索。
1、选择题BBAAB(1)Suppose 1,2,3,4 is the order which these elements push onto a stack. The sequence obtained is ().3 B.3.2.4.1 C(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 a
2、lgorithms, 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后进先出a+
3、bc-d/(e*f)克服队满溢出2(k+1)-1n(n-1)/2填空题.(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
4、sort n nodes, the number of its comparisons is _三(1) Write a function Deletion in C for linear list(线性表). (5 points)int sq_elete(list,p_n,i) int list;/*形参数组可不指定大小*/ int *p_n,i; int j; if(i=*p_n) return(1); for(j=i+1,j*p_n;j+) listj-1=listj; (*p_n)-; return(0); (2)Write a function Pop in C for linked
5、 stack链接栈. (5 points)(3)Write a function in C for binary search2分查找. (10 point )int bisect(a,n,v)int a,v, n; int i,j,m; i=0; j=n-1; while(i=j) m=(i+j)/2; if(v=am)return(m); if(vright;/set q point to node Bq-right-left =q-left;q-left-right =q-right;freee(q);(5)Write some sentences in C which insert t
6、he node b in the following figure(5pont)(附图)ACPBq =p-right;/set q point to node Cb-left =p;b-right =q;p-right =b;q-left =b;四 (2)Write a function in C of quick sort快速查找. (10 point )Position Partition(List *list, Posotion low, Position high) ListEntry pivot; Position i, lastsmall, pivotpos; Swap(low,(
7、low+high)/2,list); pivot=list-entrylow; pivotpos=low; for(i=low+1; ientryi.key, pivot.key)Swap(+pivotpos, i, list); Swap(low, pivotpos, list); return pivotpos;(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,1
8、7,14,10,24,15Hash function h(k)=k mod 5.(a)Determine the hash addresses and resolute collision by chaining. 010-151212-173419-24 (b)Write a function in C for search by chaining. (10point)void search2(t,k,p,q) NODE *t ; int k; NODE *p,*q; *p=NULL; *q=th(k); while(*q!=NULL) if (*q)-key=k) return; else
9、*p=*q; *q=(*q)-link; 五.(1)Write a function in C which will inter change all left and right subtrees in binary tree. (10 point)/*假设树的定义为struct sNode struct sNode* left,right;*/void Swap(struct sNode *t) struct sNode *p; if (NULL =t) return ; p =t-left; t-left =t-right; t-right =p; Swap(t-left); Swap(
10、t-right);(2)Write a function in C for linked queue链接队列.(10 point)void Append(QueueEntry x,Queue *q)if (QueueFull(q) Error(“cannot append an entry to a full queue.); else q-count+; q-rear=(q-rear+1)%MAXQUEUE; q-entryq-rear=x; 选择题D AB D B A(1) In a simple linked list with n nodes, the number of pointe
11、r fields with NULL Totals(). A. n B.2 C(2)In the linear lists, two concepts which are the same as each other is()A node B. record C. field D. type of structure(3)In the binary search tree, for any root of subtree, the keys of all nodes in its left subtree is () the keys of all nodes in its right sub
12、tree.A less than B equal to C great than D less than or equal to (4)For general trees, the correct choice is ()A it may be empty B at least one nodeC at least two nodes D A.B and C are incorrect(5)The bubble sort is used to n nodes, least number of comparison is()A n-1 B n C n(n-1)/2 D n(n+1)/22n n-
13、1 n+1a+b*c-d/e*f插入删除访问后进先出Hash函数 冲突填空题(1)A binary tree with n nodes storaged by standard form, there are _ pointers where _ _pointers are used to point to sub-nodes, and _ pointers are empty.(2)The postfix expression is abc*+de/f*-, then its infix expression is _(3)The basic operations of linear lists are_
