《数据结构课后习题答案总结》由会员分享，可在线阅读，更多相关《数据结构课后习题答案总结（5页珍藏版）》请在金锄头文库上搜索。
1、第一章第 1 章作业：1.1,1.2,1.6 (1) (3) 1.81.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 数据：指能够被计算机识别、存储和加工处理的信息载体。 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 逻辑结构：指数据元素之间
2、的逻辑关系。 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构. 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记
3、表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操
4、作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。1.6 设 n 为正整数，利用大O记号，将下列程序段的执行时间表示为 n 的函数。(1) i=1; k=0; while(ij) j+;else i+;分析：通过分析以上程序段，可将 i+j 看成一个控制循环次数的变量，且每执行一次循环，i+j 的值加 1。该程序段的主要时间消耗是 while 循环，而 while 循环共做了 n 次，所以该程序段的执行时间为：T(n)=O(n)1.8 按增长率由小至大的顺序排列下列各函数：2 100, (3/2)n，(2/3) n， n n ,n0.5 , n! ，2 n ，lgn ,n
5、lgn, n(3/2) 答：常见的时间复杂度按数量级递增排列,依次为:常数阶 0(1)、对数阶 0(log2n)、线性阶 0(n)、线性对数阶 0(nlog2n)、平方阶 0(n2)、立方阶 0(n3)、k 次方阶 0(nk)、指数阶 0(2n)。先将题中的函数分成如下几类：常数阶：2 100对数阶：lgnK 次方阶：n 0.5、n (3/2)指数阶 (按指数由小到大排)：n lgn、(3/2) n、2 n、 n!、 n n注意：(2/3) n由于底数小于 1，所以是一个递减函数，其数量级应小于常数阶。 根据以上分析按增长率由小至大的顺序可排列如下：(2/3) n next)Q=L;L=L-n
6、ext;P=L;while (P-next) P=P-next;P-next=Q; Q-next=NULL;return L;/ Demo答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。2.9 设顺序表 L 是一个递增有序表，试写一算法，将 x 插入 L 中，并使 L 仍是一个有序表。答：因已知顺序表 L 是递增有序表，所以只要从顺序表终端结点（设为 i 位置元素）开始向前寻找到第一个小于或等于 x 的元素位置 i 后插入该位置即可。在寻找过程中，由于大于 x 的元素都应放在 x 之后，所以可边寻找，边后移元素，当找
7、到第一个小于或等于 x 的元素位置 i 时，该位置也空出来了。算法如下：/顺序表存储结构如题 2.7void InsertIncreaseList( Seqlist *L , Datatype x ) int i;if ( L-length=ListSize)Error(“overflow);for ( i=L - length ; i0 i-)L-data i =L-data i ; / 比较并移动元素L-data i =x;L - length+;2.13 设 A 和 B 是两个单链表，其表中元素递增有序。试写一算法将 A 和 B 归并成一个按元素值递减有序的单链表 C，并要求辅助空间为
8、O(1)，请分析算法的时间复杂度。解：根据已知条件，A 和 B 是两个递增有序表，所以可以先取 A 表的表头建立空的 C 表。然后同时扫描 A 表和 B 表，将两表中最大的结点从对应表中摘下，并作为开始结点插入 C 表中。如此反复，直到 A 表或 B 表为空。最后将不为空的 A 表或 B 表中的结点依次摘下并作为开始结点插入 C 表中。这时，得到的 C 表就是由 A 表和 B 表归并成的一个按元素值递减有序的单链表C。并且辅助空间为 O(1)。算法如下：LinkList MergeSort ( LinkList A , LinkList B )/ 归并两个带头结点的递增有序表为一个带头结点递减
9、有序表ListNode *pa , *pb , *q , *C ;pa=A-next;/pa 指向 A 表开始结点C=A;C-next=NULL;/取 A 表的表头建立空的 C 表pb=B-next;/pb 指向 B 表开始结点free(B);/回收 B 表的头结点空间while ( pa & pb)if ( pb-data data ) / 当 B 中的元素小于等于 A 中当前元素时，将 pa 表的开始结点摘下q=pa;pa=pa-next;else/ 当 B 中的元素大于 A 中当前元素时，将 pb 表的开始结点摘下q=pb;pb=pb-next;q-next=C-next;C-next=
10、q;/将摘下的结点 q 作为开始结点插入 C 表/若 pa 表非空，则处理 pa 表while(pa)q=pa;pa=pa-next;q-next=C-next;C-next=q;/若 pb 表非空，则处理 pb 表while(pb)q=pb;pa=pb-next;q-next=C-next;C-next=q;return(C); 该算法的时间复杂度分析如下：算法中有三个 while 循环，其中第二个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。整个算法完成后，A 表和 B 表中的每个结点都被处理了一遍。所以若 A 表和 B 表的表长分别是 m 和 n，则该算法的时间复杂度
11、O(m+n)练习 2.1：写出在线性表中的查找运算算法。即查找数据元素 x 在表中的位置，也就是数据元素下标值加 1。例如：若 L.datai=x,则返回 i+1;若不存在，则返回 n+1练习 2.2：编写尾插法建立链表的算法。练习 2.3：若是带头指针的单链表，算法又是怎样？若是两个链表，既知道头结点，又知道尾结点，算法又是怎样？练习 2：按升序打印带头结点 h 的单链表中各节点的数据域值，并将打印完的节点从表中删除。第三章第 3 章作业：3.2, 3.3，3.4（2） ， 3.6， 3.113.2 循环队列的优点是什么? 如何判别它的空和满? 答：循环队列的优点是：它可以克服顺序队列的假上
12、溢现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。3.3 设长度为 n 的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?答：当只设头指针时，出队的时间为 1，而入队的时间需要 n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为 1。
13、因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。3.4 指出下述程序段的功能是什么? (2) SeqStack S1, S2, tmp;DataType x;./假设栈 tmp 和 S2 已做过初始化while ( ! StackEmpty (&S1)x=Pop(Push(while ( ! StackEmpty (&tmp) )x=Pop( Push( Push( (2)程序段的功能是利用 tmp 栈将一个非空栈 s1 的所有元素按原样复制到一个栈 s2 当中去。3.6 利用栈的基本操作，写一个将栈 S 中所有结点均删去的算法 void ClearStack( SeqStack *S)，并说明 S 为何要作为指针参数解：算法如下void ClearStack (SeqStack *S) / 删除栈中所有结点S-Top = -1; /其实只是将栈置空 因为要置空的是栈 S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。
