数据结构第二章习题(1)
第二章线性表
一、选择题
1. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素算法的时间复杂度（
）。
B.O(1)
C. O(n)
D.O(n2)
）
A. O(log2n) 存储方式最节省时间。A. 顺序表A. 图个元素。A. n-i
B. n-i+1
C. n-i-1
）。
B. p->next==NULLD. p==head
）。
B. 插入删除不需要移动元素D. 所需空间与线性表长度成正比
D. i
B. 树
B. 单链表
）。C. 广义表
D. 栈
）
C.
双链表
D. 单循环链表
2. 若一个线性表中最常用的操作是取第i 个元素和找第i 个元素的前趋元素，则采用（
3. 具有线性结构的数据结构是（
4. 在一个长度为n 的顺序表中，在第i 个元素之前插入一个新元素时，需向后移动（
5. 非空的循环单链表head 的尾结点p 满足（A. p->next==headC.
p==NULL
6. 链表不具有的特点是（A. 可随机访问任一元素C. 不必事先估计存储空间操作是（
）。
7. 在双向循环链表中，在p 指针所指的结点后插入一个指针q 所指向的新结点，修改指针的A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D. q->next=p->next;q->prior=p;p->next=q;p->next=q;8. 线性表采用链式存储时，结点的存储地址（A. 必须是连续的C. 连续与否均可A. n-i 10. 线性表是n 个（
A. 表元素
B. n-i+1）的有限序列。
B. 字符
C. 数据元素D. 数据项
）。）。
B. 必须是不连续的
D. 和头结点的存储地址相连续
）个元素。D. i+1
C. n-i-1
9. 在一个长度为n 的顺序表中删除第i 个元素，需要向前移动（
11. 从表中任一结点出发，都能扫描整个表的是（
A. 单链表A. O(n)
B. 顺序表B. O(1)
C. 循环链表C. O(n2)
）。
D. 静态链表）。D. O(n-1)
12. 在具有n 个结点的单链表上查找值为x 的元素时，其时间复杂度为（13. 线性表L=(a1,a2,……,an) ，下列说法正确的是（A. 每个元素都有一个直接前驱和一个直接后继B. 线性表中至少要有一个元素
C. 表中诸元素的排列顺序必须是由小到大或由大到小
D. 除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继14. 一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的存
储地址是（A. 98A. 单链表
）。
B. 100B. 双链表
C. 102C. 循环链表
D. 106
）。）。D. 顺序表
15. 在线性表的下列存储结构中，读取元素花费的时间最少的是（16. 在一个单链表中，若删除p 所指向结点的后续结点，则执行（
A. p->next=p->next->next;
B. p=p->next;p->next=p->next->next;C. p =p->next;D. p=p->next->next;
17. 将长度为n 的单链表连接在长度为m 的单链表之后的算法的时间复杂度为（
A. O(1)A. 随机存取A. (n-1)/2A. 不再需要头指针
B. 已知某结点位置后能容易找到其直接前驱C. 在进行插入、删除运算时能保证链表不断开D. 在表中任一结点出发都能扫描整个链表21. 不带头结点的单链表head 为空的判定条件是（
A. head==NULLC. head->next==head
A. 访问第i 个元素的前驱（1
）。
B. head->next==NULLD. head!=NULL
）。
B. O(n)B. 顺序存取
B. n
）。
C. O(m)）存储结构。C. 索引存取C. n+1
D. 散列存取）。
D. (n+1)/2D. O(m+n)
18. 线性表的顺序存储结构是一种（
）。
19. 顺序表中，插入一个元素所需移动的元素平均数是（20. 循环链表的主要优点是（
22. 在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（
B. 在第i 个元素之后插入一个新元素(1≤i ≤n ) C. 删除第i 个元素(1≤i ≤n ) D. 对顺序表中元素进行排序
23. 已知指针p 和q 分别指向某单链表中第一个结点和最后一个结点。假设指针s 指向另一个
单链表中某个结点，则在s 所指结点之后插入上述链表应执行的语句为（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. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况D. 线性表的链表存储结构优于顺序存储结构
25. 在表长为n 的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（A. (n-1)/2
）。
B. n/2
C. (n+1)/2
D. n ）。
26. 在一个单链表中，已知q 所指结点是p 所指结点的前驱结点，若在q 和p 之间插入一个结点s ，则执行（）。
A. s->next=p->next;p->next=s;B. p->next=s->next;s->next=p;C. q->next=s;s->next=p;D. p->next=s;s->next=q;
27. 在单链表中，指针p 指向元素为x 的结点，实现删除x 的后继的语句是（
A. p=p->next;C. p->next=p;
B. p->next=p->next->next;D. p=p->next->next;
）。
B. p 指向尾结点D. p 的直接后继是尾结点
）。
28. 在头指针为head 且表长大于1的单循环链表中，指针p 指向表中某个结点，若
p->next->next==head，则（A. p 指向头结点
C. p 的直接后继是头结点
二、填空题
1、设单链表的结点结构为（data,next ）。已知指针p 指向单链表中的结点，q 指向新结点，欲将q 插入到p 结点之后，则需要执行的语句：2、线性表的逻辑结构是
；
。
3、写出带头结点的双向循环链表L 为空表的条件4、带头结点的单链表head 为空的条件是
5、在一个单链表中删除p 所指结点的后继结点时，应执行以下操作：
q =p->next;。
。
三、判断题
1、单链表不是一种随机存储结构。
2、在具有头结点的单链表中，头指针指向链表的第一个数据结点。
3、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。4、顺序存储方式只能用于存储线性结构。
在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不一定是相邻的。5、
6、链式存储的线性表可以随机存取。
四、程序分析填空题
1、函数GetElem 实现返回单链表的第i 个元素，请在空格处将算法补充完整。int GetElem(LinkListL,int i,Elemtype *e){
LinkList p ；int j ；p=L->next;j=1;while(p&&j
}
if(!p||j>i)return ERROR; *e=; return OK;
}
2、函数实现单链表的插入算法，请在空格处将算法补充完整。
int ListInsert(LinkListL,int i,ElemType e){
LNode *p,*s;intj; p=L;j=0;
while((p!=NULL)&&(j
p=p->next;j++;}
if(p==NULL||j>i-1)return ERROR; s=(LNode*)malloc(sizeof(LNode));s->data=e;
; ;
return OK; }/*ListInsert*/
3、函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。
int int ListDelete_sq(Sqlist*L,inti){
if(iL->length)k;
for(k=i-1;klength-1;k++)
return ERROR; L->slist[k]=
（2）
;
return OK;
4}
int 、函数实现单链表的删除算法，请在空格处将算法补充完整。LNode ListDelete(LinkListL,int i,ElemType *s){
int p=L;j=0;
j; *p,*q;while((if(p->next==NULL||j>i-1))&&(jnext;j++;
q=p->next;
return ERROR; （2）
;
*s=q->data;free(q);
}/*listDelete*/
return OK; 5、写出算法的功能。
int node L(head){
p=head;
*head,*p;int n=0;while(p!=NULL){p=p->next;n++;}}
return(n);五、综合题
1. 编写算法，实现带头结点单链表的逆置算法。
}
链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，2. 有两个循环链表，
且连接后仍保持循环链表形式。
3. 设一个带头结点的单向链表的头指针为head ，设计算法，将链表的记录，按照data 域的值递增排序。
4. 编写算法, 将一个头指针为head 不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。
5. 已知head 为带头结点的单循环链表的头指针，链表中的数据元素依次为（a1，a2,a3,a4, …,an ）,A 为指向空的顺序表的指针。阅读以下程序段，并回答问题：（1）写出执行下列程序段后的顺序表A 中的数据元素；（2）简要叙述该程序段的功能。if(head->next!=head){
p=head->next;A->length=0;
while(p->next!=head){p=p->next;
A->data[A->length++]=p->data;if(p->next!=head)p=p->next;}
}
6. 设顺序表va 中的数据元数递增有序。试写一算法，将x 插入到顺序表的适当位置上，以持该表的有序性。
保
7、假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f2，设顺序表
并描述该算法的功L=(3,7,3,2,1,1,8,7,3),写出执行算法f2后的线性表L 的数据元素，
能。
void f2(SeqList*L){
int i,j,k; k=0;
for(i=0;ilength;i++){
for(j=0;jdata[i]!=L->data[j];j++);if(j==k){
if(k!=i)L->data[k]=L->data[i];k++;}}
L->length=k;}
8. 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x 且小于y 的元素（若表中存在这样的元素）同时释放被删除结点空间。
9. 在带头结点的循环链表L 中，结点的数据元素为整型，且按值递增有序存放。给定两个整数a 和b ，且a