练习题1

1．单项选择题

（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）计算机算法必须具备输入、输出和（　）等5个特性。

A．可行性、可移植性和可扩充性

B．可行性、确定性和有穷性

C．确定性、有穷性和稳定性

D．易读性、稳定性和安全性

（7）算法分析的目的是（　）。

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

B．研究算法中的输入和输出的关系

C．分析算法的效率以求改进

D．分析算法的易懂性和文档性

（8）算法分析的两个主要方面是（　）。

A．空间复杂性和时间复杂性

B．正确性和简明性

C．可读性和文档性

D．数据复杂性和程序复杂性

（9）某算法的时间复杂度为O（n2），表明该算法的（　）。

A．问题规模是n2

B．执行时间等于n2

C．执行时间与n2成正比

D．问题规模与n2成正比

（10）某算法的空间复杂度为O（1），表明执行该算法时（　）。

A．不需要存储空间

B．需要的临时存储空间为常量

C．需要的存储空间恰好为1

D．需要的临时存储空间为1

2．填空题

（1）数据结构包括数据的（ ① ）、数据的（ ② ）和数据的（ ③ ）三个方面的内容。

（2）数据结构按逻辑结构可分为两大类，它们分别是（ ① ）和（ ② ）。

（3）数据结构被形式地定义为（D，R），其中，D是（ ① ）的有限集合，R是D上的（ ② ）的有限集合。

（4）在线性结构中，开始元素（ ① ）前驱元素，其余每个元素有且只有一个前驱元素；最后一个元素（ ② ）后继元素，其余每个元素有且只有一个后继元素。

（5）在树状结构中，树根结点没有（ ① ）结点，其余每个结点有且只有（ ② ）个前驱结点；叶子结点没有（ ③ ）结点，其余每个结点的后继结点数可以是（ ④ ）。

（6）在图形结构中，每个结点的前驱结点个数和后继结点个数可以是（　）。

（7）数据的存储结构主要有4种，它们分别是（ ① ）、（ ② ）、（ ③ ）和（ ④ ）存储结构。

（8）一个算法的效率可分为（ ① ）效率和（ ② ）效率。

（9）在分析算法时，其时间复杂度是（　）的函数。

（10）在分析算法时，其空间复杂度是指执行该算法时所需（　）的大小。

3．简答题

（1）简述数据结构中运算描述和运算实现的异同。

（2）以下各函数是算法中语句的执行频度，n为问题规模，给出对应的时间复杂度。

T1（n）=nlog2n—1000log2n

T2（n）=nlog23—1000log2n

T3（n）=n2—1000log2n

T4（n）=2nlog2n—1000log2n

（3）分析下面程序段中循环语句的执行次数。

      int j=0,s=0,n=100;
      do
      {    j=j+1;
           s=s+10 ∗ j;
      } while(j<n && s<n);

（4）执行下面的语句时，语句s++的执行次数为多少？

      int s=0;
      for (i=1;i<n—1;i++)
           for (j=n;j>=i;j——)
                    s++;

（5）设n为问题规模，求以下算法的时间复杂度。

（6）设n为问题规模，是一个正偶数，试计算以下算法结束时m的值，并给出该算法的时间复杂度。