算法与数据结构复习题 第一章 绪论_如果g（n）=of（n），则o（f）+o（g）=o（f）

第一章 绪论

书面作业

一、判断题

1、数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。 (F)

解析：

逻辑结构可用不同的存储结构实现,“它依赖于计算机的存储结构”完全说不通。

2、算法和程序没有区别，在数据结构中二者是通用的。 (F)

解析：

算法与程序有区别，算法是解决问题的方法或步骤，而程序是用编程语言描述算法后形成的。在数据结构中二者不是通用的。

3、$N^2/1000$ is $O(N).$ (F)

解析：

$N^2/1000$ is $O(N^2).$

4、N! is O($N^N$). (T)

解析：

5、用渐进表示法分析算法复杂度的增长趋势。（T）

解析：

一般用渐进分析方法来分析算法复杂度的增长趋势；

• 大O表示法
• Ω表示法
• Θ表示法

详细：渐进分析方法

6、算法独立于具体的程序设计语言，与具体的计算机无关。 (T)

7、数据结构包括数据对象集以及它们的逻辑结构和物理结构，还包括与数据对象相关联的操作集，以及实现这些操作的高效的算法。 (T)

8、数据元素可以由类型互不相同的数据项构成。 (T)

9、O($n^2$)，O(1+2+···+n) 对应的算法时间复杂度相同。(T)

解析：

1+2+···+n=(1+n)*n/2=($n^2$+n)/2=$n^2$/2+n/2

O(1+2+···+n)=O($n^2$)

10、算法必须有输出，但可以没有输入。(T)

11、数据的逻辑结构与数据元素本身的内容和形式无关。（T）

12、$N^{2}logN$ and $Nlog{N}^2$ have the same speed of growth. (F) 解析： 请参考选择题13

13、算法的优劣与算法描述语言无关，但与所用计算机有关。（F)

14、对于某些算法，随着问题规模的扩大，所花的时间不一定单调增加。 （T）

二、单选题

1、要判断一个整数N（>10）是否素数，我们需要检查3到√N之间是否存在奇数可以整除N。则这个算法的时间复杂度是：(A)

1. O(√N)
2. O(N/2)
3. O(√NlogN)
4. O(0.5logN)

解析：

实现函数如下：

bool isPrimeNumber(int N){ 	
	for(int i=3;i<=sqrt(N);i=i+2) 		
		if(N%i==0) 			
			return false; 	
	return true; 
} 
1
2
3
4
5
6

最坏情况：O((√N-3)/2)=O(√N)

2、下面的程序段违反了算法的（）原则。 (A)

void sam() {  
	int n=2;	      
	while (n%2==0)    
		n+=2;    
	printf(“%d”,n); 
} 
1
2
3
4
5
6

1. 有穷性
2. 确定性
3. 可行性
4. 健壮

解析：

一直在循环，违反了算法的有穷性；

3、算法的时间复杂度取决于（D）。

1. 问题的规模
2. 待处理数据的初态
3. 计算机的配置
4. A和B

解析： 对于某些算法，即使问题规模相同，如果输入的数据不同，其时间复杂度也不同。

4、执行下面程序段时，执行S语句的频度为（D）。

for(int i=0;i<n;i++) for(int j=1;j<=i;j++)
     S; 
1
2

1. $n^2$

2. $n^2/2$

3. n(n+1)

4. n(n+1)/2

5、下面关于抽象数据类型的描述，不正确的是（D）。

1. 数据封装
2. 使用与实现分离
3. 信息隐藏
4. 用例驱动

解析： 抽象数据类型的特征是将使用与实现分离，从而实行封装和隐藏信息。抽象数据类型通过一种特定的数据结构在程序的某个部分得以实现，只关心在这个数据类型上的操作，而不关心数据结构具体实现。

6、下面程序段的时间复杂度是（A）。

x=90;    
y=100;    
while(y>0)  
    if(x>100)  
        { x=x-10; y--; }  
    else x++; 
1
2
3
4
5
6

1. O(1)
2. O(N)
3. O(N2)
4. O(log2N)

解析： 全是常数，所以时间复杂为O(1);

7、下面代码段的时间复杂度是（B）。(2分)

x=n; //n>1 
y=0; 
while( x≥(y+1)*(y+1) )
    y++;
1
2
3
4

1. O(1)

2. O($n^{1/2}$)

3. O(n)

4. O(log2n)

8、下面程序的时间复杂度为（A）。 (2分)

for(i = 0; i < m; i++)
      for(j = 0; j < t; j++)
           c[i][j] = 0; for(i = 0; i < m; i++)
