数据结构（Java语言版）-习题及答案 第2章线性表习题答案

第2章线性表习题参考答案一、单选题ABCDABCD关系字符数据元素数据项ABCD以下关于线性表和ABCD线性表中元素不能重复出现有序表属于线性表的存储结构线性表和有序表的元素具有相同的逻辑关系有序表可以采用顺序表存储，而线性表不能采用顺序表存储ABCABCD顺序表的优点是存储密度大且插入、删除运算效率高顺序表的优点是具有随机存取特性顺序表中所有元素可以连续也可以不连续存放在含n个元素的顺序表中查找序号为的元素的时间复杂度为ABCD在含n个元素的顺序表中，算法的时间复杂度是OABCD访问第个元素（≤≤n）和求第个元素的前驱元素（≤≤n）在第个元素后插入一个新元素（≤≤n）删除第个元素（≤≤n）ABCABCD所有的操作算法实现简单便于随机存取便于插入和删除元素节省存储空间ABCABCD必须是连续的一定是不连续的部分地址必须是连续的连续与否均可以ABCABCD大于1等于1小于1不能确定ABCABCD一个结点的数据成员用于存放线性表的一个数据元素一个结点的指针成员用于指向下一个数据元素的结点单链表必须带有头结点单链表中所有结点可以连续也可以不连续存放ABCABCD可随机访问任一结点插入删除不需要移动结点不必事先估计存储空间所需空间与其长度成正比ABCABCD结点中除元素值外还包括指针成员，因此存储密度小于顺序存储结构逻辑上相邻的元素物理上不必相邻可以根据头结点地址直接计算出第i个结点的地址插入、删除运算操作方便，不必移动结点ABCD若某线性表最常用的操作是查找序号ABCD顺序表带头结点的循环双链表单链表带尾结点的循环单链表ABCD将两个各有nABCDn2n-12nn-1以下关于单链表的叙述中正确的是 。Ⅰ结点中除元素值外还包括指针成员，存储密度小于顺序表Ⅱ找第个结点的时间为O)Ⅲ在插入和删除操作时不必移动结点AABCD仅Ⅰ、Ⅱ仅Ⅱ、Ⅲ仅Ⅰ、Ⅲ.Ⅰ、Ⅱ、ⅢABCABCD删除单链表中的首结点删除单链表中的尾结点在单链表首结点前插入一个新结点在单链表尾结点素后插入一个新结点ABCABCD插入一个结点使之有序的算法的时间复杂度为O)删除最大值结点使之有序的算法的时间复杂度为O)找最小值结点的算法的时间复杂度为O)以上都不对已知两个长度分别为m和n的递增单链表，若将它们合并为一个长度为m+n的递减单链表，则最好情况下的时间复杂度是 。ABCABCDO)O×n)O+n)在一个双链表中，删除p结点（非尾结点）的操作是 。 A.pprrnex=pnex;pnexprr=pprr;B.pprr=pprrprr;pprrprr=p;CC.pnexprr=p;pnex=pnexnex;D.pnex=pprrprr;pprr=pprrprr;<gye="x-dh:%;"rc="hp://cdnqngnene/bccebcdbcpng"/>ABCABCDO)On)On)Ongn)ABCD在长度为n（n≥1）的双链表中插入一个结点p（非尾结点ABCD1234在长度为n（n≥1）的双链表中删除一个结点p（非尾结点）要修改 个指针成员。AABCD1234ABCABCD单链表的存储密度较双链表高单链表的存储密度较双链表低双链表较单链表存放更多的元素单链表不能表示线性表的逻辑关系，而双链表可以ABCABCD插入、删除操作更简单可以进行随机访问可以省略表头指针或表尾指针访问前后相邻结点更方便ABCABCD单链表仅有头结点的循环单链表双链表仅有尾指针的循环单链表ABCABCD不再需要头结点已知某个结点能够容易找到它的前驱结点在进行插入、删除操作时，能更好地保证链表不断开从表中任意结点出发都能遍历整个链表ABCABCDpnex==nulp==nulpnex==hedp==headABCABCDO)On)On)Ongn)ABCABCD对于这两个链表来说，删除首结点的时间复杂度都是O)对于这两个链表来说，删除尾结点的时间复杂度都是On)循环单链表B比非循环单链表A占用更多的内存空间以上都不对ABCABCDpprr=q;qnex=p;pprrnex=q;qprr=pprr;pprr=q;pprrnex=q;qnex=p;qprr=pprr;qnex=p;qprr=pprr;pprr=q;pprrnex=q;qnex=p;qprr=pprr;pprrnex=q;pprr=q;<gye="x-dh:%;"rc="hp://cdnqngnene/eebedbdbcdddpng"/>有一个非空循环双链表，在结点p之后插入结点q的操作是qnex=pnex;pnex=q;qprr=p; 。 .pnex=q;.qprrnex=q;CC.qnexprr=q;D.qnexnex=q;<gye="xdh:%;"rc="hp://cdnqngnene/bdbdcdpng"/>ABCD在长度为n的 上，删除尾结点的时间复杂度为OABCD单链表双链表循环单链表循环双链表线性表是具有n个（）的有限序列。AABCD表元素字符数据元素数据项线性表是（）。AABCD一个有限序列，不可以为空一个无限序列，可以为空一个无限序列，不可以为空线性表有一个特点（）。AABCD若没有开始元素，则一定没有终端元素每个元素必须有一个前趋元素任何一个元素都还可能既是开始元素又是终端元素关于线性表的正确说法是（）。ABABCD线性表中至少有一个元素表中元素的排序顺序必须是由小到大或由大到小除第一个元素和最后一个元素外，其余每个元素有且仅有一个前趋和一个后继元素线性表的顺序存储结构是一种（）。AABCD顺序存取的存储结构索引存取的存储结构散列存取的存储结构以下关于顺序表的叙述中，正确的是（）。AABCD在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻顺序表和一维数组一样，都可以进行随机存取在顺序表中每一个元素的类型不必相同一个顺序表所占用存储空间的大小与（）无关。AABCD顺序表中元素的数据类型顺序表中元素各数据项的数据类型顺序表中各元素的存放次序

