数据结构与STL答案 .pdfVIP

《数据结构与STL》

教师手册

ver0.1

肖波徐雅静莫骁肖晶

2010年9月

目录

习题

习题

习题

习题

习题

习题

习题

习题

习题1

1.填空题

（1）（___________）是指数据之间的相互关系，即数据的组织形式。通常人们认为它包含

三个方面的内容，分别为数据的（___________）、（___________）及其运算。

答案：数据结构逻辑结构存储结构

（2）（___________）是数据的基本单位，在计算机程序中通常作为一个整体进行处理。

答案：数据元素

（3）数据元素之间的不同逻辑关系代表不同的逻辑结构，常见的逻辑结构有（___________）、

（___________）、（___________）和（___________）。

答案：集合线形结构树结构图结构

（4）数据的存储结构考虑的是如何在计算机中存储各个数据元素，并且同时兼顾数据元素

间的逻辑关系。基本的存储结构通常有两大类：（___________）和（___________）。

答案：顺序存储结构链式存储结构

（5）通常一个问题可以有多种不同的算法，但每个算法必须满足5个准则：输入、输出、

（___________）、（___________）和（___________）。

答案：有穷性确定性可行性

（6）通常通过衡量算法的（___________）复杂度和（___________）复杂度来判定一个算

法的好坏。

答案：时间空间

（7）常见时间复杂性的量级有：常数阶O（___________）、对数阶O（___________）、线

性阶O（___________）、线性对数阶O（___________）、平方阶O（___________）、和指数

阶O（___________）。通常认为，当问题规模较大时，具有（___________）量级的算法是

不可计算的。

答案：1lognnnlognn22n指数

（8）STL提供的标准容器有顺序容器、（___________）和（___________）。

答案：排序容器哈希容器

（9）算法可认为是STL的精髓，所有算法都是采用（___________）的形式提供的。

答案：函数模版

（10）通常认为STL由空间管理器、迭代器、泛函、适配器、（___________）和（___________）

等六部分构成，其中前面四部分服务于后面两部分。

答案：容器算法

2.选择题

（1）以下结构中，（）属于线性结构。

A.树B.图C.串D.集合

（2）算法描述的方法有很多种，常常将（）称为算法语言。

A.自然语言B.流程图C.伪代码D.程序设计语言

（3）现实生活中的家族谱，可认为是一种（）结构。

A.树B.图C.集合D.线性表

（4）手机中存储的电话号码簿，可认为是一种（）结构。

A.树B.图C.集合D.线性表

（5）NP问题是（）。

A.非多项式时间问题，即非P问题B.非确定性多项式时间问题

C.P问题的子集D.与P问题不相交的

（6）以下（）不属于STL的顺序容器。

A.向量（vector）B.列表（list）C.队列（queue）D.双端队列（deque）

（7）下面带有@标记的语句的频度(n10)是（）。

for(inti=0;in-1;i++)

for(intj=i+1;jn;j++)

@coutijendl;

A.n*(n-1)/2B.n*n/2C.n*(n+1)/2D.不确定

分析：

212

010

11(1)

2

nnn

ijii

ninn

...

==+=

.

ΣΣ=Σ..=

3.分析以下程序段的时间复杂度。

（1）for(i=l;i=n;i++){

k++;

for(j=1;j=n;j++)

m+=k;

}

（2）for(i=l;i=n;i++)

k++;

for(j=1;j=n;j++)

m+=k;

（3）i=1;

while(i=n)

i*=2;

（4）i=1;

w