下载掌阅APP，畅读海量书库
立即打开
1.对线性表，在下列哪种情况下应当采用链表表示？（）
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间
D.表中元素的个数不变
2.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为（）。
A.O（log 2 n）
B.O（1）
C.O（n）
D.O（n 2 ）
3.若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。
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.在双向循环链表中，在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；
7.线性表采用链式存储时，结点的存储地址（）。
A.必须是连续的
B.必须是不连续的
C.连续与否均可
D.和头结点的存储地址相连续
8.在一个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。
A.n-i
B.n-i+1
C.n-i-1
D.i+1
9.从表中任一结点出发，都能扫描整个表的是（）。
A.单链表
B.顺序表
C.循环链表
D.静态链表
10.在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（）。
A.O（n）
B.O（1）
C.O（n 2 ）
D.O（n-1）
11.一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的存储地址是（）。
A.98
B.100
C.102
D.106
12.在一个单链表中，若删除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；
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.在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（）。
A.p=p->next；
B.p->next=p->next->next；
C.p->next=p；
D.p=p->next->next；
1.函数实现单链表的插入算法，请在空格处将算法补充完整。
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;
}
2.函数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;
}
3.写出算法的功能。
int L(head){
node * head;
int n=0;
node *p;
p=head;
while(p!=NULL)
{ p=p->next;
n++;
}
return(n);
}
1.编写算法，实现带头结点单链表的逆置算法。
2.已知有两个带头结点的单链表A和B，A和B中的元素由小到大排列，设计一个算法，求A和B的交集C，将A和B中相同的元素插入C中。
3.顺序表A和顺序表B的元素都是非递减排列，利用线性表的基本运算，将它们合并成一个顺序表C，要求C也是非递减排列。例如，A=（6，11，11，23），B=（2，10，12，12，21），则C=（2，6，10，11，11，12，12，21，23）。
4.已知有两个顺序表A和B，A中的元素按照递增排列，B中的元素按照递减排列。试编写一个算法，将A和B合并成一个顺序表，使其按照递增有序排列，要求不占用额外的存储单元。
5.利用单链表的基本运算，实现如果在单链表A中出现的元素，在单链表B中也出现，则将A中该元素删除。
分析 如果把单链表看成是集合，这其实是求两个集合的差集A-B，即所有属于集合A而不属于集合B的元素。具体实现是，对于单链表A中的每个元素e，在单链表B中进行查找，如果在B中存在与A相同的元素，则将元素从A中删除。
6.将单链表A和B合并得到C，C中的元素仍按照非递减排列。
7.已知有两个带头结点的双向循环链表A和B，它们的元素均是按照递增排列，编写算法，将A和B合并成一个双向循环链表，并使合并后链表中的元素也按照递增排列。
分析 可以使用原有结点空间而不建立新结点合并双向循环链表。首先以A的头结点建立新的空双向链表；分别用指针p和q指向链表A和B的第一个结点，依次比较p和q指示的结点元素大小，取下较小的结点作为新链表的结点，插入到新链表的表尾，重复这一过程一直到A和B中有一个链表为空；如果A和B中有一个链表为空而另一个链表不为空时，将不空的链表剩下的部分插入新链表的表尾。
8.设A和B是两个顺序表，其元素按从小到大的顺序排列。编写一个算法，将A和B中相同元素组成一个新的从大到小的有序顺序表C，并分析算法的时间复杂度。