南邮数据结构课后答案

习题1

1. 填空题

（1）（___________）是指数据之间的相互关系，即数据的组织形式。通常人们认为它包含三个方面的内容，分别为数据的（___________）、（___________）及其运算。

答案：数据结构 逻辑结构 存储结构 （2）（___________）是数据的基本单位，在计算机程序中通常作为一个整体进行处理。 答案：数据元素 （3）数据元素之间的不同逻辑关系代表不同的逻辑结构，常见的逻辑结构有（___________）、（___________）、（___________）和（___________）。

答案：集合 线形结构 树结构 图结构

（4）数据的存储结构考虑的是如何在计算机中存储各个数据元素，并且同时兼顾数据元素间的逻辑关系。基本的存储结构通常有两大类：（___________）和（___________）。 答案：顺序存储结构 链式存储结构

（5）通常一个问题可以有多种不同的算法，但每个算法必须满足5个准则：输入、输出、（___________）、（___________）和（___________）。 答案：有穷性 确定性 可行性

（6）通常通过衡量算法的（___________）复杂度和（______

数 据 结 构B 期末试卷

班级 学号 姓名 得分

题号 分数 一 二 三 四 五 六 一、解答题：（共82分）

1、下列程序段或函数的时间复杂度。（10%）

（1） for (int k=0;k

for (int j=0;j

（3） int Prime(int n) （4）k=1; x=0;

{ int k=2 , x=(int)sqrt(n) ; do {

while (k<=x) { x++; k*=2; if (n % k= =0) break; }

k++; } while (k

if (k>x) return 1; else return 0; }

2、有A、B、C、D四个元素依次入栈，即入栈序列唯一，问共能得到多少种出栈序列？能否得到以下四种出栈序列：ABCD、BDAC、CBDA、DBAC。对能得到的序列，请写出Push、Pop序列；对不能得到的序列，请说明理由。（6%）

3、矩阵Am*n以行优先方式从1

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

第一章 绪论 一、选择题

1. 算法的计算量的大小称为计算的（ B ）。

A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（C ）

A．问题的规模 B. 待处理数据的初态 C. A 和B 3.计算机算法指的是（1C） ，它必须具备（2B） 这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（ B ） 。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A 和C. 5

第 1 章 绪 论

课后习题讲解

1. 填空

⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素

⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素

【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构

⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（ ）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性

⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模

⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为n*log2

第1章 绪论

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

答案：

数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，?}，字母字符数据对象是集合C={‘A’，‘B’，?，‘Z’， ‘a’，‘b’，?，‘z’}，学生基本信息表也可是一个数据对象。

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

逻辑结构：从逻辑关系上

第 1 章 绪 论

课后习题讲解

1. 填空

⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素

⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素

【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构

⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（ ）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性

⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模

⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为n*log2

第 1 章 绪 论

课后习题讲解

1. 填空

⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素

⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素

【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构

⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（ ）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性

⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模

⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为n*log2

第 1 章 绪 论

课后习题讲解

1. 填空

⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素

⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素

【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构

⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（ ）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性

⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模

⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为n*log2

第1章 绪论

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

答案：

数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，?}，字母字符数据对象是集合C={‘A’，‘B’，?，‘Z’， ‘a’，‘b’，?，‘z’}，学生基本信息表也可是一个数据对象。

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

逻辑结构：从逻辑关系上

数据结构（C语言版）（第2版）

课后习题答案

李冬梅 2015.3

目录

第第第第第第第第

1章绪论 ...................................................................................................................... 1 2章线性表 .................................................................................................................. 5 3章栈和队列 ............................................................................................................ 13 4章串、数组和广义表 ............................................................................................. 26 5章树