一、选择题 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. O(n2)，O(nlog2n) 5. N0-1，2N0+N1

6. d/2

7. (31，38，54，56，75，80，55，63) 8. (1，3，4，2)，(1，3，2，4)

三、应用题

1. (22，40，45，48，80，78)，(40，45，48，80，22，78) 2. 3. 4. 5.

q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q; 2,ASL=91*1+2*2+3*4+4*2)=25/9 树的链式存储结构略，二叉树略

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<j){

while (i<j && r[j]>x) j=j-1; if (i<j) {r[i]=r[j];i=i+1;}

while (i<j && r[i]<x) i=i+1; if (i<j) {r[j]=r[i];j=j-1;}

}

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;} } }

数据结构试卷（三）