第一章  概论

一、名词解释

数据表示   2.数据处理   3.数据   4.数据元素  5.逻辑关系  6.逻辑结构7.结构

8.运算   9.基本运算   10.存储结构   11.顺序存储结构   12.链式存储结构

13.索引存储结构   14.散列存储结构   15.算法   16.运行终止的程序可执行部分

17.伪语言算法 18.非形式算法 19.时空性能 20.时间复杂性 21.数据结构

二、填空题

1.计算机专业人员必须完成的两项基本任务是：_________和__________。

2.数据在计算机存储器中的存在形式称为_________。

3.概括地说，数据结构课程的主要内容包括: 数据的__________、定义在_________、数据的__________的实现。此外，该课程还要考虑各种结构和实现方法的­­­__________。

4.由一种__________结构和一组__________构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。

5.存储结构是逻辑结构的__________实现。

6.数据表示任务是逐步完成的，即数据表示形式的变化过程是__________->__________->__________。

7.数据处理任务也是逐步完成的，即转化过程是__________->__________->__________。

8.从数据结构的观点看，通常所说的"数据"应分成三个不同的层次，即__________、__________和__________。

9.根据需要，数据元素又被称为__________、__________、__________或__________。

10.在有些场合下，数据项又称为__________或__________，它是数据的不可分割的最小标识单位。

11.从某种意义上说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据

可由若干个__________构成，数据元素可由若干个__________构成。

12.根据数据元素之间关系的不同特性，通常有__________、_________、__________、__________四类基本逻辑结构，它们反映了四类基本的数据组织形式。

13.根据操作的效果，可将运算分成以下两种基本类型：

①__________型运算，其操作改变了原逻辑结构的“值”，如结点个数、某些结点的内容等；

②__________型运算，其操作不改变原逻辑结构，只从中提取某些信息作为运算的结果。

14.将以某种逻辑结构S为操作对象的运算称为“__________”，简称“__________”。

15.一般地，可能存在同一逻辑结构S上的两个运算A和B，A的实现需要或可以利用B，而B的实现不需要利用A。在这种情况下，称A可以“__________”为B。

16.存储实现的基本目标是建立数据的__________。

17.一般地，一个存储结构包括__________、__________、__________三个主要部分。

18.通常，存储结点之间可以有__________、__________、__________、_________四种关联方式，称为四种基本存储方式。

19.可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑

结构S中数据元素之间的逻辑关系。由此得到的存储结构，称为____________________或__________。

20.一个运算的实现是指一个完成该运算功能的__________。运算实现的核心是处

理步骤的规定，即___________。

21.任何算法都必须用某种语言加以描述。根据描述算法的语言的不同，可将算法分

为：___________、___________、___________三类。

22.数据结构课程着重评论算法的___________，又称为“___________”。

23.通常从___________、___________、___________、___________等几方面评价算法的(包括程序)的质量。

24.一个算法的时空性能是指该算法的___________和______________________，前者是算法包含的___________，后者是算法需要的___________。

25.通常采用下述办法来估算求解某类问题的各个算法在给定输入下的计算量：

①     根据该类问题的特点合理地选择一种或几种操作作为“___________”；

②     确定每个算法在给定输入下共执行了多少次___________，并将此次数规定为该算法在给定输入下的___________。

26.通常，一个算法在不同输入下的计算量是不同的。则可用以下两种方式来确定一个算法的计算量：

①     以算法在所有输入下的计算量的最大值作为算法的计算量，这种计算量称为算法的________或___________。

②     以算法在所有输入下的计算量的加权平均值作为算法的计算量，这种计算量称为算法的___________或___________。

27.最坏情况时间复杂性和平均时间复杂性统称为___________或___________。

28.在一般情况下，一个算法的时间复杂性是___________的函数。

29.一个算法的输入规模或问题的规模是指___________。

30.常见时间复杂性的量级有：常数阶O(___________)、对数阶O(___________)、线性阶O (___________)、平方阶O(___________)、和指数阶O(___________)。通常认为，具有指数阶量级的算法是___________，而量级低于平方阶的算法是___________的。

31.数据结构的基本任务是数据结构的___________和___________。

32.数据结构的课程的主要内容可以概括为：___________、___________、___________和___________。

33.___________与数据元素本身的内容和形式无关。

34.从逻辑关系上讲，数据结构主要分为两大类，它们是___________和___________。

35.程序段“for(i=l;i<=n;i++){k++;for(j=1;j<=n;j++)l+=k;}”的时间复杂度T(n)= ___________。

36.程序段“i=1;while(i<=n)i=i*2;”的时间复杂度T(n)= ___________。

三、单项选择题

1.以下说法错误的是

①用数字式计算机解决问题的实质是对数据的加工处理

②程序设计的实质是数据处理

③数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式

④运算实现是完成运算功能的算法，或这些算法的设计

⑤数据处理方式总是与数据某种相应的表示形式相联系，反之亦然

