东南大学十套大数据结构精彩试题及问题详解 下载本文

标准文档

{ if (P->data==x) i++; p=p->next;

}//while, 出循环时i中的值即为x结点个数 return i; }//CountX

数据结构试卷(二)参考答案

三、应用题

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。

void quickpass(int r[], int s, int t) {

int i=s, j=t, x=r[s]; while(i

while (ix) j=j-1; if (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;}

}

}

实用大全

标准文档

数据结构试卷(三)参考答案

二.填空题

13.j+1,hashtable[j].key==k 14.return(t),t=t->rchild 三、计算题 1.

AEFGBCDHFKJNULL 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 36 15 22 40 (2)ASL=

1?2?1?1?3?1.6

53、(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)

实用大全

标准文档

{

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. (19,18,16,20,30,22) 2. (16,18,19,20,32,22) 3. A[i][j]=1 4. 等于 5. BDCA

6. hashtable[i]=0,hashtable[k]=s 三、计算题 1. LS1^---->110e---->11^---->10a1^---->10b---->10c^0d^1

2.

(1) ABCDEF; BDEFCA;(2) ABCDEFGHIJK; BDEFCAIJKHG林转换为相应的二叉树;

ABCDEFIJKHG 3.H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6

实用大全