数据结构Ch2习题答案Word下载.docx
《数据结构Ch2习题答案Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构Ch2习题答案Word下载.docx（7页珍藏版）》请在冰点文库上搜索。
next=q。
10．线性表的顺序存储结构是用一组地址持续的存储单元依次存储各元素。
11．在双向链表中，每一个结点有两个指针域，一个指向前驱，另一个指向后继。
12．在一个单链表中的p所指结点以后插入一个s所指结点时，执行的操作为s->
next；
p->
next=s。
13．在一个单链表中的p所指结点之前插入一个s所指结点时，执行的操作为s->
next=s；
t=p->
data；
p->
data=s->
data=t。
（互换）
14．在一个单链中删除p所指结点时，应执行的操作是p->
data=p->
15．关于一个具有n个结点的单链表，在已知p所指结点以后插入一个新结点的时刻复杂度为O
（1）；
在给定值为x的结点后插入一个新结点的时刻复杂度为O（n）。
16．线性表的顺序存储中，元素之间的逻辑关系是通过相对位置决定的；
线性表的链接存储中，元素之间的逻辑关系是通过指针决定的。
17．在单链表中，每一个结点有1个指针域，最后一个结点的指针域为空。
18．关于一个线性表常常进行的是存取操作，很少进行插入和删除操作时，那么采纳顺序存储结构为宜；
相反，当常常进行的是插入和删除操作时，那么采纳链式存储结构为宜。
29．顺序表相关于链表的优势有容易实现和随机存取。
链表相关于顺序表的优势有不需要预分派存储空间和插入、删除操作方便。
二．选择：
1．下面关于线性表的表达错误的选项是D。
A．假设用数组表示，表中诸元素的存储位置是连在一路的
B．假设用链表表示，便于插入和删除操作
C．假设用链表表示，不需要占用一片相邻的存储空间
D．表的插入和删除操作仅许诺在表的一端运行
2．用带表头结点的链表表示线性表的要紧益处是B。
A．能够加速对表的遍历
B．使空表和非空表的处置统一
C．节省存储空间
D．能够提高存取元素的速度
3．线性表的顺序存储结构是一种A的存储结构。
A．随机存取
B．顺序存取
C．索引存取
D．HASH存取
4．在线性表的第i个元素之前入一个元素时，需将第n至第i个元素C位置。
A．向前移动一个
B．向前移动i个
C．向后移动一个
D．向后移动i个
5．在下面关于线性表的表达中，选出正确的一项D
A．线性表的每一个元素都有一个直接前驱和直接后继
B．线性表至少要有一个元素
C．线性表中的元素必需按递增或递减的顺序排列
D．除第一个元素和最后一个元素外，其余每一个元素都有一个且仅有一个直接前驱和直接后继
6．关于一个线性表假设既要求能够进行较快的插入和删除，又要求存储结构能反映数据元素间的逻辑关系，应该B
A．以顺序方式存储
B．以链接方式存储
C．以散列方式存储
D.以索引方式存储
7．以下描述线性表表达错误的选项是A
A．线性表的顺序存储的元素是从小到大顺序排列的
B．线性表的链接存储，便于插入删除操作
C．除第一个元素和最后一个元素外，其余每一个元素有且仅有一个直接前驱和直接后继
D．线性表能够为空
8．线性表的逻辑顺序与存储顺序老是一致的，这种说法B
A．正确B．不正确
9．与数据元素本身的形式、内容、相对位置、个数无关的是数据的C？
A．存储结构B．存储实现C．逻辑结构D．运算实现
10．顺序存储结构A
A．仅适合于静态查找表的存储
B．仅适合于动态查找表的存储
C．既适合静态又适合于动态查找表的存储
D．既不适合静态又不适合于动态查找表的存储
11．假设某线性表中最经常使用的操作是取第i个元素和找第i个元素的前趋元素，那么采纳A存储方式最节省时刻。
A．顺序表B．单链表C．双链表D．单循环链表
12．关于有个元素的顺序表，任意删除一个元素后，平均移动次数约为C
A．nB．lognC．n/2D．1
13．单链表的结点结构为{data,next}，下面算法要找出不带头节点的单链表中第i个元素的位置。
此算法是B
A．正确B．错误
LinklistGet（LinklistV,inti）
{p=V;
if（p==NULL）return（NULL）;
for（j=1;
j<
=i;
j++）综合
1．已知一个单链表如下图，编写一个函数将该单链表复制一个拷贝。
解：
此题的算法思想是依次查找该单链表（其头指针为head1）中的每一个节点，对每一个节点复制一个新节点并链接到新的单链表（其头指针为head2）中。
实现此题功能的函数如下：
voidcopy（LinkListhead1,LinkListhead2）
{LinkListp,q,new;
head2=（LinkList）malloc（sizeof（Node））;
/*成立一个头节点*/
p=head1;
q=head2;
while（p!
=NULL）
{new=LinkList）malloc（sizeof（Node））;
/*复制一个新节点new*/
new->
Data=p->
Data;
q->
Next=new;
/*将new链接到q以后*/
q=new;
p=p->
Next;
}
Next=NULL;
/*将最后一个节点的Next域置为NULL*/
p=head2;
/*删除头节点*/
head2-head2->
free（p）;
2．编写一个函数互换单链表中p所指向的位置和其后续位置上的两个节点，head指向该单链表的表头，p指向该单链表中的某一节点。
此题的算法思想是：
若是p存在后续节点，看它是不是是头节点，若是是，那么互换后要改变该链表的head，假设不是头节点，那么直接互换。
LinkListswap（LinkListhead,LinkListp）
{LinkListq,back;
q=p->
next;
if（q!
=NULL）/*假设p存在后续节点，那么进行相应处置*/
{
if（p==head）/*假设p指向头节点，那么将该链表的前两个节点互换位置*/
{p->
next=q->
q->
next=p;
head=q;
else/*假设p指向第二个以后的节点*/
{back=head;
/*查找p的前驱节点*/
while（back->
next!
=p）
back=back->
back->
next=q;
/*互换p和q的位置*/
next=q->
return（head）;
else
return（NULL）;
/*假设p不存在后续，那么返回NULL*/
3．有两个具有相同节点个数的单链表heada和headb如图所示，编写一个函数将其归并成如下图的单链表headc。
heada…
headb……
headc……
此题的算法思想是:
遍历两个单链表heada,headb,依次将两链表中的节点复制headc中，直到链表遍历完为止。
LinkListsum（LinkListheada,LinkListheadb）
LinkListheadc;
headc=（LinkList）malloc（sizeof（LNode））;
pa=heada;
pb=headb;
pc=headc;
while（pa!
{newnode=（LinkList）malloc（sizeof（Node））;
/*复制一个与heada链表中节点相同的节点，把它链接到headc中*/
newnode->
data=pa->
data;
pc->
next=newnode;
pa=pa->
pc=newnode;
/*pc始终指向headc链表的最后一个节点*/
new=（LinkList）malloc（sizeof（LNode））;
/*复制一个与headb链表中节点相同的节点，把它链接到headc中*/
data=pb->
pb=pb->
}
pc->
next=NULL;
newnode=headc;
headc=headc->
/*删除headc链表的头节点*/
free（newnode）;
4．有一单链表，其结点的元素值以非递减有序排列。
试编写删除该单链表中多余的元素值相同的结点的算法。
此题采纳的算法是：
从头至尾扫描该单链表，并作如此的操作：
假设当前元素节点的元素值与后续节点的元素值不相等，那么指针后移，不然删除该后续节点，直到扫描所有的节点。
voiddelete（LinkListhead）
{于开始结点的位置被寄存在头结点的指针域中，因此对链表第一个位置的操作同其他位置一样，不必特殊处置。
不管链表是不是为空，其头指针是指向头结点的非空指针，因此了，简化了链表操作的实现。
升级会员 