发布时间 : 星期五 文章数据结构习题集（C语言版严蔚敏）第一二三章更新完毕开始阅读
2.5 画出执行下列各行语句后各指针及链表的示意图。
2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a. 在P结点后插入S结点的语句序列是__________________。 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;
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;
L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i<=4;i++){ }
P->next=NULL;
for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i);
P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1;
(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);
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);
2.9 简述以下算法的功能。
(1) Status A(LinkedList L) { //L是无表头结点的单链表
if(L && L->next) { }
Q=L;
L=L->next; P=L;
while(P->next) P=P->next; P->next=Q; Q->next=NULL;
} }
return OK;
(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);
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 } 2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 解： Status InsertOrderList(SqList &va,ElemType x) { } 2.12 设 //在非递减的顺序表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; va.length++; return OK; } //删除第一个元素 for(j=a.length;j>=i+1;j--) a.elem[j-i]=a.elem[j]; a.length--; return OK; A??a1,?,am?和B??b1,?,bn?均为顺序表，A?和B?分别为A和B中除去最大共同前 缀后的子表。若 A??B??空表，则A?B；若A?=空表，而B??空表，或者两者均不为空表，且A?的首元小于B?的首元，则 A?B；否则A?B。试写一个比较A，B大小的算法。 2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x); 2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。 2.15 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。 2.16 已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。 Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len) { } 2.17 试写一算法，在无头结点的动态单链表上实现线性表操作Insert(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。 2.18试写一算法，实现线性表操作Delete(L,i)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。 2.19 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。 2.20 同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。 2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表 if(i<0||j<0||len<0) return INFEASIBLE; p=la; k=1; while(k while(k q->next=s->next; q=q->next; k++; } ?a1,?,an?逆置为 ?an,?,a1?。 2.22 试写一算法，对单链表实现就地逆置。 2.23 设线性表 A??a1,a2,?,am?，B??b1,b2,?,bn?，试写一个按下列规则合并A，B为线性表