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

void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) {

lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) {

head=p->next; p->next=0;

if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;}

else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} } }

2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。

typedef struct node {int data; struct node *lchild,*rchild;} bitree; void swapbitree(bitree *bt) {

bitree *p;

if(bt==0) return;

swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; }

3. 在链式存储结构上建立一棵二叉排序树。

#define n 10

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void bstinsert(bitree *&bt,int key) {

if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;} else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key); }

void createbsttree(bitree *&bt) {

int i;

for(i=1;i<=n;i++) bstinsert(bt,random(100)); }

17

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

二、填空题

1. n-i，r[j+1]=r[j]

2. mid=(low+high)/2，r[mid].key>k 三、应用题 2. DEBCA

3. E={(1,5),(5,2),(5,3),(3,4)},W=10 4. ASL=(1*1+2*2+3*4)/7=17/7 5. ASL1=7/6，ASL2=4/3 四、算法设计题

1. 设计判断两个二叉树是否相同的算法。

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; int judgebitree(bitree *bt1,bitree *bt2) {

if (bt1==0 && bt2==0) return(1);

else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) return(0);

else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild)); }

2. 设计两个有序单链表的合并排序算法。

void mergelklist(lklist *ha,lklist *hb,lklist *&hc) {

lklist *s=hc=0;

while(ha!=0 && hb!=0)

if(ha->datadata){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;} else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha; }

18

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

四、算法设计题

1. 设计在顺序有序表中实现二分查找的算法。

struct record {int key; int others;}; int bisearch(struct record r[ ], int k) {

int low=0,mid,high=n-1; while(low<=high) {

mid=(low+high)/2;

if(r[mid].key==k) return(mid+1); else if(r[mid].key>k) high=mid-1; else low=mid+1; }

return(0); }

2. 设计判断二叉树是否为二叉排序树的算法。 int minnum=-32768,flag=1;

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void inorder(bitree *bt) { if (bt!=0) {inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key;inorder(bt->rchild);} }

3. 在链式存储结构上设计直接插入排序算法

void straightinsertsort(lklist *&head) {

lklist *s,*p,*q; int t;

if (head==0 || head->next==0) return;

else for(q=head,p=head->next;p!=0;p=q->next) {

for(s=head;s!=q->next;s=s->next) if (s->data>p->data) break; if(s==q->next)q=p;

else{q->next=p->next; p->next=s->next; s->next=p;

t=p->data;p->data=s->data;s->data=t;}

} }

19

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

三．填空题

1. i

1. 设计在链式结构上实现简单选择排序算法。

void simpleselectsorlklist(lklist *&head) {

lklist *p,*q,*s; int min,t;

if(head==0 ||head->next==0) return; for(q=head; q!=0;q=q->next) {

min=q->data; s=q;

for(p=q->next; p!=0;p=p->next) if(min>p->data){min=p->data; s=p;} if(s!=q){t=s->data; s->data=q->data; q->data=t;} } }

2. 设计在顺序存储结构上实现求子串算法。

void substring(char s[ ], long start, long count, char t[ ]) {

long i,j,length=strlen(s);

if (start<1 || start>length) printf(\ else if (start+count-1>length) printf(\else { for(i=start-1,j=0; i

3. 设计求结点在二叉排序树中层次的算法。

int lev=0;

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void level(bitree *bt,int x) {

if (bt!=0)

{lev++; if (bt->key==x) return; else if (bt->key>x) level(bt->lchild,x); level(bt->rchild,x);} }

20

else