《算法与数据结构课后习题答案》由会员分享，可在线阅读，更多相关《算法与数据结构课后习题答案（117页珍藏版）》请在金锄头文库上搜索。
1、 第一章 绪论1.1 简述以下概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 数据：指能够被计算机识别、存储和加工处理的信息载体。 数据元素：就是数据的根本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由假设干数据项组成。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的 这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的 链接存储方法：它不要求逻辑上相邻的
2、结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。假设每个结点在索引表中都有一个索引项，那么该索引表称之为稠密索引Dense Index。假设一组结点在索引表中只对应一个索引项，那么该索引表称为稀疏索引。 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。1.4 设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1
3、.5+5000nlgn 请判断以下关系是否成立：(1) f(n)=O(g(n)(2) g(n)=O(f(n)(3) h(n)=O(n1.5)(4) h(n)=O(nlgn)分析：数学符号"O"的严格的数学定义：假设Tn和fn是定义在正整数集合上的两个函数，那么Tn=Ofn表示存在正的常数C和n0，使得当nn0时都满足0TnCfn。通俗地说，就是当n时，f(n)的函数值增长速度与Tn)的增长速度同阶。一般，一个函数的增长速度与该函数的最高次阶同阶。即：O(f(n)=nO(g(n)=n3O(h(n)=n1.5所以答案为：答：1成立。2成立。3成立。4不成立。 31.5 设有两个
4、算法在同一机器上运行，其执行时间分别为100n和2,要使前者快于后者，n至少要多大? 2n分析：要使前者快于后者，即前者的时间消耗低于后者，即：100n<2 2n 求解上式，可得答：n=151.6 设n为正整数，利用大"O"记号，将以下程序段的执行时间表示为n的函数。(1) i=1; k=0;while(i<n) k=k+10*i;i+;分析：i=1; /1k=0; /1while(i<n) /n k=k+10*i; /n-1i+; /n-1由以上列出的各语句的频度，可得该程序段的时间消耗：T(n)=1+1+n+(n-1)+(n-1)=3n可表示为T(n)
5、=O(n) (2) i=0; k=0;dok=k+10*i; i+;while(i<n);分析：i=0; /1k=0; /1do /nk=k+10*i; /n i+; /nwhile(i<n);/n由以上列出的各语句的频度，可得该程序段的时间消耗：T(n)=1+1+n+n+n+n=4n+2可表示为T(n)=O(n) (3) i=1; j=0;while(i+j<=n)if (i>j) j+;else i+;分析：通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，
6、所以该程序段的执行时间为：T(n)=O(n) (4)x=n; / n>1while (x>=(y+1)*(y+1)y+;分析：由x=n且x的值在程序中不变，又while的循环条件(x>=(y+1)*(y+1)可知：当(y+1)*(y+1)刚超过n的值时退出循环。由(y+1)*(y+1)<n得：y<n.5-1所以，该程序段的执行时间为：向下取整(n.5-1) (5) x=91; y=100;while(y>0)if(x>100) x=x-10;y-;else x+; 分析：x=91; /1y=100; /1while(y>0) /1101if(x&
7、gt;100) /1100 x=x-10; /100y-; /100elsex+; /1000以上程序段右侧列出了执行次数。该程序段的执行时间为：T(n)=O(1)1.7 算法的时间复杂度仅与问题的规模相关吗?答：算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。1.8 按增长率由小至大的顺序排列以下各函数： 2, (3/2)，(2/3)， n ,n , n! ，2 ，lgn ,n, n100nnn0.5nlgn(3/2)答：常根据以上分析按增长率由小至
8、大的顺序可排列如下：(2/3) < 2 < lgn < n < nn1000.5(3/2) < n < (3/2) < 2 < n! < n lgnnnn1.9 有时为了比拟两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大"O"记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示以下函数，并指出当n足够大时，哪一
9、个较优，哪一个较劣?函数 大"O"表示 优劣(1) T1(n)=5n-3n+60lgn 5n+O(n) 较差2222(2) T2(n)=3n+1000n+3lgn 3n+O(n) 其次(3) T3(n)=8n+3lgn 8n+O(lgn) 最差(4) T4(n)=1.5n+6000nlgn 1.5n+O(nlgn) 最优 2222 第二章 线性表2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答： 开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单
10、链表可以用头指针的名字来命名。头结点是在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不管链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化 大，难以估计其存储规模时，采用动态链表作为存储结构为好。2.基
11、于时间的考虑。假设线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 假设需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，假设链表的插入和删除主要发生在表的首尾两端，那么采用尾指针表示的单循环链表为宜。2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n那么所需移动的结点数越少。2.4 为什么在单循环链表中设置尾指针比设置
12、头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，那么开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。假设用头指针来表示该链表，那么查找终端结点的时间为O(n)。2.5 在单链表、双链表和单循环链表中，假设仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?假设可以，其时间复杂度各为多少? 答：下面分别讨论三种链表的情况。1. 单链表。假设指针p指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针
13、链找到*p结点后的结点。但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。2. 双链表。由于这样的链表提供双向指针，根据*p结点的前趋指针和后继指针可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。3. 单循环链表。根据结点位置，可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。2.6 下述算法的功能是什么? LinkList Demo(LinkList L) / L 是无头结点单链表ListNode *Q,*P;if(L&am
14、p;&L->next)Q=L;L=L->next;P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;return L;/ Demo 答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。2.7 设线性表的n个结点定义为(a0,a1,.an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList. 解：算法如下: #define ListSize 100 / 假定表空间大小为100typedef int DataType;/假定DataType的类型为int型typedef structDataType dataListSize;/ 向量data用于存放表结点int length; / 当前的表长度 Seqlist;/以上为定义表结构 void InsertList ( Seqlist *L, Datatype x, int i)/将新结点x插入L所指的顺序表的第i个结点ai的位置上，即插入的合法位置为：0<=i<=L->lengthint j;if ( i