for(j = 0; j < t; j++)
      for(k = 0; k < n; k++)
           c[i][j] = c[i][j]+a[i][k] * b[k][j]; 
1
2
3
4
5
6

1. O(m × n × t)
2. O(m + n + t)
3. O(m + n × t)
4. O(m × t + n)

解析： $m\times t+m\times t\times n=m\times t\times (1+n)=O(m\times n\times t)$

9、算法分析的目的是（C）。 (2分)

1. 找出数据结构的合理性
2. 研究算法中的输入和输出的关系
3. 分析算法的效率以求改进
4. 分析算法的易懂性和文档性

10、下面程序的时间复杂度为（C）。 (2分)

for(i = 0; i < m; i++)
     for(j = 0; j < n; j++ )
          A[i][j] = i*j; 
1
2
3

1. O(m2)
2. O($n^2$)
3. O(m × n)
4. O(m + n)

11、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（C）。 (2分)

1. 存储结构
2. 存储实现
3. 逻辑结构
4. 运算实现

解析： 存储及运算都需考虑数据元素本身的形式、内容等。而逻辑结构中关心元素之间的逻辑关系，与数据元素本身无关。

12、某数据对象由三个元素A、B、C构成，元素间关系的集合为{<A,B>，<B,C>，<C,A>}，该数据对象的逻辑结构为 © (2分)

1. 线性结构
2. 树型结构
3. 图结构
4. 集合结构

解析： 首尾相连形成图；

13、下列函数中，哪个函数具有最慢的增长速度：(B)

1. $N^{1.5}$

2. $Nlog{N}^2$

3. $N^{2}logN$

4. $N(logN{)}^2$

解析： 算法运行时间比较

14、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（C）。

1. 数据的处理方法

2. 数据元素的类型

3. 数据元素之间的关系

4. 数据的存储方法、

15、某算法的时间复杂度是 O(n2)，表明该算法的（ D）。

1. 问题规模是 n2

2. 问题规模与 n2 成正比

3. 执行时间等于 n2

4. 执行时间与 n2 成正比

16、以下程序段的时间复杂度是(B) 。

for (int i = 0; i * i < n; i++) {  printf("%d\n", i); } 
1

1. O(n)

2. O(√n)

3. O(n2)

4. O(nlgn)

解析： 与第7题类似；

17、以下关于数据结构的说法中正确的是（A）。

1. 数据结构的逻辑结构独立于其存储结构

2. 数据结构的存储结构独立于该数据结构的逻辑结构

3. 数据结构的逻辑结构唯一地决定了该数据结构的存储结构

4. 数据结构仅由其逻辑结构和存储结构决定

解析：

逻辑结构仅与数据元素间的关系有关，与其他无关；

存储结构都需考虑数据元素本身的形式、内容等；

18、以下说法正确的是（D）。

1. 数据元素是数据的最小单位
2. 数据项是数据的基本单位
3. 数据结构是带有结构的各数据项的集合
4. 一些表面上很不相同的数据可以有相同的逻辑结构

解析：

数据元素是数据的基本单位，数据项是不可分割的最小单位，数据项是构成数据元素的最小单位；

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

19、下面代码段的时间复杂度是（D）。

s=0;  
for ( i=0; i<n; i++ )  	
	for( j=0; j<n; j++ )  		
		s+=B[i][j]; 
sum=s; 
1
2
3
4
5

1. O(1)
2. O(log2n)
3. O(n)
4. O(n2)

20、算法效率的比较:

假设为解决某问题而设计的若干算法的时间复杂度分别为：

A) O(n)

B) O($n^2$)

C) O($lo{g}_{2}n$)

D) O($nlo{g}_{2}n$)

E) O($2^n$)

F) O(√n)

G) O(n!)

H) O(1)

I) O(n√n)

J) O($n^n$)

HCFADIBEGJ

O(1)<O($lo{g}_{2}n$)<O(√n)<O(n)<O($nlo{g}_{2}n$)< O(n√n)<O($n^2$)< O($2^n$)<O(n!)< O($n^n$)

解析：

三、程序填空

请在空白处填写适当内容，完成该程序。

#include <stdio.h>
#include <time.h> int F(int x); int main() {
    clock_t t1, t2;
    double t;
    int x, y;
    printf("x = ? ");
    scanf("%d", &x);
    t1 = clock();//空白
    y = F(x);
    t2 = clock();//空白
    t = (double)(t2-t1)/CLOCKS_PER_SEC;//空白
    printf("y = %d\n", y);
    printf("It took %.2f second(s)\n", t);
    
    return 0; } int F(int x) {
    ...... } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

运行效果示例

x = ? 25 y = 3712 It took 1.25 second(s) 
1