数据结构课后部分习题答案

第1章绪论1.填空⑴数据元素⑵数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。⑶集合，线性结构，树结构，图结构⑷顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹自然语言，程序设计语言，流程图，伪代码，伪代码⑺问题规模⑻Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。2.选择题⑴C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。⑵B【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。（6）A【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。（7）C【分析】高效性是好算法应具备的特性。（8）C，E3.判断题⑴错。时间复杂度要通过算法中基本语句执行次数的数量级来确定。⑵错。如数组就没有插入和删除操作。此题注意是每种数据结构。⑶错。是数据之间的逻辑关系的整体。⑷对。因此逻辑结构是数据组织的主要方面。⑸错。基本操作的实现是基于某种存储结构设计的，因而不是唯一的。4.⑴基本语句是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)2≤n，所以T(n)=O(n1/2)。⑸x++是基本语句，所以5．（1）其逻辑结构图如图1-3所示，它是一种图结构。（2）整数的抽象数据类型定义如下：ADTintegerData整数a：可以是正整数(1,2,3,…)、负整数(-1,-2,-3,…)和零OperationConstructor前置条件：整数a不存在输入：一个整数b功能：构造一个与输入值相同的整数输出：无后置条件：整数a具有输入的值Set前置条件：存在一个整数a输入：一个整数b功能：修改整数a的值，使之与输入的整数值相同输出：无后置条件：整数a的值发生改变Add前置条件：存在一个整数a输入：一个整数b功能：将整数a与输入的整数b相加输出：相加后的结果后置条件：整数a的值发生改变Sub前置条件：存在一个整数a输入：一个整数b功能：将整数a与输入的整数b相减输出：相减的结果后置条件：整数a的值发生改变Multi前置条件：存在一个整数a输入：一个整数b功能：将整数a与输入的整数b相乘输出：相乘的结果后置条件：整数a的值发生改变Div前置条件：存在一个整数a输入：一个整数b功能：将整数a与输入的整数b相除输出：若整数b为零，则抛出除零异常，否则输出相除的结果后置条件：整数a的值发生改变Mod前置条件：存在一个整数a输入：一个整数b功能：求当前整数与输入整数的模，即正的余数输出：若整数b为零，则抛出除零异常，否则输出取模的结果后置条件：整数a的值发生改变Equal前置条件：存在一个整数a输入：一个整数b功能：判断整数a与输入的整数b是否相等输出：若相等返回1，否则返回0后置条件：整数a的值不发生改变endADT（3）第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。6、⑴【解答】下面是简单选择排序算法的伪代码描述。下面是简单选择排序算法的C++描述。分析算法，有两层嵌套的for循环，所以，。⑵算法的伪代码描述如下：算法的C++描述如下：分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。第2章线性表填空1.⑴表长的一半，表长，该元素在表中的位置⑵108第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108⑶p-next=(p-next)-next⑷为了运算方便例如在插入和删除操作时不必对表头的情况进行特殊处理。⑸p-next=head如图2-8所示。⑹s-next=rear-next;rear-next=s;rear=s;q=rear-next-next;rear-next-next=q-next;deleteq;操作示意图如图2-9所示：⑺Ο(1)，Ο(n)在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。⑻循环链表，循环双链表，双链表2.选择题⑴【解答】A，B【分析】参见2.2.1。⑵【解答】D【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。⑶【解答】B⑷【解答】A⑸【解答】A【分析】线性表中最常用的操作是取第i个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。⑹【解答】D【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以，答案是D。⑺【解答】B【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。⑻【解答】B【分析】首先应顺序查找新结点在单链表中的位置。⑼【解答】C【分析】该算法需要将n个元素依次插入到有序单链表中，而插入每个元素需O(n)。⑽【解答】B【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。⑾【解答】B【分析】注意此题是在q和p之间插入新结点，所以，不用考虑修改指针的顺序。⑿【解答】D【分析】在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背线性表的逻辑特征，图2-10给出备选答案C和D的图解。3.判断题⑴错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。⑵错。两种存储结构各有优缺点。⑶错。p=q只能表示p和q指向同一起始地址，而所指类型则不一定相同。⑷错。每个元素最多只有一个直接前驱和一个直接后继，第一个元素没有前驱，最后一个元素没有后继。⑸错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺序存取结构。4．【解答】顺序表的优点：①无需为表示表中元素之间的逻辑关系而增加额外的存储空间；②可以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点：①插入和删除操作需移动大量元素；②表的容量难以确定；③造成存储空间的“碎片”。单链表的优点：①不必事先知道线性表的长度；②插入和删除元素时只需修改指针，不用移动元素。单链表的缺点：①指针的结构性开销；②存取表中任意元素不方便，只能进行顺序存取。⑴应选用顺序存储结构。因为顺序表是随机存取结构，单链表是顺序存取结构。本题很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。⑵应选用链接存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。⑶应选用链接存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。5．算法设计⑴算法思想请参见主教材第一章思想火花。下面给出具体算法。分析算法，第一次调用Reverse函数的时间复杂度为O(k)，第二次调用Reverse函数的时间复杂度为O(n-k)，第三次调用Reverse函数的时间复杂度为O(n)，所以，总的时间复杂度为O(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。⑸利用单循环链表的特点，通过指针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所示。第3章特殊线性表——栈、队列和串1.填空⑴设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5，经过push，push，pop，push，pop，push，push后，输出序列是（），栈顶指针为（）。【解答】23，1003H⑵顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top=-1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间⑶栈【分析】递归函数的调用和返回正好符合后进先出性。⑷abc+*d-【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。⑸后进先出，先进先出，对插入和删除操作限定的位置不同⑹假溢出⑺（rear-front+n）%n【分析】也可以是（rear-front）%n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。⑻Ｏ(1)，Ｏ(n)【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。2.选择题（1）C【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。（2）D【分析】此时，输出序列一定是输入序列的逆序。⑷B【分析】每个右括号与它前面的最后一个没有匹配的左括号配对，因此具有后进先出性。⑸B【分析】先进入打印缓冲区的文件先被打印，因此具有先进先出性。⑹B【分析】队列的入队顺序和出队顺序总是一致的。⑺D【分析】栈和队列的逻辑结构都是线性的，都有顺序存储和链接存储，有可能包含的运算不一样，但不是主要区别，任何数据结构在针对具体问题时包含的运算都可能不同。⑻A【分析】两栈共享空间首先两个栈是相向增长的，栈底应该分别指向两个栈中的第一个元素的位置，并注意C++中的数组下标是从0开始的。（9）C【分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的顺序也是e2、e4、e3、e6、e5、e1。3.判断题⑴【解答】错。应该有种。⑵【解答】对。只要操作满足后进先出性，都可以采用栈作为辅助数据结构。⑶【解答】对。⑷【解答】错。这是队空的判定条件，在循环队列中要将队空和队满的判定条件区别开。4.（1）【解答】⑴不能，因为在C、E出栈的情况下，A一定在栈中，而且在B的下面，不可能先于B出栈。⑵可以，设Ｉ为进栈操作，Ｏ为入栈操作，则其操作序列为I