数据结构陈明习题答案

数据结构_陈明_习题答案第 1 页共 40 页习题一答案1填空题（1） 数据元素的有限集合，k 上关系的有限集合（2） 顺序存储（连续） ，链式存储（不连续）（3） 有穷性，确定性，可行性，输入，输出（4） 时间复杂度，空间复杂度3简述下列术语（1） 数据是信息的载体，它是描述客观事物的数、字符以及所有能输入到计算机中被计算机程序识别、加工处理的信息的集合。（2） 数据元素是数据的基本单位，是对一个客观实体的数据描述。一个数据元素可以由一个或若干个数据项组成。数据元素也被称为结点或记录。（3） 数据对象具有相同性质的数据元素的集合就是一个数据对象，它是数据的一个子集。（4） 数据结构数据结构就是数据之间的相互关系（即数据的组织形式）及在这些数据上定义的数据运算方法的集合。（5） 存储结构数据的存储结构是数据的逻辑结构在计算机内部的表示或实现，又称为数据的物理结构，它包括数据元素的表示和关系的表示。（6） 数据类型是具有相同性质的计算机数据的集合及定义在这个数据集合上的一组操作的总称。5常用的存储表示方法有哪几种？（1） 顺序存储方法该方法是将逻辑上相邻的结点存储在物理位置上也相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来表示（也就是说，只存储结点的值，不存储结点之间的关系） ，这种存储表示称为顺序存储结构。（2） 链式存储方法链式存储方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的关系由附加的指针来表示，指针指向结点的邻接结点，这样将所有结点串联在一起，称为链式存储结构。（3） 索引存储方法索引存储是在存储结点信息的同时，再建立一个附加的索引表，然后利用索引表中索引项的值来确定结点的实际存储单元地址。（4） 散列存储方法散列存储的基本思想是根据结点的关键字直接计算出结点的存储地址。7举例说明一下数据结构和算法的关系。通过公式： 程序=数据结构+算法 我们可以比较直观地看出二者的关系，即数据结构（包个完整的程序括逻辑结构和存储结构）的设计和算法的编写是程序设计的两个关键步骤，一就是由一套合理的数据结构和建立在该结构上的算法构成的。具体的说：在进行程序设计之前我们首先要为待处理的数据设计一个合理的逻辑结构，进而为之设计一种适合的存储结构，因为光有逻辑结构是不够的，只有存储结构才是与计算机语言直接相关的！有了这一套前期准备，我们才能在这个基础上设计算法，用一种计算机语言去处理这些数据，最终达到程序设计的目的。当然，随着逻辑结构和存储结构的不同，我们设计的算法也会有所差别，这在以后的学习中会体会到。下面通过一个简单的例子说明这种关系。假设我们要设计一个两个 n 阶方阵相乘的程序：已知两个 n 阶方阵 A 和 B，我们要计算它们的乘积，得到一个新的 n 阶方阵 C。那么在设计这个程序之前首先想到得就是设计一种逻辑结构表示方阵，这里我们用二维数组表示它们，因为二维数组最能直观地表示这种结构；有了逻辑结构了自然还要为之设计一种存储结构，这里我们选择顺序存储方法，因为 C 语言对这种存储结构给予了很好的支持，例如定义一个n 阶实型的二维数组 A 只要用 float Ann;这条语句就可以了，C 语言在内存种为之分配了一个n*n 长度的顺序存储空间（注意：C 语言默认二维数组是按行优先存储的） ，是不是很方便？有了这些准备，我们就可以设计算法进行计算了，其算法如下：void matrixmult ( float Ann, float Bnn, float Cnn )int i , j , k ;float x ;for ( i=0; i, , 画出这个逻辑结构的图示，并确定相对于 r 哪些结点是开始结点，哪些结点是终端结点？通过以后的学习我们会知道这是一个有向图，图中共有 9 个结点，其中开始结点有 2 个，分别为 K1和 K2；终端结点有 2 个，分别为 K6 和 K7。逻辑结构图表示如下：k4k2k1k6k5k7k3k8 k911何谓算法？试详述算法设计的目的和算法必须满足的条件。算法是对特定问题求解步骤的一种描述，实际上是指令的有限序列，其中每一条指令表示一个或多个操作。我们知道，程序设计的第一步是为待处理的数据设计一种合理的数据结构（包括逻辑结构和物理结构） ，这一步固然重要，但这不是我们的目的，设计数据结构的最终目的是为了在这个基础上编写算法进而对其进行相关的操作（例如：遍历，查找，排序，插入，删除等） ，如果不去编写相应的算法那么设计数据结构也就失去了它的意义，你所输入到计算机的数据永远都是“死数据” ，程序设计也就成了空谈！一句话：设计数据结构的目的是为了对它们进行处理，而数据处理正是通过相应的算法实现的！总的来说，一个算法应具有以下 5 个重要特性：第一，有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成；第二，确定性：算法中每条指令必须有确切的含义，读者理解时不会产生二意性。并且，在任何条件下，算法只有唯一的一条执行路径，即对相同的输入只能得到相同的输出；第三，可行性：一个算法是能行的，即算法中描述的操作都是通过已经实现的基本运算执行有限次来实现的；第四，输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合；第五，输出：一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。13编写一个算法，对三个两位数按由大到小的顺序进行排序，描述构造该算法的思维程。算法如下：void order(short a, short b, short c)short t;if (a 10,000）,哪个程序对运行时间有保证？A b. N 值较小（N N 时，算法终止，运行时间为 O（NloglogN） ，写出一个程序来执行 Eratosthenes 过滤法，并证实所声明的运行时间，区别 O（N）和 O（NlogN）的运行时间有多困难？程序略15.等式 A5 + B5 + C5 + D5 + E5 = F5，有一个满足 0 next=p-next-next;（3） Head-next= =Head（Head 为链表的头结点） ，Head= =NULL（Head 为链表的第一个结点）（4） Head-next=Head-next-next（Head 为链表的头结点） ；Head=Head-next（Head 为链表的第一个结点） ，以上均假设链表存在至少两个结点。（5） D（因为顺序表具有随即存取的优点）3动态与静态数据结构在计算机内存中的存储方式有何不同？各有何优缺点？参考答案：静态存储方式（顺序存储）逻辑相邻，物理相邻。优点：便于数据的随即存取，结点存储利用率高（不需要存储指针） ；缺点：存取数据时要移动大量的元素，由于事先不知道存储结点的最大个数，所以应该分配尽可能大的存储空间，从而可能会造成空间浪费！动态存储方式（链式存储）逻辑相邻，物理不一定相邻。优点：动态分配和释放存储单元，避免了空数据结构_陈明_习题答案第 5 页共 40 页间浪费，插入删除结点不需要移动大量的其他结点，只需要修改有限的指针变量；缺点：不具备顺序存储结构随即存取的优点，查找结点需要从表头开始，一个结点的存储利用率较低，以为每个结点都要存储一个指向下个结点的指针变量。5描述以下三个概念的区别：头指针、头结点、第一个结点。参考答案：头指针指向头结点的指针变量；头结点为了操作链表方便而设置的一个特殊的结点，该结点用于标示一个链表结构的存在，他不存储实在的数据；第一个结点链表中的第一个实际存储数据的结点，区别于头结点！在有头结点的链表中第一个结点应该是头结点后面的那个结点。7试写出一个计算线性链表 P 中结点个数的算法，其中指针 P 指向该表中第一个结点，尾结点的指针域为空。int count（datatype *p）/ *假设结点存储 datatype 型的数据 */int num=0;while（ p!=NULL）+num;p=p-next;return num;9何时选用顺序表、何时选用链表作为线性表的存储结构为宜?参考答案：这应该由两种存储结构自身的特点来决定，如果经常查找某个元素，应选择顺序存储结构，因为他有随机存取的优点，在事先知道存取元素数目的大致范围的情况下也可以优先考虑这种结构，因为每个结点不需要存储指针变量所以结点的存储密度较高，所以整个顺序表的存储利用率也比较高；如果经常插入删除结点元素，应该选择链式存储结构，因为他不需要移动大量的其他结点，只需要修改有限的指针变量即可，当然，如果事先不能够确定存储结点的最大数量也可以选择这种结构，因为它具有动态分配回收的机制，不会造成大量的空间闲置现象。以上的情况其实也不绝对，要具体情况具体分析。11在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?参考答案：在顺序表中插入删除一个结点平均需要移动大约一半的结点；具体的移动次数取决于插入或者删除结点的位置 i 和顺序表的长度 n 。13在单链表、双链表和单循环链表中，若仅知道指针 p 指向某结点，不知道头指针，能否将结点*p 从相应的链表中删去?若可以，其时间复杂度各为多少?参考答案：对于三种存贮结构在题设的条件下都可以达到删除接点*P 的目的，对于双链表和单循环链表删除接点*P 比较容易，不必细讲，前者的时间复杂度为 0（1） ，后者的时间复杂度为 O（n） （时间主要耗费在查找结点*P 的前驱结点上） ，对于单链表在题设的条件下达到目的需要用到交换技术，方法是交换结点*P 和它后继结点*（P-next）的值，然后删除*（P-next）即可！时间复杂度为 0（1） 。15假设 LA、LB 为两个递增有序的线性链表，试写出将这两个线性链表归并成一个线性链表 LC 的操作算法。/*注意，在主函数中已经对 LC 数组进行了初始化，长度等于 LA 和 LB 长度之和*/*假设数组 LA 和 LB 中存储着 datatype 类型的数据元素*/Void MergeList（datatype LA ,datatype LB ,datatype LC ）int i=0,j=0,k=0;int lenthOfLA=sizeof（LA）/sizeof（datatype ）;int lenthOfLB=sizeof（LB）/sizeof（datatype ）;while（inext;/*从链表的第一个结点开始查找*/while（p!=NULLp=p-next;if（ p!=NULL）/*找到要找的结点*/s=p;q-next=p-next; free（s）;/*删除结点*/elseprintf（“ 没有找到您要找的结点n” ）; （2） /*插入学生结点 node 算法, 假设 node 在主函数中已经创建*/void InsertNode （stuNode *head,stuNode *node）stuNode *p=head,*q;q=p;p=p-next; /*从链表的第一个结点开始查找*/if（ node-scorescore）node-next=p; q-next=node;/*将结点插入表头*/return;/*算法结束*/while（p!=NULLp=p-next;if（ p= =NULL）q-next=node; /*将结点插入链表的表尾*/else /*插入结点*/node-next=p;q-next=node;19某仓库中有一批零件，按其价格从低到高的顺序构成一个单链表存于计算机内，链表的每一个结点说明同样价格的若干个零件。现在又新有 m 个价格为 s 的零件需要进入仓库，试写出仓库零件链表增加零件的算法。链表结点结构如下：数据结构_陈明_习题答案第 7 页共 40 页算法提示：/*定义一个结点，每个结点表示一种零件的相关信息*/typedef struct NODEfloat price;/*该零件的价格*/unsigned long number;/*该零件的数量*/struct NODE*next;Node;/*在头结点为 head 的单链表中插入一个零件信息结点 node 的算法如下*/*假设该结点 node 已经在主函数中创建完毕*/void InsertNode（Node*head,Node*node）Node*p=head,*q;q=p;p=p-next; /*从链表的第一个结点开始查找*/if（ node-priceprice）node-next=p; q-next=node;/*将结点插入表头*/ruturn;/*算法结束*/while（p!=NULLp=p-next;if（ p= =NULL）q-next=node; /*将结点插入链表的表尾*/else /*插入结点*/node-next=p;q-next=node;21. 设指针 P 指向单链表的首结点，指针 X 指向单链表中的任意一个结点，写出在 X 前插入一个结点 i的算法。算法提示：/*假设该链表的头结点为 head，且链表中的结点用 Node 定义*/*在结点 X 之前插入结点 i 的算法如下*/void InsertNode（Node*head,Node*i,Node*X ）Node *p=head,*q;q=p;p=p-next;/*依照题意，p 指向链表的第一个结点*/if（ p= =X）/*将结点插入头结点和第一个结点之间 */i-next=p;q-next=i;return;/*算法结束*/while（p!=NULLp=p-next;if（ p= =NULL）return NULL;/*查找失败*/elsei-next=p;q-next=i;23设多项式 A 和 B 采用线性链表的存储方式存放，试写出两个多项式相加的算法，要求把相加结果存放在 A 中。算法提示：请参考本章算法 3.23 和算法 3.24。25设指针 a 和 b 分别为两个带头结点的单链表的头指针，编写实现从单连表 La 中删除自第 i 个数据数据结构_陈明_习题答案第 8 页共 40 页元素起，共 length 个数据元素、并把它们插入到单链表 Lb 中第 j 个元素之前的算法。算法提示：void DInsert（Node *a,Node *b,int i,int j,int length）Node*ap=a-next,*bp=b-next; /*定义了两个分别处理 La 和 Lb 的两个指针变量*/Node*ap1,*ap2,*ap3,*ap4; /*定义了用于处理 La 的 4 个指针变量*/Node*bp1,*bp2; /*定义了用于处理 Lb 的 2 个指针变量*/for（int k=1;knext;ap1=ap;ap2=ap1-next;ap=ap2;for（int k=1;knext;ap3=ap;ap4=ap3-next;ap1-next=ap4; /*将 La 中长度为 length 的子链脱链*/for（int k=1;knext;bp1=bp;bp2=bp1-next;ap3-next=bp2;bp1-next=ap2; /*将长度为 length 的子链挂接到 Lb 相应的位置*/27. 设 La 和 Lb 是两个有序的循环链表， Pa 和 Pb 分别指向两个表的表头结点，是写一个算法将这两个表归并为一个有序的循环链表。算法提示：本题可以换个角度考虑，因为对于循环链表考虑的因素较单链表多，所以我们可以将两个循环链表首先处理成两个单链表（方法：将链表的最后一个结点的 next 域设置为 NULL） ，这样问题就转化为将两个普通链表归并的问题，最后再把归并好的单链表转换成循环链表（方法：将链表的最后一个结点的next 域指向该链表的头结点） 。下面我们仅给出单链表归并的算法作为参考，具体的转换由于比较简单所以这里就不详述了：void MergeList（Node*pa,Node*pb）Node*pc=pa;Node*p1=pa-next,*p2=pb-next ;While（p1!=NULL pc=pc-next; p1=p1-next;elsepc-next=p2; pc=pc-next; p2=p2-next;if（ p1!=NULL） pc-next=p1;else pc-next=p2;29. 已知有一个单向循环链表，其每个结点中含三个域：pre、data 和 next，其中 data 为数据域，next 为指向后继结点的指针域，pre 也为一个指针域，但是他的值为空（null） ，试编写一个算法将此单链表改为双向循环链表，即使 pre 成为指向前驱结点的指针域。算法提示：/* 假设链表的头指针为 head，用 Node 来定义一个结点*/void Convert（Node*head）Node*p=head,*q;q=p;p=p-next;/*从链表的第一个结点开始处理*/while（p!=head）p-pre=q;q=p;p=p-next;p-pre=q;/*构成循环*/习题四答案数据结构_陈明_习题答案第 9 页共 40 页1选择题A B A B3本题较简单，可参考本章栈操作示意图的画法，答案略。5参考答案：栈和队列都是操作受限的线性表，因此二者都具备线性表的一般特性；对于栈，元素进栈出栈的原则是“后进先出” ，即 LIFO，对于队列，元素进出队列的原则是“先进先出” ，即 FIFO。7参考答案：对于要计算的表达式 3*（5-2）+7 ；9参考答案：1 和 4。11算法提示：利用栈的 LIFO 特性，如果是左括号则将其压入栈顶，然后读取下一个字符，如果仍然是左括号，再将其压入栈顶，依次类推，直到出现右括号为止，这时将最靠近栈顶的左括号弹出，它一定与该右括号相匹配。下面以圆括号为例给出算法：int match（）seqstack s;char ch;initstack（数据结构_陈明_习题答案第 10 页共 40 页if（ch= =(）push（else