数据结构课后答案 - 北邮

习题1

1. 填空题

（1）（___________）是指数据之间的相互关系，即数据的组织形式。通常人们认为它包含三个方面的内容，分别为数据的（___________）、（___________）及其运算。

答案：数据结构 逻辑结构 存储结构 （2）（___________）是数据的基本单位，在计算机程序中通常作为一个整体进行处理。 答案：数据元素 （3）数据元素之间的不同逻辑关系代表不同的逻辑结构，常见的逻辑结构有（___________）、（___________）、（___________）和（___________）。

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

（4）数据的存储结构考虑的是如何在计算机中存储各个数据元素，并且同时兼顾数据元素间的逻辑关系。基本的存储结构通常有两大类：（___________）和（___________）。 答案：顺序存储结构 链式存储结构

（5）通常一个问题可以有多种不同的算法，但每个算法必须满足5个准则：输入、输出、（___________）、（___________）和（___________）。 答案：有穷性 确定性 可行性

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

答案：时间 空间

（7）常见时间复杂性的量级有：常数阶O（___________）、对数阶O（___________）、线性阶O（___________）、线性对数阶O（___________）、平方阶O（___________）、和指数阶O（___________）。通常认为，当问题规模较大时，具有（___________）量级的算法是不可计算的。

答案：1 logn n nlogn n2 2n 指数

（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）下面带有@标记的语句的频度(n>10)是（ ）。

for(int i=0;i

for(int j=i+1;j

@cout<

A. n*(n-1)/2

B. n*n/2

n?2n?1n?2分析：??1??n?1?i?(n?1)n?0j?i?1i?02

i3. 分析以下程序段的时间复杂度。 （1）for (i=l; i<=n; i++) {

k++;

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

m += k;

} （3）i=1;

while (i<=n)

i *= 2;

（5）k=100,i=10; do { if (i

i++;

}while (i

while (y*y*y <= n)

y++;

（8）int i=0;

while(i

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

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

k++;

for (j=1; j<=n; j++) m += k; （4）i=1;

while (i<=n)

i += 2;

（6）for (i=0; i<100; i++) for (j=0; j

sum += j;

答案：

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

O(n) O(n) O(logn) O(n)

2

(5) O(1) (6) O(1)

(7) O(n1/3) (8) O(n)

4. 将整数设计为一个类，将整数相关的常见数学运算设计为类的接口并进行实现，如求与

给定值的最大公约数、最小公倍数、枚举所有因子等。 解：

#include \#include %using std::vector;

//定义自然数类 class NaturalNumber{ public: };

//返回欧几里德算法求解最大公约数

unsigned long int NaturalNumber :: EUCLID(NaturalNumber & nn) { }

//返回最大公约数

unsigned long int NaturalNumber :: GreatestCommonDivisor(NaturalNumber & nn)

unsigned long int m = (num > nn.num) ? num : nn.num; //较大的自然数赋值给m unsigned long int n = (num < nn.num) ? num : nn.num; //较小的自然数赋值给n unsigned long int r = m % n; while (r != 0){ }

return n;

m = n; n = r; r = m % n; //……其它外部接口

unsigned long int EUCLID(NaturalNumber & n); //欧几里德算法求解最大公约数 unsigned long int num; //存储真正的自然数 NaturalNumber(unsigned long int n=0):num(n){}

unsigned long int GreatestCommonDivisor(NaturalNumber & nn);//求解最大公约数 unsigned long int LeaseCommonMultiple(NaturalNumber & nn);//求解最小公约数 int GetFactors(vector & factors); unsigned long int GetNumber(){return num;}

//求所有因子，存储在factors

中，函数返回因子个数

private:

{ }

//返回最小公倍数

unsigned long int NaturalNumber :: LeaseCommonMultiple(NaturalNumber & nn) { }

int NaturalNumber :: GetFactors( vector & factors ) { }

void main() { }

NaturalNumber p(1);

int xx = p.GreatestCommonDivisor(NaturalNumber(120)); int yy = p.LeaseCommonMultiple(NaturalNumber(120)); vector f; int t = p.GetFactors(f); int t=0;

int m = sqrt((double)num);

vector bigfactors; for (unsigned long int i=1;i

if ( m*m == num ) { t++; factors.push_back(m);}

vector ::iterator it=bigfactors.end(); if (bigfactors.size()) do {

it--;

factors.push_back(*it);

if ( 0 == num%i ) {t+=2; factors.push_back(i);bigfactors.push_back(num/i);} unsigned long int temp = EUCLID(nn); return num * nn.GetNumber() / temp; return EUCLID(nn);

}while (it!=bigfactors.begin()); return t;

习题2

1. 填空题

（1）在一个单链表中，已知每个结点包含data和next两个域，q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（___________）和（___________）操作。