顺序表的应用ppt课件.ppt

《顺序表的应用ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、顺序表的应用课后习题+算法设计题填空题顺序存储的长度为n的线性表，在任何位置上插入和删除操作的时间复杂度基本上都一样，都是（）。插入一个元素大约移动表中的（）个元素，删除一个元素时大约移动表中的（）个元素。选择题1、在数据结构的讨论中把数据结构从逻辑上分为（）A内部结构与外部结构B静态结构与动态结构C线性结构与非线性结构D紧凑结构与非紧凑结构2、数据结构的定义为(D，S)，其中D是()的集合。A算法B数据元素C数据操作D逻辑结构3、下面程序段的时间复杂度为（B）intf(intn){if(n==0

2、

3、n==1)return1;elsereturn

4、n*f(n-1);}AO(1)BO(n)CO(n2)DO(n!)2-14编写一个算法，逐个输出顺序表中的所有元素，设元素的数据类型为int。答案voidDispList(SeqListL){inti;for(i=0;i

5、L.list[i]!=x)i++;if(i>=L.size)return-1;elsereturni;}答案—方法2（课后答案）intListfind(SeqListL，datatypex){inti;for(i=0;isize>=max

6、size){printf(“顺序表已满，无法插入！”);return0;}for(i=L->size-1;i>=0&&xlist[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;ilist[i];L->list[i]=L->list[L->size-1-i];L->l

7、ist[L->size-1-i]=x;}}2-24设计一个非递减的有序顺序表，要求：（1）编写算法，实现操作集合：初始化、求元素个数、插入、删除、取元素；（2）设计一个测试主函数实际验证所设计的顺序表的正确性。设计思路对比顺序表，分析各个算法的异同。根据各个算法，编写功能函数，保存在头文件“orderlist.h”中。编写主函数，调用各个功能函数。特别操作插入删除分为指定位置删除操作和指定元素删除操作。课外题目1已知，顺序表的元素类型为整型，编写将该顺序表分成两个顺序表的算法，一个存放所的大于或等于0的数据元素，另一个存放所的小于0的数据元素。答

8、案voidSeparate(SeqlistLa,Seqlist*Lb,Seqlist*Lc){a=b=c=0;for(a=0;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

9、=0,k=0;for(inti=0;ilist[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.分别从两个有序表中取出一个元素比

10、较大小，并将较小的元素放入到C中。当一个有序表为空时，将另一个有序表的剩余元素直接放到C的后面。算法分析两个顺序表按递增方式排列，在进行