数据结构测试（长春理工大学精品课）
第2章线性表
一、选择题
1．下述( )是顺序存储结构的优点？查看答案
A．存储密度大 B．插入运算方便
C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
正确答案为A
解释：插入运算和删除运算对于顺序存储结构需要移动大量的数据元素，顺序存储结构对于非线性的逻辑结构表示比较复杂，顺序存储结构中只需要存储数据元素，不像链式结构除了存数据元素还要存储关系，因此顺序存储结构的存储密度比较大。
收起
2．下面关于线性表的叙述中，错误的是哪一个？（ )查看答案
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
正确答案是B
解释：顺序存储不利于插入删除，需要移动近一半的数据元素。
收起
3．线性表是具有n个（）的有限序列（n>0）。
查看答案
A．表元素 B．字符
C．数据元素 D．数据项
正确答案是C
解释：根据线性表的定义。
收起
4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
查看答案
A．顺序表 B．双链表
C．带头结点的双循环链表 D．单循环链表
正确答案是A
解释：顺序存储结构做相应的操作时间复杂度分别为O(1)，O(1)，O(1)因此是最节省时间的。
收起
5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
查看答案
A．单链表 B．仅有头指针的单循环链表
C．双链表 D．仅有尾指针的单循环链表
正确答案是D
解释：在仅有尾指针的单循环链表做相应操作的时间复杂度为O(1)，O(1)收起
6. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。
查看答案
A. O(0)
B. O(1)
C. O(n)
D. O(n2)
正确答案是C
解释：在顺序表的第i个位置插入一个元素平均需移动的元素的个数是[n+(n-1)+......+0]/(n+1)=n/2，因此算法时间复杂度为O（n）。
收起
7．非空的循环单链表head的尾结点p满足（）。
查看答案
A．P->next==head B．P->next==NIL
C．p==NIL D．p==head
正确答案是A
解释：循环单链表的尾结点的后继结点应当是头结点。
收起
8．在单链表指针为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;
正确答案是B
解释：p结点插入前的后继应成为s的后继，s应成为p的新后继，而且两个操作不能换位，否则p结点的后继链将丢失。
收起
9. 链表不具有的特点是（）。
查看答案
A．插入、删除不需要移动元素B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性长度成正比
正确答案是B
解释：链式存储方式不能随机访问，只能采用顺序访问的方式。
收起
10.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。
所以，它存取表中第i个元素的时间与i无关。
(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
以上错误的是（）。
查看答案
A．（1），（2） B．（1）
C．（1），（2）,(3) D.（2）
正确答案是B
解释：静态链表采用数组做为存储结构，是方便没有指针的编程语言使用，元素的后继地址记录的是元素所在的下标，因此和单链表一样只能采用顺序访问方式，插入删除操作只需修改相应下标不需移动元素。
收起
二、填空题
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
查看答案
正确答案是：顺序存储结构
解释：元素总数稳定，说明很少做插入删除操作，因此采用顺序存储最合适。
收起
2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。
查看答案
正确答案是：（n-1）/2
解释：长度为n的线性表，删除任一元素的概率为1/n，删除一个元素平均移动的元素的个数为[(n-1)+(n-2)+......+0]/n=(n-1)/2收起
3．对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为________,查看答案
正确答案是：O(1)
解释：在已知结点的后面插元素，只需修改后继元素的指针。
收起
4．对于一个具有n个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为________。
查看答案
正确答案是：O(n)
解释：查找值为x的结点，只能顺序查找，时间复杂度为O(n)收起。
5. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________。
查看答案
正确答案是：p->next=p->next->next
解释：删除其后继只需让后继的后继成为其后继。
收起
6．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。
查看答案
正确答案是：f->next=p->next; f->prior=p; p->next->prior=f; p->next=f; 收起
7.带头结点的双循环链表L为空表的条件是：________。
查看答案
正确答案是：L->next==L && L->prior==L
解释：双循环链表为空，前驱和后继都应指向头结点。
收起
8. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个。
查看答案
正确答案是：4个
解释：修改的指针分别为前一个结点的后继，后一个结点的前驱，新结点的前驱和后继。
收起
9. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：
S->next=p；s->prior= ________；p->prior=s；________=s；查看答案
正确答案是：p->prior s->prior->next
解释：插入后p的前驱成为s，s的前驱应是原来p的前驱。
收起
10. 在单链表L中，指针p所指结点有后继结点的条件是：查看答案
正确答案是：p->next！=null 收起
三、应用题
1.线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。
线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。
查看答案
参考答案：链式存储结构一般说克服了顺序存储结构的三个弱点。
首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。
其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。
收起
2. 下面是一算法的核心部分，试说明该算法的功能.查看答案
pre=L->next;
{L是一单链表，结点有数据域 data和指针域 next}
IF (pre!=null)
WHILE (pre->next!=null）
{ p=pre->next;
IF (p->data>=pre->data)
pre=p
ELSE
return(false)
}
return(true);
参考答案：该算法的功能是判断链表L是否是非递减有序，若是则返回“true”；否则返回“false”。
pre指向当前结点，p指向pre的后继。
收起。