1. 线性表为：（78，50，40，60，34，90）
?0?1??1??1?02. 邻接矩阵：?1110?0101??1011??0101?1110??
邻接表如图11所示：
图11
3. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
4. 见图12
4 2 4 4 2 4 2 2 5 4 8 2 3 8 4 5 5 8 4 3 2 5 图12
四、读算法（每题7分，共14分） 1. （1）查询链表的尾结点
（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,?,an,a1） 2. 递归地后序遍历链式存储的二叉树。 五、法填空（每空2分，共8 分） true BST->left BST->right
37
六、编写算法（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
二、填空题
1. 构造一个好的HASH函数，确定解决冲突的方法 2. stack.top++，stack.s[stack.top]=x 3. 有序
4. O(n)，O(nlog2n) 5. N0-1，2N0+N1 6. d/2
7. (31，38，54，56，75，80，55，63) 8. (1，3，4，5，2)，(1，3，2，4，5)
三、应用题
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
2
2.B 3.C 4.A 5.A 6.C 7.B 8.C
38
4. 树的链式存储结构略，二叉树略
5. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6. 略
四、算法设计题 1.
设有一组初始记录关键字序列（K1，K2，?，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。 void quickpass(int r[], int s, int t) {
int i=s, j=t, x=r[s]; while(i while (i 设有两个集合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;} } } 39 数据结构试卷（三）参考答案 一、选择题 1.B 6.B 2.B 7.D 3.A 8.C 4.A 9.B 5.A 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 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 40