严蔚敏《数据结构》（清华C语言版·第2版）典型习题和考研真题
第2章 线性表
2.1 强化习题详解
1 填空题。
（1）在顺序表中插入或删除一个元素，需要平均移动______元素，具体移动的元素个数与______有关。
（2）顺序表中逻辑上相邻的元素的物理位置______紧邻。单链表中逻辑上相邻的元素的物理位置______紧邻。
（3）在单链表中，除了首元结点外，任一结点的存储位置由______指示。
（4）在单链表中设置头结点的作用是______。
答：
（1）表中一半；待插入或删除元素在表中的位置
（2）必定；不一定
（3）其前驱结点的指针域的值
（4）插入和删除首元结点时不用进行特殊处理
---
2 对以下单链表分别执行下列各程序段，并画出结果示意图。
（1）Q=P->next;
（2）L=P->next;
（3）R->data=P->data;
（4）R->data=P->next->data;
（5）P->next->next->next->data=P->data;
（6）T=P;
while(T!=NULL){ T->data=T->data*2; T=T->next; }
（7）T=P;
while(T->next!=NULL){ T->data=T->data*2; T=T->next; }
答：
结果示意图分别如图2-2～图2-8所示。
（1）Q=P->next;：Q指向P的下一个结点
（2）L=P->next;：L指向P的下一个结点
（3）R->data=P->data;：将P结点的数据赋值给R结点
（4）R->data=P->next->data;：将P的下一个结点的数据赋值给R结点
（5）P->next->next->next->data=P->data;：将P结点的数据赋值给P的下下下一个结点
（6）从P开始，将链表中每个结点的数据值乘以2
（7）从P开始，将链表中每个结点的数据值乘以2（直到最后一个结点）
---
3 画出执行下列各行语句后各指针及链表的示意图。
答：
根据所给程序，其链表结构变化如图2-9所示。各语句执行后，链表逐步插入新结点，指针L始终指向链表的第一个结点。
---
4 已知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;
答：
a．（4）（1）
b．（7）（11）（8）（4）（1）
c．（5）（12）
d．（9）（1）（6）
【注意】单链表中在某一结点前插入一个结点需要遍历该单链表，找到其前驱节点，再进行插入操作。
---
5 已知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->next!=NULL)P=P->next; （6）while(P->next->next!=Q)P=P->next; （7）while(P->next!=Q)P=P->next; （8）while(P->next->next!=NULL)P=P->next; （9）while(P->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）
---
6 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。
a．在P结点后插入S结点的语句序列是______。
b．在P结点前插入S结点的语句序列是______。
c．删除P结点的直接后继结点的语句序列是______。
d．删除P结点的直接前驱结点的语句序列是______。
e．删除P结点的语句序列是______。
（1）P->next=P->next->next; （2）P->prior=P->prior->prior; （3）P->next=S; （4）P->prior=S; （5）S->next=P; （6）S->prior=P; （7）S->next=P->next; （8）S->prior=P->prior; （9）P->prior->next=P->next; （10）P->prior->next=P; （11）P->next->prior=P; （12）P->next->prior=S; （13）P->prior->next=S; （14）P->next->prior=P->prior; （15）Q=P->next; （16）Q=P->prior; （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）
【注意】画示意图更有利于理解。
---
7 简述以下算法的功能。
答：
（1）L的长度大于1时，将L的首元结点变成尾元结点。
（2）将单循环链表拆成两个单循环链表。
---
8 指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。
答：
错误有两处：
（1）参数不合法及判别条件不完整。合法的入口参数为：(0 （2）内层for循环语句错误，元素前移的次序错误。 低效之处：每次只删除了一个元素。 --- 9 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 答： 算法思路：从表尾开始逐个比较元素值与x的大小，若元素值大于x，则将该元素后移一位，直到找到合适位置插入x。 --- 10 设A＝(a₁,…,aₘ)和B＝(b₁,…,bₙ)均为顺序表，试写一个比较A，B大小的算法。 答： 算法思路：依次比较A和B中对应位置的元素，若找到第一个不相等的元素，则根据其大小关系确定A与B的大小；若一个表已比较完而另一个表还有剩余元素，则短的表较小；若两表完全相等，则A=B。 --- 11 试写一算法在带头结点的单链表结构上实现线性表操作LOCATE(L，x)。 答： 算法思路：从首元结点开始依次遍历链表，将每个结点的数据域与x比较，若相等则返回该结点的位置序号；若遍历完整个链表未找到，则返回0。 --- 12 试写一算法在带头结点的单链表结构上实现线性表操作LENGTH(L)。 答： 算法思路：设置一个计数器，从首元结点开始遍历链表，每经过一个结点计数器加1，直到链表末尾，返回计数器的值。 --- 13 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。 答： 算法思路：比较m和n的大小，若m 时间复杂度为T(n)=O(n)。 --- 14 已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。 答： 不正确。错误在于未考虑i=1时la的头指针需要修改的情况，以及删除后链表可能为空的情况。改正时需要增加对首元结点删除的特殊处理。 --- 15 试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L，i，b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。 答： 无头结点时，若i=1需要特殊处理（修改头指针）；带头结点时，插入操作统一处理，不必单独考虑i=1的情况。头结点的作用是插入和删除操作时不必对首元结点做特殊处理。 --- 16 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素，同时释放被删结点空间。 答： 算法思路：先找到第一个值大于mink的结点（即待删区间的起点），再找到第一个值大于等于maxk的结点（即待删区间的终点），将中间的所有结点删除并释放空间。若mink>maxk则待删元素集为空集。 --- 17 同16题条件，试写一高效的算法，删除表中所有值相同的多余元素，同时释放被删结点空间。 答： 算法思路：用两个指针p和q，p指向当前保留的结点，q遍历p之后的结点，若q的值与p的值相同则删除q，否则p移到q的位置继续，直到遍历完整个链表。 --- 18 试写一算法，实现顺序表的就地逆置。 答： 算法思路：用两个指针i和j分别指向表的首尾元素，交换a[i]和a[j]的值，然后i向后移一位、j向前移一位，继续交换，直到i≥j。 --- 19 试写一算法，对单链表实现就地逆置。 答： 算法思路：将原链表中的头结点和第一个元素结点断开，先构成一个新的空表，然后将原链表中各结点从第一个结点起依次插入这个新表的头部。 --- 20 设线性表A和B，试写一个按规则合并A，B为线性表C的算法，使得当m≤n时C=(a₁,b₁,…,aₘ,bₘ,bₘ₊₁,…,bₙ)，当m>n时C=(a₁,b₁,…,aₙ,bₙ,aₙ₊₁,…,aₘ)。 答： 算法思路：用指针pa和pb分别遍历A表和B表，交替将结点链接到C表。当较短的链表遍历完后，将较长链表的剩余部分直接链接到C表尾部。 --- 21 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表的结点空间构造C表。 答： 算法思路：采用"指针平移，一次扫描"的策略。依次比较A和B中的当前结点，将值较小的结点采用头插法插入C表，直到其中一个表为空，再将另一表中剩余结点依次头插到C表。 --- 22 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合，现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素依值递增有序排列。试对顺序表编写求C的算法。 答： 算法思路：用两个指针i和j分别遍历A和B，若A[i] --- 23 要求同22题。试对单链表编写求C的算法。 答： 算法思路：用两个指针pa和pb分别遍历A和B链表，若pa->data --- 24 对22题的条件作以下两点修改，对顺序表重新编写求得表C的算法。 （1）假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同； （2）利用A表空间存放表C。 答： （1）算法思路：在求交集的基础上，当找到相同元素时，还需要跳过A和B中所有与该元素值相同的元素，确保C中元素值不重复。 （2）算法思路：利用A表的空间，用两个指针分别指向A表的读位置和写位置，遍历A和B求交集，将结果直接写入A表的前部位置。 --- 25 对22题的条件作以下两点修改，对单链表重新编写求得表C的算法。 （1）假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同； （2）利用原表（A表或B表）中的结点构成表C，并释放A表中的无用的结点空间。 答： （1）算法思路：类似24题（1），找到相同元素后跳过所有重复值，确保C中元素值唯一。 （2）算法思路：以B表为基础构建C表，遍历A和B，将交集元素保留在B表中，释放A表中无用的结点空间。 --- 26 已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法。 答： 算法思路：先从B和C中找出共有元素，记为same。在A中从当前位置开始，凡小于same的元素均保留（存到新的位置），等于same的就跳过，大于same时就再找下一个same。 --- 27 要求同26题。试对单链表编写算法，请释放A表中的无用结点空间。 答： 算法思路：类似26题的思路，先在B和C中找到共有元素，再遍历A表，删除A中等于这些共有元素的结点，并释放其空间。 --- 28 假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。 答： 算法思路：从s结点出发，遍历循环链表找到s的前驱的前驱结点p，则p->next即为s的前驱结点，删除p->next即可。 --- 29 已知有一个单向循环链表，其每个结点中含三个域：prior，data和next，其中prior的值为空，试编写算法将此单向循环链表改为双向循环链表。 答： 算法思路：遍历单向循环链表，对每个结点p，将其后继结点的prior域指向p，即p->next->prior=p，遍历一圈后所有结点的prior域均指向其前驱结点。 --- 30 已知由一个线性链表表示的线性表中含有三类字符的数据元素，试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。 答： 算法思路：遍历原链表，根据字符类型（字母、数字、其他）将结点分别插入到三个循环链表中，最后将原链表的头结点释放。 --- 31 假设在算法描述语言中引入指针的二元运算"异或"，可利用一个指针域来实现双向链表L。试写一算法按任一方向依次输出链表中各元素的值。 答： 算法思路：根据指定的方向，从L.Left或L.Right开始遍历。利用异或性质：当前结点的LRPtr域存放左邻与右邻指针的异或，已知前一结点地址p和当前结点地址q，则下一结点地址为p^q->LRPtr。 --- 32 采用31题所述的存储结构，写出在第i个结点之前插入一个结点的算法。 答： 算法思路：先遍历找到第i个结点及其前驱结点，然后利用异或运算修改相关结点的LRPtr域，将新结点插入其中。需要注意异或指针的更新顺序。 --- 33 采用31题所述的存储结构，写出删除第i个结点的算法。 答： 算法思路：先遍历找到第i个结点及其前驱和后继结点，然后利用异或运算修改前驱和后继结点的LRPtr域，最后释放被删除结点。 --- 34 设以带头结点的双向循环链表表示的线性表L=(a₁,a₂,…,aₙ)。试写一时间复杂度O(n)的算法，将L改造为L=(a₁,a₃,…,aₙ,…,a₄,a₂)。 答： 算法思路：从首元结点开始，将奇数位置的结点依次链接在一起，将偶数位置的结点依次链接在一起，然后将偶数位置的链表逆序后连接到奇数位置链表的末尾。