顺序表的应用

顺序表的应用课后习题+算法设计题填空题顺序存储的长度为n的线性表，在任何位置上插入和删除操作的时间复杂度基本上都一样，都是（）。插入一个元素大约移动表中的（）个元素，删除一个元素时大约移动表中的（）个元素。选择题1、在数据结构的讨论中把数据结构从逻辑上分为（）A内部结构与外部结构B静态结构与动态结构C线性结构与非线性结构D紧凑结构与非紧凑结构2、数据结构的定义为(D，S)，其中D是()的集合。A算法B数据元素C数据操作D逻辑结构3、下面程序段的时间复杂度为（B）intf(intn){if(n==0||n==1)return1;elsereturnn*f(n-1);}AO(1)BO(n)CO(n2)DO(n!)2-14编写一个算法，逐个输出顺序表中的所有元素，设元素的数据类型为int。答案voidDispList(SeqListL){inti;for(i=0;iL.size;i++)printf(%d,,L.list[i]);}2-16编写一个算法，实现顺序表的定位操作：查找在顺序表中是否存在数据元素x，若存在，则返回表中第一个与x值相等的元素下标；若不存在，返回-1。答案—方法1intLocate(SeqListL,dataypex){inti=0;while(iL.size&&L.list[i]!=x)i++;if(i=L.size)return-1;elsereturni;}答案—方法2（课后答案）intListfind(SeqListL，datatypex){inti;for(i=0;iL.size;i++){if(L.list[i]==x)returni;elsecontinue;}return-1;}2-17设顺序表递增有序，编写一个算法，将数据元素x插入表中合适位置之后，顺序表仍然保持有序。答案intOrderinsert(Seqlist*L,datatypex){inti;if(L-size=maxsize){printf(“顺序表已满，无法插入！”);return0;}for(i=L-size-1;i=0&&xL-list[i];i--)L-list[i+1]=L-list[i];L-list[i+1]=x;L-size++;return1;}2-18编写算法实现顺序表的就地逆置。答案voidconverse(Seqlist*L){intmid=L-size/2,i;datatypex;for(i=0;imid;i++){x=L-list[i];L-list[i]=L-list[L-size-1-i];L-list[L-size-1-i]=x;}}2-24设计一个非递减的有序顺序表，要求：（1）编写算法，实现操作集合：初始化、求元素个数、插入、删除、取元素；（2）设计一个测试主函数实际验证所设计的顺序表的正确性。设计思路对比顺序表，分析各个算法的异同。根据各个算法，编写功能函数，保存在头文件“orderlist.h”中。编写主函数，调用各个功能函数。特别操作插入删除分为指定位置删除操作和指定元素删除操作。课外题目1已知，顺序表的元素类型为整型，编写将该顺序表分成两个顺序表的算法，一个存放所的大于或等于0的数据元素，另一个存放所的小于0的数据元素。答案voidSeparate(SeqlistLa,Seqlist*Lb,Seqlist*Lc){a=b=c=0;for(a=0;aLa.size;a++)if(La.list[a]=0)Lb-list[b++]=La.list[a];elseLc-list[c++]=La.list[a];Lb-size=b;Lc-size=c;}课外题目2已知，顺序表的元素类型为整型，编写将该顺序表分成两个顺序表的算法，一个存放所的奇数元素，另一个存放所的偶数元素。答案voidfenSq(ListSqL,ListSq*a,ListSq*Lb){intj=0,k=0;for(inti=0;iL.size;i++)if(L.list[i]%2==0){Lb-list[j]=L-list[i];j++;}else{La-list[k]=L.list[i];k++;}La.size=k;Lb.size=j;}课外题目3将两个递增有序的顺序表A、B，进行合并成一个递增有序的顺序表C，并要求同样的数据元素在新表中只出现一次。三种思路1.合并两个有序表，然后再排序。2.将有序表A存放到C中，然后将B中的元素一个一个地插入到C中,在插入的过程中注意如何优化比较次数。3.分别从两个有序表中取出一个元素比较大小，并将较小的元素放入到C中。当一个有序表为空时，将另一个有序表的剩余元素直接放到C的后面。算法分析两个顺序表按递增方式排列，在进行合并时，依次比较，哪个线性表中的元素值小就先将这个元素复制到新的线性表中，若两个元素相等，则复制一个即可，一直到其中的一个线性表中的元素全部复制到新表后，将另一个表中剩余的元素复制到新表中即可。算法的时间性能是O(m+n)，其中m是A的表长，n是B的表长。答案voidhebing(SeqlistLa,SeqlistLb,Seqlist*Lc){inta=0,b=0,c=0;while(aLa.size&&bLb.size){if(La.list[a]Lb.list[b])Lc-list[c++]=Lb.list[b++];if(La.list[a]Lb.list[b])Lc-list[c++]=La.list[a++];if(La.list[a]==Lb.list[b]){Lc-list[c++]=La.list[a++];b++}}续If(aLa.size-1)for(k=i;kLa.size;k++)Lc-list[c++]=La.list[k];If(bLb.size-1)for(k=i;kLb.size;k++)Lc-list[c++]=Lb.list[k];Lc-size=k;}作业利用第二种算法实现两个有序表的合并。课外题目4编写一个算法，实现删除顺序表中多余的值相同的元素。答案voiddel(ListSq*L){inti=0;while(iL-size-1){intj=i+1;while(jL-size)if(L.list[i]==L.list[j]){for(intk=j+1;kL.size;k++)L.list[k-1]=L.list[k];L.size--;}elsej++;i++;}}约瑟夫问题(猴子选大王描述)一堆猴子都有编号，编号是1，2，3...m,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。基本要求(1)输入数据：输入m,nm,n为整数，nm(2)中文提示按照m个猴子，数n个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能.答案课外习题5求两个集合的交集、并集、差集运算。