数据结构C语言版(严蔚敏)习题答案

数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论...................................................................................... 错误!未定义书签。

第2章线性表 .................................................................................. 错误!未定义书签。

第3章栈和队列 .............................................................................. 错误!未定义书签。

第4章串、数组和广义表 ............................................................... 错误!未定义书签。

第5章树和二叉树........................................................................... 错误!未定义书签。

第6章图............................................................................................ 错误!未定义书签。

第7章查找...................................................................................... 错误!未定义书签。

第8章排序...................................................................................... 错误!未定义书签。

严蔚敏 数据结构C 语言版答案详解第1章 绪论简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

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

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

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

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

}试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。

)解：试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：ADT Complex{-数据对象：D={r,i|r,i 为实数} 数据关系：R={<r,i>} 基本操作：InitComplex(&C,re,im)操作结果：构造一个复数C ，其实部和虚部分别为re 和im—DestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e返回复数C的第k元的值Put(&C,k,e)^操作结果：改变复数C的第k元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0 IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0）Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADT Complex^ADT RationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：}InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)>操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0 \IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0 Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)：操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber试画出与下列程序段等价的框图。

严蔚敏 数据结构C 语言版答案详解第1章 绪论1.1简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

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

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

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

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

p1EanqFDPw 1.3 设有数据结构(D,R>，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。

解：1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义<有理数是其分子、分母均为自然数且分母不为零的分数）。

DXDiTa9E3d 解：ADT Complex{数据对象：D={r,i|r,i 为实数} 数据关系：R={<r,i>} 基本操作： InitComplex(&C,re,im>操作结果：构造一个复数C ，其实部和虚部分别为re 和imDestroyCmoplex(&C>操作结果：销毁复数CGet(C,k,&e>操作结果：用e 返回复数C 的第k 元的值Put(&C,k,e>操作结果：改变复数C的第k元的值为eIsAscending(C>操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0IsDescending(C>操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0Max(C,&e>操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e>操作结果：用e返回复数C的两个元素中值较小的一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m>操作结果：构造一个有理数R，其分子和分母分别为s和m DestroyRationalNumber(&R>操作结果：销毁有理数RGet(R,k,&e>操作结果：用e返回有理数R的第k元的值Put(&R,k,e>操作结果：改变有理数R的第k元的值为eIsAscending(R>操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0IsDescending(R>操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0Max(R,&e>操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e>操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber1.5 试画出与下列程序段等价的框图。

严蔚敏数据结构课后习题及答案解析数据结构课程是计算机科学与技术专业中非常重要的一门基础课程，对于学习者来说，课后习题的巩固和答案解析是学习的重要辅助材料。

本文将针对严蔚敏老师所著的《数据结构（C语言版）》中的课后习题及答案解析进行介绍和总结。

1. 第一章：绪论（略）2. 第二章：线性表（略）3. 第三章：栈和队列3.1 课后习题3.1.1 课后习题一：给定一个整数序列，请设计一个算法，其中删除整数序列中重复出现的元素，使得每个元素只出现一次。

要求空间复杂度为O(1)。

3.1.2 课后习题二：使用栈操作实现一个队列（其中队列操作包括入队列和出队列）。

3.2 答案解析3.2.1 答案解析一：我们可以使用双指针法来实现这一算法。

设定两个指针，一个指向当前元素，另一个指向当前元素的下一个元素。

比较两个元素是否相等，如果相等，则删除下一个元素，并移动指针。

如果不相等，则继续移动指针。

这样，当指针指向序列的最后一个元素时，算法结束。

空间复杂度为O(1)，时间复杂度为O(n)。

3.2.2 答案解析二：使用两个栈来实现一个队列。

一个栈用于入队列操作，另一个栈用于出队列操作。

当需要入队列时，将元素直接入栈1。

当需要出队列时，判断栈2是否为空，如果为空，则将栈1中的元素逐个弹出并压入栈2中，然后从栈2中弹出栈顶元素。

如果栈2非空，则直接从栈2中弹出栈顶元素。

这样，就可以实现使用栈操作来实现队列操作。

4. 第四章：串（略）5. 第五章：数组和广义表（略）6. 第六章：树和二叉树（略）7. 第七章：图（略）通过对严蔚敏老师所著《数据结构（C语言版）》中的课后习题及答案解析的介绍，可以帮助学习者更好地理解和掌握数据结构这门课程的知识内容。

课后习题不仅可以帮助巩固所学知识，更加于提升学习者的能力和应用水平。

希望本文对于学习者们有所帮助。

（文章结束）。

第一章绪论一、选择题1.组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量2.数据结构是研究数据的（）以及它们之间的相互关系。

（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。

① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像② （A）结构（B）关系（C）运算（D）算法5.算法分析的目的是（）。

（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。

① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构。

（）2.算法就是程序。

（）3.数据元素是数据的最小单位。

（）4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。

（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态。

（）三、填空题1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。

2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。

3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。

数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论...................................................................................... 错误!未定义书签。

第2章线性表 .................................................................................. 错误!未定义书签。

第3章栈和队列 .............................................................................. 错误!未定义书签。

第4章串、数组和广义表 ............................................................... 错误!未定义书签。

第5章树和二叉树........................................................................... 错误!未定义书签。

第6章图............................................................................................ 错误!未定义书签。

第7章查找...................................................................................... 错误!未定义书签。

第8章排序...................................................................................... 错误!未定义书签。

数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (43)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

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

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

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

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

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

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

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

第1章绪论1.1简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

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

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

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

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。

解：1.4试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：ADTComplex{数据对象：D={r,i|r,i 为实数}数据关系：R={<r,i>}基本操作：InitComplex(&C,re,im)操作结果：构造一个复数C ，其实部和虚部分别为re 和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e 返回复数C 的第k 元的值Put(&C,k,e)操作结果：改变复数C 的第k 元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADTComplexADTRationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和m DestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADTRationalNumber1.5试画出与下列程序段等价的框图。

数据结构c语言版严蔚敏课后习题答案数据结构是计算机科学中的一个重要领域，它涉及到数据的组织、管理和存储方式，以便可以高效地访问和修改数据。

C语言作为一种广泛使用的编程语言，提供了丰富的数据结构实现方法。

严蔚敏教授编写的《数据结构（C语言版）》是许多计算机专业学生的必读教材。

以下是对该书课后习题的一些参考答案，供学习者参考。

第一章：绪论1. 数据结构的定义：数据结构是计算机中存储、组织数据的方式，它不仅包括数据元素的类型和关系，还包括数据操作的函数。

2. 数据结构的重要性：数据结构对于提高程序的效率至关重要。

合理的数据结构可以减少算法的时间复杂度和空间复杂度。

第二章：线性表1. 线性表的定义：线性表是由n个元素组成的有限序列，其中n称为线性表的长度。

2. 线性表的顺序存储结构：使用数组来存储线性表的元素，元素的存储关系是连续的。

3. 线性表的链式存储结构：使用链表来存储线性表的元素，每个元素包含数据部分和指向下一个元素的指针。

第三章：栈和队列1. 栈的定义：栈是一种特殊的线性表，只能在一端（栈顶）进行插入和删除操作。

2. 队列的定义：队列是一种特殊的线性表，允许在一端（队尾）进行插入操作，在另一端（队首）进行删除操作。

第四章：串1. 串的定义：串是由零个或多个字符组成的有限序列。

2. 串的存储结构：串可以采用顺序存储结构或链式存储结构。

第五章：数组和广义表1. 数组的定义：数组是由具有相同类型的多个元素组成的集合，这些元素按照索引顺序排列。

2. 广义表的定义：广义表是线性表的推广，其中的元素可以是数据也可以是子表。

第六章：树和二叉树1. 树的定义：树是由节点组成的，其中有一个特定的节点称为根，其余每个节点有且仅有一个父节点。

2. 二叉树的定义：二叉树是每个节点最多有两个子节点的树。

第七章：图1. 图的定义：图是由顶点和边组成的数据结构，可以表示复杂的关系。

2. 图的存储结构：图可以用邻接矩阵或邻接表来存储。

数据结构(C语言版)严蔚敏课后习题答案数据结构（C语言版）严蔚敏课后习题答案一、线性表1. 顺序表顺序表是一种存储结构，它将元素顺序存放在一块连续的存储区域中。

C语言中常用数组来实现顺序表。

以下是一些常见题目的解答：题目1：已知顺序表中存储了n个整数，请编写一个算法，将这个顺序表中的所有负数挑选出来，并将它们按照原有顺序存放在新的顺序表中。

解答：```#include <stdio.h>#define MAX_SIZE 100int main() {int A[MAX_SIZE], neg[MAX_SIZE];int n, i, j = 0;printf("Enter the number of elements: ");scanf("%d", &n);printf("Enter the elements: ");for (i = 0; i < n; i++) {scanf("%d", &A[i]);if (A[i] < 0) {neg[j] = A[i];j++;}}printf("Negative numbers: ");for (i = 0; i < j; i++) {printf("%d ", neg[i]);}return 0;}```题目2：假设顺序表A和B中的元素递增有序排列，编写一个算法合并这两个顺序表，并使合并后的顺序表仍然递增有序。

解答：```#include <stdio.h>#define MAX_SIZE 100int main() {int A[MAX_SIZE], B[MAX_SIZE], C[MAX_SIZE * 2]; int m, n, i, j, k;printf("Enter the number of elements in the first list: "); scanf("%d", &m);printf("Enter the elements in increasing order: ");for (i = 0; i < m; i++) {scanf("%d", &A[i]);C[i] = A[i];}printf("Enter the number of elements in the second list: "); scanf("%d", &n);printf("Enter the elements in increasing order: ");for (i = 0; i < n; i++) {scanf("%d", &B[i]);C[m + i] = B[i];}// Merge A and B into Ci = j = k = 0;while (i < m && j < n) { if (A[i] < B[j]) {C[k] = A[i];i++;} else {C[k] = B[j];j++;}k++;}while (i < m) {C[k] = A[i];i++;k++;}while (j < n) {C[k] = B[j];j++;k++;}printf("Merged list in increasing order: ");for (i = 0; i < m + n; i++) {printf("%d ", C[i]);}return 0;}```2. 链表链表是一种动态的数据结构，它通过结点之间的指针联系起来。

数据结构c语言版严蔚敏习题答案数据结构是计算机科学中一个重要的基础概念，它涉及到数据的组织、存储和管理方式。

在C语言中实现数据结构，可以有效地提高程序的效率和性能。

严蔚敏教授的《数据结构（C语言版）》是一本广泛使用的教材，它详细介绍了各种数据结构的原理和实现方法。

以下是对该书习题的一些答案分析：# 线性表线性表是最基本的数据结构，它由一系列线性排列的元素组成。

在C语言中，线性表通常使用数组或链表来实现。

- 数组实现：数组是一种静态数据结构，其大小在定义时确定，不支持动态扩展。

- 链表实现：链表是一种动态数据结构，可以灵活地添加和删除元素。

# 栈和队列栈是一种后进先出（LIFO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。

- 栈的实现：可以使用数组或链表来实现栈。

栈的基本操作包括入栈（push）和出栈（pop）。

- 队列的实现：同样可以使用数组或链表实现队列。

队列的基本操作包括入队（enqueue）和出队（dequeue）。

# 树和二叉树树是一种层次结构的数据结构，其中每个节点有零个或多个子节点。

二叉树是树的一种特殊形式，每个节点最多有两个子节点。

- 二叉树遍历：包括前序遍历、中序遍历和后序遍历。

- 二叉搜索树：一种特殊的二叉树，其中每个节点的值都大于或等于其左子树中的所有节点的值，且小于或等于其右子树中的所有节点的值。

# 图图是由顶点（或称为节点）和边组成的数据结构。

图可以是无向的或有向的。

- 图的表示：图可以通过邻接矩阵或邻接表来表示。

- 图的遍历：包括深度优先搜索（DFS）和广度优先搜索（BFS）。

# 查找查找是数据结构中用于检索特定元素的过程。

- 顺序查找：在数组中按顺序查找元素。

- 二分查找：在有序数组中使用二分查找算法快速定位元素。

# 排序排序是将一组数据按照特定顺序排列的过程。

- 冒泡排序：通过重复遍历待排序的数列，比较每对相邻元素的大小，并在必要时交换它们的位置。

- 快速排序：一种分而治之的排序算法，通过选取一个“基准”元素并将数列分为两部分，一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。

数据结构习题集答案(C语言版严蔚敏)第2章线性表2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

解：头指针是指向链表中第一个结点的指针。

首元结点是指链表中存储第一个数据元素的结点。

头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。

它可以对空表、非空表以及首元结点的操作进行统一处理。

2.2 填空题。

解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。

(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。

单链表中逻辑上相邻的元素的物理位置不一定紧邻。

(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。

(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。

2.3 在什么情况下用顺序表比链表好？解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。

2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。

解：2.5 画出执行下列各行语句后各指针及链表的示意图。

L=(LinkList)malloc(sizeof(LNode)); P=L;for(i=1;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next; P->data=i*2-1;}P->next=NULL;for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2);for(i=1;i<=3;i++) Del_LinkList(L,i);解：2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是__________________。

第 1 章绪论1.1简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

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

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

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

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3设有数据结构(D,R)，其中D = {d1, d 2, d 3, d 4}，R = {r}，r = {(d1, d 2), (d 2, d3),(d 3, d 4)}试按图论中图的画法惯例画出其逻辑结构图。

解：1.4试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：ADT Complex{数据对象：D={r,i|r,i 为实数}数据关系：R={<r,i>}基本操作：InitComplex(&C,re,im)操作结果：构造一个复数 C，其实部和虚部分别为re 和 imDestroyCmoplex(&C)操作结果：销毁复数 CGet(C,k,&e)操作结果：用 e 返回复数C 的第k 元的值Put(&C,k,e)操作结果：改变复数 C 的第k 元的值为eIsAscending(C)操作结果：如果复数 C 的两个元素按升序排列，则返回 1，否则返回 0IsDescending(C)操作结果：如果复数 C 的两个元素按降序排列，则返回 1，否则返回 0 Max(C,&e)操作结果：用 e 返回复数C 的两个元素中值较大的一个Min(C,&e)操作结果：用 e 返回复数C 的两个元素中值较小的一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m 为自然数，且 m 不为 0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数 R，其分子和分母分别为 s 和mDestroyRationalNumber(&R)操作结果：销毁有理数 RGet(R,k,&e)操作结果：用 e 返回有理数 R 的第k 元的值Put(&R,k,e)操作结果：改变有理数 R 的第k 元的值为 eIsAscending(R)操作结果：若有理数 R 的两个元素按升序排列，则返回 1，否则返回 0 IsDescending(R)操作结果：若有理数 R 的两个元素按降序排列，则返回 1，否则返回 0 Max(R,&e)操作结果：用 e 返回有理数 R 的两个元素中值较大的一个Min(R,&e)操作结果：用 e 返回有理数 R 的两个元素中值较小的一个}ADT RationalNumber1.5试画出与下列程序段等价的框图。

数据结构（C语⾔版第2版）课后习题答案严蔚敏版数据结构（C语⾔版 第2版）课后习题答案 严蔚敏 等 编著，仅供参考，还是⾃⼰认真做了再看第1章 绪论5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（ C ）。

A．动态结构和静态结构 B．紧凑结构和⾮紧凑结构C．线性结构和⾮线性结构 D．内部结构和外部结构（2）与数据元素本⾝的形式、内容、相对位置、个数⽆关的是数据的（ C ）。

A．存储结构 B．存储实现C．逻辑结构 D．运算实现（3）通常要求同⼀逻辑结构中的所有数据元素具有相同的特性，这意味着（ B ）。

A．数据具有同⼀特点B．不仅数据元素所包含的数据项的个数要相同，⽽且对应数据项的类型要⼀致C．每个数据元素都⼀样D．数据元素所包含的数据项的个数要相等（4）以下说法正确的是（ D ）。

A．数据元素是数据的最⼩单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．⼀些表⾯上很不相同的数据可以有相同的逻辑结构解释：数据元素是数据的基本单位，数据项是数据的最⼩单位，数据结构是带有结构的各数据元素的集合。

（5）算法的时间复杂度取决于（ D ）。

A．问题的规模 B．待处理数据的初态C．计算机的配置 D．A和B解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。

如某些排序的算法，其执⾏时间与待排序记录的初始状态有关。

为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。

（6）以下数据结构中，（ A ）是⾮线性数据结构A．树 B．字符串 C．队列 D．栈6．试分析下⾯各程序段的时间复杂度。

（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;答案：O(1)解释：程序的执⾏次数为常数阶。

（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;答案：O(m*n)解释：语句a[i][j]=0;的执⾏次数为m*n。

数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论...................................................................................... 错误!未定义书签。

第2章线性表 .................................................................................. 错误!未定义书签。

第3章栈和队列 .............................................................................. 错误!未定义书签。

第4章串、数组和广义表 ............................................................... 错误!未定义书签。

第5章树和二叉树........................................................................... 错误!未定义书签。

第6章图............................................................................................ 错误!未定义书签。

第7章查找...................................................................................... 错误!未定义书签。

第8章排序...................................................................................... 错误!未定义书签。

严蔚敏《数据结构（C语言版）习题集》答案第一章绪论void print_descending(int x,int y,int z)....+f[m-k]=f[m-1]+f[m-2]+......+f[m-k]+f[m-k-1]-f[m-k-1]=2*f[m-1]-f[m-k-1]所以上述算法的时间复杂度仅为O(m). 如果采用递归设计,将达到O(k^m). 即使采用暂存中间结果的方法,也将达到O(m^2).typedef struct{char *sport;enum{male,female} gender;char schoolname; port!=NULL){switch(result[i].schoolname){case 'A':score[ 0 ].totalscore+=result[i].score;if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;else score[ 0 ].femalescore+=result[i].score;break;case 'B':score[ 0 ].totalscore+=result[i].score;if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;else score[ 0 ].femalescore+=result[i].score;break;………………}i++；}for(i=0;i<5;i++){printf("School %d:\n",i);printf("Total score of male:%d\n",score[i].malescore);printf("Total score of female:%d\n",score[i].femalescore);printf("Total score of all:%d\n\n",score[i].totalscore);}}void polyvalue(){float temp;float *p=a;printf("Input number of terms:");scanf("%d",&n);printf("Input value of x:");scanf("%f",&x);printf("Input the %d coefficients from a0 to a%d:\n",n+1,n);p=a;xp=1;sum=0;Status Insert(LinkList &L,int i,int b)void merge1(LinkList &A,LinkList &B,LinkList &C)void SqList_Intersect(SqList A,SqList B,SqList &C)void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)iList为带头结点的单循环链表类型.{s=L->next;A=(CiList*)malloc(sizeof(CiLNode));p=A;B=(CiList*)malloc(sizeof(CiLNode));q=B;C=(CiList*)malloc(sizeof(CiLNode));r=C; .4,2的顺序重排双向循环链表L中的所有结点{p=;while(p->next!=L&&p->next->next!=L){p->next=p->next->next;p=p->next;} 同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.DuLNode * Locate_DuList(DuLinkedList &L,int x) int x;int y;} coordinate;void Repaint_Color(int g[m][n],int i,int j,int color)归形式的算法该怎么写呢?void NiBoLan(char *str,char *new)题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b).Status g(int m,int n,int &s)void InitCiQueue(CiQueue &Q)Status EnCyQueue(CyQueue &Q,int x)省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?int Delete_SubString(Stringtype &s,Stringtype t)读者用此程序取代作者早些时候对题给出的程序.void StrAssign(Stringtype &T,char chars&#;)h&&T[j].ch!=c) j++; h) T[j].num++;else T[j]={c,1};}h;j++)printf("%c: %d\n",T[j].ch,T[j].num);}前一个程序的区别在于,串s业已存在.{for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next){p->ch=q->ch;pre=p;}while(q){p=(LStrNode*)malloc(sizeof(LStrNode));p->ch=q->ch;pre->next=p;pre=p;}p->next=NULL;}算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2).void Get_LPubSub(Stringtype S,Stringtype T) for(k=0,j=jmin;j<=jmax;j++){if(A[j]==B[j-i]) k++;else k=0;if(k>maxlen){lps1=j-k+1;lps2=j-i-k+1;maxlen=k;}}一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。