设一个顺序表（最多可存放个元素）目前有个元素，第（≤≤）个元素存放在d中，若把一个新元素存入d，则（）。AABCD会产生运行错误d～d不构成一个顺序表顺序表的长度大于顺序表元素个数，会降低存储空间的利用率以上都不对设一个顺序表（最多可存放个元素）目前有个元素，第（≤≤）个元素存放在d中，现删除d的元素而不做元素移动，则（）AABCDd～d不构成一个顺序表顺序表的长度变为19以上都不对顺序表具有随机存取特性，指的是（）。AABCD查找值为x的元素与顺序表中元素个数n有关查找序号为i的元素与顺序表中元素个数n无关查找序号为i的元素与顺序表中元素个数n有关

二、编程题H—数列有序问题时间限制：，空间限制：。个整数，已经按照从小到大顺序排列好，现在另外给一个整数m，请将该数插入到序列中，并使新的序列仍然有序。输入格式：输入数据包含多个测试实例，每组数据由两行组成，第一行是n和m，第二行是已经有序的n个数的数列。n和m同时为0标示输入数据的结束，本行不做处理。输出格式：对于每个测试实例，输出插入新的元素后的数列。答：prtvu*;pubccsn{cnt]n=newn;pubccntJephntk){ntcnp;nk=)reurnnk;rnt=k+;;++){rcn=*kp=;cn>k;cn){p=p+)%cn;p<k)cn=;}cn==k){reurn;}}}pubccvdnSrngrg){Scnnercn=newScnnerSyen;hecnhNex){ntk=cnnexIn;fk==)brek;SyeuprnnJephk;}}}.HDU1443—：2000ms，空间限制：65536Kn个人，编号为1，2，…，n，站在一个圆圈中，每隔m个人就杀一个人，最后仅剩下一个人。约瑟夫很聪明，可以选择最后一个人的位置，从而挽救他的生命。例如，当n=6且m=5时，按顺序出列人员是5，4，6，2，3，1，那么1会活下来。假设在圈子里前面恰好有k个好人，后面恰好有k个坏人，你必须确定所有坏人都在第一个好人前面被杀的最小m。输入格式：输入文件包含若干行，每行一个k，最后一行为0，你可以假设0<k<14。输出格式：输出文件中每行给出输入文件中的k对应的最小m。答：prtvu*;pubccsn{cnt]n=newn;pubccntJephntk){ntcnp;nk=)reurnnk;rnt=k+;;++){rcn=*kp=;cn>k;cn){p=p+)%cn;p<k)cn=;}cn==k){reurn;}}}pubccvdnSrngrg){Scnnercn=newScnnerSyen;hecnhNex){ntk=cnnexIn;fk==)brek;SyeuprnnJephk;}}}.OJ—公牛数学问题时间限制：，空间限制：。问题描述：公牛在数学上比奶牛好多了，它们可以将巨大的整数相乘，得到完全精确的答案。农夫约翰想知道它们的答案是否正确。请你帮助他检查公牛队的答案。读入两个正整数（每个不超过40位）并计算其结果，以常规方式输出（没有额外的前导零）。约翰要求你自己这样做，不要使用特殊的库函数进行乘法。输入格式：输入两行每行包含一个十进制数。输出格式：输出一行表示乘积。答：prtvng*;prtvu*;pubccsn{pubccSrnguSrngSrng)//两个数字字符串相乘{nt]=newn;nt]b=newn;nt]c=newn;nt;nt=engh;ntn=engh;r=;i<;++)=chr;r=;i<n;++)b=chrn;r=;i<;++)r=;j<n;++)c+]+=*b;r=;i<;++)>=10){c+]+=c/;10;}Srngn="";r=cengh;>=;)c=)brek;r;>=;)+=c[i];returnans;pubccvdnSrng]rg){Scnnercn=newScnnerSyen;Srng;=cnnexne;=cnnexne;Srng=u;Syeuprnn;}}

