线性表练习题(答案)

《线性表练习题(答案)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第2章线性表一选择题1•下列程序段的时间复杂度为(C)。for(inti=l;i<=n;i++)for(intj=1;j<=m;j++)A[i]Ul=i*j；D.(m+n)A.0(m2)B.0(n2)C.O(m*n)2•下面关于线性表的叙述中，错误的是哪一个？(B)A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。3•线性表是具有n个(C)的有限序列(n>0)oA

2、.表元素B.字符C・数据元素D.数据项4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用(A)存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用(D)存储方式最节省运算时间。A.单链表C・双链表B•仅有头指针的单循环链表D•仅有尾指针的单循环链表6.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。A.单链表B.单循环链表C.带尾指针的单循

3、环链表D.带头结点的双循环链表7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用(D)存储方式最节省运算时间。A.单链表B.双链表C・单循环链表D.带头结点的双循环链表8•链表不具有的特点是(B)A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比9.下面的叙述不正确的是(B,C)A・线性表在链式存储时，查找第i个元素的时间同i的值成正比B.线性表在链式存储时，查找第i个元素的I]寸间同i的值无关C.线性表在顺序存储时，查找第i

4、个元素的时间同i的值成正比D.线性表在顺序存储时，查找第i个元素的时间同i的值无关10.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为(C)(l<=i<=n+l)oA.0(0)B.O(l)C.O(n)D.0(n2)11.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为(C)oA.O(n)O(n)B.0(n)0(1)C.0(1)0(n)D.0(1)0(1)12.线性表(al,a2,...,an)以链接方式存储时，访问第i位置元素的时间复杂性为(C)D.0(i-

5、1)A.O(i)B.O(1)C.O(n)13.循环链表H的尾结点P的特点是(A)oA.P->next=HB.P->next=H->nextC.P=HD-P=H->next9.完成在双循环链表结点p之后插入s的操作是（D）；A.p->next=s;s->priou=p;p->next->priou=s;s->next=p->next;B.p->next->priou=s;p->next=s;s->priou=p;s->next=p->next;C・s->priou=p;s->next=p->next;p->n

6、ext=s;p->next->priou=s;D.s->priou=p;s->next=p->next;p・>next->priou=s;p・>next=s;10.设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B插入结点X的操作序列为（B）。A.s->next=p->next；p->next=-s；B.q->next=s；s->next=p；C・p->next=s->next；s->next=p；D.p->next=s；s->next=q；二、判

7、断1•顺序存储结构的主要缺点是不利于插入或删除操作。（1）2.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（1）3.对任何数据结构链式存储结构一定优于顺序存储结构。（0）4•顺序存储方式只能用于存储线性结构。（0）5.集合与线性表的区别在于是否按关键字排序。（0）6.线性表的特点是每个元素都有一个前驱和一个后继。（0）7.取线性表的第i个元素的时间同i的大小有关・（1）&线性表只能用顺序存储结构实现。（0）9•顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（0）10.链表是采用链

8、式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。（1）三、填空1.线性表L=（al,a2,...,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是—（n-1）/2o2.在一个长度为n的顺序表中第i个元素（l<=i<=n）之前插入一个元素吋，需向后移动n+1-i个元素。3.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执