2.根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的

数据组织形式。以下解释错误的是                                 (   )

①集合中任何两个结点之间都有逻辑关系但组织形式松散

②线性结构中结点按逻辑关系依次排列形成一条"锁链"

③树形结构具有分支、层次特性，其形态有点像自然界中的树

④图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接

3.关于逻辑结构，以下说法错误的是                               (   )

①逻辑结构与数据元素本身的形成、内容无关

②逻辑结构与数据元素的相对位置有关

③逻辑结构与所含结点个数无关

④一些表面上很不相同的数据可以有相同的逻辑结构

⑤逻辑结构是数据组织的某种"本质性"的东西

4.根据操作的效果，可将运算分成加工型运算、引用型运算两种基本类型。对于表格

处理中的五种功能以下解释错误的是                               (   )

①查找引用型运算，功能是找出满足某种条件的结点在s(线形结构)中的位置

②读取引用型运算 功能是读出s(线形结构)中某指定位置结点的内容

③插入引用型运算，功能是在s(线形结构)的某指定位置上增加一个新结点

④删除加工型运算，功能是撤消s(线形结构)某指定位置上的结点

⑤更新加工型运算，功能是修改s(线形结构)中某指定结点的内容

5.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是  (   )

①存储结点每个存储结点可以存放一个或一个以上的数据元素

②数据元素之间关联方式的表示 也就是逻辑结构的机内表示

③附加设施，如为便于运算实现而设置的“哑结点”等等

6.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是

①每个存储结点只能存放一个数据元素                        (   )

②数据元素之间的关联方式可由存储结点之间的关联方式直接表达

③一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级

④语言级描述可经编译自动转换成机器级 因此也可以看成是一种机内表示

7.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质

量。以下解释错误的是                                          (   )

①正确性 算法应能正确地实现预定的功能(即处理要求)

②易读性 算法应易于阅读和理解 以便于调试 修改和扩充

③健壮性 当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果

④高效性 即达到所需要的时间性能

8.对于数据结构课程的主要内容，以下解释正确的是                (   )

①数据结构的定义，包括逻辑结构、存储结构和基本运算集

②数据结构的实现，包括存储实现、运算实现和基本运算集

③数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储

选择

9，与数据元素本身的形式、内容、相对位置、个数无关的是数据的          (   )

①存储结构    ②存储实现       ③逻辑结构        ④运算实现10顺序存储结构                                                       (   )

①仅适合于静态查找表的存储

②仅适合于动态查找表的存储

③既适合静态又适合动态查找表的存储

④既不适合静态又不适合动态查找表的存储

11.算法的时间复杂度，都要以通过算法中执行频度最高的语句的执行次数来确定这种

观点                                                                 (   )

①正确               ②错误

12以下说法正确的是                                                  (   )

①所谓数据的逻辑结构指的是数据元素之间的逻辑关系。

②逻辑结构与数据元素本身的内容和形式无关

③顺序文件只适合于存放在磁带上，索引文件只能存放在磁盘上

④基于某种逻辑结构之上的运算，其实现是惟一的

13以下说法正确的是                                                  (   )

①数据元素是数据的最小单位

②数据项是数据的基本单位

③数据结构是带有结构的各数据项的集合

④数据结构是带有结构的数据元素的集合

14以下说法错误的是                                                  (   )

①所谓数据的逻辑结构指的是数据元素之间的逻辑关系的整体

②数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的

③数据结构、数据元素、数据项在计算机中的映象分别称为存储结构、结点、数据域

④数据项是数据的基本单位

15通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着     (   )

①数据元素具有同一特点

②不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致

③每个数据元素都一样

④数据元素所包含的数据项的个数要相等

四、简答及应用

1数据与数据元素有何区别？

2·为什么说数据元素之间的逻辑关系是数据内部组织的主要方面?

3·逻辑结构与存储结构是什么关系?

4·运算与运算的实现是什么关系?有哪些相同点和不同点？

5，类C语言与标准C语言的主要区别是什么?

五、算法设计

1、  设计求解下列问题的类C语言算法，并分析其最坏情况时间复杂性及其量级。

（1）       在数组A[1..n]中查找值为K的元素,若找到则输出其位置i(1<=i<=n),否则输出0作为标志。

（2）       找出数组A[1..n]中元素的最大值和次最大值（本小题以数组元素的比较为标准操作）。

 

 

第一章       绪论参考答案

一、名词解释  （略）

