《数据结构》吕云翔编著第2章线性表习题解答.pdf

该【《数据结构》吕云翔编著第2章线性表习题解答 】是由【青山代下】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【《数据结构》吕云翔编著第2章线性表习题解答 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构第二章****题解答一、,向第i个元素(1≤i≤n+1)之前插入一个新元素时,需要从后向前依次后移(B)个元素。A、n-iB、n-i+1C、n-i-1D、,删除第i个元素(1≤i≤n+1)时,需要从前向后依次前移(A)个元素。A、n-iB、n-i+1C、n-i-1D、,在等概率情况下,查找成功时的平均查找长度(即需要比较的元素个数)为(C)。.(n+1)/2D.(n-1)/,删除值为x的元素时需要比较元素和移动元素的总次数为(C)。A.(n+1)/.n+(B)。(n)(1)(n*n)(log2n),它的前驱结点的引用为q,则删除p的后继结点的操作为(B)。====,则在保存所有系数项的线性表表示中,其线性表长度为(A)。+-+2二、,共包含有________多个插入元素的位置,共包含有________多个删除元素的位置。(答案n+1n),则最好采用________存储结构,若经常需要对线性表进行表头插入和删除运算,则最好采用________存储结构。(答案:顺序链式),若每次都调用插入算法把一个元素插入到表头,则整个算法的时间复杂度为________,若每次都调用插入算法把一个元素插入到表尾,则整个算法的时间复杂度为________。(答案:O(n)O(n)),若每次都调用插入算法把一个元素插入到表头,则整个算法的时间复杂度为________,若每次都调用插入算法把一个元素插入到表尾,则整个算法的时间复杂度为________。(答案:O(1)O(1)),在表头插入元素的时间复杂度为________,在表尾插入元素的时间复杂度为________。(答案:O(n),O(1)),在表头插入结点的时间复杂度为________,在表尾插入结点的时间复杂度为________。(答案:O(1),O(1))(结点)的时间复杂度分别为________和_______。(答案:O(1),O(n))三、,要求当删除一个元素后检查数组空间的大小,若空间利用率小于40%同时数组长度大于maxSize时则释放数组的一半存储空间。publicvoidremove(inti)throwsException{if(i<0||i>curLen-1)删除位置非法for(intj=i;i<curLen-1;i++)listItem[j]=listItem[j+1];curLen--;if((double)curLen/maxSize<&&curLen>maxSize){maxSize=maxSize/2;listItem=newObject[maxSize];(maxSize);}},它包含有一维数组参数Object[]a,,并且根据a数组中的所有不同的元素值建立一个集合。publicsequenceSet(Object[]a){length=0;setArray=newObject[(int)(*)];for(inti=0;i<;i++){intj;for(j=0;j<length;j++)if(setArray[j].equals(a[i]))break;if(j==length){setArray[length]=a[i];length++;}}},返回一个顺序存储的集合set中所有元素的最大值,假定元素类型为Double。publicstaticObjectmaxValue(Setset){sequenceSetdset=(sequenceSet)set;if(()==0)returnnull;Doublex=(Double)(1);for(inti=1;i<();i++){Doubley=(Double)(i+1);if(pareTo(x)>0)x=y;}returnx;},它包含有一个参数为Setset,实现把set所指向的顺序集合的内容复制到当前集合中的功能。publicsequenceSet(Setset){sequenceSetdset=(sequenceSet)set;setArray=newObject[];for(inti=0;i<;i++)setArray[i]=[i];length=;},实现两个顺序存储集合的差运算,并返回所求得的差集。publicstaticSetdifference(Setset1,Setset2){sequenceSetdset2=(sequenceSet)set2;sequenceSet1dset3=newsequenceSet(set1);for(inti=0;i<();i++)((i+1));returndset3;},实现两个链接存储集合的差运算,并返回所求得的差集。publicstaticSetdifference1(Setset1,Setset2){linkSetdset1=(linkSet)set1;linkSetdset2=(linkSet)set2;linkSetdset3=newlinkSet();if(n<=0||m<=0||s<=0){参数值不合法,退出运行!(1);}sequenceLista=newsequenceList(n);//定义和创建一个线性表ainti,k;for(i=1;i<=n;i++)(i,i);//插入n个元素,元素值依次为1~nk=s;//给k赋初值为s,开始从编号为s的人起报数for(i=1;i<n;i++){//循环n-1次,每次使一个人出列k=(k+m-1)%();//计算出待出列的元素序号if(k==0)k=();//若k的值为0则应修改为表尾的序号//(k);//从线性表中删除序号为k的元素}((1));//输出最后剩余的一个元素的值}staticvoidlinkJosephus(intn,intm,ints){//使用链表解决约琵夫问题的算法,n为人数if(n<=0||m<=0||s<=0){参数值不合法,退出运行!(1);}linkLista=newlinkList();//定义和创建一个空的线性链表ainti,k;for(i=n;i>=1;i--)(i,1);//插入n个结点,结点值依次为1~nNodep=(),q=,head=p;//q指向表头结点,p为前驱k=1;//给k赋初值1while(k<s){//循环结束后q结点为第s个结点p=q;q=;if(q==head){p=q;q=;}//若q为附加表头结点,则移到表头k++;}for(i=1;i<n;i++){//循环n-1次,每次从1报数到mk=1;while(k<m){//每次循环结束,q指向要出列的结点p=q;q=;if(q==head){p=q;q=;}//使指针跳过表头附加结点k++;}=;//从链表中删除q结点if(==head){//使指针跳过表头附加结点p=head;q=;}elseq=;//修改q的值,将从q结点重新报数}();//最后一个人出列}publicstaticvoidmain(String[]args){linkJosephus(8,4,1);seqJosephus(8,4,1);}}