三、填空题线性表是有限个性质相同的数据元素的。 答：序列在线性表中，除了开始元素外，每个元素。 答：只有唯一的前趋元素在非空线性表中，终端元素是。 答：唯一的有10个学生排成一列，这些学生的信息构成的逻辑结构是一种。 答：线性表顺序表是线性表的一种顺序存储结构，采用存放线性表中的元素及其关系。 答：一维数组线性表的存储结构是一种随机存储结构。 答：顺序顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置相邻。 答：必定;不一定.在线性表的顺序存储结构中，元素之间的逻辑关系是通过元素的决定的；在线性表的链式存储结构中，元素之间的逻辑关系是通过结点的决定的。答：物理存储位置;指针域

四、判断题线性表中所有元素的数据类型必须相同。 答：正确线性表中的结点按前趋、后继关系可以排成一个线性序列。 答：正确空的线性表就是所有元素尚未赋值的线性表。 答：错误在一个含有n（n≥）个元素的线性表中，所有元素值不能相同。 答：错误线性表中每个元素都有一个前趋元素和一个后继元素。 答：错误线性表的长度是线性表占用的存储空间的大小。 答：错误线性表的存储结构大小与线性表中元素类型有关。 答：正确线性表的逻辑顺序总与其物理顺序一致。 答：错误线性表的顺序存储结构优于链式存储结构。 答：错误顺序表具有随机存取特性，而链表不具有随机存取特性。 答：正确五、简答题线性表有何特点，线性表中的元素可以重复出现吗？ 答：线性表是有限个相同性质的元素的序列，数据元素呈现线性关系，每个元素至多只有一个前趋元素和一个后继元素。由于线性表中元素与其位置有关，所以线性表中的元素可以重复出现。什么叫做随机存取特性？ 答：随机存取特性是针对存储结构的，而不是针对逻辑结构的。一种存储结构具有随机存取特性，是指对于给定元素序号，在时间O内能够找到该元素的值，顺序表具有随机存取特性。顺序表具有随机存取特性，所以在含有n个元素的顺序表中查找值为x的元素所花时间为O。这句话正确吗？ 答：错误。一种存储结构具有随机存取特性，是指对于给定元素序号，在时间O内能够找到该元素的值，并不是给定元素值x，能在时间O能够找到该元素。在顺序表中查找值为x的元素所花时间为On。要想在O的时间内存取第个表元素，线性表采用顺序表还是单链表？ 答：采用顺序表，因为顺序表具有随机存取特性，而单链表不具有随机存取特性，在单链表中存取第个表元素的时间为On简述顺序表和链表存储方式的主要优缺点。 答：顺序表的优点是可以随机存取元素，存储密度高，结构简单；缺点是需要一片地址连续的存储空间，不便于插入和删除元素（需要移动大量的元素），表的容量不便扩充。链表的优点是便于结点的插入和删除（只需要修改指针域，不需要移动结点），表的容量扩充十分方便；缺点是不能进行随机访问，只能顺序访问，另外每个结点上增加指针域，导致存储密度较低。.线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？答：应选择链式存储结构。它可动态申请内存空间，容易实现表容量的扩充，不受表长度（即表中元素个数）的影响，另外插入和删除操作的时间复杂度为O。应选择顺序存储结构。顺序表具有随机存取特性，当以序号存取元素时的时间复杂度为O。在什么情况下使用顺序表比链表好？ 答：当线性表很少进行插入和删除操作，或者插入和删除操作总是在尾部进行时，使用顺序表比链表好。何时选用顺序表、何时选用链表作为线性表的存储结构为宜？ 答：在实际应用中，应根据具体问题的要