最新数据结构线性表答案Word文件下载.docx
《最新数据结构线性表答案Word文件下载.docx》由会员分享，可在线阅读，更多相关《最新数据结构线性表答案Word文件下载.docx（48页珍藏版）》请在冰点文库上搜索。
next=S;
（2）P->
next=P->
next->
（3）P->
next=S->
（4）S->
（5）S->
next=L;
（6）S->
（7）Q=P;
（8）while（P->
next!
=Q）P=P->
（9）while（P->
=NULL）P=P->
（10）P=Q;
（11）P=L;
（12）L=S;
（13）L=P;
a.（4）
（1）
b.（7）（11）（8）（4）
（1）
c.（5）（12）
d.（9）
（1）（6）
2.7已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a.删除P结点的直接后继结点的语句序列是____________________。
b.删除P结点的直接前驱结点的语句序列是____________________。
c.删除P结点的语句序列是____________________。
d.删除首元结点的语句序列是____________________。
e.删除尾元结点的语句序列是____________________。
（1）P=P->
next=P;
（4）P=P->
（5）while（P!
（6）while（Q->
=NULL）{P=Q;
Q=Q->
（7）while（P->
（10）Q=P;
（11）Q=P->
（12）P=L;
（13）L=L->
（14）free（Q）;
a.（11）（3）（14）
b.（10）（12）（8）（3）（14）
c.（10）（12）（7）（3）（14）
d.（12）（11）（3）（14）
e.（9）（11）（3）（14）
2.8已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。
a.在P结点后插入S结点的语句序列是_______________________。
b.在P结点前插入S结点的语句序列是_______________________。
c.删除P结点的直接后继结点的语句序列是_______________________。
d.删除P结点的直接前驱结点的语句序列是_______________________。
e.删除P结点的语句序列是_______________________。
priou=P->
priou->
priou;
（4）P->
priou=S;
priou=P;
（7）S->
（8）S->
（9）P->
（10）P->
（11）P->
（12）P->
（13）P->
（14）P->
（15）Q=P->
（16）Q=P->
（17）free（P）;
（18）free（Q）;
a.（7）（3）（6）（12）
b.（8）（4）（5）（13）
c.（15）
（1）（11）（18）
d.（16）
（2）（10）（18）
e.（14）（9）（17）
2.9简述以下算法的功能。
（1）StatusA（LinkedListL）{//L是无表头结点的单链表
if（L&
&
L->
next）{
Q=L;
L=L->
while（P->
next）P=P->
next=Q;
Q->
returnOK;
（2）voidBB（LNode*s,LNode*q）{
p=s;
while（p->
=q）p=p->
p->
next=s;
voidAA（LNode*pa,LNode*pb）{
//pa和pb分别指向单循环链表中的两个结点
BB（pa,pb）;
BB（pb,pa）;
（1）如果L的长度不小于2，将L的首元结点变成尾元结点。
（2）将单循环链表拆成两个单循环链表。
2.10指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。
StatusDeleteK（SqList&
a,inti,intk）
{
//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素
if（i<
1||k<
0||i+k>
a.length）returnINFEASIBLE;
//参数不合法
else{
for（count=1;
count<
k;
count++）{
//删除第一个元素
for（j=a.length;
j>
=i+1;
j--）a.elem[j-i]=a.elem[j];
a.length--;
}
//从顺序存储结构的线性表a中删除第i个元素起的k个元素
//注意i的编号从0开始
intj;
0||i>
a.length-1||k<
0||k>
a.length-i）returnINFEASIBLE;
for（j=0;
j<
=k;
j++）
a.elem[j+i]=a.elem[j+i+k];
a.length=a.length-k;
2.11设顺序表va中的数据元素递增有序。
试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
StatusInsertOrderList（SqList&
va,ElemTypex）
//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法
inti;
if（va.length==va.listsize）return（OVERFLOW）;
for（i=va.length;
0,x<
va.elem[i-1];
i--）
va.elem[i]=va.elem[i-1];
va.elem[i]=x;
va.length++;
2.12设
和
均为顺序表，
分别为
中除去最大共同前缀后的子表。
若
空表，则
；
=空表，而
空表，或者两者均不为空表，且
的首元小于
的首元，则
否则
。
试写一个比较
，
大小的算法。
StatusCompareOrderList（SqList&
A,SqList&
B）
inti,k,j;
k=A.length>
B.length?
A.length:
B.length;
for（i=0;
if（A.elem[i]>
B.elem[i]）j=1;
if（A.elem[i]<
B.elem[i]）j=-1;
if（A.length>
k）j=1;
if（B.length>
k）j=-1;
if（A.length==B.length）j=0;
returnj;
2.13试写一算法在带头结点的单链表结构上实现线性表操作Locate（L,x）;
intLocateElem_L（LinkList&
L,ElemTypex）
inti=0;
LinkListp=L;
while（p&
p->
data!
=x）{
p=p->
i++;
if（!
p）return0;
elsereturni;
2.14试写一算法在带头结点的单链表结构上实现线性表操作Length（L）。
//返回单链表的长度
intListLength_L（LinkList&
L）
if（p）p=p-next;
while（p）{
returni;
2.15已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。
试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。
请分析你的算法的时间复杂度。
voidMergeList_L（LinkList&
ha,LinkList&
hb,LinkList&
hc）
LinkListpa,pb;
pa=ha;
pb=hb;
while（pa->
next&
pb->
next）{
pa=pa->
pb=pb->
pa->
hc=hb;
while（pb->
next）pb=pb->
pb->
next=ha->
else{
hc=ha;
next）pa=pa->
pa->
next=hb->
2.16已知指针la和lb分别指向两个无头结点单链表中的首元结点。
下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。
试问此算法是否正确？
若有错，请改正之。
StatusDeleteAndInsertSub（LinkedListla,LinkedListlb,inti,intj,intlen）
0||j<
0||len<
0）returnINFEASIBLE;
p=la;
k=1;
while（k<
i）{p=p->
k++;
q=p;
=len）{q=q->
s=lb;
j）{s=s->
s->
next=p;
q->
next=s->
StatusDeleteAndInsertSub（LinkList&
la,LinkList&
lb,inti,intj,intlen）
LinkListp,q,s,prev=NULL;
intk=1;
//在la表中查找第i个结点
k<
i）{
prev=p;
p）returnINFEASIBLE;
//在la表中查找第i+len-1个结点
while（q&
len）{
q=p->
q）returnINFEASIBLE;
//完成删除，注意，i=1的情况需要特殊处理
prev）la=q->
elseprev->
next=q->
//将从la中删除的结点插入到lb中
if（j=1）{
next=lb;
lb=p;
while（s&
j-1）{
s=s->
s）returnINFEASIBLE;
//完成插入
2.17试写一算法，在无头结点的动态单链表上实现线性表操作Insert（L,i,b），并和在带头结点的动态单链表上实现相同操作的算法进行比较。
StatusInsert（LinkList&
L,inti,intb）//在无头结点链表L的第i个元素之前插入元素b
p=L;
q=（LinkList*）malloc（sizeof（LNode））;
q.data=b;
if（i==1）
q.next=p;
L=q;
//插入在链表头部
else
while（--i>
1）
p=p->
q->
next=p->
next=q;
//插入在第i个元素的位置
}//Insert
2.18试写一算法，实现线性表操作Delete（L,i），并和在带头结点的动态单链表上实现相同操作的算法进行比较。
StatusDelete（LinkList&
L,inti）//在无头结点链表L中删除第i个元素
if（i==1）
L=L->
//删除第一个元素
//删除第i个元素
}//Delete
2.19已知线性表中的元素以值递增有序排列，并以单链表作存储结构。
试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。
StatusListDelete_L（LinkList&
L,ElemTypemink,ElemTypemaxk）
LinkListp,q,prev=NULL;
if（mink>
maxk）returnERROR;
p=L;
data<
maxk）{
if（p->
=mink）{
prev->
free（q）;
2.20同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。
voidListDelete_LSameNode（LinkList&
LinkListp,q,prev;
if（p&
data==prev->
data）{
2.21试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表
逆置为
//顺序表的逆置
StatusListOppose_Sq（SqList&
ElemTypex;
L.length/2;
x=L.elem[i];
L.elem[i]=L.elem[L.length-1-i];
L.elem[L.length-1-i]=x;
2.22试写一算法，对单链表实现就地逆置。
//带头结点的单链表的逆置
StatusListOppose_L（LinkList&
LinkListp,q;
next=L->
2.23设线性表
，试写一个按下列规则合并A，B为线性表C的算法，即使得
当
时；
时。
线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。
注意：
单链表的长度值m和n均未显式存储。
//将合并后的结果放在C表中，并删除B表
StatusListMerge_L（LinkList&
A,LinkList&
B,LinkList&
C）
LinkListpa,pb,qa,qb;
pa=A->
pb=B->
C=A;
while（pa&
pb）{
qa=pa;
qb=pb;
qb->
next=qa->
qa->
next=qb;
pa）qb->
next=pb;
pb=B;
free（pb）;
2.24假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。
//将合并逆置后的结果放在C表中，并删除B表
StatusListMergeOppose_L（LinkList&
pa=A;
//保存pa的前驱指针
//保存pb的前驱指针
A->
if（pa->
next=A->
//将当前最小结点插入A表表头
next=qa;
while（pa）{
while（pb）{
2.25假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。
试对顺序表编写求C的算法。
//将A、B求交后的结果放在C表中
StatusListCross_Sq（SqList&
B,SqList&
inti=0,j=0,k=0;
while（i<
A.length&
j<
B.length）{
B.elem[j]）i++;
else
B.elem[j]）j++;
ListInsert_Sq（C,k,A.elem[i]）;
2.26要求同2.25题。
试对单链表编写求C的算法。
//将A、B求交后的结果放在C表中，并删除B表
StatusListCross_L（LinkList&
LinkListpa,pb,qa,qb,pt;
//
升级会员 