数据结构经典算法试题
- 格式：doc
- 大小：33.50 KB
- 文档页数：8
r->data=pb->data; pre->next=r;
pre=r;
pb=pb->next;}
Else∥处理pa- >data=pb->data;
{pre->next=pa; pre=pa;
pa=pa->next;∥两结点数据相等时，只将ha的数据链入。
pb=pb->ຫໍສະໝຸດ ext;}if(pa!=null)pre->next=pa;∥将两链表中剩余部分链入结果链表。
else pc->next=pb;∥若hb表未空，则链入结果表。
free(hb); return(ha);
}
1）已知递增有序的两个单链表A，B分别存储了一个集合。设计算法实现求两个集合的并集的运算A:=A∪B【合肥工业大学1999五、1（8分）】解答完全同上2
2）已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。【南京航空航天大学2001六（10分）】
LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。｛LinkedList la;
la=(LinkedList)malloc(sizeof(LNode));
if(pa)pc->next=pa; else pc->next=pb;
free(la);free(lb);∥释放原来两链表的头结点。
2.设带头结点且头指针为ha和hb的两线性表A和B分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和B的并集AUB。要求该并集中的元素仍保持递增有序。且要利用A和B的原有结点空间。【北京邮电大学1992二（15分）】
else if(pa->data>pb->data)
{pc->next=pb;pc=pb;pb=pb->next;}
Else{pc->next=pa;pc=pa;pa=pa->next;∥处理pa->data=pb->data.
u=pb;pb=pb->next;free(u);}
if(pa) pc->next=pa;∥若ha表未空，则链入结果表。
LinkedList Union(LinkedList ha,hb)
{ pa=ha->next;pb=hb->next;∥设工作指针pa和pb。
pc=ha;∥pc为结果链表当前结点的前驱指针。
while(pa&&pb)
if(pa->data<pb->data)
{pc->next=pa;pc=pa;pa=pa->next;}
else pre->next=pb;
free(la);
}
2）已知头指针分别为la和lb的带头结点的单链表中，结点按元素值非递减有序排列。写出将la和lb两链表归并成一个结点按元素值非递减有序排列的单链表（其头指针为lc），并计算算法的时间复杂度。【燕山大学1998五（20分）】
pa=la->next;pb=hb->next;
1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998三、1（5分）】
LinkedList Union(LinkedList la,lb)
{ pa=la->next; pb=lb->next;
la->next=null;
while(pa!=null && pb!=null)∥当两链表均不为空时作
if(pa->data<=pb->data)
{ r=pa->next;
pa->next=la->next;∥将pa结点链于结果表中，同时逆置。
la->next=pa;
pa=r;
}
else
{r=pb->next;
la->next=ha;
pa=ha;
pb=hb;
pre=la;
while(pa&&pb)
if(pa->data<pb->data)∥处理ha中数据
{pre->next=pa;pre=pa;pa=pa->next;}
else if(pa->data>pb->data)∥处理hb中数据。
{r=(LinkedList)malloc(sizeof(LNode));
else if(pa->data<pb->data) {u=pa;pa=pa->next;free(u);}
else {u=pb; pb=pb->next; free(u);}
while(pa){ u=pa; pa=pa->next; free(u);}
{r=pb->next; pb->next=la->next; la->next=pb; pb=r; }
}
1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997四、3（15分）】
pa=la->next;pb=lb->next;
pc=la;∥结果表中当前合并结点的前驱的指针。
while(pa&&pb)
if(pa->data==pb->data)∥交集并入结果表中。
{pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;free(u);}
lc=(LinkedList )malloc(sizeof(LNode));
pc=lc;∥pc是结果链表中当前结点的前驱
while(pa&&pb)
if(pa->data<pb->data)
{pc->next=pa;pc=pa;pa=pa->next;}
else {pc->next=pb;pc=pb;pb=pb->next;}
pb->next=la->next;∥将pb结点链于结果表中，同时逆置。
la->next=pb;
pb=r;
}
while(pa!=null)∥将la表的剩余部分链入结果表，并逆置。
{r=pa->next; pa->next=la->next; la->next=pa; pa=r; }
while(pb!=null)
pre=r;
pb=pb->next;}
Else∥处理pa- >data=pb->data;
{pre->next=pa; pre=pa;
pa=pa->next;∥两结点数据相等时，只将ha的数据链入。
pb=pb->ຫໍສະໝຸດ ext;}if(pa!=null)pre->next=pa;∥将两链表中剩余部分链入结果链表。
else pc->next=pb;∥若hb表未空，则链入结果表。
free(hb); return(ha);
}
1）已知递增有序的两个单链表A，B分别存储了一个集合。设计算法实现求两个集合的并集的运算A:=A∪B【合肥工业大学1999五、1（8分）】解答完全同上2
2）已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。【南京航空航天大学2001六（10分）】
LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。｛LinkedList la;
la=(LinkedList)malloc(sizeof(LNode));
if(pa)pc->next=pa; else pc->next=pb;
free(la);free(lb);∥释放原来两链表的头结点。
2.设带头结点且头指针为ha和hb的两线性表A和B分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和B的并集AUB。要求该并集中的元素仍保持递增有序。且要利用A和B的原有结点空间。【北京邮电大学1992二（15分）】
else if(pa->data>pb->data)
{pc->next=pb;pc=pb;pb=pb->next;}
Else{pc->next=pa;pc=pa;pa=pa->next;∥处理pa->data=pb->data.
u=pb;pb=pb->next;free(u);}
if(pa) pc->next=pa;∥若ha表未空，则链入结果表。
LinkedList Union(LinkedList ha,hb)
{ pa=ha->next;pb=hb->next;∥设工作指针pa和pb。
pc=ha;∥pc为结果链表当前结点的前驱指针。
while(pa&&pb)
if(pa->data<pb->data)
{pc->next=pa;pc=pa;pa=pa->next;}
else pre->next=pb;
free(la);
}
2）已知头指针分别为la和lb的带头结点的单链表中，结点按元素值非递减有序排列。写出将la和lb两链表归并成一个结点按元素值非递减有序排列的单链表（其头指针为lc），并计算算法的时间复杂度。【燕山大学1998五（20分）】
pa=la->next;pb=hb->next;
1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998三、1（5分）】
LinkedList Union(LinkedList la,lb)
{ pa=la->next; pb=lb->next;
la->next=null;
while(pa!=null && pb!=null)∥当两链表均不为空时作
if(pa->data<=pb->data)
{ r=pa->next;
pa->next=la->next;∥将pa结点链于结果表中，同时逆置。
la->next=pa;
pa=r;
}
else
{r=pb->next;
la->next=ha;
pa=ha;
pb=hb;
pre=la;
while(pa&&pb)
if(pa->data<pb->data)∥处理ha中数据
{pre->next=pa;pre=pa;pa=pa->next;}
else if(pa->data>pb->data)∥处理hb中数据。
{r=(LinkedList)malloc(sizeof(LNode));
else if(pa->data<pb->data) {u=pa;pa=pa->next;free(u);}
else {u=pb; pb=pb->next; free(u);}
while(pa){ u=pa; pa=pa->next; free(u);}
{r=pb->next; pb->next=la->next; la->next=pb; pb=r; }
}
1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997四、3（15分）】
pa=la->next;pb=lb->next;
pc=la;∥结果表中当前合并结点的前驱的指针。
while(pa&&pb)
if(pa->data==pb->data)∥交集并入结果表中。
{pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;free(u);}
lc=(LinkedList )malloc(sizeof(LNode));
pc=lc;∥pc是结果链表中当前结点的前驱
while(pa&&pb)
if(pa->data<pb->data)
{pc->next=pa;pc=pa;pa=pa->next;}
else {pc->next=pb;pc=pb;pb=pb->next;}
pb->next=la->next;∥将pb结点链于结果表中，同时逆置。
la->next=pb;
pb=r;
}
while(pa!=null)∥将la表的剩余部分链入结果表，并逆置。
{r=pa->next; pa->next=la->next; la->next=pa; pa=r; }
while(pb!=null)
