1、一、选择题1. 算法的时间复杂度取决于(A )。A问题的规模 B. 待处理数据的初态 C. A和B2一个算法应该是( B )。 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C. 3. 下面关于算法说法错误的是( ABC )A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的4从逻辑上可以把数据结构分为(C )两大类。 A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构5在下面的程序段中,对x的赋值语句的频度为( C )FOR i:=1 TO n
2、DO FOR j:=1 TO n DO x:=x+1;A O(2n) BO(n) CO(n2) DO(log2n) 二、判断题1. 数据元素是数据的最小单位。(错,数据项是数据不可分割的最小单位。)2. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。 (错,逻辑结构中描述的是数据元素之间的逻辑关系。)3算法的优劣与算法描述语言无关,但与所用计算机有关。(错,同一个算法用不同的语言实现,或用不同的编译程序进行编译,或者在不同的计算机上运行时,效率均不同)4数据的物理结构是指数据在计算机内的实际存储形式。 (错,物理机构是指数据的逻辑结构在计算机存储器中的实现) 5. 数据结构的基本操作的设置的
3、最重要的准则是,实现应用程序与存储结构的独立。三、填空题1数据的物理结构包括 数据元素 的表示和 关系 的表示。2数据的逻辑结构是指数据集合中各数据元素之间所固有的逻辑关系。3一个数据结构在计算机中 存储关系 称为存储结构。4数据结构中评价算法的两个重要指标是 时间复杂度和空间复杂度 。5在下面的程序段中,对的赋值语句的频度为O(n)(表示为n的函数) FORi: TO nDOFORj:TO iDO FOR k:1TO jDO:delta;四、应用题1. 数据结构是一门研究什么内容的学科? 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科2. 数据元
4、素之间的关系在计算机中有几种表示方法?各有什么特点? 集合:机构中的数据元素之间除了“同属一个集合”的关系外,别无其他关系; 线性结构:结构中的数据元素之间存在一个对一个得关系;树形结构:结构中的数据元素之间存在一个对多个的关系;图状结构或网状结构:机构中的数据元素之间存在多个对多个的关系。3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处,抽象数据类型的主要特点是什么?使用抽象数据类型的主要好处是什么? 数据类型是一个值得集合和定义在这个值集上的一组操作的总称;抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。4. 回答问题(1)在数据结构课程中,数据的逻辑结构,数据的
5、存储结构及数据的运算之间存在着怎样的关系?算法设计,取决于选定的逻辑结构;算法实现,依赖于选取的存储结构。(2) 若逻辑结构相同但存储结构不同,则为不同的数据结构。这样的说法对吗?举例说明之。 对,如学生表,既可用顺序存储结构,又可用链式存储结构。(3) 在给定的逻辑结构及其存储表示上可以定义不同的运算集合,从而得到不同的数据结构 。这样说法对吗?举例说明之。对,如对全校学生进行学号查找,和对某个系进行学号查找,都用顺序存储结构,可是数据结构不同。 (4)评价各种不同数据结构的标准是什么?取决于该数据结构中数据元素及其之间关系的表示。5评价一个好的算法,您是从哪几方面来考虑的?答:正确性,可读性,健壮性,效率及低存储量需求这四个方面。