数据结构答案 第1章 绪论学习指导.doc

第1章绪论

1.1知识点分析

1. 数据

数据是信息的载体，是对客观事物的符号表示。数据是计算机化的现实世界的事物的抽 象描述。凡是能被计算机识别、存取和加工处理的符号、字符、图形、图象、声音、视频信 号等一切信息都可以称为数据。

2. 数据元素

数据元素是对现实世界中某独立个体的数据描述，是数据的基本单位。数据元素也称为 结点，通常由若干数据元素组成。

3. 数据项

数据项是数据不可分割的、具有独立意义的最小数据单位，是对数据元素属性的描述。 数据、数据元素、数据项反映了数据组织的三个层次，即数据可以由若干个数据元素组 成，数据元素又有若干数据项组成。

4. 数据对象

数据对象是性质相同的数据元素的集合，是数据的一个了集。

5. 数据结构

数据结构是相互之间存在的一?种或多种特定关系的数据元素的集合。简言之，数据结构 是指数据之间的关系，即数据的组织形式。数据结构包括以下三个方面：

(1) 数据的逻辑结构

指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立 于计算机的。一个数据的逻辑结构G可以用二元组G=(D, R)来表示，其中D是数据元素的 集合，R是D上所有数据元素之间关系的有限集合。

线性结构是指数据元素之间存在“一对一”关系的逻辑结构，非线性结构是指数据元素之 间存在“一对多”或哆对多”关系的逻辑结构。

(2) 数据的存储结构

数据元素及其关系在计算机存储器内的表示，称为数据的存储结构，也称为数据的物理 结构。数据的存储结构是数据的逻辑结构用计算机语言的实现，它依赖于计算机语言。

(3) 数据的运算

指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而运算的实现则是在 存储结构上进行的。

6. 算法的描述和分析

数据的运算是通过算法来描述的，对于算法的说明可以使用不同的语言，对同一问题可 以有不同的算法。首选选用的算法必须是正确的。其次，主要考虑执行算法所耗费的时间(即 时间效率)和执行算法所耗费的存储空间(即空间效率)。

(1) 时间复杂度

通常把算法中所包含简单操作次数的多少叫做算法的时间夏杂度。但是当一个算法比较 复杂时，其时间复杂度的计算会变得相当困难。一般情况下，算法中原操作重复执行的次数 是规模n的某个函数f(n),算法的时间复杂度T(n)的数量级可记作：T(n)=O(Rn))。

算法的时间复杂度T(n)是该算法的时间消耗，一个算法的时间耗费就是该算法中所有语 句的执行次数(频度)之和。当n-8时(即当n相当大时)，T(n)的数量级(阶)，用大“0” 记号表示。由于

limT(n)/f(n)=C, C是不为0的常数,所以T(n)=O(f(n))o其实，f(n)就是T(n) 中最高阶的那一项，是算

法中频度最大的语句频度。

一般情况下，对于循环语旬只需要考虑循环体中语句的执行次数，而忽略该语句中循环 头的部

分。有时，循环体中语句的频度不仅与问题规模n有关，还与输入实例等其它因素有 关，此时可以用最坏情况下的时间复杂度作为算法的时间复杂度。

(2) 空间复杂度

一个程序的空间复杂度是指程序运行从开始到结束所需要的存储空间。类似于算法的时 间复杂度，我们把算法所需存储空间的量度，记作：S(n)=O(f(n))。其中n为问题的规模。 一个程序上机执行时，除了需要存储空间来存放本身所用的指令、常数、变量和输入数据以 外，还需要一些对数据进行操作的工作单元和实现算法所必需的辅助空间。在进行时间复杂 度分析时，如果所占空间量依赖于特定的输入，一般都按最坏情况来分析。

程序运行时所需要的存储空间包括以下两个部分：

固定部分：主要包括程序代码、常量、变量、结构体变量等所占的空间。空间与所处理 的数据大小和个数无关，或者说与问题事例的特征无关。

可变部分：空间大小与算法在某次执行中处理的特定数据的大小和规模有关。

1.2典型习题分析

【例1】算法与程序的区别

分析：算法与程序的既有区别，又有联系。其区别是：

(1) 算法必须满足有穷性，而程序则不一定满足有穷性。例如，我们启动计算机必须使用 操作系

统，只要不关机或不遭受破坏，操作系统就永不终止“即使没有作业运行，它也一直 处在一个等待循环之中。因此，操作系统是一个不终|上的计算过程，但它不满足算法的定义。

(2) 程序中的指令必须用计算机可以接受的语言书写，而算法则无此限制。但是，当用一 个计算

