数据结构及应用算法 课后复习题（附答案 严蔚敏版）(3)

b. 在P结点前插入S结点的语句序列是__________________。 c. 在表首插入S结点的语句序列是__________________。 d. 在表尾插入S结点的语句序列是__________________。 (1) P->next=S;

(2) P->next=P->next->next; (3) P->next=S->next; (4) S->next=P->next; (5) S->next=L; (6) S->next=NULL; (7) Q=P;

(8) while(P->next!=Q) P=P->next; (9) while(P->next!=NULL) P=P->next; (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; (2) P->next=P;

(3) P->next=P->next->next; (4) P=P->next->next;

(5) while(P!=NULL) P=P->next;

(6) while(Q->next!=NULL) { P=Q; Q=Q->next; } (7) while(P->next!=Q) P=P->next; (8) while(P->next->next!=Q) P=P->next; (9) while(P->next->next!=NULL) P=P->next; (10) Q=P; (11) Q=P->next; (12) P=L; (13) L=L->next; (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结点的语句序列是_______________________。 (1) P->next=P->next->next; (2) P->priou=P->priou->priou; (3) P->next=S; (4) P->priou=S; (5) S->next=P; (6) S->priou=P; (7) S->next=P->next; (8) S->priou=P->priou; (9) P->priou->next=P->next; (10) P->priou->next=P; (11) P->next->priou=P; (12) P->next->priou=S; (13) P->priou->next=S; (14) P->next->priou=P->priou; (15) Q=P->next; (16) Q=P->priou; (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) Status A(LinkedList L) { //L是无表头结点的单链表

}

if(L && L->next) { }

return OK;

Q=L;

L=L->next;

P=L;

while(P->next) P=P->next; P->next=Q;

Q->next=NULL;

(2) void BB(LNode *s, LNode *q) {

p=s;

while(p->next!=q) p=p->next; p->next =s;

}

void AA(LNode *pa, LNode *pb) { }

//pa和pb分别指向单循环链表中的两个结点 BB(pa,pb); BB(pb,pa);

解：(1) 如果L的长度不小于2，将L的首元结点变成尾元结点。

(2) 将单循环链表拆成两个单循环链表。

2.10 指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。

Status DeleteK(SqList &a,int i,int k) {

//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素 if(i<1||k<0||i+k>a.length) return INFEASIBLE;//参数不合法 else {

for(count=1;count

} 解：

Status DeleteK(SqList &a,int i,int k) { }

2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

解：

Status InsertOrderList(SqList &va,ElemType x) {

//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;

if(va.length==va.listsize)return(OVERFLOW); for(i=va.length;i>0,x

va.elem[i]=va.elem[i-1]; va.elem[i]=x;

//从顺序存储结构的线性表a中删除第i个元素起的k个元素 //注意i的编号从0开始 int j;

if(i<0||i>a.length-1||k<0||k>a.length-i) return INFEASIBLE; for(j=0;j<=k;j++)

a.elem[j+i]=a.elem[j+i+k];

}

//删除第一个元素

for(j=a.length;j>=i+1;j--) a.elem[j-i]=a.elem[j]; a.length--;

return OK;

a.length=a.length-k; return OK;

}

va.length++; return OK;

2.12 设A??a1,?,am?和B??b1,?,bn?均为顺序表，A?和B?分别为A和B中除去最大共同前缀后的子表。若A??B??空表，则A?B；若A?=空表，而B??空表，或者两者均不为空表，且A?的首元小于B?的首元，则A?B；否则A?B。试写一个比较A，B大小的算法。

解：

Status CompareOrderList(SqList &A,SqList &B) { }

2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x);

解：

int LocateElem_L(LinkList &L,ElemType x) { }

2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。

解：

//返回单链表的长度

int ListLength_L(LinkList &L) {

int i=0; LinkList p=L; if(p) p=p-next; while(p){

p=p->next; int i=0; LinkList p=L;

while(p&&p->data!=x){ }

if(!p) return 0; else return i;

p=p->next; i++; int i,k,j;

k=A.length>B.length?A.length:B.length; for(i=0;i

if(A.length>k) j=1; if(B.length>k) j=-1; if(A.length==B.length) j=0; return j;

if(A.elem[i]>B.elem[i]) j=1; if(A.elem[i]

}

}

i++;

return i;

2.15 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。

解：

void MergeList_L(LinkList &ha,LinkList &hb,LinkList &hc) { }

2.16 已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。

Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len) { } 解：

if(i<0||j<0||len<0) return INFEASIBLE; p=la;

k=1;

p=p->next;

k++; }

LinkList pa,pb; pa=ha; pb=hb;

while(pa->next&&pb->next){ }

if(!pa->next){ } else{ }

hc=ha;

while(pa->next) pa=pa->next; pa->next=hb->next; hc=hb;

while(pb->next) pb=pb->next; pb->next=ha->next; pa=pa->next; pb=pb->next;

while(k

while(k<=len){ s=lb; k=1; while(knext=p; return OK;

q=q->next; k++; }

s=s->next; k++; }

q->next=s->next;

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构及应用算法 课后复习题（附答案 严蔚敏版）(3)在线全文阅读。