数据结构试卷(一)参考答案
一、选择题(每题2分,共20分)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二、填空题(每空1分,共26分)
1. 正确性 易读性 强壮性 高效率 2. O(n)
3. 9 3 3
4. -1 3 4 X * + 2 Y * 3 / - 5. 2n n-1 n+1 6. e 2e 7. 有向无回路
8. n(n-1)/2 n(n-1)
9. (12,40) ( ) (74) (23,55,63) 10.增加1
11.O(log2n) O(nlog2n) 12.归并
三、计算题(每题6分,共24分)
1. 线性表为:(78,50,40,60,34,90)
?0?1??1??1?2. 邻接矩阵:?01010111011101010??1?1??1?0??
邻接表如图11所示:
图11
3. 用克鲁斯卡尔算法得到的最小生成树为: (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
4. 见图12
2 4 4 2 2
图12 2 4 4 5 4 8
2
3 5 4 8 26
2 5 8 4 3 5
四、读算法(每题7分,共14分) 1. (1)查询链表的尾结点
(2)将第一个结点链接到链表的尾部,作为新的尾结点 (3)返回的线性表为(a2,a3,?,an,a1) 2. 递归地后序遍历链式存储的二叉树。 五、法填空(每空2分,共8 分)
true BST->left BST->right 六、编写算法(8分)
int CountX(LNode* HL,ElemType x)
{ int i=0; LNode* p=HL;//i为计数器 while(p!=NULL)
{ if (P->data==x) i++; p=p->next;
}//while, 出循环时i中的值即为x结点个数 return i; }//CountX
数据结构试卷(二)参考答案
一、选择题 1.D 2.B
3.C
4.A
5.A
6.C
7.B
8.C
二、填空题
1. 构造一个好的HASH函数,确定解决冲突的方法 2. stack.top++,stack.s[stack.top]=x 3. 有序 4. 5. 6. 7. 8.
O(n),O(nlog2n) N0-1,2N0+N1 d/2
(31,38,54,56,75,80,55,63) (1,3,4,5,2),(1,3,2,4,5)
2
三、应用题
1. (22,40,45,48,80,78),(40,45,48,80,22,78) 2. q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q; 3. 2,ASL=91*1+2*2+3*4+4*2)=25/9 4. 树的链式存储结构略,二叉树略
5. E={(1,3),(1,2),(3,5),(5,6),(6,4)} 6. 略
四、算法设计题 1.
设有一组初始记录关键字序列(K1,K2,?,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki。
27
void quickpass(int r[], int s, int t) {
int i=s, j=t, x=r[s];
while(i while (i r[i]=x; } 2. 设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C用 链式存储结构表示。 typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) { lklist *p,*q,*t; for(p=ha,hc=0;p!=0;p=p->next) { for(q=hb;q!=0;q=q->next) if (q->data==p->data) break; if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } } 数据结构试卷(三)参考答案 一、选择题 1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第3小题分析:首先用指针变量q指向结点A的后继结点B,然后将结点B的值复制到结点A中,最后删除结点B。 第9小题分析:9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数,而堆排序只需要在初始堆的基础上再进行10次筛选即可,每次筛选的时间复杂度为O(log2n)。 二、填空题 1. 顺序存储结构、链式存储结构 2. 9,501 3. 5 4. 出度,入度 5. 0 6. e=d 7. 中序 8. 7 28 9. O(1) 10. i/2,2i+1 11. (5,16,71,23,72,94,73) 12. (1,4,3,2) 13. j+1,hashtable[j].key==k 14. return(t),t=t->rchild 第8小题分析:二分查找的过程可以用一棵二叉树来描述,该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。 三、计算题 1. AEFNULLDHFKJGBC 2、H(36)=36 mod 7=1; H1(22)=(1+1) mod 7=2; ….冲突 H(15)=15 mod 7=1;….冲突 H2(22)=(2+1) mod 7=3; H1(15)=(1+1) mod 7=2; H(40)=40 mod 7=5; H(63)=63 mod 7=0; H(22)=22 mod 7=1; ….冲突 (1) 0 1 2 3 4 5 6 63 (2)ASL= 36 15 22 40 1?2?1?1?35?1.6 3、(8,9,4,3,6,1),10,(12,18,18) (1,6,4,3),8,(9),10,12,(18,18) 1,(3,4,6),8,9,10,12,18,(18) 1,3,(4,6),8,9,10,12,18,18 1,3, 4,6,8,9,10,12,18,18 四、算法设计题 1. 设计在单链表中删除值相同的多余结点的算法。 typedef int datatype; typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) 29 { lklist *p,*q,*s; for(p=head;p!=0;p=p->next) { for(q=p->next,s=q;q!=0; ) if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;} } } 2. 设计一个求结点x在二叉树中的双亲结点算法。 typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; bitree *q[20]; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) { if (bt!=0 && flag==0) if (bt->data==x) { flag=1; return;} else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); } } void parent(bitree *bt,char x) { int i; preorder(bt,x); for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf(\ else if (i<=r) printf(\} 数据结构试卷(四)参考答案 一、选择题 1.C 2.D 6.A 7.B 二、填空题 1. O(n2),O(nlog2n) 2. p>llink->rlink=p->rlink; p->rlink->llink=p->rlink 3. 3 4. 2k-1 5. n/2 6. 50,51 7. m-1,(R-F+M)%M 8. n+1-i,n-i 30 3.D 8.A 4.B 9.C 5.C 10.A