数据结构综合算法题.doc

《数据结构综合算法题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、综合算法题1、已知两个链表A和B分别表示两个集合，其元素递增排列。写一算法，求A与B的交集，其元素也递增排列，并存放于A链表中。voiddiffence(LinkList&La,LinkListLb){//带头结点的单链表La,Lb,其元素递增排列,求其交集,并存放与La中p=La;q=Lb-->next;while(p-->next){while(p-->next-->data>q-->data)q=q-->next;//直到Lb中第一个不小于该结点的元素值止if(p-->next-->data==q-->data)p=p-->next;el

2、se{r=p-->next;p-->next=r-->next;free(r);}例：A：3，4，5，6，7B：1，4，6，8交集：4，6}//while(p-->next)}//diffence2．已知（k1，k2，……，kp）是堆，则可以写一个时间复杂度为O（logn）的算法，将（k1，k2，……，kp，kp+1）调整为堆，试编写“从p=1起，逐个插入建堆”的算法，并讨论由此方法建堆的时间复杂度。（10分）VoidcreateHeap(HeapType&H,intn){（1分）//从第一个元素起逐步插入建一个大顶堆for(p=2;p<=n;

3、++p){//此时从H.r[1]……H.r[p]已是大顶堆j=p;for(i=j/2;i<=1;i=i/2){if(LT(H.r[i].key,H[j].key)H.r[i]ß>H.r[j];j=i;}//for}//for}//CreateHeap时间复杂度：当H.r[1]……H.r[p-1]已是大顶堆时，插入第p个元素，将其调整为堆，实际上是走了一条从叶子到根的路径，需比较次，故共需比较：++……+

4、替的冒泡排序算法。voidBubbleSort2(inta[],intn)//相邻两趟向相反方向起泡的冒泡排序算法{change=1;low=0;high=n-1;//冒泡的上下界while(lowa[i+1]){a[i]<-->a[i+1];change=1;}//有交换，修改标志changehigh--;//修改上界for(i=high;i>low;i--)//从下向上起泡if(a[i]

5、a[i]<-->a[i-1];change=1;}low++;//修改下界}//while}//BubbleSort2[算法讨论]题目中“向上移”理解为向序列的右端，而“向下移”按向序列的左端来处理。4．编程求以孩子—兄弟表示法存储的森林的叶子结点数。要求描述结构。[题目分析]当森林（树）以孩子兄弟表示法存储时，若结点没有孩子（fch=null）,则它必是叶子，总的叶子结点个数是孩子子树（fch）上的叶子数和兄弟（nsib）子树上叶结点个数之和。typedefstructnode{ElemTypedata;//数据域structnode*fch

6、,*nsib;//孩子与兄弟域}*Tree;intLeaves(Treet)//计算以孩子-兄弟表示法存储的森林的叶子数{if(t)if(t->fch==null)//若结点无孩子，则该结点必是叶子return(1+Leaves(t->nsib));//返回叶子结点和其兄弟子树中的叶子结点数elsereturn(Leaves(t->fch)+Leaves(t->nsib));//孩子子树和兄弟子树中叶子数之和}//结束Leaves