(完整)东南大学十套数据结构试题及答案,推荐文档

数据结构试卷（二）参考答案

三、应用题

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

数据结构试卷（三）参考答案

二．填空题

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

AEFGBCDHFKJNULL 2、H(36)=36 mod 7=1; H１(22)=(1+1) mod 7=2; ….冲突

H(15)=15 mod 7=1;….冲突 H2(22)=(2+1) mod 7=3; H１(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) {

14

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(\

15

数据结构试卷（四）参考答案

二、填空题

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

0123456789456^9^38^^^^^^27^

四、算法设计题

1. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表

中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 typedef char datatype;

typedef struct node {datatype data; struct node *next;}lklist;

16