二、填空题

 1、数据表示    数据处理                 2、机内表示

 3、逻辑结构    逻辑结构上的基本运算     存储结构和运算     评价和选择

 4、逻辑性    基本运算                   5、存储

 6、机外表示    逻辑结构     存储结构

 7、处理要求    基本运算和运算     算法

 8、数据    数据元素    数据项

 9、元素    结点    顶点    记录

 10、字段    域                          11、数据元素   数据项

 12、集合    线性结构     树形结构    图状结构

 13、加工    引用                        14、定义在S上的运算      S上运算

 15、归纳                                16、机内表示

 17、存储结点    数据元素之间关联方式的表示      附加设施

 18、顺序存储方式    链式存储方式    索引存储方式    散列存储方式

 19、给定逻辑结构S的存储实现      存储映象

 20、程序    算法设计

 21、运行终止的程序可执行部分      伪语言算法    非形式算法

 22、时空性能    算法分析            23、正确性能  易读性   健壮性  高效性

 24、时间性能（或时间效率）  空间性能（或空间效率）   计算量    存储量

 25、标准操作    标准操作    计算量

 26、最坏情况时间复杂性   最坏情况时间复杂度  平均时间复杂性  平均时间复杂度

 27、时间复杂性    时间复杂度              28、算法输入规模

 29、作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数

 30、1   log₂n  n   n²    2ⁿ   实际不可计算     高效

 31、设计     实现

 32、数据结构的定义     数据结构的实现   数据结构的评价   选择

 33、数据的逻辑结构                     34、线性结构    非线性结构

 34、O（n²）                            36、o(log₂n)。

三、单项选择题

1.②     2.①     3.②     4.③     5.①     6.②     7.④    8.③    9.③

10.③    11.②   12.②    13.④   14.④   15.②

四、简答及应用

1．  凡能被计算机存储、加工的对象通称为数据。

数据元素是数据的基本单位，在程序中作为一个整体而加以考虑和处理。换句话说，

数据元素被当作运算的基本单位，并且通常具有完整确定的实际意义。根据需要，数据

元素又被称为元素、结点、顶点或记录。

在很多情况下，数据元素又是由数据项组成的，但数据项通常不肯有完整确定的实际意义，或不被当作一个整体对待。在有些场合下，数据项又称为字段或域。它是数据的不可分割的最小标识单位。

 从某种意义上说，数据，数据元素和数据实际反映了数据组织的三个层次，数据可由若干个数据元素构成，而数据元素又可由若干个数据项构成。

２、所谓逻辑关系是指数据元素之间的关联方式或称“邻接关系”。数据元素之间逻辑关系的整体称为逻辑结构。数据的逻辑结构就是数据的组织形式。关于逻辑结构的以下几点需特别注意：

（１）、逻辑结构与数据元素本身的形成、内容无关。

（２）、逻辑结构与数据元素的相对位置无关。

（３）、逻辑结构与所含结点个数无关。

由此可见，一些表面上很不相同的数据可以有相同的逻辑结构，因此，逻辑结构是数据组织的某种“本质性”的东西，是数据内部组织的主要方面。

　　　　３、逻辑结构反映数据元素之间的逻辑关系，而存储结构是数据结构在计算机中的表示，它包括数据元素的表示及其关系的表示。

　　　　４、一般地，运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。一个运算的实现是指一个完成该运算功能的程序。

　　　　　　相同点：运算与运算的实现都能完成对数据的“处理”或某种特定的操作。

　　　　　　不同点：运算只描述处理功能，不包括处理步骤和方法，而运算实现的核心是处理步骤。

　　　　５、类Ｃ语言基本上是标准Ｃ语言的简化。类Ｃ语言与标准Ｃ语言的主要区别如下：

（１）   局部量的说明可以省略（但形参表中及函数类型的说明需保留），重要的变量需在注解中用文字说明基类型和作用。

（２）   分情形语句可以采用下述形式：

　switch

  {   case  条件１：语句序列１；break;

case  条件2：语句序列2；break;

……

case  条件n：语句序列n；break;

default: 语句序列n+1;

}

其中“default: 语句序列n+1;”可以省略。

（３）   不含goto语句，增加了一个出错处理语句error（字符串），其功能是终止它所在算法的执行并回送表示出错信息的字符串。

（４）   输入输出语句有：

输入语句 scanf([格式串]，变量度，……，变量n);

输出语句 printf([格式串]，变量度，……，变量n);

           (５)  类Ｃ语言的形参书写比标准Ｃ语言简单，如int abc (int a,int b,int c)可以简写为 int abc(int a,b,c)。

　　　五．算法设计

　　　　１．（１）int locate(dataytpe A[1..n],dateytpe k)

                 {  i=n;

                    while ((I<=n)&&(A[i]!=k)) I++;

                    if (I<=n)   return(i);

                    else       return(o);

                  }

             当查找不成功时，总是比较n+1次，所以，最坏时间复杂性为n+1。其量

T（n）=O(n).

 

（２）Void CZ_max(datatype A[n],x,y)

       { x=A[1]; y=A[1];

        for(I=2;I<=n;I++)

          if(x<A[i]{y=x;x=A[i];}          

          else if(y<A[i] y=A[i];            

}

若经条件判断语句为标准操作，则最坏情况时间复杂性为n-1。其量级为

T(n)=O(n).