算法设计习题(完整).doc

《算法设计习题(完整).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本文算法设计题涉及的顺序表和线性链表的类型定义如下：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;typedefstructLNode{ELemTypedata;StructLNode*next;}LNode,*LinkList;算法设计习题1、设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。voidInsert(Sq

2、list&L,inte)//把e插入到递增顺序表L中{inti;int*newbase;if(L.length>=L.listsize)//va空间不足{newbase=(int*)malloc((LISTINCREMENT+L.listsize)*sizeof(int));//分配空间if(!newbase)exit(OVERFLOW);//分配空间不成功则返回L.elem=newbase;//新基址L.listsize=L.listsize+LISTINCREMENT;//增加存储容量}for(i=L.length-1;

3、(i>=0)&&(L.elem[i]>e);i--)L.elem[i+1]=L.elem[i];//大于e的元素依次后移L.elem[i+1]=e;//插入eL.length++;//长度+1}2、设A=(a1,…..am)和B=(b1,……,bn)均为顺序表，A’和B’分别为A和B中除去最大共同前缀后的子表(例如，A=(x,y,y,z,x,z),B=(x,y,y,z,y,x,x,z),则两者中最大的共同前缀为(x,y,y,z)，在两表中除去最大共同前缀后的子表分别为A’=(x,z)和B’=(y,x,x,z)。若A’=B’=

4、空表，则A=B；若A’=空表，而B’空表，或者两者都不为空表，且A’的首元小于B’的首元，则AB。试写一个比较A,B大小的算法（请注意：在算法中，不要破坏原表A和B，并且，也不一定先求得A’和B’才进行比较）。charcompare(SqListA,SqListB)//比较顺序表A,B{intshortest;inti=0;if(A.length>B.length)shortest=B.length;elseshortest=A.length;for(i=0;i

5、i]>B.elem[i])return'>';//以短表的长度作循环if(A.elem[i]B.length)return'>';if(A.length

6、LL的时候n++{p=p->next;n++;}return(n);}4、已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。LinkListLink(LinkList&L1,LinkList&L2,LinkList&L3,intm,intn){//将两个单链表连接在一起,m,n分别为L1与L2的长度L

7、Node*p,*q;p=L1->next;q=L2->next;if(m>=n){while(q->next)q=q->next;//查找短链表终端结点q->next=p;//长的放在短的后面L3->next=L2->next;}else{while(p->next)p=p->next;//查找短链表终端结点p->next=q;//长的放在短的后面L3->next=L1->next;}returnL3;}时间复杂度为o(min(m.n))5、已知指针la和lb分别指向两个无头结点单链表中的首结点。下列算法是从表la中删除自第

8、i个元素起共len个元素后，将它们插入到表lb中第j个元素之前。试问次算法是否正确？若有错，则请改正之。StatusDeleteAndInsertSub(LinkedListla,LinkedListlb,intI,intj,intlen){if(i<0

9、

10、j<0

11、

12、len<0)retur