第二部分 线性表 答案.docx
《第二部分 线性表 答案.docx》由会员分享，可在线阅读，更多相关《第二部分 线性表 答案.docx（15页珍藏版）》请在冰点文库上搜索。
第二部分线性表答案
第二部分线性表
一、选择题
1．关于顺序存储的叙述中,哪一条是不正确的（B）
A.存储密度大
B.逻辑上相邻的结点物理上不必邻接
C.可以通过计算直接确定第i个结点的位置
D.插入、删除操作不方便
2．长度为n的单链表连接在长度为m的单链表后的算法的时间复杂度为（C）
AO（n）BO
（1）CO（m）DO（m+n）
3．在n个结点的顺序表中，算法的时间复杂度是O
（1）的操作是：
（A）
A访问第i个结点（1<=i<=n）和求第i个结点的直接前趋（2<=i<=n）
B在第i个结点（1<=i<=n）后插入一个新结点
C删除第i个结点（1<=i<=n）
D将n个结点从小到大排序
4．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：
（B）
（A）110（B）108（C）100（D）120
5．已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da，则第i个结点的地址为：
（A）
A）da+（i-1）*mB）da+i*mC）da-i*mD）da+（i+1）*m
6．在具有n个结点的单链表中，实现（A）的操作，其算法的时间复杂度为O（n）。
A）遍历链表和求链表的第i个结点B）在地址为p的结点之后插入一个结点
C）删除开始结点D）删除地址为p的结点的后继结点
7．链表是一种采用（B）存储结构存储的线性表。
（A）顺序（B）链式（C）星式（D）网状
8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址：
（D）
（A）必须是连续的（B）部分地址必须是连续的
（C）一定是不连续的（D）连续或不连续都可以
9．线性表Ｌ在（B）情况下适用于使用链式结构实现。
（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入
（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂
10．在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为（ A）
A.n-i+1 B.n-i C.i D.i-1
11．线性表是（ A ）。
a、一个有限系列，可以为空 b、一个有限系列，不能为空
c、一个无限系列，可以为空 d、一个无限系列，不能为空
12.（ A ）线性表。
A.（孔子,诸葛亮,曹雪芹）B.{A,B,C,D}
C.{10,11,12,13,14}D.（1,2,3,...）
13.（ ）是表示线性数据结构的。
A.循环链表B.邻接多重表C.孩子链表D.单链表
14.将线性表的数据元素以（B）结构存放,查找一个数据元素所需时间不依赖于表长。
A.循环双链表B.哈希（Hash）表C.一维数组D.单链表
15.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（B）。
（A）s->link=p;p->link=s;
（B）s->link=p->link;p->link=s;
（C）s->link=p->link;p=s;
（D）p->link=s;s->link=p;
16.在循环链表中first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是（D）。
（A）current->link=NULL（B）first->link=current
（C）first=current（D）current->link=first
17.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（D）个结点。
A.nB.n/2C.（n-1）/2D.（n+1）/2
18.在一个具有n个结点的有序单链表中，插入一新结点并仍然有序的时间复杂度为（B）。
A.O
（1）B.O（n）C.O（n2）D.O（nlog2n）
19.用链表表示线性表的优点是（ C）。
A.便于随机存取 B.花费的存储空间比顺序表少
C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同
20.当需要随机查找线性表的元素时,宜采用（C）作存储结构。
A.双向链表B.循环链表C.顺序表D.单链表
21.线性表的链接实现有利于（ A ）运算。
A、插入 b、读表元 c、查找 d、定位
22.线性表采用链式存储时，其地址（D）。
A 必须是连续的 B 部分地址是连续的
C 一定是不连续的 D 连续与否均可以
23.设单链表中指针p指着结点a，若要删除a之后的结点（若存在），则需要修改指针的操作为（ A ）。
A、p->next=p->next->next b、p=p->next
C、p=p->next->next d、p->next=p
24.向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（B）个元素。
A、8B、63.5C、63D、7
25.向一个有127个元素的顺序表中删除一个元素，平均要移动（C）个元素
（A）8（B）63.5（C）63（D）7
26.用链表表示线性表的优点是（A）
A便于插入和删除操作B数据元素的物理顺序与逻辑顺序相同
C花费的存储空间较顺序存储少D便于随即存取
27.以下数据结构中不属于线性数据结构的是（C）
A队列B线性表C二叉树D栈
28．对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为（B）。
A．N+1B．NC．（N+1）/2D．N/2
29．下列叙述中正确的是（A）。
A.线性表是线性结构B.栈与队列是非线性结构
C.线性链表是非线性结构D.二叉树是线性结构
30．在单链表中，增加头结点的目的是（A）。
A.方便运算的实现B.使单链表至少有一个结点
C.标识表结点中首结点的位置D.说明单链表是线性表的链式存储实现
31．线性表的顺序存储结构和线性表的链式存储结构分别是（B）。
A.顺序存取的存储结构、顺序存取的存储结构
B.随机存取的存储结构、顺序存取的存储结构
C.随机存取的存储结构、随机存取的存储结构
D.任意存取的存储结构、任意存取的存储结构
33．线性表中正确的说法是（D）。
A.每个元素都有一个直接前驱和一个直接后继
B.线性表至少要求一个元素
C.表中的元素必须按由小到大或由大到小排序
D.除了第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继
34．线性表是具有n个（C）的有限序列。
A.表元素B.字符C.数据元素D.数据项
35．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C）。
（1≤i≤n+1）
A.O（0）B.O
（1）C.O（n）D.O（n2）
36．在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度（B）。
A.O
（1）B.O（n）C.O（nlogn）D.O（n2）
37．某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素，删除运算是指删除表头第一个元素，那么采用（A）存储方式最节省运算时间。
A.仅有尾指针的单向循环链表B.仅有头指针的单向循环链表
C.单向链表D.双向链表
二、填空题
1．在单项链表中删除一个指定结点的后继的时间复杂度为[O
（1）]
2．线性表中______数据元素的个数______________________称为表的长度。
3.在n个结点的单链表中，在P指向的结点之后插入一个结点的时间复杂度为_O（n）。
4．设长度为n的线性表顺序存贮,若在它的第i-1和第i个元素之间插入一个元素,共需移动__n-i+1_______个元素（15．在顺序表中访问任意结点的时间复杂度为O
（1），因此顺序表也称为随机存储的数据结构。
6．在单链表中要在已知结点*p之前插入一新结点，需找到插入点，其时间复杂度为O（n），而在双链表中，完成同样操作的时间复杂度为O
（1）。
7．循环链表的主要优点是 从任何一个结点出发可以遍历所有结点 。
8．在一个单链表中删除p所指结点的下一个结点时，应执行以下操作：
q=p->link;
p->link=__p->link->link____
Deleteq
9．将适当的语句添入单链表搜索函数find中。
templateListNode*List:
:
find（Typevalue）
{current=first->link；
while（current!
=NULL）
if（current->data=value）break
elsecurrent=current->link;
return__current_____
}
10．顺序存储方法是把逻辑上相邻的结点存储在物理位置__也相邻______的存储单元中。
11．顺序存储结构使线性表中逻辑上相邻的数据元素在物理上也相邻。
因此，这种表便于__随机__访问，是一种__随机访问存储结构__。
12．在一个不带头结点的单链表中，在表头插入或删除与其在其他位置插入或删除操作的过程___不相同________。
13．已知L是无头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点，添加合适的语句。
1）P结点之后插入结点S：
S->next=P->next;P->next=S;
2）P结点之前插入结点S：
pre=L;
while（pre->next!
=P）pre=pre->next;
S->next=P;pre->next=S;
3）在表首插入结点S：
S->next=L;L=S;
4）在表尾插入结点S：
while（P->next）P=P->next;
P->next=S;S->next=NULL;
14．已知P结点是某双向链表的中间结点，添加合适的语句。
1）P结点之后插入结点S：
S->next=P->next;S->prior=P;
P->next->Prior=S;P->next=S;
2）P结点之前插入结点S：
S->next=P;S->prior=P->prior;
P->prior->next=S;P->prior=S;
3）删除P结点的直接后继结点：
Q=P->next;P->next=Q->next;Q->next->prior=P;free（Q）;
4）删除P结点的直接前驱结点：
Q=P->prior;P->prior=Q->prior;Q->prior->next=P;free（Q）;
5）删除P结点：
P->prior->next=P->next;P->next->prior=P->prior;free（P）;
15．在链表的结点中，数据元素所占存储量和整个结点所占的存储量之比称作存储密度。
三、判断题
1．线性链表中各个链结点之间的地址不一定要连续。
（R）
2．若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。
（W）
3．若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。
（W）
4．若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。
（W）
5．在顺序表中取出第i个元素所花费的时间与i成正比。
（W）
四、算法题
1．设n个元素的线性表顺序存储在一维数组st[1..maxlen]的前n个位置上,试将新元素e插入表中第i-1个和第i个元素之间,写出算法。
typedefstruct
{
ElemTypest[1..maxlen]; //存放线性表的数组
intn; //n是线性表的长度
}SeqList;
SeqListSeqLiseInit（）
{ //构造一个线性链表L
SeqListL; //定义为顺序表
L.lengh=0; //顺序表的长度为0
returnL
}
voidSeqListInsert（SeqlistL,inti,ElemTypex）
{ //在顺序表中的第i个位置插入元素x
if（L.length==maxlen）
{
printf（"thelistisfull"）;
exit（0）; //表满,退出
}
if（i<1||i>L.length）
{
printf（"positionerror"）;
exit（0）; //插入位置错,退出
}
for（j=L.length-1;j>=i-1;j--）
L.data[j+1]=L.data[j]; //第i个位置后的数组元素逐一后移
L.data[i-1]=x;//新元素插入到第i个位置
L.length++; //顺序表长度增1
}
3.执行下面的C程序,指出输出结果。
#include
#include
structnode
{chardata；
structnode*next；
}；
voidlink_list（structnode*p）
{while（p!
=NULL）
{printf（"%c",p->data）；p=p->next；
}
printf（"\n"）；
}
main（）
{charch；
structnode*q,*p,*f,*head=NULL；
for（ch='A'；ch<'F'；ch++）
{p=（structnode*）malloc（sizeof（structnode））；
p->data=ch；p->next=head；head=p；link_list（p）；
}
p=head；head=NULL；
while（p!
=NULL）
{q=p；p=p->next；q->next=head；head=q；f=head；
while（f->next!
=NULL）
{link_list（head）；f=f->next->next；
}
}
}
A
BA
CBA
DCBA
EDCBA
FEDCBA
F
FE
FED
FED
FEDC
FEDC
FEDCB
FEDCB
FEDCB
FEDCBA
FEDCBA
FEDCBA
4．下列算法完成的功能？
1）ListNode*Demo1（LinkListL,ListNode*p）
/*L是带有头结点的单链表*/
{ListNode*q=L->next;
while（q&&q->next!
=p）
q=q->next;
if（q）
returnq;
else
error（“*pisnotinL!
”）;
}
寻找结点P的前驱结点，若存在则返回前驱结点的地址，若不存在则给出错误信息
2）voidDemo2（ListNode*p,ListNode*q）
{DataTypetemp;
temp=p->data;
p->data=q->data;
q->data=temp;
}
交换结点p和q数据域的内容
3）LinkListDemo3（LinkListL）
/*L是无头结点的单链表*/
{ListNode*p,*q;
if（L&&L->next）
{q=L;
L=L->next;
p=L;
While（p->next）p=p->next;
p->next=q;
q->next=NULL;
}
returnL;
}
将链表L第一个结点变为最后一个结点
4）LinkList*Connect（LinkList*L1,LinkList*L2）
/*L1,L2是带有头结点的单链表*/
{LinkList*p;
p=L1;
while（p->next!
=NULL）p=p->next;
p->next=L2->next;
return（L1）;
}
将L2连接到L1后面
5．设Head为带头结点的单链表的头指针，试写出算法，若为非空表，则输出首结点和尾结点的值（data值），否则输出“EmptyList!
”。
Structnode{
Intdata;
Structnode*next;
};
printht（structnode*Head）
{structnode*p;
if（Head->next==NULL）printf（“EmptyList!
”）;
else{
printf（“首结点的值为%d”,Head->next->data）;
p=Head->next;
while（p->next）p=p->next;
if（p!
=Head->next）printf（“尾结点的值为%d”,p->data）;
elseprintf（“仅有一个结点！
”）;
}
}
6．假设有两个按元素递增有序排列的线性表A和B，均为单链表存储结构。
请编写算法，将表A和表B归并成一个按元素值非递减有序（允许相同值）排列的线性表C，并要求利用原表（即表A和表B）的结点空间存放表C。
link*merge（Link*A,Link*B）
{Link*s,*r;
/*假设A和B都是带头结点的单链表*/
Link*p=A->next;
Link*q=B->next;
C=A;C->next=NULL;r=C;
While（p&&q）
If（p->data<=q->data）{
s=p->next;
p->next=r->next;r->next=p;r=p;
p=s;
}
else{
s=q->next;
q->next=r->next;r->next=q;r=q;
q=s;
}
while（p）r->next=p;
while（q）r->next=q;
free（B）;
return（C）;
}
7．判断链表L是否为递增的。
分析：
要判断链表L从第二个元素开始的每个元素的值是否比其前驱的值大。
若不成立，则整个链表不是按序递增的，否则是递增的。
不妨设指针p指向L的一个结点，pre指向p的前驱结点。
算法描述如下：
Intisincrease（LinkListL）
{
LinkListpre；
Pre=L->next；
if（pre！
=NULL）
while（pre->next）
{p=pre->next；/*pre指向第一个结点*/
if（p->data>pre->data）
pre=p；/*工作指针后移，继续进行*/
else
return0；/*一旦发现某个后继元素值小于其前驱元素值，非递增返回*/
}
return1；
}
升级会员 