数据结构单元 同步训练及答案.doc

单元1 同步训练及答案一、选择题1、数据的运算定义在数据的逻辑构造上，只有确定了   ，才能具体实现这些运算。A、数据对象B、逻辑构造C、存储构造D、数据操作2、数据构造指的是数据之间的相互关系，即数据的组织形式。数据构造一般包括   三方面内容。A、数据的逻辑构造、数据的存储构造、数据的描述 B、数据的逻辑构造、数据的存储构造、数据的运算 C、数据的存储构造、数据的运算、数据的描述 D、数据的逻辑构造、数据的运算、数据的描述 3、数据的逻辑构造包括   。A、线性构造和非线性构造B、线性构造和树型构造 C、非线性构造和集合构造D、线性构造和图状构造 4、根本的逻辑构造包括   。A、树型构造、图状构造、线性构造和非线性构造 B、集合构造、线性构造、树型构造和非线性构造 C、集合构造、树型构造、图状构造和非线性构造 D、集合构造、线性构造、树型构造和图状构造 5、数据的存储方法主要包括   。A、顺序存储方法和链式存储方法B、顺序存储方法和构造存储方法 C、链式存储方法和构造存储方法D、索引存储方法和构造存储方法6、算法是对特定问题求解步骤的一种描述，是一系列将输入转换为输出的计算步骤。其特性除了包含输入和输出外，还包括   。A、有穷性、正确性、可行性B、有穷性、正确性、确定性C、有穷性、确定性、可行性D、正确性、确定性、可行性7、如果将与计算机软硬件相关的因素确定下来，那么一个特定算法的运行工作量就只依赖于   。A、计算机硬件B、实现算法的语言 C、问题的规模D、编译生成的目标代码的质量8、评价一个算法时间性能的主要标准是   。A、算法易于调试B、算法易于理解 C、算法的稳定性和正确性D、算法的时间复杂度9、下面程序段各语句执行次数之和为   。i=s=0;while (s<n) i+;s+; A、2n+1B、3n+1C、3n+2D、3n+310、下面程序段执行的时间复杂度为   。for(i=1;i<=n;i+)for(j=1;j<=i;j+)s+;A、O(n) B、O(lgn) C、O(n2) D、O(n3) 二、解答题1、简述以下概念：数据、数据元素、数据构造、逻辑构造、存储构造、线性构造、非线性构造。2、试举一个数据构造的例子、表达其逻辑构造、存储构造、运算三个方面的内容。3、常用的存储表示方法有哪几种 4、设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n+5000nlgn 请判断以下关系是否成立：(1) f(n)=O(g(n) (2) g(n)=O(f(n) (3) h(n)=O(n)(4) h(n)=O(nlgn) 5、设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大6、分析下面程序段执行的时间复杂度。(1) i=1; k=0; while(i<=n-1) k+=10*i;i+;(2) i=0; k=0; dok=k+10*i;i+;  while(i<n);(3) i=1; j=0;  while(i+j<=n)  if (i>j) j+;else i+; 7、算法的时间复杂度仅与问题的规模相关吗 8、按增长率由小至大的顺序排列以下各函数： 参考答案一、选择题1、C2、B3、A4、D5、A6、C7、C8、D9、C10、C二、解答题1、答：数据：指能够被计算机识别、存储和加工处理的信息载体。数据元素：就是数据的根本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由假设干数据项组成。数据构造：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容：数据的逻辑构造、存储构造和数据的运算。逻辑构造：指数据元素之间的逻辑关系。存储构造：数据元素及其关系在计算机存储器内的表示，称为数据的存储构造。线性构造：数据逻辑构造中的一类。它的特征是假设构造为非空集，那么该构造有且只有一个开场结点和一个终端结点，并且所有结点都有且只有一个直接前驱和一个直接后继。线性表就是一个典型的线性构造。栈、队列、串等都是线性构造。非线性构造：数据逻辑构造中的另一大类，它的逻辑特征是一个结点可能有多个直接前驱和直接后继。数组、广义表、树和图等数据构造都是非线性构造。2、答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据构造。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开场结点它的前面无记录和一个终端结点它的后面无记录，其他的结点那么各有一个也只有一个直接前驱和直接后继它的前面和后面均有且只有一个记录。这几个关系就确定了这个表的逻辑构造是线性构造。这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢 即用一片连续的内存单元来存放这些记录如用数组表示还是随机存放各结点数据再用指针进展链接呢 这就是存储构造的问题。在这个表的某种存储构造根底上，可实现对这张表中的记录进展查询，修改，删除等操作。对这个表可以进展哪些操作以及如何实现这些操作就是数据的运算问题了。3、答：常用的存储表示方法有四种：顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来表达。由此得到的存储表示称为顺序存储构造，通常借助程序语言的数组描述。链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储构造,通常借助于程序语言的指针类型描述。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。假设每个结点在索引表中都有一个索引项，那么该索引表称之为稠密索引Dense Index。假设一组结点在索引表中只对应一个索引项，那么该索引表称为稀疏索引。散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。4、答：1成立。 2成立。3成立。4不成立。5、解：要使前者快于后者，即前者的时间消耗低于后者，即：100n2<2n，求解可得n=15。6、答：(1)各语句的执行频度分别为：1，1，n，(n-1)，(n-1)，可得该程序段的时间消耗：T(n)=1+1+n+(n-1)+(n-1)=3n，程序段执行的时间复杂度为T(n)=O(n)。(2)各语句的执行频度分别为：1，1，n，n，n，可得该程序段的时间消耗：T(n)=1+1+n+n+n+n=4n+2，程序段执行的时间复杂度为T(n)=O(n)。(3) 将i+j看成一个控制循环次数的变量，每执行一次循环，i+j的值加1，即j+和i+只能执行到一个，可将循环体看成一条语句。各语句的执行频度分别为：1，1，n+1，n，可得该程序段的时间消耗：T(n)=1+1+(n+1)+n=2n+3，程序段执行的时间复杂度为T(n)=O(n)。7、答：算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。8、答：常见的时间复杂度按数量级递增排列，依次为:常数阶O(1)、对数阶、线性阶O (n)、线性对数阶、平方阶、立方阶、k次方阶、指数阶。先将题中的函数分成如下几类：常数阶：对数阶：lgnK次方阶：、指数阶 (按指数由小到大排)：、 n!、 注意：由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。根据以上分析按增长率由小至大的顺序可排列如下：<< lgn<<<<<< n!<。