《天津大学19秋--数据结构第五 组》由会员分享，可在线阅读，更多相关《天津大学19秋--数据结构第五 组（4页珍藏版）》请在金锄头文库上搜索。
1、天津大学网络教育学院试卷专用纸考试科目： 数据结构 学习中心： 姓名： 学号：答题：第（ 五 ）组答案：一、编程题（每小题30分，共60分）(一)1.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。typedefchar datatype;typedefstruct node datatype data; struct node *next;lklist;voidsplit(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc)lklist *p; ha=0,
2、hb=0,hc=0;for(p=head;p!=0;p=head)head=p-next; p-next=0;if (p-data=A &p-datanext=ha; ha=p;else if (p-data=0 &p-datanext=hb; hb=p; else p-next=hc; hc=p;2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 typedefstructnodeintdata;structnode*lchild,*rchild;bitree;voidswapbitree(bitree*bt)bitree*p;if(bt=0)return;swapbitree(b
3、t-lchild);swapbitree(bt-rchild);p=bt-lchild;bt-lchild=bt-rchild;bt-rchild=p;(二)1. 设计在单链表中删除值相同的多余结点的算法。 typedefintdatatype;typedefstructnodedatatypedata;structnode*next;lklist;voiddelredundant(lklist*&head)lklist*p,*q,*s;for(p=head;p!=0;p=p-next)for(q=p-next,s=q;q!=0;)if(q-data=p-data)s-next=q-next;
4、free(q);q=s-next;elses=q,q=q-next; 2. 设计一个求结点x在二叉树中的双亲结点算法。 typedefstructnodedatatypedata;structnode*lchild,*rchild;bitree;bitree*q20;intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx)if(bt!=0&flag=0)if(bt-data=x)flag=1;return;elser=(r+1)%20;qr=bt;preorder(bt-lchild,x);preorder(bt-rchild,x);voidparent(
5、bitree*bt,charx)inti;preorder(bt,x);for(i=f+1;ilchild-data=x|qi-rchild-data)break;if(flag=0)printf(notfoundxn);elseif(idata);elseprintf(notparent);二、解答题（20分）(一)对下面的带权无向图采用prim算法从顶点开始构造最小生成树。（写出加入生成树顶点集合S和选择Edge的顺序） 9 10 7 5 6 7 11 8S:顶点号Edge:(顶点，顶点，权值)(，9)(，5)( ，7)(，6)( ，7)三、画图题（20分）(一)已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树对应的二叉树。123456789101112131415dataABCDEFGHIJKLMNOparent011122334456678（1）从森林转换为二叉树： （2）计算二叉树的深度的算法： Int depth(tree *T) If(!T) Return 0; Else Return 1+max(depth(T-Lchild),depth(-Rchild);
