数据结构与算法 习题与练习答案

《数据结构与算法 习题与练习答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、附录习题与练习解答第1章习题与练习解答一、选择题答案1～7：BCCBBDC二、基本知识题答案1．名词解释答案数据：一切能够由计算机接受和处理的对象。数据项：数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。数据元素：数据的基本单位，在程序中作为一个整体加以考虑和处理，也称为元素、顶点或记录。它可以由若干个数据项组成。数据结构：数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。数据逻辑结构：数据元素之间的逻辑关系，是从逻辑上描述数据，与数据的存储无关，独立于计算机。数据物理结构：数

2、据元素及其关系在计算机存储器内的表示，是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言的。算法：对特定问题求解步骤的一种描述。它是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算。由此问题相关的一定输入，计算机依照这些规则进行计算和处理，经过有限的计算步骤后能得到一定的输出。算法的时间复杂性：是该算法的时间耗费，它是该算法所求解问题规模n的函数。当n趋向无穷大时，我们把时间复杂性T(n)的数量级称为算法的渐进时间复杂性。2．答：对算法进行分析的目的有两个。第1个目的是可以从解决同一问题的不同算法中区分相对优劣，选出较为适用

3、的一种。第2个目的是有助于设计人员考虑对现有算法进行改进或设计出新的算法。3．答：算法的最坏时间复杂性是研究各种输入中运算最慢的一种情况下的运算时间；平均时间复杂性是研究同样的n值时各种可能的输入，取它们运算时间的平均值。4．答：评价好的算法有4个方面。一是算法的正确性；二是算法的易读性；三是算法的健壮性；四是算法的时空效率(运行)。5．答：对算法A1和A2的时间复杂度T1和T2取对数，得nlog2和2logn。显然，算法A2好于算法A1。三、答案1．答：该程序段的时间复杂性为T(n)=O(n)。2．答：该程序段的时间复杂性T(n)=O(lo

4、g10n)。附录习题与练习解答23．答：该程序段的时间复杂性T(n)=O(n)。4．答：该程序段的时间复杂性为T(n)=O(n)。第2章习题与练习解答一、选择题答案1～5：ABBBC6～10：ADCBB二、基本知识题答案1．答：链式存储结构克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只需修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。2．答：采用链式存储结构，它根据实际需要申请内存空间

5、，而当不需要时又可将不用节点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。3．答：顺序表用节点物理位置的相邻性来反映节点间的逻辑关系，其优点：节省存储、随机存取，当表长变化较小、主要操作是进行查找时，宜采用顺序表。链表用附加的指针来反映节点间的逻辑关系，插入和删除操作相对比较方便，当表长变化较大，主要操作是进行插入和删除时，宜采用链表。4．答：双链表比单链表多增加了一个指针域以指向节点的直接前趋，它是一种对称结构，因此在已知某个节点之前或之后插入一个新节点、删除该节点或其直接后继都同样方便，操作的时间复杂度为O(1)；而单链表

6、是单向结构，对于找一个节点的直接前趋的操作要从开始节点找起，其时间复杂度为O(n)。5．答：由于对表的操作常常在表的两端进行，所以对单循环链表，当知道尾指针rear后，其另一端的头指针是rear->next->next(表中带头节点)。这会使操作变得更加容易。6．答：s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;7．答：s->next=p->next;p->next=s;temp=p->data;p->data=s->data;s->data=temp;8．答：多项式A(x)用链表

7、表示如下：headA411981138170∧三、算法设计题答案1.解：将该线性表逆序可以通过将A[0]与A[n-1]、A[1]与A[n-2]…两两交换来完成。注意互相交换的A[i]与A[j]的数组下标的关系i+j=n-1，i从0到n/2-1变化。实现本题功能的函数如下：voidReverse(intA[],intn){inti,j,temp;for(i=0;i<=n/2-1;i++){j=n-1-i;·259·数据结构与算法temp=A[i];A[i]=A[j];A[j]=temp;}}2.解：依次遍历A中的元素，比较当前的元素值，大于0者

8、赋给B，小于或等于0者赋给C。voidSqlit(SeqListA,SeqList&B,SeqList&C){inti,j=0,k=0;for(i=0;i