数据结构各章习题及答案!.pdfVIP

数据结构各章习题及答案!--第1页

数据结构习题及解答

第1章概述

【例1-1】分析以下程序段的时间复杂度。

for(i=0;in;i++)

for(j=0;jm;j++)

A[i][j]=0;

解：该程序段的时间复杂度为O(m*n)。

【例1-2】分析以下程序段的时间复杂度。

i=s=0;①

while(sn)

{i++;②

s+=i;③

}

解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O(1)。语句②和语

句③构成while循环语句的循环体，它们的执行次数由循环控制条件中s与n的值确定。假

定循环重复执行x次后结束，则语句②和语句③各重复执行了x次。其时间复杂度按线性

累加规则为O(x)。此时s与n满足关系式：s≥n，而s=1+2+3+„+x。所以有：1+2+3+„+x

≥n，可以推出：

118n11

2n

224

x=

x与n之间满足x=f(n），所以循环体的时间复杂度为O(n)，语句①与循环体由

线性累加规则得到该程序段的时间复杂度为O(n）。

【例1-3】分析以下程序段的时间复杂度。

i=1;①

while(i=n)

i=2*i;②

解：其中语句①的执行次数是1，设语句②的执行次数为f(n)，则有：2f(n)n。

数据结构各章习题及答案!--第1页

数据结构各章习题及答案!--第2页

得：T（n）=O(logn)

2

【例1-4】有如下递归函数fact(n)，分析其时间复杂度。

fact(intn)

{if(n=1)

return(1);①

else

return(n*fact(n-1));②

}

解：设fact（n）的运行时间函数是T(n)。该函数中语句①的运行时间是O(1)，语句

②的运行时间是T(n-1)+O(1)，其中O(1)为常量运行时间。

由此可得fact（n）的时间复杂度为O(n)。

习题1

一、单项选择题

1.数据结构是指（1.A）。

A.数据元素的组织形式B.数据类型

C.数据存储结构D.数据定义

2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2.C）。

A.存储结构B.逻辑结构

C.链式存储结构D.顺序存储结构

3.树形结构是数据元素之间存在一种（3.D）。

A.一对一