1、数据结构课后部分习题答案第 1 章 绪 论 1. 填空数据元素 数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 集合，线性结构，树结构，图结构 顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性自然语言，程序设计语言，流程图，伪代码，伪代码 问题规模 (1)，(nlog2n) 【分析】 用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。2. 选择题 C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一
2、个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。B【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。（6）A【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。（7）C 【分析】高效性是好算法应具备的特性。 （8）C，E 3. 判断题错。时间复杂度要通过算法中基本语句执行次数的数量级来确定。错。如数组就没有插入和删除操作。此题注意是每种数据结构。 错。是数据之间的逻辑关系的整体。 对。因此逻辑结构是数据组织的主要方面。错。基本操作的实现是基于某种存储结构设计的，因而不是唯一的。4.
3、 基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。 基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。 分析条件语句，每循环一次，i+j 整体加1，共循环n次，所以T(n)=O(n)。 设循环体共执行T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即： (T(n)+1)2n，所以T(n)=O(n1/2)。 x+是基本语句，所以 5（1）其逻辑结构图如图1-3所示，它是一种图结构。（2）整数的抽象数据类型定义如下： ADT integer Data 整数a：可以是正整数(1, 2, 3, )、负整数(-1, -2, -3, )和零Operation
4、 Constructor 前置条件：整数a不存在 输入：一个整数b 功能：构造一个与输入值相同的整数输出：无 后置条件：整数a具有输入的值 Set前置条件：存在一个整数a 输入：一个整数b 功能：修改整数a的值，使之与输入的整数值相同 输出：无 后置条件：整数a的值发生改变 Add 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相加 输出：相加后的结果 后置条件：整数a的值发生改变 Sub 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相减 输出：相减的结果 后置条件：整数a的值发生改变 Multi 前置条件：存在一个整数a 输入：一个整数b
5、 功能：将整数a与输入的整数b相乘 输出：相乘的结果 后置条件：整数a的值发生改变Div 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相除 输出：若整数b为零，则抛出除零异常，否则输出相除的结果 后置条件：整数a的值发生改变 Mod 前置条件：存在一个整数a 输入：一个整数b 功能：求当前整数与输入整数的模，即正的余数输出：若整数b为零，则抛出除零异常，否则输出取模的结果 后置条件：整数a的值发生改变 Equal 前置条件：存在一个整数a 输入：一个整数b 功能：判断整数a与输入的整数b是否相等 输出：若相等返回1，否则返回0 后置条件：整数a的值不发生改变 end
6、ADT （3）第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。6、【解答】下面是简单选择排序算法的伪代码描述。 下面是简单选择排序算法的C+描述。 分析算法，有两层嵌套的for循环，所以， 。算法的伪代码描述如下：算法的C+描述如下：分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。第 2 章 线性表 填空1. 表长的一半，表长，该元素在表中的位置 108 第5个元素的存储地址=第1个元素的存储地址(51)2=108 p-next=(p-next)-next为了运算方便 例如在插入和删除操作时不必对表头的情况进行特殊处
7、理。p-next=head 如图2-8所示。s-next =rear-next; rear-next =s; rear =s;q=rear-next-next; rear-next-next=q-next; delete q; 操作示意图如图2-9所示：(1)，(n) 在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为(n)。 循环链表，循环双链表，双链表2. 选择题【解答】A，B 【分析】参见2.2.1。【解答】D 【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连
8、续，也可以不连续，甚至可以零散分布在内存中任意位置。【解答】B 【解答】A 【解答】A 【分析】线性表中最常用的操作是取第i 个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。【解答】D 【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以，答案是D 。【解答】B 【分析】在链表中的最后一个结点之
9、后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。【解答】B 【分析】首先应顺序查找新结点在单链表中的位置。【解答】C 【分析】该算法需要将n个元素依次插入到有序单链表中，而插入每个元素需O(n)。【解答】B 【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。【解答】B 【分析】注意此题是在q和p之间插
10、入新结点，所以，不用考虑修改指针的顺序。【解答】D 【分析】在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背线性表的逻辑特征，图2-10给出备选答案C和D的图解。3. 判断题错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。错。两种存储结构各有优缺点。错。p=q只能表示p和q指向同一起始地址，而所指类型则不一定相同。错。每个元素最多只有一个直接前驱和一个直接后继，第一个元素没有前驱，最后一个元素没有后继。错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺序存取结构。4 【解答】顺序表的优点： 无需为表示表中元素之间的逻辑关系而增加额外的存储空间； 可
11、以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点： 插入和删除操作需移动大量元素； 表的容量难以确定； 造成存储空间的“碎片”。单链表的优点： 不必事先知道线性表的长度； 插入和删除元素时只需修改指针，不用移动元素。单链表的缺点： 指针的结构性开销； 存取表中任意元素不方便，只能进行顺序存取。 应选用顺序存储结构。因为顺序表是随机存取结构，单链表是顺序存取结构。本题很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。 应选用链接存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。 应选用链接存储结构。因为一个城市的设计和规划涉及活动很多，需要经
12、常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。5算法设计 算法思想请参见主教材第一章思想火花。下面给出具体算法。分析算法，第一次调用Reverse函数的时间复杂度为O(k)，第二次调用Reverse函数的时间复杂度为O(n-k)，第三次调用Reverse函数的时间复杂度为O(n)，所以，总的时间复杂度为O(n)。从数组的两端向中间比较，设置两个变量i和j，初始时i=0，j=n-1，若Ai为偶数并且Aj为奇数，则将Ai与Aj交换。分析算法，两层循环将数组扫描一遍，所以，时间复杂度为(n)。参见2.2.3。顺序表的逆置，即是将对称元素交换，设顺序表的长
13、度为length，则将表中第i个元素与第length-i-1个元素相交换。具体算法如下：单链表的逆置请参见2.2.4算法2-4和算法2-6。利用单循环链表的特点，通过指针s可找到其前驱结点r以及r的前驱结点p，然后将结点r删除，如图2-11所示，具体算法如下：在单链表A中依次取元素，若取出的元素是字母，把它插入到字母链表B 中，若取出的元素是数字，则把它插入到数字链表D中，直到链表的尾部，这样表B，D，A中分别存放字母、数字和其他字符。具体算法如下：从头到尾扫描单链表，若当前结点的元素值与后继结点的元素值不相等，则指针后移；否则删除该后继结点。具体算法如下： 设工作指针p和q分别指向循环双链表
14、的开始结点和终端结点，若结点p和结点q的数据域相等，则工作指针p后移，工作指针q前移，直到指针p和指针q指向同一结点（循环双链表中结点个数为奇数），或结点q成为结点p的前驱（循环双链表中结点个数为偶数）。如图2-12所示。第 3 章 特殊线性表栈、队列和串 1. 填空 设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5， 经过push，push，pop，push，pop，push，push后，输出序列是（ ），栈顶指针为（ ）。【解答】23，1003H顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top= -1和top=NULL，栈顶指针top等于数组的长度和内存无可
15、用空间栈 【分析】递归函数的调用和返回正好符合后进先出性。abc+*d-【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。后进先出，先进先出，对插入和删除操作限定的位置不同 假溢出（rear-front+n）% n 【分析】也可以是（rear-front）% n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。(1)，(n) 【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。2. 选择题（1
16、）C 【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。（2）D【分析】此时，输出序列一定是输入序列的逆序。B【分析】每个右括号与它前面的最后一个没有匹配的左括号配对，因此具有后进先出性。B 【分析】先进入打印缓冲区的文件先被打印，因此具有先进先出性。B【分析】队列的入队顺序和出队顺序总是一致的。D【分析】栈和队列的逻辑结构都是线性的，都有顺序存储和链接存储，有可能包含的运算不一样，但不是主要区别，任何数据结构在针对具体问题时包含的运算都可能不同。A 【分析】两栈共享空间首先两个栈是相向增长的，栈底应该分别指向两个栈中的第一个元素的位置
17、，并注意C+中的数组下标是从0开始的。（9）C 【分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的顺序也是e2、e4、e3、e6、e5、e1。3. 判断题【解答】错。应该有 种。【解答】对。只要操作满足后进先出性，都可以采用栈作为辅助数据结构。【解答】对。【解答】错。这是队空的判定条件，在循环队列中要将队空和队满的判定条件区别开。4. （1）【解答】不能，因为在C、E出栈的情况下，A一定在栈中，而且在B的下面，不可能先于B出栈。可以，设为进栈操作，为入栈操作，则其操作序列为IIIOOOIOIO。（2）假设有一个顺序队列，如图3-6所示，队尾指针rear=4，队头指针front=
18、1，如果再有元素入队，就会产生“上溢”，此时的“上溢”又称为“假溢出”，因为队列并不是真的溢出了，存储队列的数组中还有2个存储单元空闲，其下标分别为0和1。（3）栈顶元素为6，栈底元素为1。其执行过程如图3-7所示。（4）队头元素为5，队尾元素为9。其执行过程如图3-8所示。5、 算法设计出队操作是在循环链表的头部进行，相当于删除开始结点，而入队操作是在循环链表的尾部进行，相当于在终端结点之后插入一个结点。由于循环链表不带头结点，需要处理空表的特殊情况。入队算法如下：出队算法如下：操作步骤为： 将所有元素出栈并入队； 依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈； 将奇
19、数结点出栈并入队； 将偶数结点出队并入栈； 将所有元素出栈并入队； 将所有元素出队并入栈即为所求。第 4 章 广义线性表多维数组和广义表 1. 填空（3）存取，修改，顺序存储 【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。（4）1140【分析】数组A中每行共有6个元素，元素A1510的前面共存储了(15-10)6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。（5）d+41【分析】元素A85的前面共存储了(1+2+8)+5=41个元素。（6）三元组顺序表，十字链
20、表2. 选择题（2）D，E，K【分析】数组A为9行10列，共有90个元素，所以，存放A至少需要906=540个存储单元，第8列和第5行共有18个元素（注意行列有一个交叉元素），所以，共占108个字节，元素A85按行优先存储的起始地址为d+810+5=d+85，设元素Aij按列优先存储的起始地址与之相同，则d+j9+i=d+85，解此方程，得i=4，j=9。（3）B （4）C【分析】数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常没有插入和删除操作。（5）D【分析】在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。 （6）C
21、（7）D【分析】稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分布有规律，就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映象函数。3. 判断题【解答】错。例如二维数组可以看成是数据元素为线性表的线性表。【解答】对。因为三元组表除了存储非零元素值外，还需要存储其行号和列号。【解答】对。因为压缩存储后，非零元素的存储位置和行号、列号之间失去了确定的关系。4一个稀疏矩阵如图4-4所示，写出对应的三元组顺序表和十字链表存储表示。【解答】对应的三元组顺序表如图4-5所示，十字链表如图4-6所示。5、（2）【解答】在矩阵中逐行寻找该行中的最小值，然后对其所在的
22、列寻找最大值，如果该列上的最大值与该行上的最小值相等，则说明该元素是鞍点，将它所在行号和列号输出。具体算法如下：分析算法，外层for循环共执行n次，内层第一个for循环执行m次，第二个for循环最坏情况下执行n次，所以，最坏情况下的时间复杂度为(mn+n2)。第 5 章 树和二叉树1. 填空题有且仅有一个，互不相交度，孩子，双亲2i-1，(n+1)/2，(n-1)/2 【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。2h -1，2h-1【分析】最小
23、结点个数的情况是第1层有1个结点，其他层上都只有2个结点。2k-1【分析】在满二叉树中叶子结点的个数达到最多。50【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。12【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。CDBGFEA【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。2n，n-1，n+1 n，n-1【分析】n-1个分支结点是经过n-1次合并后得到的。2、选择题D D【分析】此题并没有指明是完全二叉树，则其深度最
24、多是n，最少是 +1。B【分析】此题注意是序列正好相反，则左斜树和右斜树均满足条件。C 【分析】线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为1。B，C 【分析】深度为k的完全二叉树最少结点数的情况应是第k层上只有1个结点，最多的情况是满二叉树，编号最小的叶子应该是在结点数最少的情况下，叶子结点的编号。D【分析】满二叉树中没有度为1的结点，所以有m个叶子结点，则度为2的结点个数为m-1。A【分析】三种遍历次序均是先左子树后右子树。 A，BD，A【分析】由森林转换的二叉树中，根结点即为第一棵树的根结点，根结点的左子树是由第一棵树中除了根结点以外其余结点组成的
25、，根结点的右子树是由森林中除第一棵树外其他树转换来的。 B3. 判断题错。某结点是否有前驱或后继的线索，取决于该结点的标志域是否为1。对。由前序遍历的操作定义可知。错。二叉树和树是两种不同的树结构，例如，左斜树是一棵二叉树，但它的度为1。对。因为根结点无兄弟结点。错。二叉树的顺序存储结构是按层序存储的，一般适合存储完全二叉树。4（1）因为在满二叉树中没有度为1的结点，所以有：n=n0+n2 设B为树中分枝数，则n=B+1所以B=n0 +n2-1再由二叉树性质：n0=n2+1代入上式有：B=n0+n0-1-1=2(n0-1)（2）【解答】证明采用归纳法。设二叉树的前序遍历序列为a1a2a3 an
26、，中序遍历序列为b1b2b3 bn。当n=1时，前序遍历序列为a1，中序遍历序列为b1，二叉树只有一个根结点，所以，a1= b1，可以唯一确定该二叉树；假设当n=k时，前序遍历序列a1a2a3 ak和中序遍历序列b1b2b3 bk可唯一确定该二叉树，下面证明当n=k+1时，前序遍历序列a1a2a3 akak+1和中序遍历序列b1b2b3 bk bk+1可唯一确定一棵二叉树。在前序遍历序列中第一个访问的一定是根结点，即二叉树的根结点是a1，在中序遍历序列中查找值为a1的结点，假设为bi，则a1=bi且b1b2 bi-1是对根结点a1的左子树进行中序遍历的结果，前序遍历序列a2a3 ai是对根结点
27、a1的左子树进行前序遍历的结果，由归纳假设，前序遍历序列a2a3 ai和中序遍历序列b1b2 bi-1唯一确定了根结点的左子树，同样可证前序遍历序列ai+1ai+2 ak+1和中序遍历序列bi+1bi+2 bk+1唯一确定了根结点的右子树。（3）【解答】设该树的总结点数为n，则n=n0+n1+n2+nm 又：n=分枝数+1=0n0+1n1+2n2+mnm+1由上述两式可得：n0= n2+2n3+(m-1)nm+1（4）二叉树的构造过程如图5-12 所示。（5）构造的哈夫曼树如图5-13所示。树的带权路径长度为：WPL=24+34+53+73+83+92+112=120（6）以各字符出现的次数作
28、为叶子结点的权值构造的哈夫曼编码树如图5-14所示。其带权路径长度=25+15+34+53+92+43+43+72=98，所以，该字符串的编码长度至少为98位。5算法设计本算法不是要打印每个结点的值，而是求出结点的个数。所以可将遍历算法中的“访问”操作改为“计数操作”，将结点的数目累加到一个全局变量中，每个结点累加一次即完成了结点个数的求解。具体算法如下：【解答】本算法的要求与前序遍历算法既有相同之处，又有不同之处。相同之处是打印次序均为前序，不同之处是此处不是打印每个结点的值，而是打印出其中的叶子结点，即为有条件打印。为此，将前序遍历算法中的访问操作改为条件打印即可。算法如下：【解答】当二叉
29、树为空时，深度为0；若二叉树不为空，深度应是其左右子树深度的最大值加1，而其左右子树深度的求解又可通过递归调用本算法来完成。具体算法如下：【解答】要想得到后序的逆序，只要按照后序遍历相反的顺序即可，即先访问根结点，再遍历根结点的右子树，最后遍历根结点的左子树。注意和前序遍历的区别，具体算法如下：【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲。具体算法如下：【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲，然后将结点x的双亲结点中指向结点x的指针置空。具体算法如下：【解答】按照题目要求，设置一个工作栈以完成对该树的非递归算法，思路如下： 每访问一个结点，将此结点
30、压栈，查看此结点是否有左子树，若有，访问左子树，重复执行该过程直到左子树为空。 从栈弹出一个结点，如果此结点有右子树，访问右子树执行步骤，否则重复执行步骤。具体算法如下：【解答】对二叉树进行后序遍历，在遍历过程中访问某结点时交换该结点的左右子树。具体算法如下：【解答】先在链表中进行遍历，在遍历过程中查找值等于x的结点，然后由此结点的最左孩子域firstchild找到值为x结点的第一个孩子，再沿右兄弟域rightsib找到值为x结点的第i个孩子并返回指向这个孩子的指针。树的孩子兄弟表示法中的结点结构定义如下：template struct TNode T data; TNode *firstchild, *rightsib; ; 具体算法如下：第 6 章 图 1. 填空题 0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 其自身邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表
