数据结构--线性表习题及答案
第⼆章线性表
⼀、选择题
1、若长度为n的线性表采⽤顺序存储结构，在其第i个位置插⼊⼀个新元素算法的时间复杂度（）。
A. O(log2n)
B.O(1)
C. O(n)
D.O(n2)
2、若⼀个线性表中最常⽤的操作是取第i个元素和第i个元素的前趋元素，则采⽤（）存储⽅式最节省时间。
A. 顺序表
B. 单链表
C.  双链表
D. 单循环链表
3、具有线性结构的数据结构是（）。
A. 图
B. 树
C. ⼴义表
D.栈
4、在⼀个长度为n的顺序表中，在第i个元素之前插⼊⼀个新元素时，需向后移动（）个元素。
A. n-i
B. n-i+1
C. n-i-1
D. i
5、⾮空的循环单链表head的尾结点p满⾜（）。
A. p->next==head
B. p->next==NULL
C.  p==NULL
D. p==head
6、链表不具有的特点是（）。
A. 可随机访问任⼀元素
B. 插⼊删除不需要移动元素
C. 不必事先估计存储空间
D. 所需空间与线性表长度成正⽐
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. 必须是连续的
B. 必须是不连续的
C. 连续与否均可
D. 和头结点的存储地址相连续
9、在⼀个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。
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. O(n)
B. O(1)
C. O(n2)
D. O(n-1)
13、线性表L=(a1,a2,……,an)，下列说法正确的是（）。
A. 每个元素都有⼀个直接前驱和⼀个直接后继
B. 线性表中⾄少要有⼀个元素
C. 表中诸元素的排列顺序必须是由⼩到⼤或由⼤到⼩
D.除第⼀个和最后⼀个元素外，其余每个元素都由⼀个且仅有⼀个直接前驱和直接后继
14、⼀个顺序表的第⼀个元素的存储地址是90，每个元素的长度为2，则第6个元素的存储地址是（）。
A. 98
B. 100
C. 102
D. 106
15、在线性表的下列存储结构中，读取元素花费的时间最少的是（）。
A. 单链表
B. 双链表
C. 循环链表
D. 顺序表
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)
B. O(n)
C. O(m)
D. O(m+n)
18、线性表的顺序存储结构是⼀种（）存储结构。
A. 随机存取
B. 顺序存取
C. 索引存取
D. 散列存取
19、顺序表中，插⼊⼀个元素所需移动的元素平均数是（）。
A. (n-1)/2
B. n
C. n+1
D. (n+1)/2
10、循环链表的主要优点是（）。
A. 不再需要头指针
B. 已知某结点位置后能容易到其直接前驱
C. 在进⾏插⼊、删除运算时能保证链表不断开
D. 在表中任⼀结点出发都能扫描整个链表
11、不带头结点的单链表head为空的判定条件是（）。
A. head==NULL
B. head->next==NULL
C. head->next==head
D. head!=NULL
12、在下列对顺序表进⾏的操作中，算法时间复杂度为O(1)的是（）。
A. 访问第i个元素的前驱（1<）
B. 在第i个元素之后插⼊⼀个新元素()
C. 删除第i个元素()
D. 对顺序表中元素进⾏排序
13、已知指针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；
14、在以下的叙述中，正确的是（）。
A. 线性表的顺序存储结构优于链表存储结构　
B. 线性表的顺序存储结构适⽤于频繁插⼊/删除数据元素的情况
C. 线性表的链表存储结构适⽤于频繁插⼊/删除数据元素的情况
D. 线性表的链表存储结构优于顺序存储结构
15、在表长为n的顺序表中，当在任何位置删除⼀个元素的概率相同时，删除⼀个元素所需移动的平均个数为（）。
A. (n-1)/2
B. n/2
C. (n+1)/2
D. n
16、在⼀个单链表中，已知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;
17、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（）。
A. p=p->next;
B. p->next=p->next->next;
C. p->next=p;
D. p=p->next->next;
18、在头指针为head且表长⼤于1的单循环链表中，指针p指向表中某个结点，若p->next->next==head，则（）。
A. p指向头结点
B. p指向尾结点
C. p的直接后继是头结点
D. p的直接后继是尾结点
⼆、填空题
1、设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，欲将q插⼊到p结点之后，则需要执⾏的语句：  q-next=p-next,p-next=q          。
答案：q->next=p->next  p->next=q
2、线性表的逻辑结构是线性结构，其所含元素的个数称为线性表的长度。
答案：线性结构长度
3、写出带头结点的双向循环链表L为空表的条件    L-prior=L-next=L            。
答案：L->prior==L->next==L
4、带头结点的单链表head为空的条件是  head-next==null        。
答案：head->next==NULL
5、在⼀个单链表中删除p所指结点的后继结点时，应执⾏以下操作：
q = p->next;
p->next=_q-next  ___;
数据结构与算法分析答案答案：q->next
三、判断题
1、单链表不是⼀种随机存储结构。P
2、在具有头结点的单链表中，头指针指向链表的第⼀个数据结点（的存储位置）。O
3、⽤循环单链表表⽰的链队列中，可以不设队头指针，仅在队尾设置队尾指针。P
4、顺序存储⽅式只能⽤于存储线性结构。O
5、在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不⼀定是相邻的。O
6、链式存储的线性表可以随机存取。O
四、程序分析填空题
1、函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。
Title
int GetElem(LinkList L,int i,Elemtype *e){
LinkList p；int j；
p=L->next;j=1;
while(p&&j<i){
(1)    ;++j;
}
if(!p||j>i)  return ERROR;
*e=    (2)    ;
return OK;
}
答案：(1)p=p->next    (2)p->data
2、函数实现单链表的插⼊算法，请在空格处将算法补充完整。
int ListInsert(LinkList L,int i,ElemType e){
LNode *p,*s;int j;
p=L;j=0;
while((p!=NULL)&&(j<i-1)){
p=p->next;j++;
}
if(p==NULL||j>i-1) return ERROR;
s=(LNode *)malloc(sizeof(LNode));
s->data=e;
(1)            ;
(2)              ;
return OK;
}/*ListInsert*/
答案：(1)s->next=p->next    (2)p->next=s
3、函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。int ListDelete_sq(Sqlist *L,int i){
int k;
if(i<1||i>L->length) return ERROR;
for(k=i-1;k<L->length-1;k++)
L->slist[k]=      （1）      ;
（2）          ;
return OK;
}
答案：（1）L->slist[k+1]    （2） --L->Length
4、函数实现单链表的删除算法，请在空格处将算法补充完整。
int ListDelete(LinkList L,int i,ElemType *s){
LNode *p,*q;
int j;
p=L;j=0;
while((        （1）    )&&(j<i-1)){
p=p->next;j++;
}
if(p->next==NULL||j>i-1) return ERROR;
q=p->next;
（2）          ;
*s=q->data;
free(q);
return OK;
}/*listDelete*/
答案：(1)p->next!=NULL    (2)p->next=q->next
5、写出算法的功能。
int L(head){
node * head;
int n=0;
node *p;
p=head;
while(p!=NULL)
{ p=p->next;
n++;
}
return(n);
}
答案：求单链表head的长度
五、综合题
1、编写算法，实现带头结点单链表的逆置算法。
答案：void invent(Lnode *head)
{Lnode *p,*q;
if(!head->next) return ERROR;
p=head->next; q=p->next; p->next =NULL;
while(q)
{p=q; q=q->next; p->next=head->next; head->next=p;}
}
2、有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。