数据结构单元1同步训练及答案.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+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) 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)=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++;
}
(2) i=0; k=0;
　 do{
k=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、C 2、B 3、A 4、D 5、A
6、C 7、C 8、D 9、C 10、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次方阶、指数阶。
先将题中的函数分成如下几类：
常数阶：
对数阶：lgn
K次方阶：、
指数阶 (按指数由小到大排)：、、、 n!、
注意：由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。
根据以上分析按增长率由小至大的顺序可排列如下：
<< lgn<<<<<< n!<。