单元1 同步训练及答案
一、选择题
1、数据的运算定义在数据的逻辑结构上，只有确定了（ ），才能具体实现这些运算。
A、数据对象
B、逻辑结构
C、存储结构
D、数据操作
2、数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括（ ）三方面内容。
A、数据的逻辑结构、数据的存储结构、数据的描述 B、数据的逻辑结构、数据的存储结构、数据的运算 C、数据的存储结构、数据的运算、数据的描述 D、数据的逻辑结构、数据的运算、数据的描述 3、数据的逻辑结构包括（ ）。 A、线性结构和非线性结构 C、非线性结构和集合结构
B、线性结构和树型结构 D、线性结构和图状结构
4、基本的逻辑结构包括（ ）。
A、树型结构、图状结构、线性结构和非线性结构 B、集合结构、线性结构、树型结构和非线性结构 C、集合结构、树型结构、图状结构和非线性结构 D、集合结构、线性结构、树型结构和图状结构 5、数据的存储方法主要包括（ ）。 A、顺序存储方法和链式存储方法 C、链式存储方法和结构存储方法
B、顺序存储方法和结构存储方法 D、索引存储方法和结构存储方法
6、算法是对特定问题求解步骤的一种描述，是一系列将输入转换为输出的计算步骤。其特性除了包含输入和输出外，还包括（ ）。
A、有穷性、正确性、可行性 C、有穷性、确定性、可行性 工作量就只依赖于（ ）。
A、计算机硬件 C、问题的规模
B、实现算法的语言 D、编译生成的目标代码的质量 B、算法易于理解 D、算法的时间复杂度
B、有穷性、正确性、确定性 D、正确性、确定性、可行性
7、如果将与计算机软硬件相关的因素确定下来，那么一个特定算法的运行
8、评价一个算法时间性能的主要标准是（ ）。 A、算法易于调试 C、算法的稳定性和正确性
9、下面程序段各语句执行次数之和为（ ）。
i=s=0; while (s i++; s++; } A、2n+1 B、3n+1 C、3n+2 D、3n+3 10、下面程序段执行的时间复杂度为（ ）。 for(i=1;i<=n;i++) for(j=1;j<=i;j++) s++; A、O(n) 二、解答题 1、简述下列概念：数据、数据元素、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 2、试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 3、常用的存储表示方法有哪几种? 4、设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立： (1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n1.5) (4) h(n)=O(nlgn) 5、设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大? 6、分析下面程序段执行的时间复杂度。 (1) i=1; k=0; while(i<=n-1) { k+=10*i; i++; } B、O(lgn) C、O(n2) D、O(n3) (2) i=0; k=0; do{ k=k+10*i; i++; }while(i if (i>j) j++; else i++; } 7、算法的时间复杂度仅与问题的规模相关吗? 8、按增长率由小至大的顺序排列下列各函数： nn，（2/3），nn，n，n!，2n，lgn，nlgn，n2。 2100，（3/2） 3参考答案 一、选择题 1、C 6、C 2、B 7、C 3、A 8、D 4、D 9、C 5、A 10、C 二、解答题 1、答： 数据：指能够被计算机识别、存储和加工处理的信息载体。 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容：数据的逻辑结构、存储结构和数据的运算。 逻辑结构：指数据元素之间的逻辑关系。 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前驱和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。