一,简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。
解答：
● 数据：指能够被计算机识别、存储和加工处理的信息载体。
● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。
● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。
● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。
● 逻辑结构：指数据元素之间的逻辑关系。
● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。
● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。
● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。
二,设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0;?
while(i<n)
{ k=k+10*i;i++;
}?
解析：
i=1; //1
k=0; //1
? while(i<n) //n
{ k=k+10*i; //n-1
i++; //n-1
}?
由以上列出的各语句的频度，可得该程序段的时间消耗：
T(n)=1+1+n+(n-1)+(n-1)=3n
可表示为T(n)=O(n)
(2) i=0; k=0;
do{
k=k+10*i; i++;?
}
while(i<n);?
解析：
i=0; //1
k=0; //1
do{ //n
k=k+10*i; //n
i++; //n
}
while(i<n);//n?
由以上列出的各语句的频度，可得该程序段的时间消耗：
T(n)=1+1+n+n+n+n=4n+2
可表示为T(n)=O(n)
(3) i=1; j=0;?
while(i+j<=n)?
{
if (i>j) j++;
else i++;
}
解析：
通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为：
T(n)=O(n)
(4)x=n; // n>1?
while (x>=(y+1)*(y+1))
y++;
解析：
由x=n且x的值在程序中不变，又while的循环条件(x>=(y+1)*(y+1))可知：当(y+1)*(y+1)刚超过n的值时退出循环。
由(y+1)*(y+1)<n得：y<n^0.5-1
所以，该程序段的执行时间为：
向下取整(n^0.5-1)
(5) x=91; y=100;?
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++;
解析：
x=91; //1
y=100; //1
while(y>0) //1101
if(x>100) //1100
{ x=x-10; //100
y--; //100
}
else?
x++; //1000
以上程序段右侧列出了执行次数。该程序段的执行时间为：
T(n)=O(1)
三,按增长率由小至大的顺序排列下列各函数：
2100,(3/2)n，(2/3)n,nn,n0.5,n!,2n,lgn,nlgn,n(3/2)
解答：
常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。
先将题中的函数分成如下几类：
常数阶：2100
对数阶：lgn
K次方阶：n0.5、n(3/2)
指数阶 (按指数由小到大排)：nlgn、(3/2)n、2n,n!,nn
注意：(2/3)^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。
根据以上分析按增长率由小至大的顺序可排列如下：
(2/3)n < 2100 < lgn < n0.5 < n(3/2) < nlgn < (3/2)n < 2n < n! < nn?
解答：
● 数据：指能够被计算机识别、存储和加工处理的信息载体。
● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。
● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。
● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。
● 逻辑结构：指数据元素之间的逻辑关系。
● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。
● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。
● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。
二,设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0;?
while(i<n)
{ k=k+10*i;i++;
}?
解析：
i=1; //1
k=0; //1
? while(i<n) //n
{ k=k+10*i; //n-1
i++; //n-1
}?
由以上列出的各语句的频度，可得该程序段的时间消耗：
T(n)=1+1+n+(n-1)+(n-1)=3n
可表示为T(n)=O(n)
(2) i=0; k=0;
do{
k=k+10*i; i++;?
}
while(i<n);?
解析：
i=0; //1
k=0; //1
do{ //n
k=k+10*i; //n
i++; //n
}
while(i<n);//n?
由以上列出的各语句的频度，可得该程序段的时间消耗：
T(n)=1+1+n+n+n+n=4n+2
可表示为T(n)=O(n)
(3) i=1; j=0;?
while(i+j<=n)?
{
if (i>j) j++;
else i++;
}
解析：
通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为：
T(n)=O(n)
(4)x=n; // n>1?
while (x>=(y+1)*(y+1))
y++;
解析：
由x=n且x的值在程序中不变，又while的循环条件(x>=(y+1)*(y+1))可知：当(y+1)*(y+1)刚超过n的值时退出循环。
由(y+1)*(y+1)<n得：y<n^0.5-1
所以，该程序段的执行时间为：
向下取整(n^0.5-1)
(5) x=91; y=100;?
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++;
解析：
x=91; //1
y=100; //1
while(y>0) //1101
if(x>100) //1100
{ x=x-10; //100
y--; //100
}
else?
x++; //1000
以上程序段右侧列出了执行次数。该程序段的执行时间为：
T(n)=O(1)
三,按增长率由小至大的顺序排列下列各函数：
2100,(3/2)n，(2/3)n,nn,n0.5,n!,2n,lgn,nlgn,n(3/2)
解答：
常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。
先将题中的函数分成如下几类：
常数阶：2100
对数阶：lgn
K次方阶：n0.5、n(3/2)
指数阶 (按指数由小到大排)：nlgn、(3/2)n、2n,n!,nn
注意：(2/3)^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。
根据以上分析按增长率由小至大的顺序可排列如下：
(2/3)n < 2100 < lgn < n0.5 < n(3/2) < nlgn < (3/2)n < 2n < n! < nn?