机可以接受的语言来书写算法时，它就是程序。一般而言，算法比较抽象，而程序则 比较具体。

【例2】通常一个算法的时间复杂度是指( )。

A.算法的平均时间复杂度 B.算法在最坏情况下的时间复杂度 C.算法的期望运行时间 D.算法在最好情况下的时间复杂度

分析：如果没有“平均”、“最好”、“最坏”的修饰语，时间复杂度就是指最坏的时间复杂度。 最坏时间复杂度是算法的所有输入可能情况的执行时间的上界，所以应选Bo

【例3】当n从1变化到10时，比较n、2n、n\\ 2\\ n!、/增长率的变化。

解：表1-1给出当n从1变化到10时的各函数变化过程，可见当n>=10时，按增长率由小 到大排列次序依次为：n> 2n> n2^ n'、2「、n!、nn0

表1-1 各函数值增长表 n 1 2 3 4 5 6 7 8 9 10 2n 2 4 6 8 10 12 14 16 18 20 2 n3 1 8 27 64 125 216 343 512 792 1000 2n 2 4 8 16 32 64 128 256 512 1024 n! 1 2 6 24 120 720 5040 40320 362880 3628800 nn 1 4 27 256 3125 46656 823543 16777216 3.9X108 i.oxio10 )。

1 4 9 16 25 36 49 64 81 100 【例4】T(n)=nsinn,贝佣大“O”记号可以表示为( A. T(n)=O(n') B. T(n)=O(l)

C. T(n)= O (n) D.不确定

分fr： sinn的取值范围是.1到1之间，所以T(n)的上界为0(n>,即0(n),所以应选C°

【例5】设两个算法的执行时间分别为100僵和2气它们在同一台计算机上运行，要使前者 快于后者，n至少要多大？

分析：要使前者快于后者，即要求满足100n2<2n的n。由于1001?和211这两个函数都是单 调增加函数，随着n的增大，211的递增速度比100子快。在n>=l的整数情况下，可测出当 n>=15时，lOOn%?11 (可以编一个程序进行测试)。所以要使前者快于后者，n至少要大于 等于15o 【例6】当n充分大时，按从小到大的次序对下列时间排序：

(1) (2) (3) (4)

Ti(n)=5n2+10n+61gn T2(n)=3n2+100n+31gn T3(n)=8n2+3 Ign T4(n)=2n2+6000nlgn

分析：为了比较两个同数量级算法的优劣，需突出主项的常数因了，而将低次的项用大“O” 的记 号进行表示。则 T1 (n)=5n2+10n+61gn=5n2+O(n) , T2(n)=3n2+100n+31gn=3n2+O(n),

T3(n)=8n2+31gn= 8n2+O(lgn), T4(n)=2n2+6000nlgn=2n2+O(nIgn)0 当 n 足够大时，T((n)、丁血)、 T3(n)、T?n)的时间复杂度都为0(F),虽然它们的数量级相同，但他们主项的系数还是有区 别。因为T?n)主项常数因了

顺序为：T4(n)、T2(n).「(n)、T3(n)o

【例 7]设三个函数 f、g、h 分别为：Hn)=100n'+rr+100、g(n)=25n'+50n\\ h(n)=i? 5+50nlgn, 请判

断下列关系是否成立：

(1) f(n)=O (g(n))

分析：

(2) h(n)=O (n15)

(3) h(n)=O (nlgn)

(1) lim f{n)/g(n)=lim( 100n^+n2+100)/(25n '+50n2)=4,即 f(n)和 g(n)的数量级相同。

所以(1 ) f(n)= O (g(n))成立。

(2) h(n)的数量级取决于r?5和nlgn, 50是与n无关的常数因子,可以忽略。因为 小 的 数量级大

于 Ign,也大于 nlgn,即 lim h(n)/n''=lim (n‘'+50nlgn)/n\所以(2) h(n)=O (n15) 成立。

(3) lim h(n)/nlgn=lim(n15+50nlgn)/nlgn=oo,所以(3) h(n)=O (nlgn)不成立。

【例8】将一维数组中的元素逆置的算法如下，试分析其时间频度及时间发杂度。

void exchange (int a[],int n)

{

fbt (int i=0; i<=n/2-l;i++)

(

int t=a[i]; a[i]=a[n-i-l]; a[n-i-l]=t; } }

答：时间频度为T(n)=3n/2,当n充分大时，n的系数3/2可以忽略不计，所以其时间夏杂度 为 O(n)o

【例9]将n个元素按升序排列的算法如下，试分析其时间频度及时间复杂度。

void sort(int a[],int n)

int i,j,k,t;

fbt (i=O;i