清华大学出版社数据结构(C++版)(第2版)课后习题答案最全整理

内容发布更新时间 : 2024/12/23 23:49:06星期一 下面是文章的全部内容请认真阅读。

⑾ 在一个单链表中,已知q所指结点是p所指结点的直接前驱,若在q和p之间插入s所指结点,则执行( )操作。

A s->next=p->next; p->next=s; B q->next=s; s->next=p; C p->next=s->next; s->next=p; D p->next=s; s->next=q; 【解答】B

【分析】注意此题是在q和p之间插入新结点,所以,不用考虑修改指针的顺序。

⑿ 在循环双链表的p所指结点后插入s所指结点的操作是( )。 A p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; C s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; D s->prior=p; s->next=p->next; p->next->prior=s; p->next=s 【解答】D

【分析】在链表中,对指针的修改必须保持线性表的逻辑关系,否则,将违背线性表的逻辑特征,图2-10给出备选答案C和D的图解。

3. 判断题

⑴ 线性表的逻辑顺序和存储顺序总是一致的。

【解答】错。顺序表的逻辑顺序和存储顺序一致,链表的逻辑顺序和存储顺序不一定一致。

⑵ 线性表的顺序存储结构优于链接存储结构。 【解答】错。两种存储结构各有优缺点。 ⑶ 设p,q是指针,若p=q,则*p=*q。

【解答】错。p=q只能表示p和q指向同一起始地址,而所指类型则不一定相同。

⑷ 线性结构的基本特征是:每个元素有且仅有一个直接前驱和一个直接后继。 【解答】错。每个元素最多只有一个直接前驱和一个直接后继,第一个元素没有前驱,最后一个元素没有后继。

⑸ 在单链表中,要取得某个元素,只要知道该元素所在结点的地址即可,因此单链表是随机存取结构。

【解答】错。要找到该结点的地址,必须从头指针开始查找,所以单链表是顺序存取结构。

4.请说明顺序表和单链表各有何优缺点,并分析下列情况下,采用何种存储结构更好些。

⑴ 若线性表的总长度基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素。

⑵ 如果n个线性表同时并存,并且在处理过程中各表的长度会动态发生变化。 ⑶ 描述一个城市的设计和规划。

【解答】顺序表的优点:① 无需为表示表中元素之间的逻辑关系而增加额外的存储空间;② 可以快速地存取表中任一位置的元素(即随机存取)。顺序表的

缺点:① 插入和删除操作需移动大量元素;② 表的容量难以确定;③ 造成存储空间的“碎片”。

单链表的优点:① 不必事先知道线性表的长度;② 插入和删除元素时只需修改指针,不用移动元素。单链表的缺点:① 指针的结构性开销;② 存取表中任意元素不方便,只能进行顺序存取。

⑴ 应选用顺序存储结构。因为顺序表是随机存取结构,单链表是顺序存取结构。本题很少进行插入和删除操作,所以空间变化不大,且需要快速存取,所以应选用顺序存储结构。

⑵ 应选用链接存储结构。链表容易实现表容量的扩充,适合表的长度动态发生变化。

⑶ 应选用链接存储结构。因为一个城市的设计和规划涉及活动很多,需要经常修改、扩充和删除各种信息,才能适应不断发展的需要。而顺序表的插入、删除的效率低,故不合适。

5.算法设计

⑴ 设计一个时间复杂度为O(n)的算法,实现将数组A[n]中所有元素循环右移k个位置。

【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。

分析算法,第一次调用Reverse函数的时间复杂度为O(k),第二次调用Reverse函数的时间复杂度为O(n-k),第三次调用Reverse函数的时间复杂度为O(n),所以,总的时间复杂度为O(n)。

⑵ 已知数组A[n]中的元素为整型,设计算法将其调整为左右两部分,左边所有元素为奇数,右边所有元素为偶数,并要求算法的时间复杂度为O(n)。 【解答】从数组的两端向中间比较,设置两个变量i和j,初始时i=0,j=n-1,若A[i]为偶数并且A[j]为奇数,则将A[i]与A[j]交换。具体算法如下:

分析算法,两层循环将数组扫描一遍,所以,时间复杂度为O(n)。 ⑶ 试编写在无头结点的单链表上实现线性表的插入操作的算法,并和带头结点的单链表上的插入操作的实现进行比较。 【解答】参见2.2.3。

⑷ 试分别以顺序表和单链表作存储结构,各写一实现线性表就地逆置的算法。

【解答】顺序表的逆置,即是将对称元素交换,设顺序表的长度为length,则将表中第i个元素与第length-i-1个元素相交换。具体算法如下:

单链表的逆置请参见2.2.4算法2-4和算法2-6。

⑸ 假设在长度大于1的循环链表中,即无头结点也无头指针,s为指向链表中某个结点的指针,试编写算法删除结点s的前趋结点。

【解答】利用单循环链表的特点,通过指针s可找到其前驱结点r以及r的前驱结点p,然后将结点r删除,如图2-11所示,具体算法如下:

⑹ 已知一单链表中的数据元素含有三类字符:字母、数字和其他字符。试编写算法,构造三个循环链表,使每个循环链表中只含同一类字符。 【解答】在单链表A中依次取元素,若取出的元素是字母,把它插入到字母链表B 中,若取出的元素是数字,则把它插入到数字链表D中,直到链表的尾部,这样表B,D,A中分别存放字母、数字和其他字符。具体算法如下:

⑺ 设单链表以非递减有序排列,设计算法实现在单链表中删去值相同的多余结点。

【解答】从头到尾扫描单链表,若当前结点的元素值与后继结点的元素值不相等,则指针后移;否则删除该后继结点。具体算法如下:

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4 ceshi