数据结构试卷1线性表

题目部分，(卷面共有100题,855.0分,各大题标有题量和总分)一、单项选择题(39小题,共91.0分)(3分)[1]将下图所示的S所指结点加到P所指结点之后，其语句应为：A、s-next=p+l；p-next=s；B、(*p).Next=s;(*s)．next=(*p).next;C、s-nex=p-next;p-next=s-next;D、s-nex=p-next;p-nex=s;(2分)[2]顺序存储结构的主要缺点是不利于插入或删除操作。()(2分)[3]在双向链表存储结构中，删除p所指的结点时须修改指针A、(p^.llink)^.rlink:=p^.rlink(p^.rlink)^.llink:=p^.llink;B、p^.llink:=(p^.llink)^.llink(p^.llink)^.rlink:=p;C、(p^.rlink)^.llink:=pp^.rlink:=(p^.rlink)^.rlinkD、p^.rlink:=(p^.llink)^.llinkp^.llink:=(p^.rlink)^.rlink;(3分)[4]对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是A、head==NULLB、head→next==NULLC、head→next==headD、head!=NULL(2分)[5]在单链表指针为p的结点之后插入指针为s的结点，正确的操作是A、p-next=s;s-next=p-next;B、s-next=p-next;p-next=s;C、p-next=s;p-next=s-next;D、p-next=s-next;p-next=s;(2分)[6]双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为A、p＾.llink:=q;q＾.rlink:=p;p＾.llink＾.rlink:=q;q^.llink:=p^.llink;B、q＾.llink:=p^.llink;p＾.llink^.rlink:=q;q＾.rlink:=p;p^.llink:=q^.rlink;C、q^.rlink:=p;p^.rlink:=q;p^.llink^.rlink:=q;q^.rlink:=p;D、p^.llink^.rlink:=q;q^.rlink:=p;q^.llink:=p^.llink;p^.llink:=q;(2分)[7]在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是注:双向链表的结点结构为(llink,data,rlink)。供选择的答案：A、p↑.llink：=q；q↑.rlink：=p；p↑.llink↑.rlink：=q；q↑.llink：=q；B、p↑.llink：=q；p↑.llink↑.rlink：=q；q↑.rlink：=p；q↑.llink:=p↑.llink；C、q↑.rlink：=p；q↑.llink：=p↑.llink；p↑.llink↑.rlink：=q;p↑.llink：=q;D、q↑.llink:=p↑.llink；q↑.rlink:=p；p↑.llink：=q；p↑.llink：=q；(2分)[8]循环链表H的尾结点P的特点是A、P^.NEXT:=HB、P^.NEXT:=H^.NEXTC、P:=HD、P:=H^.NEXT(2分)[9]非空的循环单链表head的尾结点p↑满足A、p↑.link=headB、p↑.link=NILC、p=NILD、p=head(2分)[10]若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1=i=n+1)。A、O(0)B、O(1)C、O(n)D、O(n2)(2分)[11]链表不具有的特点是A、插入、删除不需要移动元素B、可随机访问任一元素C、不必事先估计存储空间D、所需空间与线性长度成正比(3分)[12]线性表L=(a1，a2，…，an)，下列说法正确的是A、每个元素都有一个直接前驱和一个直接后继B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到人或由达到小D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接屙继(5分)[13]线性表的表元存储方式有(（1）)和链接两种。试指出下列各表中使用的是何种存储方式：表1是(（2）)存储方式；表2是(（3）)存储方式；表3是(（4）)存储方式；表4是(（5）)存储方式。表左的s指向起始表元。表元编号货号数量表元间联系16184022205233103154450120557811766910240表元编号货号数量表元间联系16184052205213103154450120257811766910243表元编号货号数量表元间联系1618405220521供选择的答案：A、连续B、单向链接C、双向链接D、不连接E、循环链接F、树状G、网状H、随机I、顺序J、顺序循环(3分)[14]以下说法错误的是A、求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B、顺序存储的线性表可以随机存取C、由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D、线性表的链式存储结构优于顺序存储结构(3分)[15]以下说法错误的是A、循环链表来说，从表中任一结点出发都能通过前后移操作扫描整个循环链表B、对单链表来说，只有从头结点开始才能扫描表中全部结点C、双链表的特点是找结点的前趋和后继都很容易D、对双链表中来说，结点*p的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针中(3分)[16]在双向链表存储结构中，删除p所指的结点时颁修改指针A、B、C、D、(3分)[17]将图所示的s所指结点加到p所指结点之后，其语句应为3103154450120057811766910243表元编号货号数量表元间联系1216184052220521031031546450120035781176169102435A、s-next=p+l;p-next=s;B、(*p)．next=s;(*s).next=(*p).next;C、s-next=p-next；p-next=s-next;D、s-next=p-next；p-next=s;(3分)[18]（1）静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关(2)静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是_______A、(1)、(2)B、(1)C、(1)、(2)、(3)D、(2)(3分)[19]若长度为n的线性表采用顺序存储结构，在其第一个位置插入个新元素算法的时间复杂度为_______。A、o(N)B、0(1)C、o(n)D、o()(3分)[20]线性表是具有n个()的有限序列。A、表元素B、字符C、数据元素D、数据项E、信息项(2分)[21]静态链表中指针表示的是A、内存地址B、数组下标C、下一元素地址D、左、右孩子地址(2分)[22]若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。A、单链表B、双链表C、单循环链表D、带头结点的双循环链表(2分)[23]设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。A、单链表B、单循环链表C、带尾指针的单循环链表D、带头结点的双循环链表(2分)[24]线性表是具有n个（）的有限序列（n0）。A、表元素B、字符C、数据元素D、数据项E、信息项(2分)[25]下面关于线性表的叙述中，错误的是哪一个？A、线性表采用顺序存储，必须占用一片连续的存储单元。B、线性表采用顺序存储，便于进行插入和删除操作。C、线性表采用链接存储，不必占用一片连续的存储单元。D、线性表采用链接存储，便于插入和删除操作。(2分)[26]下述哪一条是顺序存储结构的优点？A、存储密度大B、插入运算方便C、删除运算方便D、可方便地用于各种逻辑结构的存储表示(2分)[27]L是线性表，已知ListLength(L)的值是5，运算DeleteList（L，2）后ListLength（L）的值是。A、5B、0C、4D、6(2分)[28]下列说法正确的是。A、线性表的逻辑顺序与存储顺序总是一致的B、线性报第链式存储结构中，内存中可用的存储单元可以使连续的，也可以不连续C、线性表弟顺序存储结构优于链式存储结构D、每种数据结构都具有插入、删除和查找三种基本运算(2分)[29]指针P指向循环链表L的首元素的条件是。A、P=LB、P-nest=LC、L-nest=PD、P-nest=null(2分)[30]线性表中各元素之间的关系是()关系。A、层次B、网状C、有序D、集合(2分)[31]线性表（L）经运算InitList（L）后，函数IEmpty（L）的值是。A、0B、,falseC、1D、Null(2分)[32]假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针字段，现要把一个指针s所指的新结点作为非空双链表中q所指结点（中间结点）的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是。A、.q-right=s；s-left=q；q-right-left=s；s-right=q-right；B、s-left=q；q-right=s；q-right-left=s；s-right=q-right；C、s-left=q;s-right=q-right;q-right-left=s;q-right=s;D、以上都不对(2分)[33]设非空单链表的数据字段为data，指针字段为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i+1个结点，下列算法段能正确完成上述要求的是。A、s-next=p-next=s；B、p-next=s；s-next=p-next；C、s-next=p-next；p-next=s；交换p-data和s-data；D、p=s；s-next=p(2分)[34]在长度为n的顺序表的第i（1≤i≤n+1）各位置上插入一个元素，元素的移动次数为。A、n-i+1B、n-iC、iD、i-1(2分)[35]指针p指向线性链表L首元素的条件是。A、p=LB、L-next=pC、p-next=LD、p-next=null(2分)[36]两指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱的条件是。A、p-next=qB、q-next=pC、p=qD、p-next=null(2分)[37]指针P所指的元素是小、双向循环链表Lde尾元素的条件是。A、P==LB、p==nullC、p-prior==LD、p-next==L(2分)[38]线性表采用链式存储时，其地址。A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续与否均可以(2分)[39]如果一个顺序表中第一个元素的存储地址为1000,每个元素占4个地址单元，那么，第6个元素的存储地址应是A、1020B、1010C、1016D、1024二、算法设计题(61小题,共764.0分)(10分)[1]请写一个算法将顺序存储结构的线性表（a1...an）逆置为(an...a1)。类似本题的另外叙述有：(1)设有一带头结点的单链表,编程将链表颠倒过来.要求不用另外的数组或结点完成.(2)设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为O（n）。（注：用程序实现）(3)试编写求倒排循环链表元素的算法。(4)请设计算法将不带头结点的单链表就地逆置。