数据结构----从概念到C++实现 第一章 基础概念题和计算题

1.数据元素是数据的基本单位。

2.顺序存储结构中数据元素之间的逻辑关系是由存储位置表示的。

3.链式存储结构中数据元素之间的逻辑关系是由指针表示的。

4.假设有如下遗产继承规则：丈夫和妻子可以互相继承遗产，子女可以继承父亲或者母亲的遗产，子女间不能互相继承。则表示该遗产继承关系的数据结构应该是( A).

（A）图 （B）树 （C）线性表 （D）集合

5.设待处理问题的规模为n，若一个算法的时间复杂度为2n*log2^5n+8n,则表示称数量级的形式为_____n*log2^n_______

6.下列程序段加下划线的语句执行了(C)次。

for(m=0,i=1;i<=n;i++)

for(j=1;j<=2*i;j++)

m=m+1;

C.n(n+1)

解释：

n=1 i=1满足i<=n j=1<=2 m执行2次

n=2 i=1满足i<=n j=1<=4 m执行4次

n=3 i=1满足i<=n j=1<=6 m执行6次

由此可以找出对应的关系

当外层循环为n次数时，内层循环语句执行次数为2n

所有总执行次数为

(2+4+...+2n)=2*(1+2+...+n)=2n*(n+1)/2=n*(n+1)

7.程序段

i=1,k=0;

while(i<=n){

k=k+10*i;

i++;

}

的时间复杂度为O(n).

8.程序段

i=1;k=0;

do{

k=k+10*i;

i++;

}while(i<=n);

的时间复杂度为O（n）。

9.程序段

i=1;j=0;

while(i+j<=n)

if(i>j) j++;

else i++;

解释：

i=1; j=0;

while(i+j<=n)

if(i>j) j++; else i++;

每循环一次，i或j增1，且非同时增1，即i+j增1。循环重复执行n次。

∴ T(n) = O(n)

10.程序段

y=0;

while((y+1)*(y+1)<=n)

y=y+1;

的时间复杂度为（C）

解析：while的循环条件是:
x>=(y+1)*(y+1),如果(y+1)*(y+1)>n，
就是超过n时的值便退出循环。
所以(y+1)*(y+1)<n.
y<x^(1/2) -1 这就是执行时间了。

11.程序段

for(i=1;i<=n;i++)

    for(j=1;j<=i;j++)

        for(k=1;k<=j;k++)

            x++;

的时间复杂度为（C）

C.O(n^3)

12.程序段

for(i=n-1;i>=1;i--)

for(j=1;j<=i;j++)

if(A[j]>A[j+1])

A[j]与A[j+1]对换;

的时间复杂度为（D）

解析：冒泡排序时间复杂度：O(n²)

时间复杂度
        这个时间复杂度还是很好计算的：外循环和内循环以及判断和交换元素的时间开销；

       最优的情况也就是开始就已经排序好序了，那么就可以不用交换元素了，则时间花销为：[ n(n-1) ] /  2；所以最优的情况时间复杂度为：O( n^2 )；

       最差的情况也就是开始的时候元素是逆序的，那么每一次排序都要交换两个元素，则时间花销为：[ 3n(n-1) ] / 2；（其中比上面最优的情况所花的时间就是在于交换元素的三个步骤）；所以最差的情况下时间复杂度为：O( n^2 )；

13.程序段

for(i=1;i<=n;i++)

    for(j=2*i;j<=n;j++)

        y+=i*j;

的时间复杂度（）

解析：O(n^2)
公式是n+(n-2)+(n-4)+...，一共[n/2]个。当n为偶数的时候它就是2+4+6+...+n=n*(n+1)/2。

14.【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，

减少了不必要的乘法运算。

15.算法设计（用伪代码或C++程序设计语言描述算法，并分析）：找出整型数组A[n]中的最大值和次最大值。