练习

选择题

• 算法的计算量的大小称为计算的（ ）。
  A．效率
  B．复杂性
  C．现实性
  D．难度
  
• 计算机算法指的是解决问题的步骤序列，它必须具备（ ）三个特性。
  A．可执行性、 可移植性、 可扩充性
  B．可执行性、 确定性、 有穷性
  C．确定性、 有穷性、 稳定性
  D．易读性、 稳定性、 安全性
  
• 以下数据结构中，（ ）是非线性数据结构。
  A．树
  B．字符串
  C．队
  D．栈
  
• 连续存储设计时，存储单元的地址（ ）。
  A．一定连续
  B．一定不连续
  C．不一定连续
  D．部分连续，部分不连续
  
• 此程序的复杂度为( )。[大连理工2008研]

for(int i=0;i<m;i++)
  for(int j=0;j<n;j++)
    A[ilj]=i*j;

• A. 0 (m²)
  B.0 (n²)
  C.0 (mXn)
  D. O (m+n)
• 计算算法的时间复杂度是属于一种( )。 [北京理工2005研]
  A.事前统计的方法
  B.事前分析估算的方法
  C.事后统计的方法
  D.事后分析估算的方法
  
• 以下属于逻辑结构的是( )。 [西安电子2001研]
  A.顺序表
  B.哈希表
  C.有序表
  D.单链表
  
• 以下数据结构中，哪一个是线性结构? ( ) [北方交通大学2001研]
  A.广义表
  B.二叉树
  C.稀疏矩阵
  D.串
  
• 下面说法错误的是 ()。
  (1) 算法原地工作的含义是指不需要任何额外的辅助空间
  (2) 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2ⁿ) 的算法
  (3) 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
  (4) 同一个算法，实现语言的级别越高，执行效率就越低
  A. (1)
  B. (1)， (2)
  C. (1)， (4)
  D. (3)
  

判断题

• 数据元素是数据的最小单位。 （ ）
• 数据的逻辑结构是指数据的各数据项之间的逻辑关系。 （ ）
• 算法的优劣与算法描述语言无关，但与所用计算机有关。 （ ）
• 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ ）
• 抽象数据类型与计算机内部表示和实现无关。 （ ）

填空题

• 数据结构中评价算法的两个重要指标是______。
• 数据结构是研讨数据的 1______和 2______以及它们之间的相互关系，并对与这种结构定义相应的 3______，设计出相应的 4______。
• 一个算法具有5个特性：1______、2______、3 ______、有零个或多个输入、 有一个或多个输出。
• 抽象数据类型的定义仅取决于它的一组____， 而与____无关，即不论其内部结构如何变化，只要它的___不变， 都不影响其外部使用。[山东大学2001研]

简答题

分析以下程序段中语句4的频度以及该程序段的时间复杂度。

for(i=0;i<n;i++) // 1
{
  y=y+1; // 2
  for(j=0;j<=2*n;j++) // 3 
    x++; // 4
}

分析以下算法的时间复杂度。

void fun(int n)
{
  int i=0;
  int s=0; .
  while(s<n)
  {
    ++i; 
    s=s+i;
  }
}

以下算法的时间复杂度为多少?

void hanoi(int n,char x,char y,char z)
{
  if(n==1)
    printf("'move %c to %c\n",x,z);
  else
  {
    hanoi(n-1 ,x,z,y);
    printf( "move%cto%c\n",x,2);
    hanoi(n-1,y,x,z);
  }
}

答案与解析

选择题

算法的计算量的大小称为计算的（ ）。

A．效率

B．复杂性

C．现实性

D．难度

【答案】B

【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。

计算机算法指的是解决问题的步骤序列，它必须具备（ ）三个特性。

A．可执行性、 可移植性、 可扩充性

B．可执行性、 确定性、 有穷性

C．确定性、 有穷性、 稳定性

D．易读性、 稳定性、 安全性

【答案】B

【解析】一个算法通常需要具备五大特性：有穷性；确定性；可执行性；输入一个算法有零个或多个输入；输出一个算法有零个或者多个输出，其中前三项必须具备。

以下数据结构中，（ ）是非线性数据结构。

