习题

1.填空题

（1）数据结构所研究的内容包括数据的逻辑结构、数据的物理结构和数据的运算集合。存储结构（又称物理结构）是逻辑结构在_____，它包括_____和_____的表示。施加于_____之上的一组操作构成了数据的运算集合。

（2）数据类型是高级语言中的_____数据结构。

（3）算法的设计要求包括：正确性、可读性、健壮性和_____，可读性的含义是_____，健壮性是指_____。

（4）算法效率的度量应抛开具体机器的，对于一个特定算法只考虑算法本身的效率，而算法自身的执行效率是_____函数。

（5）一个算法的时间复杂度随问题的输入数据集的不同而不同，通常讨论_____情况下的时间复杂度。

（6）一个算法的语句频度表达式是5n*n*log2n+2n*n*n*log2n+1000*n*n*n*n，这个算法的时间复杂度是_____，另一个算法的语句频度表达式是40*n*n+2log2n+1000，这个算法的时间复杂度是_____。

（7）算法的时间复杂度与空间复杂度相比，通常以_____作为主要度量指标。

（8）在下面程序段中，s=s+p语句的频度为_____，p*=j语句的频度为_____，该程序段的时间复杂度为_____。

i=0,
s=0;
while (++i<=n)
{  p=1;
  for(j=1;j<=i;j++)
      p*=j;
  s=s+p;
}

2.判断题

（1）数据元素是数据的最小单位。

（2）算法可以用不同的语言描述，如果用类C语言或类Pascal语言等高级语言来描述，算法实际上就是程序了。

（3）存储结构既要存储数据元素本身又要表示数据元素之间的逻辑关系。

（4）数据结构是带有结构的数据元素的集合。

（5）数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据需要而建立的。

（6）数据结构在计算机中的映像（或表示）称为存储结构。

（7）算法的可读性的含义是：对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果。

（8）数据的物理结构是指数据在计算机内实际的存储形式。

（9）算法的时间复杂度是算法执行时间的绝对度量。

（10）算法的正确性是指算法不存在错误。

3.简答题

（1）简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构。

（2）设n为正整数，给出下列算法中原操作语句的语句频度及程序段的时间复杂度。

（a）i=1;

k=0;

while (i<=n-1)
{
     k=k+2*i;
     i++;
}

（b）i=1;k=0;

do
{
         k=k+2*i;
         i++;
}
while (i!=n)

（c）x=91;

n=100;
while (n>0)
     if (x>100 )
     {
         x=x-10;
         n=n-1;
     }
     else
x++;

（d）x=n;/* n>1 */

y=0;
while (x>=(y+1)*( y+1))
     y++;

（e）for(i=1;i<=n;i++)

for(i=1;i<=n;i++)
     for(j=i;j<=i;j++)
          for(k=j;k<=j;k++)
               x++;