第2章_线性表_自测题

数据结构第二章线性表习题02线性表【单选题】1.以下不属于线性结构特点的就是（c）。

ａ、存有且仅有一个数据元素并无轻易前驱ｂ、存有且仅有一个数据元素并无轻易后继ｃ、有且仅有一个数据元素既无直接前驱又无直接后继ｄ、大多数据元素存有且仅有一个轻易前驱，存有且仅有一个轻易后继2.线性表是具有n个（c）的有限序列。

ａ、信息项ｂ、字符ｃ、数据元素ｄ、数据项3.线性表的逻辑顺序与存储顺序总是一致的，这种说法（b）。

ａ、正确ｂ、不正确4.在顺序表，数据元素e1与其轻易后继e2在存储边线上（a）。

ａ、必相连ｂ、必不相连ｃ、可以相连可不相连5.在长为n的顺序表中删除一个数据元素，平均需移动（d）个数据元素。

ａ、nｂ、n-1ｃ、n/2ｄ、(n-1)/26.在短为n的顺序表填入一个数据元素，平均值须要移动（c）个数据元素。

ａ、nｂ、n-1ｃ、n/2ｄ、(n-1)/27.单链表是一种（b）存取的存储结构ａ、随机ｂ、顺序ｃ、索引ｄ、连续8.以下属顺序存储结构优点的就是（a）。

ａ、存储密度大ｂ、插入运算方便ｃ、删除运算方便ｄ、可方便地用于各种逻辑结构的存储表示9.以下属于单链表中优点的就是（c）。

ａ、顺序存取ｂ、插入操作能在o(1)的时间复杂度上完成ｃ、插入时不需移动数据元素ｄ、节省存储空间10.在单链表，数据元素e1与其轻易后继e2在存储边线上（c）。

ａ、必相连ｂ、必不相连ｃ、可以相连可不相连11.以下属单链表与循环链表区别的是（b）。

ａ、结点结构相同ｂ、搜寻结点的算法中，循环完结条件相同ｃ、对存储空间连续性的建议相同ｄ、对与否涵盖头结点的建议相同12.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（a）存储方式最节省时间。

ａ、顺序表中ｂ、双链表中ｃ、率先垂范结点的双向循环链表ｄ、单循环链表13.若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（d）存储方式最节省运算时间。

第2章重点：单链表的存储结构，插入和删除的算法一、填空. 线性表中结点的集合是的，结点间的关系是的。

3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。

4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。

6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置相邻。

单链表中逻辑上相邻的元素的物理位置相邻。

7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由指示。

三、单项选择题（）（）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（）2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120（）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）（B）在第i个结点后插入一个新结点（1≤i≤n）（C）删除第i个结点（1≤i≤n）（D）将n个结点从小到大排序（）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7（）5. 链接存储的存储结构所占存储空间：（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针（B）只有一部分，存放结点值（C）只有一部分，存储表示结点间关系的指针（D）分两部分，一部分存放结点值，另一部分存放结点所占单元数（）6. 链表是一种采用存储结构存储的线性表；（A）顺序（B）链式（C）星式（D）网状（）7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以（）8．线性表Ｌ在情况下适用于使用链式结构实现。

B. 单链表
C. 双链表
D. 单循环链表
3.具有线性结构的数据结构是（ ）。
A. 图
B. 树
C. 广义表
D. 栈
4.在一个长度为 n 的顺序表中，在第 i 个元素之前插入一个新元素时，需向后移动（ ）
个元素。
A. n-i
B. n-i+1
C. n-i-1
5.非空的循环单链表 head 的尾结点 p 满足（ ）。
A. n-i
B. n-i+1
C. n-i-1
D. i+1
10.线性表是n个（ ）的有限序列。
A. 表元素
B. 字符 C. 数据元素 D. 数据项
11.从表中任一结点出发，都能扫描整个表的是（ ）。
A. 单链表
B. 顺序表
C. 循环链表
D. 静态链表
12.在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（ ）。
A. q->next=s->next；s->next=p； B. s->next=p；q->next=s->next；
C. p->next=s->next；s->next=q； D. s->next=q；p->next=s->next； 24.在以下的叙述中，正确的是（ ）。
A. 线性表的顺序存储结构优于链表存储结构 B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
A. p->next=p->next->next;
B. p=p->next;p->next=p->next->next;
C. p =p->next;

一、选择题1、用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是（）A、当前结点所在的地址域B、指针域C、空指针域D、空闲域2、不带头结点的单链表head为空的判断条件是（）A、head==NULLB、head->next==NULLC、head->data==NULLD、head!=NULL3、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行（）A、s->next=p; q->next=s;B、p->next=s->next; s->next=p;C、q->next=s->next; s->next=p;D、p->next=s; s->next=q;4、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）A、O（1）B、O（n）C、O（n2）D、O（nlog2n）5、一个单链表中，若删除p所指结点的后续结点，则执行（）A、p->next=p->next->next;B、p=p->next; p->next=p->next->next;C、p->next=p;D、p=p->next->next;6、已知一个顺序存储的基本线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1，则第i个结点的地址为（）A、d1+(i-1)*mB、d1+i*mC、d1-i*mD、d1+(i+1)*m7、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）A、访问第i个结点(1<=i<=n)和求第i个结点的直接前驱(2<=i<=n)B、在第i个结点后插入一个新结点(1<=i<=n)C、删除第i个结点(1<=i<=n)D、将n个结点从小到大排序8、下面给出的算法段是要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双向链表中，能正确完成要求的算法段是（）A、q->next=p; q->prior=p->prior; p->prior=q; p->prior->next=q;B、p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;C、q->prior=p->prior; q->next=p; p->prior->next=q; p->prior=q;D、以上都不对9、在循环双链表的p所指结点之后插入s所指结点的操作是（）A、p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;B、p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;C、s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;D、s->prior=p; p->next->prior=s; s->next=p->next; p->next=s;10、从具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。