数据结构概论：填空题

1.计算机专业人员必须完成的两项基本任务是：(数据表示)和(数据处理)。

2.数据在计算机存储器中的存在形式称为(机内表示)。

3.概括地说，数据结构课程的主要内容包括: 数据的(逻辑结构)、定义在(逻辑结构上的基本运算)、数据的(存储结构和运算)的实现。此外，该课程还要考虑各种结构和实现方法

的(评价和选择)。

4.由一种(逻辑)结构和一组（基本运算）构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。

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

6.数据表示任务是逐步完成的，即数据表示形式的变化过程是（机外表示）->（逻辑结构）->（存储结构）。

7.数据处理任务也是逐步完成的，即转化过程是（处理要求）->（基本运算和运算）->（算法）。

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

9.根据需要，数据元素又被称为（元素）、（结点）、（顶点）或（记录）。

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

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

12.根据数据元素之间关系的不同特性，通常有（集合）、（线性结构）、（树形结构）、（图状结构）四类基本逻辑结构，它们反映了四类基本的数据组织形式。

13.根据操作的效果，可将运算分成以下两种基本类型：
①（加工）型运算，其操作改变了原逻辑结构的“值”，如结点个数、某些结点的内容等；
②（引用）型运算，其操作不改变原逻辑结构，只从中提取某些信息作为运算的结果。

14.将以某种逻辑结构S为操作对象的运算称为“（定义在S上的运算）”，简称“（S上的运算）”。


15.一般地，一个存储结构包括（存储结点）、（数据元素之间关联方式的表示）、（附加设施）三个主要部分。

16.通常，存储结点之间可以有（顺序存储方式）、（链式存储方式）、（索引存储方式）、（散列存储方式）四种关联方式，称为四种基本存储方式。

17.可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑结构S中数据元素之间的逻辑关系。
由此得到的存储结构，称为（给定逻辑结构S的存储实现）或（存储映象）。

18.一个运算的实现是指一个完成该运算功能的（程序）。运算实现的核心是处理步骤的规定，即（算法设计）。

19.数据结构课程着重评论算法的（时空性能），又称为“（算法分析）”。

20.通常从（正确性）、（易读性）、健壮性、（高效性）等几方面评价算法的(包括程序)的质量。

21.一个算法的时空性能是指该算法的时间性能（或时间效率）和空间性能（或空间效率），前者是算法包含的（计算量），后者是算法需要的（存储量）。

22.通常采用下述办法来估算求解某类问题的各个算法在给定输入下的计算量：
① 根据该类问题的特点合理地选择一种或几种操作作为“（标准操作）”；
② 确定每个算法在给定输入下共执行了多少次（标准操作），并将此次数规定为该算法在给定输入下的（计算量）。

23.通常，一个算法在不同输入下的计算量是不同的。则可用以下两种方式来确定一个算法的计算量：
① 以算法在所有输入下的计算量的最大值作为算法的计算量，这种计算量称为算法的（最坏情况时间复杂性）或（最坏情况时间复杂度）。
② 以算法在所有输入下的计算量的加权平均值作为算法的计算量，这种计算量称为算法的（平均时间复杂性）或（平均时间复杂度）。

24.在一般情况下，一个算法的时间复杂性是（算法输入规模）的函数。

25.一个算法的输入规模或问题的规模是指（作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数）。


26.数据结构的基本任务是数据结构的（设计）和（实现）。

27.数据结构的课程的主要内容可以概括为：（数据结构的定义）、（数据结构的实现）、（数据结构的评价）和（选择）。

28.（数据的逻辑结构）与数据元素本身的内容和形式无关。

29.从逻辑关系上讲，数据结构主要分为两大类，它们是（线性结构）和（非线性结构）。