欢迎来到天天文库
浏览记录
ID:50548339
大小:2.32 MB
页数:6页
时间:2020-03-10
《数据结构试题大题编程及参考答案.doc》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、数据结构考试题参考答案1、设顺序表L中的数据元素递增有序。试写一算法,将数据元素x插入到顺序表L的适当位置,以保持该表的有序性。解:存储结构为:typedefstructSeqList{DataType*data;intMaxLen;intlen;}SeqList;算法如下:voidinsertLx(SeqList&L,DataTypex){if(L.len==L.maxlen)return;inti=L.len-1;while(i>=0&&x2、在带头结点的单链表L的元素x前插入一个结点y。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下:voidinsert_y_before_x(LinkListL,ElemTypex,ElemTypey){Lnode*q,*p=L;while(p->next&&p->next->data!=x)p=p->next;//找x的前驱结点p;if(!p->next)return;//若不存在结点x,则返回;q=newLnode;q->data=y;q->next=p->next;p->ne3、xt=q;}3、试写一个算法,统计带头指针的单链表L的元素个数。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下:intlength(LinkListL){intlen=0;Lnode*p=L;while(p){len++;p=p->next;}returnlen;}注:如果单链表是带头结点的,则算法如下:intlength(LinkListL){intlen=0;Lnode*p=L->next;;while(p){len++;p=p->next;}returnlen;}4、试写4、一个算法,在带头结点的单链表L的第k个结点后插入一个结点x。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下:voidinsert_after_k(LinkListL,intk,ElemTypex){if(k<0)return;Lnode*q,*p=L;inti=0;while(p&&inext;}//找到第k个结点p;if(!p)return;//若不存在第k个结点,则返回;q=newLnode;q->data=x;q->next=p->next;p-5、>next=q;}注:如果是在L的第k个结点前插入一个结点,则找第k-1个结点p,然后插入。5、试写一个算法,在带头结点的单链表L中删除所有的数据元素为x的结点。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下:voidDelete_all_x(LinkListL,Elemtypex){Lnode*p,*q;p=L;while(p){if(p->next&&p->next->data==x){q=p->next;p->next=q->next;deleteq;}elsep=p->6、next;}}注意:要删除所有的值为x的结点。6、假设一个单循环链表L的数据域为整型,设计一个算法,求该表中所有结点的数据之和。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;假设L带头结点,且L指向头结点,则算法如下:intsum_Of_Data(LinkListL){ints=0;Lnode*p=L->next;while(p!=L){s+=p->data;p=p->next;}returns;}假设L不带头结点,且L指向循环链表中任何一个结点,则算法如下:intsum_of_dat7、a(LinkListL){ints=0;Lnode*p=L;if(L){s+=p->data;p=p->next;while(p!=L){s+=p->data;p=p->next;}}returns;}注:以上两种情形,只要给出其中一种情形的解即可。7、假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数。解:存储结构如下: typedefstructbitnode{ElemTypedata;structbitnode*lch
2、在带头结点的单链表L的元素x前插入一个结点y。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下:voidinsert_y_before_x(LinkListL,ElemTypex,ElemTypey){Lnode*q,*p=L;while(p->next&&p->next->data!=x)p=p->next;//找x的前驱结点p;if(!p->next)return;//若不存在结点x,则返回;q=newLnode;q->data=y;q->next=p->next;p->ne
3、xt=q;}3、试写一个算法,统计带头指针的单链表L的元素个数。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下:intlength(LinkListL){intlen=0;Lnode*p=L;while(p){len++;p=p->next;}returnlen;}注:如果单链表是带头结点的,则算法如下:intlength(LinkListL){intlen=0;Lnode*p=L->next;;while(p){len++;p=p->next;}returnlen;}4、试写
4、一个算法,在带头结点的单链表L的第k个结点后插入一个结点x。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下:voidinsert_after_k(LinkListL,intk,ElemTypex){if(k<0)return;Lnode*q,*p=L;inti=0;while(p&&inext;}//找到第k个结点p;if(!p)return;//若不存在第k个结点,则返回;q=newLnode;q->data=x;q->next=p->next;p-
5、>next=q;}注:如果是在L的第k个结点前插入一个结点,则找第k-1个结点p,然后插入。5、试写一个算法,在带头结点的单链表L中删除所有的数据元素为x的结点。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下:voidDelete_all_x(LinkListL,Elemtypex){Lnode*p,*q;p=L;while(p){if(p->next&&p->next->data==x){q=p->next;p->next=q->next;deleteq;}elsep=p->
6、next;}}注意:要删除所有的值为x的结点。6、假设一个单循环链表L的数据域为整型,设计一个算法,求该表中所有结点的数据之和。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;假设L带头结点,且L指向头结点,则算法如下:intsum_Of_Data(LinkListL){ints=0;Lnode*p=L->next;while(p!=L){s+=p->data;p=p->next;}returns;}假设L不带头结点,且L指向循环链表中任何一个结点,则算法如下:intsum_of_dat
7、a(LinkListL){ints=0;Lnode*p=L;if(L){s+=p->data;p=p->next;while(p!=L){s+=p->data;p=p->next;}}returns;}注:以上两种情形,只要给出其中一种情形的解即可。7、假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数。解:存储结构如下: typedefstructbitnode{ElemTypedata;structbitnode*lch
此文档下载收益归作者所有