数据结构讨论小课堂和习题解答

《数据结构讨论小课堂和习题解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、讨论小课堂11.算法和程序的区别是什么呢？【参考答案】：算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。要设计一个好的

2、算法通常要考虑以下的要求。⑴正确。算法的执行结果应当满足预先规定的功能和性能要求。⑵可读。一个算法应当思路清晰、层次分明、简单明了、易读易懂。⑶健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。⑷高效。有效使用存储空间和有较高的时间效率。2，你认为应该如何评估一个数据结构或算法的有效性。【参考答案】：前提之一是算法的正确性；其二还必须考虑执行算法所耗费的时间和执行算法所耗费的空间（主要是只指辅助空间），以及算法是否易读、易编码和易于调试。3，讨论数据结构的重要性。【参考答案】：如今计算机的应用已深入到社会生活的各个领域，计算机处理的对象由单纯的数值发展到字符、图象、声音等，表示这些对

3、象的数据成分往往不是单一的，而是多成分且形成一定的结构　。因此,在程序设计中，除了应精心设计算法外，还应精心组织数据（包括原始数据、中间结果、最终结果），使之形成一定的组织形式（数据结构），以便让计算机尽可能高效率地处理。在实际程序设计的实践中，数据结构和算法是不同的但又是互相联系的两个方面。我们甚至还可以说，问题的算法往往取决于选定的数据结构。所以N.Wirth教授认为程序设计=算法+数据结构。我们已经初步地学习了高级语言（例如pascal）的程序设,掌握了一些程序设计方法与技巧。然而，这些方法与技巧对于现实的程序设计工作来说，是远远不够的。以下举几个例子加以说明。例1求真分数117/29的

4、值，求到小数点后50位例2求真分数7/27的值，精确到小数点后50位。　　　　1.输出117/29的值。　　　　2.a<－余数。b<－29　　　　3.aa*10。　　　　4.输出a/b的商。　　　　5.a<－余数。　　　　6.如未达要求，转3，否则结束。例3从键盘输入若干个数，并将其排序输出。相同的数，只输出一个。本例似乎不难，可以采取的策略之一：用一个数组来存放输入的数，然后排序输出。策略之二：边输入边排序。我们注意到：输出只能是不同的数，因而这是一个搜索加排序的问题。所以，不论采取那一种策略，用数组这一种结构不是最佳的结构，因为效率很低。事实上，若用二叉树作为存储结构，效率则会大大提高。例

5、4工作安排的可行性问题。为了直观了解工作环节之间的制约关系，通常用"有向图"来表示这种安排。　　　　　　习题11.抽象数据类型的定义由哪几部分组成？1.1【参考答案】：数据对象、数据关系和基本操作三部分。2.按数据元素之间的逻辑关系不同，数据结构有哪几类？1.2【参考答案】：线性结构、树型结构、图状结构和集合四类。3.你能举出几个你熟悉的"序列"的例子来吗？1.3【参考答案】：　如："0，1，2，…，9","A，B，C，…，Z"。4.简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。5.数据结构和数据类型两个概念之间有区别吗？1.5【参考答案】：简单地说，数据

6、结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。6.简述线性结构与非线性结构的不同点。1.6【参考答案】：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。7.有下列两段描述：（1）voidpro1()(2)voidpro2(){{n=2;y=0;While(n%2==0)x=5/y;n=n+2;printf(“%d,%d,x,y);printf(“%d”,n);}}这两段描述均不能满足算法的特征，试问它们违反了算法的那些特征？1.7【参考答案】：（1）是一个死循环，违反了算法的有穷性特征

7、。（2）出现除零错误，违反了算法的可行性特征。8.分析并写出下面的各语句组所代表的算法的时间复杂度。(1)for(i=0;i