数据结构第一章参

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              C. n*(n+1)/2           D. 不确定

分析： 

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;

while (i<=n)

i += 2;

（5）k=100,i=10;

     do {

     if (i        i++;

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

     for (j=0; j            sum += j;

（7）y=0;

while (y*y*y <= n)

y++;

（8）int i=0;

while(ireturn i==n?-1:i ;

答案：    

    (1)  O(n2)

    (2)  O(n)

    (3)  O(logn)

    (4)  O(n)

    (5)  O(1)

    (6)  O(1)

    (7)  O(n1/3)

    (8)  O(n)

4.将整数设计为一个类，将整数相关的常见数算设计为类的接口并进行实现，如求与给定值的最大公约数、最小公倍数、枚举所有因子等。

解：

#include "math.h"

#include "vector"

using std::vector;

//定义自然数类

class NaturalNumber{

public:  

    NaturalNumber(unsigned long int n=0):num(n){}

    unsigned long int GreatestCommonDivisor(NaturalNumber & nn);//求解最大公约数

    unsigned long int LeaseCommonMultiple(NaturalNumber & nn);//求解最小公约数

    int GetFactors(vector & factors);    //求所有因子，存储在factors中，函数返回因子个数

    unsigned long int GetNumber(){return num;}

    //……其它外部接口

private:

    unsigned long int EUCLID(NaturalNumber & n); //欧几里德算法求解最大公约数

    unsigned long int num; //存储真正的自然数

};

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

unsigned long int NaturalNumber :: EUCLID(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){

        m = n; n = r; r = m % n;

    }

    return n;

}

//返回最大公约数

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

{

    return EUCLID(nn);

}

//返回最小公倍数

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

{

    unsigned long int temp = EUCLID(nn);

    return num * nn.GetNumber() / temp;

}

int NaturalNumber :: GetFactors( vector & factors )

{

    int t=0;

    int m = sqrt((double)num);

    vector bigfactors;

    for (unsigned long int i=1;i    {

        if ( 0 == num%i ) {t+=2; factors.push_back(i);bigfactors.push_back(num/i);}

    }

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

vector ::iterator it=bigfactors.end();

    if (bigfactors.size()) do

    {

        it--;

        factors.push_back(*it);

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

    return t;

}

void main()

{

    NaturalNumber p(1);

    int xx = p.GreatestCommonDivisor(NaturalNumber(120));

    int yy = p.LeaseCommonMultiple(NaturalNumber(120));

vector f;

    int t = p.GetFactors(f);

}