数据结构-绪论篇：思维导图（基于教材）错题复盘+计算题（基于习题解析）1.思维导图2.错题复盘+计算题2.1 某算法的语句执行频度为(3n+nlog2n+n^2+8)，其时间复杂度为（C）A.O(n) B.O(nlog2n) C.O(n^2) D.O(log2n)解析：这题考的是时间复杂度计算，分析算法时间复杂度的基本方法为：找出所有语句中语句频度最大的那条语句作为基本语句，而根据定理简化算法：在计算时间复杂度时，可忽略所有低次幂项和最高次幂项的系数。可得语句频度最大的是C2.2 以下程序段中语句"x++"的语句频度为（D）for (i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++;
A.(n(n+1)(2n+1))/2B.(n(n+1)(n+1))/2C.(n(n+1)(2n+1))/6D.(n(n+1)(n+2))/6解析：从程序段中不难发现，这条语句频度与各层循环变量取值有关，计算过程如下2.3 以下程序段中语句"m++"的语句频度为（A）int m=0,i,j;
for(i=1;i<=n;i++)
for(j=1;j<=2*i;j++)
m++;
A.n(n+1) B.n C.n+1 D.n^2解析：原理跟上题一样，根据程序段改j的上限再计算即可2.4 设一组数组中有n个数组元素，则读取第i个数组元素的平均复杂度为（C）A.O(n) B.O(nlog2n) C.O(1) D.O(n^2)解析：数组可以通过下标直接查找，跟数组个数无关，所以平均复杂度是O(1)2.5 下面说法错误的是（A）1.算法原地工作的含义是指不需要任何额外的辅助空间2. 在相同规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2^n)的算法3. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界4. 某算法的时间复杂度为O(n^2)，表明该算法的执行时间与n*n成正比A.1 B.1，2 C.1，4 D.3解析：原地工作是指算法在实现时所需的辅助空间相对于输入数据量而言是个常数，并不是指不需要任何额外空间，所以错误。其他语句描述的都没毛病，不过我记不住2.6 下面算法将一维数组a中的n个数逆序存放到原数组中，空间复杂度为（B）for(i=0;i<n;i++)
b[i]=a[n-i-1];
for(i=0;i<n;i++)
a[i]=b[i];
A.O(1) B.O(n) C.O(log2n) D.O(n^2)解析：该算法是将借助数组b完成数组a的元素逆序，所以，空间复杂度为O(n)2.7 下面算法将一维数组a中的n个数逆序存放到原数组中，空间复杂度为（A）for(i=0;i<n/2;i++){
t=a[i];
a[i]=a[n-i-1];
a[n-i-1]=t;}
A.O(1) B.O(n) C.O(log2n) D.O(n^2)解析：该算法是将借助临时变量t完成数组a的元素逆序2.8 设数据结构A=(D,R)，其中D={1,2,3,4}，R={r},r={<1,2>,<2,3>,< 3,4>,<4,1>}，则数据结构A是（C）A.线性结构 B.树结构 C.图 D.集合解析：这题考的是逻辑结构，数据元素之间存在多对多的关系，所以是A是图结构2.9 顺序存储结构中数据元素间的逻辑关系是由（C）表示的A.线性结构 B.非线性结构 C.存储位置 D.指针2.10 链式存储结构中的数据元素间的逻辑关系是由（D）表示的A.线性结构 B.非线性结构 C.存储位置 D.指针2.11 抽象数据类型的三个组成部分分别为（A）A.数据对象、数据关系和基本操作 B.数据元素、逻辑结构和存储结构C.数据项、数据元素和数据类型 D.数据元素、数据结构和数据类型2.12 对一个算法的评价，不包括以下（B）方面的内容A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度2.13 通常从正确性、易读性、健壮性、高效性等四个方面评价算法的质量，以下解释错误的是（D）A.正确性算法应能正确地实现预订的功能B.易读性算法应易于阅读和理解，以便调试、修改和扩充C.健壮性指当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果D.高效性即达到所需要的时间性能解析：高效性包括时间和空间两方面，不仅指时间性能高效2.14 下面关于抽象数据类型的描述错误的是（B）A.数据封装 B.用例驱动 C.信息隐藏 D.使用与实现相分离2.15 某算法的时间复杂度为O(n^2)，表明该算法的（C）A.问题规模是n^2 B.执行时间是n^2 C.执行时间与n^2成正比 D.问题规模与n^2成正比2.16 以下关于数据结构的说法中正确的是（A）A.数据结构的逻辑结构独立于其存储结构B.数据结构的存储结构独立于该数据结构的逻辑结构C.数据结构的逻辑结构唯一地决定了该数据结构的存储结构D.逻辑结构和存储结构均相同的数据结构一定为同一数据结构解析：A：逻辑结构是从逻辑关系上描述数据，与数据的存储无关。BC：同一逻辑结构采用不同的存储方法可以得到不同的存储结构。D：从思维导图就可以看出来，数据结构包括逻辑结构、存储结构和数据运算，逻辑结构和存储结构均相同而数据运算不同的数据结构，不一定是同一数据结构。2.17 在存储数据时，通常不仅需要存储数据元素的值，还要存储（C）A.数据元素的类型 B.数据的基本运算 C.数据元素之间的关系 D.数据的存取方式2.18 设n是描述问题规模的非负整数，下面程序段的时间复杂度是（A）x=2;
while(x<n/2)
x=2*x;
A.O(log2n) B.O(n) C.O(nlog2n) D.O(n^2)解析：设循环体内的基本语句x=2*x的执行次数为k，执行k次时，x=2^(k+1)。由循环结束条件x<n/2可得，2^(k+1)<n/2，即k<log2n -2，k=log2n+C（C为常数），因此T(n)=O(log2n)2.19 下面程序段的时间复杂度是（C）count=0;
for(k=1;k<=n;k*=2)
for(j=1;j<=n;j++)
count++;
A.O(log2n) B.O(n) C.O(nlog2n) D.O(n^2)解析：嵌套循环时间复杂度=内层时间复杂度*外层时间复杂度。内层循环条件跟外层循环变量无关，所以外层循环执行一次，内层循环执行n次，所以内层循环的时间复杂度为O(n)。外层循环结束条件为k<=n，增量条件定义为k*=2，所以循环次数为2^k≤n，即k≤log2n，所以外层循环的时间复杂度为O(log2n)。因此T(n)=T(内层)*T(外层)=O(n)*O(log2n)=O(nlog2n)2.20 下面函数的时间复杂度是（B）int func(int n){
int i=0,sum=0;
while(sum<n) sum+=++i;
return i;
}
A.O(log2n) B.O(n^(1/2)) C.O(n) D.O(n^2)解析：这段函数是求前i项和，直到该项和大于等于n，sum+=++i等价于++i；sum=sum+i；，所以sum=1+2+……+i=(1+i)*i/2，由循环结束条件sum<n可得(1+i)*i/2<n，i是循环次数，所以T(n)=O(n^(1/2))2.21 设n是描述问题规模的非负整数，下列程序段的时间复杂度是（B）x=0;
while(n≥(x+1)*(x+1))
x=x+1;
A.O(log2n) B.O(n^(1/2)) C.O(n) D.O(n^2)解析：基本语句x=x+1，设循环次数为k，当执行第k次循环时，x的值为k-1。由循环结束语句得n≥k^2，所以k≤n^(1/2)2.22 试分析下列各算法的时间复杂度1.基本语句x=x-10;y--;x++执行次数由x，y决定，而x，y是常数，所以T(n)=O(1)x=90,y=100;
while(y>0)
if(x>100){
x=x-10;
y--;}
else x++;
2.嵌套循环，外层执行次数为n，内层为m，所以T(n)=O(n*m)for(i=0;i<n;i++)
for(j=0;j<m;j++)
a[i][j]=0;
3.嵌套循环，外层执行次数为n，内层为n，所以T(n)=O(n^2)s=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
s+=B[i][j];
4.设基本语句i=i*3执行次数为k，则3^k≤n。所以T(n)=O(log3n)i=1;
while(i<=n)
i=i*3;
5.基本语句x++执行次数为n-1+n-2+……+1=n(n-1)/2所以T(n)=O(n^2)x=0;
for(i=1;i<n;i++)
for(j=1;j<n-i;j++)
x++;
6.跟2.21原理一样，只不过是数值变了，T(n)=O(n^(1/2))x=n;
y=0;
while(x>=(y+1)*(y+1))
y++;
这章重点就是记住概念，会算时间复杂度}