欢迎来到天天文库
浏览记录
ID:39693323
大小:2.32 MB
页数:6页
时间:2019-07-09
《数据结构试题大题编程及参考答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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.len++;}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=ne3、wLnode;q->data=y;q->next=p->next;p->next=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;L4、node*p=L->next;;while(p){len++;p=p->next;}returnlen;}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;}//找5、到第k个结点p;if(!p)return;//若不存在第k个结点,则返回;q=newLnode;q->data=x;q->next=p->next;p->next=q;}注:如果是在L的第k个结点前插入一个结点,则找第k-1个结点p,然后插入。5、试写一个算法,在带头结点的单链表L中删除所有的数据元素为x的结点。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下:voidDelete_all_x(LinkListL,Elemtypex){Lno6、de*p,*q;p=L;while(p){if(p->next&&p->next->data==x){q=p->next;p->next=q->next;deleteq;}elsep=p->next;}}注意:要删除所有的值为x的结点。6、假设一个单循环链表L的数据域为整型,设计一个算法,求该表中所有结点的数据之和。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;假设L带头结点,且L指向头结点,则算法如下:intsum_Of_Data(LinkLis7、tL){ints=0;Lnode*p=L->next;while(p!=L){s+=p->data;p=p->next;}returns;}假设L不带头结点,且L指向循环链表中任何一个结点,则算法如下:intsum_of_data(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、假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数。解:存储结构如8、下: typedefstructbitnode{ElemTypedata;structbitnode*lch
2、;L.len++;}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=ne
3、wLnode;q->data=y;q->next=p->next;p->next=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;L
4、node*p=L->next;;while(p){len++;p=p->next;}returnlen;}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;}//找
5、到第k个结点p;if(!p)return;//若不存在第k个结点,则返回;q=newLnode;q->data=x;q->next=p->next;p->next=q;}注:如果是在L的第k个结点前插入一个结点,则找第k-1个结点p,然后插入。5、试写一个算法,在带头结点的单链表L中删除所有的数据元素为x的结点。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下:voidDelete_all_x(LinkListL,Elemtypex){Lno
6、de*p,*q;p=L;while(p){if(p->next&&p->next->data==x){q=p->next;p->next=q->next;deleteq;}elsep=p->next;}}注意:要删除所有的值为x的结点。6、假设一个单循环链表L的数据域为整型,设计一个算法,求该表中所有结点的数据之和。解:存储结构如下:typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;假设L带头结点,且L指向头结点,则算法如下:intsum_Of_Data(LinkLis
7、tL){ints=0;Lnode*p=L->next;while(p!=L){s+=p->data;p=p->next;}returns;}假设L不带头结点,且L指向循环链表中任何一个结点,则算法如下:intsum_of_data(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、假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数。解:存储结构如
8、下: typedefstructbitnode{ElemTypedata;structbitnode*lch
此文档下载收益归作者所有