[数据结构与算法(严蔚敏 C语言第二版)]第1章 绪论（课后习题+答案解析）

1. 简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

• 数据

• 数据是客观事物的符号表示，是所有能输人到计算机中并被计算机程序处理的符号的总称。数据是信息的载体，能够被计算机识别、存储和加工

• 数据元素

• 是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

• 数据项

• 是组成数据元素的、有独立含义的、不可分割的最小单位。

• 数据对象

• 是性质相同的数据元素的集合，是数据的一个子集。

• 数据结构

• 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是带“结构”的数据元素的集合，“结构”是指数据元素之间存在的关系。

• 逻辑结构

• 数据元素之间的逻辑关系，数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的，是从具体问题抽象出来的数学模型

• 存储结构

• 数据元素及其关系在计算机内存中的表示（又称映像、存储方式），数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。存储结构既要存储各数据元素的数据，又要存储数据元素之间的逻辑关系

• 抽象数据类型

• 抽象数据类型是指一个数学模型以及定义在此数学模型上得一组操作的总称，不考虑计算机内的具体存储结构和运算的具体实现算法

2. 试举一个数据结构的例子，叙述其逻辑结构和存储结构两个层次的含义及相互关系。

• 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。
• 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构;如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。
• 即相同的逻辑结构，可以对应不同的存储结构。

3. 简述逻辑结构的四种基本关系并画出它们的关系图。

• 集合结构：数据元素之间除了“属于同一个集合”的关系外，别无其他关系
• 线性结构：数据元素之间存在一对一的关系
• 树结构：数据元素之间存在一对多的关系
• 图结构或网状结构：数据元素之间存在多对多的关系
• 

4. 存储结构由哪两种基本的存储方法实现?

1. 顺序存储结构

• 顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述
• 顺序存储结构要求所有的元素依次存放在一片连续的存储空间中

2. 链式存储结构

• 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系使用指针来表示
• 链式存储结构通常借助于程序设计语言的指针类型来描述

5. 选择题

• (1)在数据结构中，从逻辑上可以把数据结构分成()。

• A.动态结构和静态结构
• B.紧凑结构和非紧凑结构
• C．线性结构和非线性结构
• D.内部结构和外部结构
• 答案：C
• 解析：

• 在数据结构中，从逻辑上可以把数据结构分成线性结构和非线性结构
• 图、树、集合等结构为非线性结构

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

• A.存储结构
• B.存储实现
• C.逻辑结构
• D.运算实现
• 答案：C
• 解析：

• 逻辑结构表示的是数据元素之间的逻辑关系，数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的，是从具体问题抽象出来的数学模型
• 运算实现与数据元素的形式、内容和个数有关，数据元素形式、内容和个数不同运算实现可能有所不同
• 存储结构和存储实现是数据元素在计算机内存中的表示和实现，与数据元素本身的形式、内容、相对位置、个数相关

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

• A. 数据具有同一特点
• B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
• C．每个数据元素都一样
• D．数据元素所包含的数据项的个数要相等
• 答案：C
• 解析

• 同一逻辑结构中的所有数据元素具有相同的特性，每个数据元素的数据项的个数相同且类型一致。数据元素数据项的内容可不同

• (4）以下说法正确的是()。

• A．数据元素是数据的最小单位
• B．数据项是数据的基本单位
• C．数据结构是带有结构的各数据项的集合
• D.一些表面上很不相同的数据可以有相同的逻辑结构
• 答案：D
• 解析：

• 数据项是组成数据元素的、有独立含义的、不可分割的最小单位。
• 数据的基本单位是数据元素
• 数据结构为数据元素及数据元素之间关系的集合

• (5）算法的时间复杂度取决于()。

• A.问题的规模
• B.待处理数据的初态
• C.计算机的配置
• D.A和 B
• 答案：D
• 解析：

• 算法的时间复杂度取决于问题的规模和待处理数据的初态，问题的规模越大时间复杂度越大，数据的初态不同算法所需的时间不同

• (6）以下数据结构中,()是非线性数据结构。

• A．树
• B.字符串
• C.队列
• D.栈
• 答案：A
• 解析：

• 字符串、队列、栈均为线性表中的一种，树结构为非线性结构

6. 试分析下列各个算法的时间复杂度