算法与数据结构练习一答案.doc

习题一一、选择题1、数据构造是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的B和运算的学科。 A构造 B关系 C运算 D算法2、在数据构造中，从逻辑上可以把数据构造分成C。 A动态构造和静态构造 B紧凑构造和非紧凑构造 C线性构造和非线性构造 D逻辑构造和存储构造3、线性表的逻辑顺序和存储顺序总是一致的，这种说法B。 A正确 B不正确 C无法确定 D以上答案都不对4、算法分析的目的是C。 A找出算法的合理性 B研究算法的输人与输出关系 C分析算法的有效性以求改良 D分析算法的易懂性二、填空题1、数据 是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，数据 是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。 2、数据元素是数据的根本单位，有些情况下也称为元素、结点、顶点、记录等。3、数据项是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为_数据项。 4、简而言之，数据构造是数据之间的相互关系，即数据的组织形式。 5、数据的逻辑构造是指数据之间的逻辑关系。逻辑构造是从逻辑关系上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑构造可以看作是从具体问题抽象出来的数学模型。 6、数据的存储构造指数据元素及其关系在计算机存储器内的表示。存储构造是逻辑构造在计算机里的实现，也称之为映像。 7、数据的运算是指对数据施加的操作。它定义在数据的逻辑构造之上，每种逻辑构造都有一个数据的运算。常用的有：查找、排序、插人、删除、更新等操作。 8、数据逻辑构造可以分为四种根本的类型，集合构造中的元素除了仅仅只是同属于一个集合_，不存在什么关系。 9、数据逻辑构造的四种根本类型中，线性构造_中的元素是一种一对一的关系，这种构造的特征是：假设构造是非空集，那么有且只有一个开场结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。 10、数据逻辑构造的四种根本类型中，树形构造中的元素是一种一对多的关系。 11、图型构造或图状构造是一种多对多的关系。在这种逻辑构造中，所有结点均可以有多个前驱和多个后继。 12、有时也可将树型构造、集合和图型构造称为非线性构造，这样数据的逻辑构造就可以分为线性构造和非线性构造两大类。 13、顺序存储方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储构造只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。 14、链接存储方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。 15、 16、散列存储方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。 17、所谓算法Algorithm是对特定问题求解方法和步骤的一种描述，它是指令的一组有限序列，其中每个指令表示一个或多个操作。18、算法的有穷_性是指算法必须能够在执行有限个步骤之后完毕，并且每个步骤都必须在有穷的时间内完成。 19、算法确实定性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是一样的就只能得到一样的输出结果。 20、算法的可行性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的根本运算执行有限_次来实现，即算法的具体实现应该能够被计算机执行。 21、判断一个算法的好坏主要以下几个标准：正确性，可读性_、强健性、效率。 22、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机运行时间的长短和所占据空间的大小。 23、空间复杂度SPace ComPlexity也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用存储空间的大小。三、判断题 1、顺序存储方式只能用于存储线性构造。×树型构造也可以用顺序方式进展存储。 2、数据元素是数据的最小单位。×数据元素是数据的根本单位，数据项是数据的最小单位。 3、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言描述，那么算法实际上就是程序了。×算法用各种计算机语言描述表现为一个程序，但是不等于程序，程序逻辑不一定能满足有穷性。 4、数据构造是带有构造的数据元素的集合。对5、数据的逻辑构造是指各元素之间的逻辑关系，是用户根据需要而建立的。对 6、数据构造、数据元素、数据项在计算机中的映像分别称为存储构造、结点、数据域。对 7、数据的物理构造是指数据在计算机中实际的存储形式。对 8、具有存取任一元素的时间相等这一特点的存储构造称为随机存取构造。对四、综合题 1、用大O形式表示下面算法的时间复杂度： fori=0；im；i十十 forj=0；jn；j Aij=i*j； O(m×n)。 2、写出下面算法的时间复杂度： i0； s=0； while(sn i+; s+=i; O() 3、写出以下算法的时间复杂度： fori0; im; iforj0 ; jt; j cij=0；fori=0；im；i forj=o; j<t; j+ fork=0；kn；k cijaik*bkj; O(m×n×t)。4、写出下面算法的时间复杂度：i=1;whilein i=i*3; log3(n)。5、求下面函数中各条语句的频度和算法的时间复杂度：primeint n int i2； while (ni！=0isqrt(n) ) i+; ifisqrt(n) ) printfd is a prime number.n，n； else printfd is not a prime number.n，n； O()