A．树

B．字符串

C．队

D．栈

【答案】A

【解析】非线性结构是指存在一对多或者多对一的关系。常见的非线性结构有树结构和图结构。

连续存储设计时，存储单元的地址（ ）。

A．一定连续

B．一定不连续

C．不一定连续

D．部分连续，部分不连续

【答案】A

【解析】连续存储是指数据的物理存储相连，即存储单元的地址是连续的。

此程序的复杂度为( )。[大连理工2008研]

for(int i=0;i<m;i++)
  for(int j=0;j<n;j++)
    A[ilj]=i*j;

A. 0 (m²)

B.0 (n²)

C.0 (mXn)

D. O (m+n)

[答案] C

[解析]时间复杂度是指基本操作重复执行次数的阶数T(n) =O(f(n))。基本操作为A[il[j]=i*j，该语句的执行次数与外层的两个循环次数相等，为mXn，因此，算法的复杂度为0 (mXn)。

计算算法的时间复杂度是属于一种( )。 [北京理工2005研]

A.事前统计的方法

B.事前分析估算的方法

C.事后统计的方法

D.事后分析估算的方法

[答案] B

[解析]度量一个程序的执行时间通常有两种方法:

①事后统计。

②事前分析估计。

算法的时间复杂度是指算法中基本操作重复执行的次数的阶数，算法的时间复杂度是在程序运行之前对算法所消耗资源的一种估算方法，计算算法的时间复杂度属于事前分析估算的方法。

以下属于逻辑结构的是( )。 [西安电子2001研]

A.顺序表

B.哈希表

C.有序表

D.单链表

[答案] C

[解析]顺序表是线性表的顺序存储结构；哈希表是存储结构(散列存储结构)；单链表是线性表的链式存储结构；有序表是指已经按照某一关键字排好序的线性表，它是逻辑结构。因此，C项正确，而ABD三项都是数据元素在计算机中的存储结构，属于物理结构，而不是题目要求的逻辑结构。

以下数据结构中，哪一个是线性结构? ( ) [北方交通大学2001研]

A.广义表

B.二叉树

C.稀疏矩阵

D.串

[答案] D

[解析]线性结构：数据元素之间存在一对一的关系，常见的线性结构有：线性表、栈、队列、双队列、数组、串。非线性结构指存在多对一或者一对多的关系，逻辑特征上表现为一个结点可能有多个前驱结点或多个后继结点，常见的非线性结构有：二维数组、多维数组、树、图、广义表等。广义表(又称列表)是一种非线性的数据结构，是线性表的一种推广。

下面说法错误的是 ()。

(1) 算法原地工作的含义是指不需要任何额外的辅助空间

(2) 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2ⁿ) 的算法

(3) 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

(4) 同一个算法，实现语言的级别越高，执行效率就越低

A. (1)

B. (1)， (2)

C. (1)， (4)

D. (3)

[答案] C

[解析]

①一个可执行程序可能涉及中间变量和数组等，需要额外的存储空间，如果这个额外空间相对于问题的规模(输入数据)来说是个常数，称之为原地工作，辅助空间为O (1)。

②对于相同的数据规模，O(n)的效率显然优于O(2ⁿ)。

③算法在最坏情况下的时间复杂度，指算法计算量可能达到的最大值，是估算算法执行时间的一个上界

④编译链接后的最终的机器指令操作的次数越少，说明该语言在某种编译链接环境下效率越高，实际上即使同一种语言在不同的编译环境下，也有可能不同。

[注意]在对错判断题中忌“绝对化”，当出现一定，任何等表示绝对性的词语的时候需要慎重对待。

判断题

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

【答案】 ×

【解析】数据项是数据的不可分割的最小单位，而数据元素是数据的基本单位。

数据的逻辑结构是指数据的各数据项之间的逻辑关系。 （ ）

【答案】 ×

【解析】数据的逻辑结构是指数据元素之间的逻辑关系。

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

【答案】 ×

【解析】算法的优劣取决于它的时间复杂度和空间复杂度有关，与算法描述语言和所用计算机都无关。

顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ ）

【答案】 ×

