数据结构练习题第一章概论 .pdfVIP

数据结构练习题第一章概论

第一章概论

一、名词解释

1.数据表示

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为操作对象的运算称为“_定义在S上的运

算_”，简称“_S上运算_”。

15.一般地，可能存在同一逻辑结构S上的两个运算A和B，A的

实现需要或可以利用B，而B的实现不需要利用A。在这种情况下，称

A可以“_归纳_”为B。

16.存储实现的基本目标是建立数据的_机内表示_。

17.一般地，一个存储结构包括_存储结点__、_数据元素之间关联

方式的表示_、_附加设施_三个主要部分。

18.通常，存储结点之间可以有_顺序存储方式_、_链式存储方式_、

_索引存储方式_、_散列存储方式_四种关联方式，称为四种基本存储

方式。

19.可用任何一种存储方式所规定的存储结点之间的关联方式来间

接表达给定逻辑

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

给定逻辑结构S的存储实现__或_存储映象_。

20.一个运算的实现是指一个完成该运算功能的_程序_。运算实现

的核心是处

理步骤的规定，即_算法设计_。

21.任何算法都必须用某种语言加以描述。根据描述算法的语言的

不同，可将算法分

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

_三类。

22.数据结构课程着重评论算法的_时空性能_，又称为“_算法分析

_”。

23.通常从_正确性能_、_易读性_、_健壮性_、_高效性_等几方面

评价算法的(包括程序)的质量。

24.一个算法的时空性能是指该算法的_时间性能_和_空间性能_，

前者是算法包含的_计算量，后者是算法需要的_存储量_。

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

下的计算量：

①根据该类问题的特点合理地选择一种或几种