文档介绍：严蔚敏-习题
--
2
--
习题1
一、单项选择题
A1. 数据结构是指（ ）。
C2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。
D3. 树形结构是数据元素之间存在一种（ ）。
B4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ ）。
for(i=1; i<=n; i++)
for(j=i; j<=n; j++)
x++;
(1) () (n) ()
CA5. 算法分析的目的是（1），算法分析的两个主要方面是（2）。
（1）
--
3
--
，后半句错 ，后半句对
10. 计算机内部数据处理的基本单位是（ ）。
二、填空题
1. 数据结构按逻辑结构可分为两大类，分别是____________ __和_________________。
2. 数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。
3. 线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。
4. 一个算法的效率可分为__________________效率和__________________效率。
5. 在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。
6. 在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。
--
5
--
7. 线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。
8. 下面程序段的时间复杂度是__________________。
for(i=0;i<n;i++)
for(j=0;j<n;j++)
A[i][j]=0;
9. 下面程序段的时间复杂度是__________________。
i=s=0;
while(s<n)
{ i++;
s+=i;
}
10. 下面程序段的时间复杂度是__________________。
s=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
s+=B[i][j];
sum=s;
11. 下面程序段的时间复杂度是__________________。
i=1;
while(i<=n)
i=i*3;
12. 衡量算法正确性的标准通常是____________________________________。
13. 算法时间复杂度的分析通常有两种方法，即___________和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。
--
5
--
三、求下列程序段的时间复杂度。
1. x=0;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
x++;
2. x=0;
for(i=1;i<n;i++)
for(j=1;j<=n-i;j++)
x++;
3. int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<=n;j++)
{ c[i][j]=0;
for(k=0;k<n;k++)
c[i][j]=a[i][k]*b[k][j]
}
4. i=n-1;
while((i>=0)&&A[i]!=k))
j--;
return (i);
5. fact(n)
{