【解析】前者正确，后者错误。 顺序存储方式在插入、删除元素时需要挪动大量的元素，执行效率较低。

抽象数据类型与计算机内部表示和实现无关。 （ ）

【答案】 √

【解析】抽象数据类型只表示数据的逻辑结构，与计算机内部表示和实现无关。

填空题

数据结构中评价算法的两个重要指标是______。

【答案】算法的时间复杂度和空间复杂度

数据结构是研讨数据的 1______和 2______以及它们之间的相互关系，并对与这种结构定义相应的 3______，设计出相应的 4______。

【答案】逻辑结构；物理结构；操作（运算）；算法

一个算法具有5个特性：1______、2______、3 ______、有零个或多个输入、 有一个或多个输出。

【答案】有穷性；确定性；可行性

抽象数据类型的定义仅取决于它的一组____， 而与____无关，即不论其内部结构如何变化，只要它的___不变， 都不影响其外部使用。[山东大学2001研]

[答案]逻辑特性;在计算机内部如何表示和实现;数学特性

简答题

分析以下程序段中语句4的频度以及该程序段的时间复杂度。

for(i=0;i<n;i++) // 1
{
  y=y+1; // 2
  for(j=0;j<=2*n;j++) // 3 
    x++; // 4
}

答:

语句的频度是指该语句被重复执行的次数。在本题中语句④执行的次数是内外两层循环的次数，即n(2n+1) =2n²+n， 因此该语句的频度是2n²+n。（2n+1是由于内层循环的j从0加到2n，每次一共会执行2n+1次内层循环）

时间复杂度可以用算法中的基本操作重复执行的次数来度量，本程序段中的语句④即为基本操作，所以该算法的时间复杂度 T(n) = O(2n²+n) = O(n²)。

分析以下算法的时间复杂度。

void fun(int n)
{
  int i=0;
  int s=0; .
  while(s<n)
  {
    ++i; 
    s=s+i;
  }
}

答:显然n为问题规模，基本操作为语句“++i"和“s=s+i”。变量i与s都从0开始，假设循环执行m次结束，即当循环m次时，m=n，则有s 0 = 0 , s 1 = 1 , s 2 = 1 + 2 = 3 , s 3 = 1 + 2 + 3 = 6 ， . . , s m = m ( m + 1 ) 2 s_0=0, s_1=1, s_2=1+2=3, s_3=1+2+3=6，.., s_m=\frac{m (m+1)}{2}s0=0,s1=1,s2=1+2=3,s3=1+2+3=6，..,sm=2m(m+1)(其中s m s_msm为执行到第m次的时候s的值)，可得m ( m + 1 ) 2 < n \frac{m (m+1)}{2} < n2m(m+1)<n，由一元二次方程的求根公式可得

m = − 1 + 8 n + 1 2 m=\frac{-1+\sqrt{8n+1}}{2}m=2−1+8n+1

则基本语句关于问题规模n的函数为

f ( n ) = − 1 + 8 n + 1 2 f(n)=\frac{-1+\sqrt{8n+1}}{2}f(n)=2−1+8n+1

算法的时间复杂度为

T ( n ) = O ( f ( n ) ) = O ( n ) T(n) = O(f(n)) = O(\sqrt{n})T(n)=O(f(n))=O(n)

以下算法的时间复杂度为多少?

void hanoi(int n,char x,char y,char z)
{
  if(n==1)
    printf("'move %c to %c\n",x,z);
  else
  {
    hanoi(n-1 ,x,z,y);
    printf( "move%cto%c\n",x,2);
    hanoi(n-1,y,x,z);
  }
}

答:

设函数hanoi (n)的执行时间为T(n)，则hanoi (n-1)的执行时间为T (n-1)。

有:

当n=1时，T (1) =1;

当n>1时，T (n)=2T(n-1)+1。

所以有:

T(n)

= 2T(n-1) +1

=2(2T(n-2) +1) +1

=2²T(n-2) +1+2

=2² (2T (n-3) +1) +1+2

= 2³ T (n-3) +1+2+2²

= …

= 2^n-1T(1) +1+2+2²+…+2^n-2

= 2^n-1+2^n-1-1

=2ⁿ-1

=O (2ⁿ)