数据结构与算法（C语言） 第1章 习题答案.docx

《数据结构与算法（C语言） 第1章 习题答案.docx》由会员分享，可在线阅读，更多相关《数据结构与算法（C语言） 第1章 习题答案.docx（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题答案.填空题(1)数据(2)数据元素(3)数据项(4)数据对象(5)结构(6)逻辑结构、物理结构1 .选择题1) D (2) B (3) B (4) D (5) C (6) B3 .思考题(1)逻辑结构分为4种类型。线性结构中的数据元素之间是一对一的关系，即数据元素存在依次排列的先后次序关 系，且只有一个起始数据元素和一个终止数据元素。树形结构中的数据元素之间存在一对多的关系，即层次关系或分支关系。这种结构只 有一个起始数据元素(称为树根)，其他数据元素称为树叶。图形结构中的数据元素之间存在多对多的网络关系，即数据元素之间相互连接成网状。集合结构中的数据元素除了同属一个集合外，它们之间没有

2、其他关系。各个元素是“平等”的，该结构类似于数学中的集合。(2)物理结构即存储结构，主要指的是数据的逻辑结构在实际的计算机内存中存储的 形式。通常数据的存储结构有以下4种类型。顺序存储指的是将相邻的数据元素存放在计算机地址连续的存储单元中链式存储中，逻辑上相邻的数据元素在内存上不一定也相邻，简单地说，链式存储中 的数据元素存储在内存的任意位置。索引存储指的是在存储数据元素的同时建立索引列表，存储元素之间的关系。这是一 种为了加速检索而创立的存储结构。散列存储指的是根据数据元素的关键字直接计算出该数据元素的存储位置。(3)算法有5个基本的特性：输入、输出、有穷性、确定性、可行性。一个算法可以有多

3、个或没有输入，具体的输入量取决于算法中的数据对象。一个算法必须有一个或多个输出，这些输出是算法对输入进行运算后的结果。有穷性指的是算法在执行有限的操作次数后自动停止，不会出现无限循环的情况，且 每次操作都可以在有限时间内完成。确定性指的是算法的每次操作都具有确定的含义，不会出现二义性。可行性指的是算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。 简单地说，算法可以转换为程序上机运行，并可以得到正确的结果。(4)对于同一个问题，可以有很多种算法。因此，判断一个算法是否为最优算法，可 以从以下4个方面考虑。算法的正确性指的是算法能正确反映问题的需求，能经得起一切可输入数据的测试。可读

4、性指的是算法的设计应该尽可能简单，便于阅读、理解。健壮性指的是算法可以对不合法的输入数据做出处理，而不是产生异常或极端的结果。高效率指的是算法的执行时间要尽量短，对存储空间的使用要尽可能少。在满足前3 个要求的前提下，高效率是决定算法是否优劣的重要指标。(5)事后统计法指的是通过设计好的测试程序和数据，利用计算机本身对不同算法程 序的运行时间进行比拟，从而确定算法效率的高低。事前分析法指的是在设计算法程序前，根据统计方法对算法进行估算。一个好的算法 所消耗的时间，应该是算法中每条语句执行的时间之和，每条语句的执行时间是该语句的 执行次数与该语句执行一次所需时间的乘积。(6)如果有某个辅助函数f(n),并且存在一个正常数c使得f(n)*c=T(n)恒成立，记 作T(n)=O(f(n)。通常将O(f(n)称为算法的渐进时间复杂度，简称时间复杂度。使用0()计 算时间复杂度的记法称为大0记法。一般情况下，随着n的增大，T(n)增长最慢的算法为 最优算法。通过计算算法存储量可以得到算法的空间复杂度，算法空间复杂度的计算公式记作 S(n)=0(f(n),其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。随着问题规 模n的增大，算法运行所需存储量的增长率与f(n)的增长率相同。4.编程题(1)i=s=0； while(sn) i+； s+=i；