一个算法的存储空间包括输入数据、程序和辅助变量所占用的空间，用空间复杂度度量算法所需的存储空间。在对算法进行空间复杂度分析时，只需考查辅助变量所占用的空间。算法的空间复杂度也是问题规模n的函数f（n），算法的空间度量记作：

若额外空间对于输入数据量来说是常数，则称此算法为原地工作或就地工作。若算法所需的存储量依赖特定的输入，则通常以最坏的情况计算其存储量。为了实现递归需要一个递归栈，递归算法的空间复杂度需要根据递归深度来确定。

例1.8　用C++语言描述的数组求和算法如下，计算其空间复杂度。

【解】该程序段的函数体内定义了sum和i两个辅助变量空间，与问题的规模n无关，算法的空间复杂度为O（1）。

例1.9　用C++语言描述的算法如下，计算f（a，n，0）的空间复杂度。

【解】设f（a，n，k）的临时空间大小为S（k），其中定义了一个辅助变量i，其通项公式为

f（a，n，0）需要的辅助空间为

f（a，n，0）的空间复杂度为O（n）。

一、选择

1.数据结构是一门研究非数值计算的程序设计问题中计算机的（　　），以及它们之间的（　　）和操作的学科。

A.操作对象

B.数据映象

C.关系

D.算法

2.逻辑上数据结构可分为（　　）。

A.动态结构和静态结构

B.线性结构和非线性结构

C.紧凑结构和非紧凑结构

D.内部结构和外部结构

3.集合结构的数据元素之间是（　　）。

A.一对一关系

B.一对多关系

C.多对多关系

D.空关系

4.算法分析考虑（　　）两方面的问题。

A.正确性和空间复杂度

B.易读性和健壮性

C.数据复杂性和程序复杂性

D.时间复杂度和空间复杂度

5.数据采用链式存储结构时，要求（　　）。

A.每个结点占用一片连续的存储空间

B.所有结点占用一片连续的存储空间

C.每个结点后继结点的数量与指针域的数量相等

D.结点的最后一个数据域是指针类型

6.算法分析的目的是（　　）。

A.找出数据结构的合理性

B.分析算法的效率

C.研究算法中输入和输出的关系(www.daowen.com)

D.分析算法的易理解性

7.（　　）是算法设计的要求。

A.正确性

B.确定性

C.输入和输出

D.有穷性

8.算法的时间复杂度与（　　）有关。

A.计算机硬件

B.程序设计语言

C.机器语言的质量

D.问题的规模

9.用C++语言描述的算法如下，其时间复杂度为（　　）。

A.O(n)

B.O(n2)

C.O(n/2)

D.O(1)

二、填空

1.算法的五大特性为有穷性、确定性、输入、输出和________。

2.顺序存储结构用一组地址连续的空间存放数据元素，逻辑上相邻的数据元素，物理上________相邻。链式存储结构用一组地址任意的空间存放数据元素，逻辑上相邻的数据元素，物理上________相邻。

3.数据结构在计算机中的表示包括数据结构中数据________和数据元素之间________的表示。

4.算法效率的度量方法有____________和____________。

5.一个没有循环的算法中的基本运算次数与问题规模n无关，其时间复杂度记为________。

三、简答

1.简述数据结构的4种形式以及各种形式的特点。

2.简述数据结构、数据类型和抽象数据类型的区别。

3.设有3个表示算法频度的函数分别为f（n）=8n3+100n2+2 000，g（n）=8n3+3 000n2，h（n）=n1.5+5000nlog2 n，试求它们对应的时间复杂度。

4.设有以下3个函数f（n）=21n4+2n2+1000，g（n）=15n4+500n2，h（n）=5000n3.5+nlog2 n判断下列说法是否正确：

（1）f（n）的时间复杂度是O（g（n））；

（2）h（n）的时间复杂度是O（f（n））；

（3）g（n）的时间复杂度是O（h（n））；

（4）h（n）的时间复杂度是O（n3.5）；

（5）h（n）的时间复杂度是O（nlog2 n）。

四、计算

1.计算下列算法的时间复杂度。

2.已知n是偶数，试计算执行下列算法后m的值和该算法的时间复杂度。

3.已知n为2的幂，且n＞2，试求下列算法的时间复杂度和变量count的值。