数据结构课后习题答案第2章范文

链表的缺点：① 指针的结构性开销；② 存取表中任意元素不方便，只能进行顺序存取。

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

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

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

⑴ 设计一个时间复杂度为Ｏ(n)的算法，实现将数组A[n]中所有元素循环右移k个位置。 【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。

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

⑵ 已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为Ｏ(n)。

【解答】从数组的两端向中间比较，设置两个变量i和j，初始时i=0，j=n-1，若A[i]为偶数并且A[j]为奇数，则将A[i]与A[j]交换。具体算法如下：

分析算法，两层循环将数组扫描一遍，所以，时间复杂度为Ｏ(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中分别存放字母、数字和其他字符。具体算法如下：

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

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

⑻ 判断带头结点的双循环链表是否对称。

【解答】设工作指针p和q分别指向循环双链表的开始结点和终端结点，若结点p和结点q的数据域相等，

则工作指针p后移，工作指针q前移，直到指针p和指针q指向同一结点（循环双链表中结点个数为奇数），或结点q成为结点p的前驱（循环双链表中结点个数为偶数）。如图2-12所示。

学习自测及答案

1. 已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（ ）。 A 108 B 180 C 176 D 112 【解答】D

2．在长度为n的线性表中查找值为x的数据元素的时间复杂度为： （ ）。 A O(0) B O(1) C O(n) D O(n2) 【解答】C

3．在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（ ）个元素，删除第i（1≤i≤n）个元素时，需向前移动（ ）个元素。 【解答】n-i+1，n-i

4．在单链表中，除了头结点以外，任一结点的存储位置由（ ）指示。