数据结构复习题

1绪论沈阳理工大学应用技术学院信息与控制学院计算机科学与技术教研室2011-5-8

数据构造复习题：绪论单选题1、在数据构造中，与所使用的计算机无关的数据叫__C___构造。A存储|B物理|C逻辑|D物理和存储2、在数据构造中，从逻辑上能够把数据构造分成___C___。A动态构造和静态构造|B紧凑构造和非紧凑构造|C线性构造和非线性构造|D内部构造和外部构造图3、数据构造在计算机内存中的表达是指____A___。数据的存储构造|数据构造|数据的逻辑构造|数据元素之间的关系4、在数据构造中，与所使用的计算机无关的是数据的__A____构造。逻辑|存储|逻辑和存储|物理5、在下列的叙述中，对的的是__B___。线性表的线性存储构造优于链表存储构造|二维数组是其数据元素为线性表的线性表|栈的操作方式是先进先出|队列的操作方式是先进后出6、在决定选用何种存储构造时，普通不考虑_______。各结点的值如何|结束个数的多少|对数据有哪些运算|所用编程语言实现这种构造与否方便7、在存储数据时，普通不仅要存储各数据元素的值，并且还要存储_______。数据的解决办法|数据元素的类型|数据元素之间的关系|数据的存储办法8、下面说法错误的是_______。(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相似的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏状况下，预计算法执行时间的一种上界(4)同一种算法，实现语句的级别越高，执行效率越低(1)|(1)、(2)|(1)、(4)|(3)9、普通规定同一逻辑构造中的全部数据元素含有相似的特性。这意味着______。数据元素含有同一特点|不仅数据元素所包含的数据项的个数要相似，并且对应的数据项的类型要一致|每个数据元素都同样|数据元素所包含的数据项的个数要相等10、下列说法对的的是_______。数据元素是数据的最小单位|数据项是数据的基本单位|数据构造是带构造的数据项的集合|某些表面上很不相似的数据能够有相似的逻辑构造11、____是数据的最小单元,_____是数据的基本单位.数据项|数据元素|信息项|表元素12、数据构造是指_____以及它们之间的_____.(1)数据元素(2)构造|(1)计算办法(2)关系|(1)逻辑存储(2)运算|(1)数据映像(2)算法13、计算机所解决的数据普通含有某种内在的关系,这是的指_____.数据和数据之间存在的某种关系|元素和元素之间存在某种关系|元素内部含有某种构造|数据项和数据项之间存在某种关系14、数据的逻辑构造能够分为_____两类.动态构造和表态构造|紧凑构造和非紧凑构造|线性构造和非线性构造|内部构造和外部构造15、数据的逻辑构造是指_____关系的整体.数据元素之间逻辑|数据项之间逻辑|数据类型之间|存储构造之间16、在存储数据时,普通不仅要存储各数据元素的值,并且还要存储_____.数据的解决办法|数据元素的类型|数据元素之间的关系|数据的存储办法17、在数据的存储构造中,一种存储结点存储一种_____.数据项|数据元素|数据构造|数据类型18、在计算机的存储器中表达时,物理地址和逻辑地址直接对应并且是持续的,称之为_____.逻辑构造|次序存储构造|链式存储构造|以上都对19、数据采用链式存储构造时,规定_____.每个结点用占一片持续的存储区域|全部结点占用一片持续的存储区域|结点的最后一种数据域是指针类型|每个结点有多少个后继,就设多少个指针域20、数据的运算_____.效率与采用何种存储构造有关|是根据存储构造来定义的|有算术运算和关系运算两大类|必须用程序设计语言来描述21、下列说法中,不对的的是_____.数据元素是数据的基本单位|数据项是数据中不可分割的最小可标记单位|数据可由若干个数据元素构成|数据项可由若干个数据元素构成22、_____不是算法的基本特性.可行性|长度有限|在规定的时间内完毕|拟定性23、计算机中算法指的是解决某一问题的有限运算序列,它必须含有输入、输出、_____.可行性、可移植性和可扩充性|可行性、有穷性和拟定性|拟定性、有穷性和稳定性|易读性、稳定性和拟定性24、下列不属于算法特性的是_____.可行性|有输入|拟定性|强健性25、下面有关算法的说法对的的是_____.算法最后必须由程序实现|算法的有穷性是对于任意的一组输入值必须在有穷环节后结束|算法的可行性是指指令不能有二义性|以上几个都是错误的26、算法的时间复杂度与______有关问题规模|计算机硬件性能|编译程序质量|程序设计语言27、算法分析的重要任务是分析_____.算法与否含有较好的可读性|算法中与否存在语法错误|算法的功效与否符合设计规定|算法的执行时间和问题规模之间的关系28、某算法的时间复杂度为O(n2),表明该算法的_____.问题规模是n2|执行时间等于n2|执行时间与n2成正比|问题规模与n2成正比29、算法分析的目的是_____.找出数据构造的合理性|研究算法中输入和输出关系|分析算法的效率以求改善|分析算法的易读性和文档性30、线性表是含有n个______的有限序列。表元素|字符|数据元素|数据项31、线性表是______。一种有限序列，可觉得空|一种有限序列，不可觉得空|一种无限序列，可觉得空|一种无限序列，不可觉得空32、线性表采用链表存储时，其地址______。必须是持续的|一定是不持续的|部分地址必须是持续的|持续与否均能够33、链表不含有的特点是______。可随机访问任一结点|插入删除不需要移动元素|不必事先预计存储空间|所需空间与其长度成正比34、线性表的静态存储构造与次序存储构造相比优点是_______。全部的操作算法实现简朴|便于随机存取|便于插入和删除|便于运用零碎的存储器空间35、设线性表有n个元素，下列操作中，_______在次序表上实现比在链表上实现效率更高。输出第i(1<=i<=n)个元素值|交换第1个元素与第2个元素的值|次序输出这n个元素的值|输出与给定值x相等的元素在线性表中的序号36、对于一种线性表，既规定能够较快地进行插入和删除，又规定存储构造能够反映数据元素之间的逻辑关系，则应采用_______存储构造。次序|链式|散列|索引37、设线性表中有2n个元素，下列操作中，______在单链表上实现要比在次序表上实现效率更高。删除指定的元素|在最后一种元素的背面插入一种新元素|次序输出前k个元素|交换第i个元素和第2n-i-1个元素的值(i=0，1，…，n-1)38、需要分派较大空间，插入和删除不需要移动元素的线性表，其存储构造是______。单链表|静态链表|线性链表|次序存储构造39、如果最惯用其所长的操作是取第i个结点及其前驱，则采用______构造方式最节省时间。单链表|双链表|单循环链表|次序表40、与单链表相比，双链表的优点之一是______。插入、删除操作更简朴|能够进行随机访问|能够省略表头指针或表尾指针|访问前后相邻结点更灵活41、数据构造在计算机内存中的表达是指______.数据的存储构造|数据构造|数据的逻辑构造|数据元素之间的关系42、下面程序段的时间复杂度为_________．O(m)|O(n)|O(m*n)|O(m+n)for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;数据构造复习题答案：绪论单选题1、存储|物理|逻辑|物理和存储C1C2C3A4A5B6A1C2C3A4A5B6A7C8A9B10D11AB12AB13B14C3、数据的存储构造|数据构造|数据的逻辑构造|数据元素之间的关系A4、逻辑|存储|逻辑和存储|物理A5、线性表的线性存储构造优于链表存储构造|二维数组是其数据元素为线性表的线性表|栈的操作方式是先进先出|队列的操作方式是先进后出B6、各结点的值如何|结束个数的多少|对数据有哪些运算|所用编程语言实现这种构造与否方便A7、数据的解决办法|数据元素的类型|数据元素之间的关系|数据的存储办法C8、(1)|(1)、(2)|(1)、(4)|(3)A9、数据元素含有同一特点|不仅数据元素所包含的数据项的个数要相似，并且对应的数据项的类型要一致|每个数据元素都同样|数据元素所包含的数据项的个数要相等B10、数据元素是数据的最小单位|数据项是数据的基本单位|数据构造是带构造的数据项的集合|某些表面上很不相似的数据能够有相似的逻辑构造D11、数据项|数据元素|信息项|表元素A|B12、(1)数据元素(2)构造|(1)计算办法(2)关系|(1)逻辑存储(2)运算|(1)数据映像(2)算法A|B13、数据和数据之间存在的某种关系|元素和元素之间存在某种关系|元素内部含有某种构造|数据项和数据项之间存在某种关系B14、动态构造和表态构造|紧凑构造和非紧凑构造|线性构造和非线性构造|内部构造和外部构造C15A16C17B18B19A20A21D22B23B24D25B26A27D15A16C17B18B19A20A21D22B23B24D25B26A27D28C29C30C31A32D33A34C35A36B37A38B39B40D41A42C16、数据的解决办法|数据元素的类型|数据元素之间的关系|数据的存储办法C17、数据项|数据元素|数据构造|数据类型B18、逻辑构造|次序存储构造|链式存储构造|以上都对B19、每个结点用占一片持续的存储区域|全部结点占用一片持续的存储区域|结点的最后一种数据域是指针类型|每个结点有多少个后继,就设多少个指针域A20、效率与采用何种存储构造有关|是根据存储构造来定义的|有算术运算和关系运算两大类|必须用程序设计语言来描述A21、数据元素是数据的基本单位|数据项是数据中不可分割的最小可标记单位|数据可由若干个数据元素构成|数据项可由若干个数据元素构成D22、可行性|长度有限|在规定的时间内完毕|拟定性B23、可行性、可移植性和可扩充性|可行性、有穷性和拟定性|拟定性、有穷性和稳定性|易读性、稳定性和拟定性B24、可行性|有输入|拟定性|强健性D25、算法最后必须由程序实现|算法的有穷性是对于任意的一组输入值必须在有穷环节后结束|算法的可行性是指指令不能有二义性|以上几个都是错误的B26、问题规模|计算机硬件性能|编译程序质量|程序设计语言A27、算法与否含有较好的可读性|算法中与否存在语法错误|算法的功效与否符合设计规定|算法的执行时间和问题规模之间的关系D28、问题规模是n2|执行时间等于n2|执行时间与n2成正比|问题规模与n2成正比C29、找出数据构造的合理性|研究算法中输入和输出关系|分析算法的效率以求改善|分析算法的易读性和文档性C30、表元素|字符|数据元素|数据项C31、一种有限序列，可觉得空|一种有限序列，不可觉得空|一种无限序列，可觉得空|一种无限序列，不可觉得空A32、必须是持续的|一定是不持续的|部分地址必须是持续的|持续与否均能够D33、可随机访问任一结点|插入删除不需要移动元素|不必事先预计存储空间|所需空间与其长度成正比A34、全部的操作算法实现简朴|便于随机存取|便于插入和删除|便于运用零碎的存储器空间C35、输出第i(1<=i<=n)个元素值|交换第1个元素与第2个元素的值|次序输出这n个元素的值|输出与给定值x相等的元素在线性表中的序号A36、次序|链式|散列|索引B37、删除指定的元素|在最后一种元素的背面插入一种新元素|次序输出前k个元素|交换第i个元素和第2n-i-1个元素的值(i=0，1，…，n-1)A38、单链表|静态链表|线性链表|次序存储构造B39、单链表|双链表|单循环链表|次序表D40、插入、删除操作更简朴|能够进行随机访问|能够省略表头指针或表尾指针|访问前后相邻结点更灵活D41、数据的存储构造|数据构造|数据的逻辑构造|数据元素之间的关系A42、O(m||O(m*n)|O(m+n)C数据构造复习题：绪论判断题1、数据元素是数据的最小单位。2、数据项是数据的基本单位。3、数据元素是数据的最小单位4、数据对象就是一组任意数据元素的集合5、任何数据构造都含有3个基本运算:插入、删除和查找.6、数据是由某些类型相似的数据元素构成的7、数据是逻辑构造与各数据元素在计算机中如何存储有关8、如果数据元素值发生变化,则数据的逻辑构造也随之变化.9、逻辑构造相似的数据,能够采用多个不同的存储办法.10、逻辑构造相似的数据,结点类型也一定相似11、逻辑构造不相似的数据,必须采用不同的存储方式来存储12、数据的逻辑构造是指数据的各数据项之间的逻辑关系.13、算法的优劣与算法描述语言有无关，但与全部计算机有关。14、算法能够用不同的语言描述，如果用C或Pascal等高级语言来描述，则算法事实上就是程序了。15、程序一定是算法。16、算法最后必须由计算机程序实现。19、强健的算法不会因非法入输数据而出现莫名其妙的执行成果。数据构造复习题答案：绪论判断题1、False2、False3、False4、False5、False6、True7、False8、False9、True10、False11、False12、False13、False14、False15、False16、False19、True数据构造复习题：绪论算法分析题1、求两个n阶矩形的乘法C=A*B,其算法以下:#defineMAX100voidmaxtrixmult(int,floata[MAX][MAX],b[MAX][MAX],floatc[MAX][MAX]){inti,j,k;floatx;for(i=1;i<=n;i++)//①{for(j=1;j<=n;j++)//②{x=0;//③for(k=1;k<=n;k++)//④x+=a[i][k]*b[k][j];//⑤c[i][j]=x;//⑥}}}计算①～⑥各语句的频度,并分析该算法的时间复杂度。2、设n是偶数,试计算运行下列程序段后m的值并给出该程序段的时间复杂度。m=0;for(i=1;i<=n;i++)for(j=2*1;j<=n;j++)m++;3、阅读下列算法:voidsuan_fa(intn){inti,j,k,s,x;for(s=0,i=0;i<n;i++)for(j=i;j<n;j++)s++;i=1;j=n;x=0;while(i<j){i++;j--;x+=2;}pirntf("s=%d,x=%d",s,x);}(1)分析算法中语句"s++;"的执行次数;(2)分析算法中语句"x+=2;"的执行次数;(3)分析该算法的时间复杂度;(4)假定n=5,试指出执行该算法的输出成果。6、设n是偶数,试计算运行下列程序段后m的值并给出该程序段的时间复杂度。intm=0,i,j;for(i=1;i<=n;i++)for(j=2*i;j<=n;j++)m++;数据构造复习题答案：绪论算法分析题1、答：语句频度for(i=1;i<=n;i++)//①……n+1{for(j=1;j<=n;j++)//②……n(n+1){x=0;//③……n2for(k=1;k<=n;k++)//④……n2(n+1)x+=a[i][k]*b[k][j];//⑤……n3c[i][j]=x;//⑥……n2因此：f(n)n+1+n(n+1)+n2+n2(n+1)+n3+n2=2n3+4n2+2n+1=O(n3)2、答：m+n(n-1)O(n2)3、分析算法中语句”s++;”的执行次数：n+（n-1）+(n-2)+…+1=n(n+1)/2分析算法中语句”x+=2;”的执行次数:n/2分析该算法的时间复杂度:O(n2)假定n=5，试指出执行该算法的输出成果:s=15,x=46、数据构造复习题：绪论填空题1、一种数据构造在计算机中______称为存储构造。2、数据逻辑构造涉及________，_________和________三种类型，树形构造和图形构造合称为________。3、在线性构造中，第一种结点________前驱结点，其它每个结点有且只有_______个前驱结点：最后一种结点______后续结点，其它每个结点有且只有______个后续结点。4、在树形构造中，树根结点没有______结点，其它每个结点有且只有______个前驱结点:叶子结点没有______结点,其它每个结点后的后续结点能够_______5、在图形构造中，每个结点的前驱结点数和后续结点数能够________。6、线性构造中元素之间存在_________关系，树形构造中元素之间存在_______关系，图形构造中元素之间存在________关系。7、算法的5个重要特性是_________、__________、__________、输入和输出。8、算法能够用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实现上就是程序了。这个断言是________。9、数据构造、数据元素和数据项在计算机中的映射(或表达)分别称为存储构造、结点和数据域。这个断言是_______。10、下面程序段的时间复杂度是_______。for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;11、下面程序段的时间复杂度是_______。i=s=0;while(s<n){i++;s+=i;}12、下面程序段的时间复杂度是_______。s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;13、下面程序段的时间复杂度是________。i=1;while(i<=n)i=i*3;14、有以下递归函数fact(n),分析其时间复杂度。intfact(intn){if(n<=1)return1;elsereturn(n*fact(n-1));}15、指出下列各算法的时间复杂度(1)prime(intn){inti=2;while(n%i!=0&&i<sqrt(n))i++;if(i*1.0>sqrt(n))printf"是一素数";elseprintf"不是一素数";}(2)sum1(intn){intp=1,sum=0,i;for(i=1;i<=n;i++){p*=i;sum+=p;}returm(sum);}(3)sum2(intn){intsum=0,i,j;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++)p*=j;sum+=p;}return(sum);}16、数据的逻辑构造是指_____.17、一种数据构造在计算机中的______称为存储构造.18、次序存储办法是把逻辑上_____存储在物理位置上______里;链式存储办法中结点间的逻辑关系是由_____的.19、数据构造是指研究数据的_____和_____以及它们之间的互有关系,并对这种构造定义对应的_____,设计出对应的_____,从而确保通过这些运算后所得到的新构造是原来的构造类型.20、一种算法含有5个特性:_____、_____、_____、输入和输出。21、算法的执行时间是_____的函数。22、数据的逻辑构造是从逻辑上描述数据,它与数据的______无关,是独立于计算机的.23、数据的逻辑构造被分为____________、____________、____________和____________４种。24、数据的存储构造被分为____________、____________、____________和____________４种。25、在线性构造、树形构造和图形构造中，前驱和后继结点之间分别存在着____________、____________、____________的联系。26、一种抽象数据类型涉及____________和____________两个部分。27、从一维数组a[n]中次序查找出一种最大值元素的时间复杂度为____________，输出一种二维数组b[m][n]中全部元素值的时间复杂度为____________28、在下面程序段中，s=s+p语句的执行次数为____________，p*=j语句的执行次数为____________，该程序段的时间复杂度为____________。inti=0,s=0;while(++i<=n){intp=1;for(intj=1;j<=i;j++)p*=j;s=s+p;}29、一种算法的时间复杂度为（3*n*n+2nlog2n+4n-7)/(5n)，其数量级表达为____________。30、从一种数组a[10]中次序查找元素时，假定查找每个元素的概率都相似，则进行一次查找运算时的平均查找长度（即同元素的平均比较次数）为____________。31、从一种数组a[7]中次序查找元素时，假定查找第1个元素a[0]的概率为1/3，查找第2个元素a[1]的概率为1/4，其找其它元素的概率均相似，则在查找成功时同元素的平均比较次数为____________。32、对于一种n*n的矩阵Ａ的任意矩阵元素a[i][j]，按行存储时和按列存储时的地址之差是____________。设两种存储时的开始存储地址均为ＬＯＣ(0,0)，每个元素所占存储单元数均为d。33、设有一种二维数组A[10][20]，按行寄存于一种持续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是____________34、设有一种二维数组A[10][20]，按列为主序寄存于一种持续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是____________。37、在线性表的单链接存储构造中，每个结点包含有两个域，一种叫____________，另一种叫____________域。数据构造复习题答案：绪论填空题1、映射2、线性构造|树形构造|图形构造|非线性构造3、没有|1|没有|14、前驱|1|后续|任意多个5、任意多个6、一对一|一对多|多对多7、有穷性|拟定性|可行性8、错误9、对的10、O(n*m)11、O(√n)12、O(n2)13、O(log3n)14、O(n)15、O(√n)|O(n)|O(n2)16、数据元素之间的逻辑关系17、映像?表达?映像或表达18、相邻的结点|相邻的存储单元|附加的指针字段表达19、存储构造?物理构造|逻辑构造|运算|算法20、可行性|有穷性|拟定性21、问题规模22、存储构造、物理构造23、集合构造、线性构造、树形构造、图形构造（次序无先后）24、次序构造、链接构造、索引构造、散列构造（次序无先后）25、1:1|1:N|M:N26、数据|操作27、O(n)|O(m*n)28、n|n(n+1)/229、O(n)30、5.531、35/1232、(i-j)*(n-1)*d33、32234、22637、值|指针数据构造复习题：绪论问答题1、当你为解决某一问题而选择数据构造时,应从哪些方面考虑?2、简述逻辑构造与存储构造的关系.3、数据运算是数据构造的一种重要方面,试举例阐明两个数据构造的逻辑构造和存储方式完全相似,只是对于运算的定义不同,因而两个构造含有明显不同的特性,则这两个数据构造是不同的.数据构造复习题答案：绪论问答题1、解答：普通从两方面考虑：第一是算法所需的存储空间量；第二是算法所需的时间。对算法所需的时间又涉及下列三点：（1）程序运行时所需输入的数据总量。（2）计算机执行每条指令所需的时间。（3）程序中指令重复执行的次数。2、答：数据的逻辑构造反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储构造是数据构造在计算机中的表达，涉及数据元素的表达及其关系的表达。3、答：栈和队列的逻辑构造相似，其存储表达也可相似（次序存储和链式存储），但由于其运算集合不同而成为不同的数据构造。2线性表沈阳理工大学应用技术学院信息与控制学院计算机科学与技术教研室2011-5-8

数据构造复习题：线性表单选题1、在一种长度为n的次序表中，向第i个元素(1≤i≤n+1)之前插入一种新元素时，需向后移动_____个元素。2、从一种含有n个节点的单链表中查找其值等于x结点时，在查找成功的状况下，需平均比较_____个结点。3、在一种单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点，则执行_____。4、线性表是_____。5、对次序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，删除一种元素时大概要移动表中的_____个元素。6、线性表采用链式存储时，其地址_____。7、设单链表中指针p指着结点m，指针f指着将要插入的新结点x，当x插在链表中最后一种结点m之后时，只要先修改_____后修改p->link=f即可。8、在双向链表存储构造中，删除p所指的结点时需修改指针_____。9、在双向链表存储构造中，删除p所指的结点的前趋结点（若存在）时需修改指针_____。10、根据线性表的链式存储构造，每个结点所含指针的个数，链表分为单链表和_____。11、在线性表的链式存储构造中，逻辑上相邻的元素在物理位置上_____。12、链表不含有的特点是_______。13、不带头结点的单链表head为空的鉴定条件是______。14、带头结点的单链表的head为空的鉴定条件是______。15、带头结点的双循环表L为空表的条件是______。16、非空的循环单链表head的尾结点(由p所指向)满足_______。17、在循环双链表的p所指结点之前插入s所指结点的操作是_______。18、若某表最惯用的操作是在最后一种结点之后插入一种结点或删除最后一种结点，则采用______存储方式最节省运算时间。19、某线性表最惯用的操作是在最后一种结点之后插入一种结点或删除第一种结点，故采用_____存储方式最节省运算时间。20、需要分派较大空间，插入和删除不需要移动元素的线性表，其存储构造是_______。21、如果最惯用的操作是取第i个结点及其前驱，则采用______存储方式最节省时间。22、在一种含有n个结点的有序单链表中插入一种新结点并仍然保持有序的时间复杂度是______。23、在一种长度为n(n>1)的单链表上，设有头和尾两个指针，执行________操作与链表的长度有关。24、设线性表有n个元素，下列算法中，_______在次序表上实现比在链表上实现效率更高。25、设线性表中有2n个元素，算法_______，在单链表上实现要比在次序表上实现效率更高。26、与单链表相比，双链表的优点之一是________。27、如果对线性表的运算只有4种，即删除第一种元素，删除最后一种元素，在第一种元素前面插入新元素，在最后一种元素的背面插入新元素，则最后使用________。28、如果对线性表的运算只有两种，即删除第一种元素，在最后一种元素的背面插入新元素，则最佳使用_______。29、设有两个长度为n的单链表，结点类型相似。若以h1为表头指针的链表是非循环的，以h2为表头指针的链表是循环的，则_______。30、在长度为n的______上，删除第一种结点，其算法的时间复度为O(n)。31、将两个各有n个元素的有序次序表归并成一种有序次序表，其最少的比较次数是_____。32、带头结点的单链表L为空的鉴定条件是______。33、在一种含有n个结点的有序单链表中插入一种新结点并仍然保持有序的时间复杂度是_______。34、在一种长度为n(n>1)的带头结点的单链表h上，，另设有尾指针r(指向尾结点)，执行_______操作与链表的长度有关。35、在一种双链表中，在*p结点之后插入结点*q的操作是______。36、在一种双链表中，在*p结点之前插入*q结点的操作是______。37、在一种双链体现式，删除*p结点的操作是_______。38、在一种双链表中，删除*p结点之后的一种结点的操作是________。39、非空的循环单链表L的尾结点(由p所指向)满足______。40、带头结点的双循环链表L为空表的条件是______。41、若某表最惯用的操作是在最后一种结点之后插入一种结点或删除最后一种结点，则采用_________存储方式最节省运算时间。42、如果对含有n(n>1)个元素的线性表的运算只有4种:删除第一种元素；删除最后一种元素；在第一种元素前面插入新元素；在最后一种元素的背面插入新元素，则最佳使用________。43、某线性表最惯用的操作是在最后一种结点之后插入一种结点或删除第一种结点，则采用_______存储方式最节省运算时间。44、设有两个长度为n的单链表，结点类型相似，若以h1为头结点的链表是非循环的，以h2为头结点指针的链表是循环的，则________。45、在长度驎n(n>1)的______上，删除第一种元素，其算法的时间复杂度为O(n)。46、元素A、B、C、D依次进次序栈后，栈顶元素是_______，栈底元素是______。47、通过下列栈运算后，X的值是______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);48、通过下列的栈运算后，StackEmpty(s)的值是______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)49、设一种栈的输入序列为A、B、C、D，则借助一种栈所得到的输出序列不可能是______。50、若线性表最惯用的运算是存取第i个元素及其前驱的值,则采用______存储方式节省时间.51、链表不含有的特点是______.52、在一种长度为n的次序存储的线性表中，向第i个元素(1<=i<=n+1)位置插入一种新元素时，需要从后向前依次后移_________个元素．53、在一种长度为n的次序存储的线性表中，删除第i个元素(1<=i<=n)时，需要从前向后依次前移_________个元素．54、在一种长度为n的线性表中次序查找值为x的元素时，查找成功时的平均查找长度（即x同元素的平均比较次数，查找每个元素的概率都相等）为（）．57、在一种单链表HL中，若要删除由指针q所指向结点的后继结点，则执行_________。数据构造复习题答案：线性表单选题1、n-1|n-i+1|n-i-1|IB2、n|n/2|(n-1)/2|(n+1)/2D3、s->next=p->next;p->next=s;|p->next=s->next;s->next=p;|q->next=s;s->next=p;|p->next=s;s->next=q;C4、一种有限序列，可觉得空。|一种有限序列，不能为空。|一种无限序列，可觉得空。|一种无限序列，不能为空。A5、n+1|n-1|(n-1)/2|nC6、必须是持续的。|部分地址必须是持续的。|一定是不持续的。|持续与否均能够。D7、f->link=p;|f->link=p->link;|p->link=f->link;|f=nil;B8、((p->rlink)->rlink)->link=p;p->rlink=(p->rlink)->rlink;|(p->llink)->rlink=p->rlink;(p->rlink)->llink=p->llink;|p->llink=(p->llink)->llink;((p->llink)->llink)->rlink=p;|((p->llink)->llink)->rlink=p;p->llink=(p->llink)->llink;B9、((p->llink)->llink)->rlink=p;p->llink=(p->llink)->llink;|((p->rlink)->rlink)->llink=p;p->rlink=(p->rlink)->rlink;|(p->llink)->rlink=p->rlink;(p->rlink)->llink=p->llink;|p->llink=(p->llink)->llink;((p->llink)->llink)->rlink=p;A10、循环链表|多重链表|普通链表|无头结点链表B11、一定相邻|不一定相邻|有时相邻|B12、可随机访问任一结点|插入删除不需要移动元素|不必事先预计存储空间|所需空间与其长度成正比A13、head==NULL|head->next==NULL|head->next==head|head!=NULLA14、head==NULL|head->next==NULL|head->next==head|head!=NULLB15、L=NULL|L->next==NULL|L->prior==NULL|L->next==LD16、p->next==NULL|p==NULL|p->next==head|p==headC17、p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior;|p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior;|s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s;|s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;D18、单链表|给出表头指针的单循环链表|双链表|带头结点的双循环链表D19、单链表|仅有头结点的单循环链表|双链表|仅有尾指针的单循环链表D20、单链表|静态链表|线性链表|次序存储构造B21、单链表|双链表|单循环链表|次序表D22、O(1)|O(n)|O(n2)|O(nlog2n)B23、删除单链表中的第一种元素|删除单链表中的最后一种元素|在单链表第一种元素前插入一种新元素|在单链表最后一种元素后插入一种新元素B24、输出第i(0<=i<=n-1)个元素值|交换第0个元素与第1个元素的值|次序输出这n个元素的值|输出与给定值x相等的元素在线性表中的序号A25、删除全部值为x的元素|在最后一种元素的背面插入一种新元素|次序输出前k个元素|交换第i个元素和第2n-i-1个元素的值(i=0,i,…,n-1)A26、插入、删除操作更简朴|能够进行随机访问|能够省略表头指针或表尾指针|次序访问相邻结点更灵活D27、只有表尾指针没有头指针的循环单链表|只有表尾指针没有表头指针的非循环双链表|只有表头指针没有表尾指针的循环双链表|现有表头指针也有表尾指针的循环单链表C28、只有表头指针没有表尾指针的循环单链表|只有表尾指针没有表头指针的循环单链表|非循环双链表|循环双链表B29、对于两个链表来说，删除第一种结点的操作，其时间复杂度都是O(1)|对于两个链表来说，删除最后一种结点的操作，其时间复杂度都是O(n)|循环链表要比非循环链表占用更多的内存空间|h1和h2是不同类型的变量B30、只有表头指针的不带表头结点的循环单链表|只有表尾指针的不带表头结点的循环单链表|只有表尾指针的带表头结点的循环单链表|只有表头指针的带表头结点的循环单链表A31、n|2n-1|2n|n-1A32、L==NULL|L->next==NULL|L->next==L|L!=NULLB33、O(1)|O(n)|O(n^2)|O(nlog2n)B34、删除单链表中的第一种元素|删除单链表中的最后一种元素|在单链表第一种元素前插入一种新元素|在单链表最后一种元素后插入一种新元素B35、q->prior=p;p->next=q;p->next->prior=q;q->next=p->next;|q->next=p->next;p->next->prior=q;p->next=q;q->prior=p;|p->next=q;q->prior=p;q->next=p->next;p->next->prior=q;|p->next->prior=q;q->next=p->next;q->prior=p;p->next=q;B36、p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;|q->prior=p->prior;p->prior->next=q;q->next=p;p->prior=q->next;|q->next=p;p->next=q;q->prior->next=q;q->next=p;|p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q;D37、p->prior->nexxt=p->next;p->next->prior=p->prior;|p->prior=p->prior->prior;p->prior->prior=p;|p->next->prior=p;p->next=p->next->next;|p->next=p->prior->prior;p->prior=p->rprior->priorA38、p->next=p->next->next;p->next->next->prior=p;|p->next->prior=p;p->next=p->next->next;|p->next=p->next->next;p->next->prior=p;|p->next->next=p->next;p->next->pror=p;C39、p->next==NULL|p==NULL|p->next==L|p==LC40、L->==NULL|L->next->prior==NULL|L->prior==NULL|L->next==LD41、单链表|给出表头指针的循环单链表|双链表|带头结点的循环双链表D42、只有尾结点指针没有头结点指针的循环单链表|只有尾结点指针没有头结点指针的非循环单链表|只有头结点指针没有尾结点指针的循环双链表|现有头结点指针也有尾结点指针的循环单链表C43、单链表|仅有头结点的单循环链表|双链表|仅有尾结点指针的单循环链表D44、对于两个链表来说，删除第一种结点的操作，其时间复杂度都是O(1)|对于两个链表来说，删除最后一种结点的操作，其时间复杂度都是O(n)|循环链表要比非循环链表占用更多的内在空间|h1和h2是不同类型的变量B45、只有首结点指针h的不带头结点的循环单链表|只有尾结点指针r的不带头结点的循环单链表|只有尾结点指针r的带头结点h的循环单链表|只有头结点h的循环单链表A46、A|B|C|DD|A47、a|b|1|0A48、a|b|1|0C49、A、B、C、D|D、C、B、A|A、C、D、B|D、A、B、CD50、单链表|双链表|单循环链表|次序表D51、可随机访问任一结点|插入删除不需要移动元素|不必事先预计存储空间|所需空间与其长度成正比A52、n-i|n-i+1|n-i-1|IB53、n-1|n-i+1|n-i-1|IA54、n|n/2|(n+1)/2|(n-1)/2C57、p=q->next;p->next=q->next;|p=q->next;q->next=p;|p=q->next;q-next=p->next;|q->next=q->next->next;q->next=q;C数据构造复习题：线性表判断题1、次序存储的线性表能够随机存取。2、线性表中的元素能够是多个各样的，但同一线性表中的数据元素含有相似的特性，因此，是属于同一数据对象。3、在单链表中，任何两个元素的存储位置之间都有固定的联系，由于能够从头结点查找任何一种元素。4、在单链表中，要获得某个元素，只要懂得该元素的指针即可，因此，单链表是随机存取的存储构造。5、链表的每个结点中，都正好包含一种指针。6、线性表中每个元素都有一种直接前驱和直接后继。7、线性表中全部元素的排列次序必须由小到大或由大到小。8、静态链表的存储空间在运算中能够变化大小。9、静态链表现有次序存储构造的优点，又有动态链表的优点。因此，它存取表中的第i个元素的时间与i无关。10、静态链表中能容纳元素个数的最大数在定义时就拟定了，后来不能增加。11、静态链表与动态链表的插入、删除操作类似，不需做元素的移动。12、线性表的次序存储构造优于链式存储构造。15、在双链表中，能够从任一结点开始沿同一方向查找任何其它结点。数据构造复习题答案：线性表判断题1、True2、True3、False4、False5、False6、False7、False8、False9、False10、True11、True12、False15、False数据构造复习题：线性表算法分析题1、己知一种次序表L,其中的元素按值非递减有序排列,设计一种算法插入一种元素x后保持该次序表仍按递减有序排列。规定算法的空间复杂度为O(1)。2、设计一种算法从次序表L中删除全部值为X的元素。规定算法的空间复杂度为O(1)。3、从次序表L中删除重复的元素,并使剩余元素间的对应次序保持不变.规定本算法的空间复杂记度为O(1)。4、有一种单链表(不同结点的数据域值可能相似),其头指针为head,设计一种算法计算数据域为x的结点个数。5、己知线性表元素递增有序,并以带头结点的单链表作存储构造,设计一种高效算法,删除表中全部值不不大于mink且不大于maxk的元素(若表中存在这样的元素)。并分析所写算法的时间复杂度。6、设计一种在带头结点的单链表中删除一种最小值结点的高效算法。7、有一种不带头结点的单链表L(最少有1人结点),其头指针为head,设计一种算法将L逆置,即最后一种结点变成第一种结点,原来倒数第二个结点变成第二个结点,如此等等。8、用单链表表达集合,设计一种算法求两个集合的差。规定不破坏原有的结点。9、用单链表表达集合,设计一种算法求两个集合的并。规定不破坏原有的结点。10、设计一种算法,将一种头结点指针为a的单链表A分解成两个单链表A和B,其头结点指针分别为a和b,使得A链表中含有原链表A中序号为奇数的元素,而B链表中含有原链表A中序号为倒数的元素,且保持原来的相对次序。11、有一种单链表,其结点的元素值以递增有序排列,设计一种算法删除该单链表中多出的元素值相似的结点。12、己知两个寄存整数的有序单链表(己按整数从小至大的次序排序),指针L1和L2分别指向这两个单链表的头结点。设计一种算法,将L1和L2合并成一种单链表,且新的链表仍按整数由小到大的次序排列,新的单链表的结点由L1和L2的结点构成。规定合并后的单链表运用原来单链表的存储空间。13、设计一种算法,将线性表lb连接到la之后,规定其时间复杂度为O(1),占用的辅助空间尽量小。描述所用的构造。14、设指针p指向双链表中的结点X,指针f指向将要插入的新结点Y,Y要插入在结点X之后,写出指针需要修改的有关环节。15、有一种循环双链表,每个结点由两个指针(prior和next)以及核心字(data)构成,p指向其中某一结点,设计一种算法从该循环双链表中删除p所指的结点。16、设有一种循环双链表,其中有一结点的指针为p,设计一种算法将p与其后续结点进行交换。19、设A和B是两个单链表(带头结点)，其表中元素递增有序。设计一种算法将A和B归并成一种按元素值递增有序的单链表C，规定辅助空晨为O(1)，并分析算法的时间复杂度。数据构造复习题答案：线性表算法分析题1、答：voidinsert(sqlist&L,ElemTypex){inti=0,j;while(i<L.Length&&L.data[i]<x)i++:for(j=L.Length-1;j>=i;j--)L.data[j+1]=L.data[j];L.data[i]=x;L.Length++;}2、voiddelnode(SqList&A,ElemTypeitem){intk=0,i=0;while(i<A.length){if(A.data[i]==item)k++;elseA.data[i-k]=A.data[i];i++;}A.length=A.length-k}3、4、intListlant(Salist&L,ElemTypee){/*带有头结点*/p=head;intn=0;while(p!=NULL){if(p->next->data==x)n++;p=p-.next;}returnn;}5、voidDelnodes(LinkList*&L,ElemTypemink,ElemTypemaxk){LinkList*p=head->next;While(p!=null&&p->data<mink)//*r为*p的前驱结点{r=p;p=p->next;}q=p;//求值域刚好>minwhile(q!=null&&q->data>maxk)//求值域刚好<maxq=q->next;r->next=q->next;while(r!=q){r=p->next;free(p);p=r;}free(q);}6、voidDels(LinkList*&head){p=head,q=head->next;while(q->next!=null){if(p->next->data>q->next->data)p=q;q=q->next;}p->next=p->next->next;}7、voidReverse(LinkList*&head){p=head;q=p->next;//q指向p的后继结点，仅为目前结点if(q=null)return(p);//仅有一种结点p->next=null;//原链表的首结点位新链表的尾结点if(q->next==null)//仅有两个结点{q->next=p;return(q);}r=q->next;while(r->next!=null){q->next=p;//实现逆置p=q;q=r;r=r->next;}q->next=p;return(r);}8、TypedefElemtypeint;TypedefstructLnode{Elemtypedata;StructLNode*next;}Lnode,*LinkList;#include<stdio.h>LinkListcreatlist(){//建立单链表LinkListhead,r,s;ElemTypex;head=(LinkList)malloc(sizeof(LNode));//建立单链表头结点r=head;printf(“输入系列整数，0标志结束\n”);scanf(“&d”,&x);while(x){//x=0则退出while循环s=(LinkList)mslloc(sizeof(LNode));s->data=x;r->next=s;r=s;scanf(“%d”,&x);)//whiler->next=NULL;s=head;//删除头结点head=head->next;free(s);return(head);}statusListFind(LinkListL,Elemtypee){//查找元素eLinkListp;p=L;while(p&&p->data!=e)p=p->next;If(p)returnFALSE;elsereturnTRUE;}voidLis9、TypedefElemtypeint;TypedefstructLnode{Elemtypedata;StructLNode*next;}Lnode,*LinkList;voidMergeList(LinkListHa,LinkListHb,LinkList&Hc){LinkListp,q,r,s;Hc=(LinkList)malloc(sizeof(Lnode));r=Hc;p=Ha;q=Hb;while(p&&q){s=(LinkList)malloc(sizeof(Lnode));r->next=s;r=s;if(p->data<q->data){s->data=p->data;p=p->next;}elseif(p->data<q->data){s->data=q->data;q=q->next;}else{s->data=p->data;p=p->next;q=q->next;}}while(q)//把Q及之后的结点复制到Hc{s=(LinkList)malloc(sizeof(Lnode));s->data=q->data;r->next=s;r=s;q=q->next;}while(p)//把P后的结点复制到Hc{s=(LinkList)malloc(sizeof(Lnode));s->data=p->data;r->next=s;r=s;p=p->next;}r->next=NULL;s=Hc;Hc=Hc->next;free(s);//删除头结点}10、Voidpartition(LinkList&a,LinkList&b){LinkListr,p,q;p=a->next;b=(LinkList)malloc(sizeof(Lnode));q=b;While(p->next){r=p->next;p->next=r->next;r->next=NULL;q-next=r;q=q->next;p=p->next;}}11、//p扫描单链表。*p的值域=其后结点的值域，删除后者voidDels(LinkList*&head){LinkList*p=head->next;while(p->next!=null){if(p->data==p->next->data)/改重复值的结点{q=p->next;/q指向返回重复结点p->next=q->next;free(q);}elsep=p->next;}}12、voidMergelistL(LinkList&L1,LinkList&L2){LinkList*p,*q,*r,*u,*c;p=L1->next;q=L2->next;c=L1/c为合并后新链表的表头指针r=L1while(p!=Null)&&(q!=Null)Swich{casep->data>q->data;/*是L2表中小者加入C表尾部{u=q->next;/*u为暂存指针，避免链断r->next=q;r=q;q->next=p;q=u;}casep->data<=q->data/*将A表中小者加入到C表尾部{r=p;p=p->next;}}if(q!=Null)/如果A表已空时将B表为结束部分链接结束部分->cb表尾部r->next=q;return(c);}13、typedefstructslnode{Elemtypedata;structslnode*next;}slnodetype;slnodetype*p,*q,*s;voidmerge(slnodetype*la,slnodetype*lb){slnodetype*p;p=lb->next;Lb->next=la->next;la->next=p->next;free(p);}14、statasInsertDubList(DuLinkList&L,inte){malloc(f);f->data=Y;if(p->next==null){p->next=f;f->prior=p;}else{f->prior=p;p->next->prior=f;f->next=p->next;p->next=f;}}15、Statasdelete(cirLinkList&L){If(L=null)Error(‘nodata’);If(p→next=L){L→next=L;L→prior=L.Free(p);}Else{p→prior→next=→next;p→next→prior=→prior;free(p);}}16、stataschange(CirLinkList&L){If(L=null)error(‘nodata’);elseIf(p->next==null)error(‘can’tchange’)else{q=p->next;p->prior->next=q;q->prior=p->prior;p->n