第1章 绪论 数据结构第2版李冬梅

《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)【第一章绪论】1. 数据结构是计算机科学中的重要基础知识，它研究的是如何组织和存储数据，以及如何通过高效的算法进行数据的操作和处理。

本章主要介绍了数据结构的基本概念和发展历程。

【第二章线性表】1. 线性表是由一组数据元素组成的数据结构，它的特点是元素之间存在着一对一的线性关系。

本章主要介绍了线性表的顺序存储结构和链式存储结构，以及它们的操作和应用。

【第三章栈与队列】1. 栈是一种特殊的线性表，它的特点是只能在表的一端进行插入和删除操作。

本章主要介绍了栈的顺序存储结构和链式存储结构，以及栈的应用场景。

2. 队列也是一种特殊的线性表，它的特点是只能在表的一端进行插入操作，而在另一端进行删除操作。

本章主要介绍了队列的顺序存储结构和链式存储结构，以及队列的应用场景。

【第四章串】1. 串是由零个或多个字符组成的有限序列，它是一种线性表的特例。

本章主要介绍了串的存储结构和基本操作，以及串的模式匹配算法。

【第五章数组与广义表】1. 数组是一种线性表的顺序存储结构，它的特点是所有元素都具有相同数据类型。

本章主要介绍了一维数组和多维数组的存储结构和基本操作，以及广义表的概念和表示方法。

【第六章树与二叉树】1. 树是一种非线性的数据结构，它的特点是一个节点可以有多个子节点。

本章主要介绍了树的基本概念和属性，以及树的存储结构和遍历算法。

2. 二叉树是一种特殊的树，它的每个节点最多只有两个子节点。

本章主要介绍了二叉树的存储结构和遍历算法，以及一些特殊的二叉树。

【第七章图】1. 图是一种非线性的数据结构，它由顶点集合和边集合组成。

本章主要介绍了图的基本概念和属性，以及图的存储结构和遍历算法。

【总结】1. 数据结构是计算机科学中非常重要的一门基础课程，它关注的是如何高效地组织和存储数据，以及如何通过算法进行数据的操作和处理。

本文对《数据结构》第二版严蔚敏的课后习题作业提供了参考答案，涵盖了第1-7章的内容。

《⼤话数据结构》⽬录第⼀章数据结构绪论1.1 开场⽩1.2 你数据结构怎么学的？1.3 数据结构起源1.4 基本概念和术语1.5 逻辑结构与物理结构1.6 抽象数据类型1.7 总结回顾1.8 结尾语第⼆章算法2.1 开场⽩2.2 数据结构与算法关系2.3 两种算法的⽐较2.4 算法定义2.5 算法的特征2.6 算法设计的要求2.7 算法效率的度量⽅法2.8 函数的渐进增长2.9 算法时间复杂度2.10 常见的时间复杂度2.11 最坏情况与平均情况2.12 算法空间复杂度2.13 总结回顾2.14 结束语第三章线性表3.1 开场⽩3.2 线性表的定义3.3 线性表的抽象数据类型3.4 线性表的顺序存储结构3.5 顺序存储结构的插⼊与删除3.6 线性表的链式存储结构3.7 单链表的读取3.8 单链表的插⼊与删除3.9 单链表的整表创建3.10 单链表的整表删除3.11 单链表结构与顺序存储结构优缺点3.15 总结回顾3.16 结束语第四章栈和队列4.1 开场⽩4.2 栈的定义4.3 栈的抽象数据类型4.4 栈的顺序存储结构及实现4.5 两栈共享空间4.6 栈的链式存储结构及实现4.7 栈的作⽤4.8 栈的应⽤ ———— 递归4.9 栈的应⽤ ———— 四则运算表达式求值4.10 队列的定义4.11 队列的抽象数据类型4.12 循环队列4.13 队列的链式存储结构及实现4.14 总结回顾4.15 结束语第五章串5.1 开场⽩5.2 串的定义5.3 串的⽐较5.4 串的抽象数据类型5.5 串的存储结构5.6 朴素的模式匹配算法5.7 KMP模式匹配算法5.8 总结回顾5.9 结束语第六章树6.1 开场⽩6.2 树的定义6.3 树的抽象数据类型6.4 树的存储结构6.5 ⼆叉树的定义6.6 ⼆叉树的性质6.7 ⼆叉树的存储结构6.11 树、森林与⼆叉树的转换6.12 赫夫曼树及其应⽤6.13 总结回顾6.14 结束语第七章图7.1 开场⽩7.2 图的定义7.3 图的抽象数据类型7.4 图的存储结构7.5 图的遍历7.6 最⼩⽣成树7.7 最短路径7.8 拓扑排序7.9 关键路径7.10 总结回顾7.11 结束语第⼋章查找8.1 开场⽩8.2 查找概论8.3 顺序表查找8.4 有序表查找8.5 线性索引查找8.6 ⼆叉排序树8.7 平衡⼆叉树(AVL树)8.8 多路查找树(B树)8.9 散列表查找(哈希表)概述8.10 散列函数的构造⽅法8.11 处理散列冲突的⽅法8.12 散列表查找实现8.13 总结回顾8.14 结束语第九章排序9.1 开场⽩9.2 排列的基本概念与分类9.3 冒泡排序9.4 简单选择排序9.6 希尔排序9.7 堆排序9.8 归并排序9.9 快速排序9.10 总结回顾9.11 结束语。

数据结构教案(总32页) -CAL-FENGHAI.-(YICAI)-Company One1-CAL-本页仅作为文档封面，使用请直接删除2015 至2016 学年第二学期数据结构课程教案课程编码： 1261D03总学时／周学时： 80 / 5开课时间： 2016年2 月 24日第 1 周至第 16 周授课年级、专业、班级： 15级网工程2班使用教材严蔚敏. 数据结构（C语言版）[M] 北京：清华大学出版社，2011.系别/教研室：信息工程学院 / 物联网工程授课教师：刘波教学目标：《数据结构》是物联网工程专业的一门专业必修课。

用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是《数据结构》要研究的内容。

主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。

通过本课程教学，使学生了解数据结构的基本概念，理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，掌握算法描述及算法的评价标准，熟悉在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会，旨在培养学生基本的、良好的程序设计技能，编制高效可靠的程序，并为学生日后学习操作系统和数据库等后续课程奠定基础。

教学要求:本课程主要是以抽象数据类型的观点来组织和讲解线性表、栈、队列、树、二叉树、图等各种主要的数学模型并定义为相应的抽象数据类型，给出各种物理表示法和有关算法，关于数据处理技术介绍几种主要的排序和查找算法。

学生通过学习该课程后主要应掌握以下内容：1．了解数据结构及有关的基本概念；2．了解各种抽象数据类型的性质；3．掌握各种抽象数据类型的实现和基本算法；4．对算法的时间和空间复杂性有一定的分析能力；5．能够选择适当的数据结构和存储结构以及设计有效的算法，解决实际问题；6．掌握数据结构在排序和查找等常用算法中的应用。

教学重点：抽象数据类型、顺序表、单链表、循环链表、栈、队列、数组、特殊矩阵、树和二叉树、最小生成树、拓扑排序、查找、内部排序教学难点：单链表、栈、循环队列、特殊矩阵、二叉树、关键路径、最短路径教学方法与手段：1．理论部分以讲授法为主，结合讨论及课堂练习实现教学目的。

吉首大学硕士研究生入学考试自命题考试大纲考试科目代码：[827]一、考试形式与试卷结考试科目名称：计算机学科专业基础（自命题）构1)试卷成绩及考试时间：本试卷满分为150分，考试时间为180分钟。

2)答题方式：闭卷、笔试3)试卷内容结构a:客观题部分40%b:主观题部分60%4)题型结构a:单项选择题，10小题，每小题2分，共20分b:填空题，5空，每空2分，共10分c:程序填空题，10空，每空3分，共30分d:综合应用题，6小题，每小题10分，共60分e:编程题，2小题，每题15分，共30分二、考试内容与考试要求考试内容一、绪论1、掌握数据结构的基本概念2、了解抽象数据类型3、理解算法五个要素的确切含义4、掌握算法时间复杂度和空间复杂度的分析方法二、线性表1、理解线性表的逻辑结构特性2、掌握线性表顺序存储结构的基本操作及实现3、掌握线性表链式存储结构的基本操作及实现4、理解链表中的头结点、头指针和首元结点的区别5、理解循环链表、双向链表的特点6、能根据具体问题选择顺序或链式存储方式，掌握表的逆置、合并等操作的实现方法三、栈和队列1、理解栈和队列的基本概念2、掌握栈和队列的顺序存储结构的基本操作及实现3、理解栈和队列的链式存储结构的基本操作及实现4、了解栈和队列的应用四、串1、理解串的基本定义2、掌握串的定长顺序存储、堆分配存储和块链存储的表示及其实现方法3、掌握串的模式匹配算法五、数组和广义表1、掌握数组的地址计算方法2、了解稀疏矩阵的两种压缩存储方法的特点和适用范围3、了解广义表的结构特点及其存储方法六、树和二叉树1、理解树和森林的概念，包括树的定义、树的术语2、掌握二叉树的概念、性质及表示方法3、掌握二叉树的遍历算法，并且能灵活运用递归遍历方式实现二叉树的其他操作4、理解树的存储、树和森林与二叉树的转换方法5、掌握哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径长度的计算七、图1、掌握图的基本概念及相关术语和性质2、掌握图的邻接矩阵和邻接表表示法3、掌握图的两种搜索路径的遍历：深度优先搜索和广度优先搜索的算法4、掌握构造最小生成树的两种算法及拓扑排序算法的思想5、掌握迪杰斯特拉算法和弗洛伊德算法八、查找1、理解查找在数据处理中的重要性，掌握查找表的相关概念2、掌握线性表的查找方法，能根据问题选择顺序查找、折半查找及分块查找方法求解3、掌握树表的查找方法，能构造二叉排序树，并将其调整为平衡二叉树4、理解散列表的基本概念，了解常用的散列函数构造方法和冲突解决办法九、排序1、掌握排序的基本概念，了解排序方法的分类2、理解插入排序、交换排序、选择排序、归并排序及基数排序的基本思想3、掌握直接插入排序、冒泡排序、简单选择排序的实现方法十、分治法1、掌握分治法的基本思想2、掌握归并排序、快速排序、折半查找、二叉树遍历、大整数乘法和矩阵相乘、棋盘覆盖等问题的分治设计方法3、了解排序问题的复杂性下限十一、回溯法1、掌握回溯法的基本思想2、掌握N皇后、最优装载、图的着色、0/1背包等问题的回溯法设计方法3、掌握剪枝函数的设计，能准确分析回溯法的效率十二、动态规划法1、掌握动态规划的主要思想和基本要素2、掌握矩阵连乘、最优二叉查找树、最长公共子序列、图像压缩、电路布线等问题的动态规划设计方法3、了解自顶向下的动态规划方法设计策略十三、贪心法1、掌握贪心算法的主要思想和基本要素2、掌握最小代价生成树、单起点最短路路径、自由前缀码编码等问题的贪心算法策略3、了解数据结构在程序效率分析的重要性考试要求1、掌握数据结构的基本概念、基本原理和基本方法。

数据结构（ 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. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

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

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

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

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

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

北京林业大学实验任务书备注：实验共分4次，其中实验1――实验3为设计性实验，实验4为综合性实验，具体安排下面一一列出。

北京林业大学09学年—10学年第 2学期数据结构实验任务书专业名称：实验学时： 4课程名称：数据结构任课教师：李冬梅实验题目：线性表的基本操作实验环境： Visual C++实验目的：1、掌握线性表的定义；2、掌握线性表的基本操作，如建立、查找、插入和删除等。

实验内容：定义一个包含学生信息（学号，姓名，成绩）的的顺序表和链表，使其具有如下功能：(1) 根据指定学生个数，逐个输入学生信息；(2) 逐个显示学生表中所有学生的相关信息；(3) 根据姓名进行查找，返回此学生的学号和成绩；(4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）；(5) 给定一个学生信息，插入到表中指定的位置；(6) 删除指定位置的学生记录；(7) 统计表中学生个数。

实验提示：学生信息的定义：typedef struct {char no[8]; //8位学号char name[20]; //姓名int price; //成绩}Student;顺序表的定义typedef struct {Student *elem; //指向数据元素的基地址int length; //线性表的当前长度}SqList；链表的定义：typedef struct LNode{Student data; //数据域struct LNode *next; //指针域}LNode,*LinkList;实验要求：(1) 程序要添加适当的注释，程序的书写要采用缩进格式。

(2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。

(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。

(4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。

第一章绪论1.1基本术语数据(data)是人们利用便于书写、记忆和交流的符号对现实世界的事物及其活动所做的记录。

因此，一个数值、一个单词、一句话、一篇文章、一幅图画都被称为数据。

数据元素(data Element)简称元素，它是一个数据整体中相对独立的单位。

简称记录，它是数据处理领域组织数数据中的每个数据元素在许多应用场合结构。

一个数据记录由一个或多个数据项(Item)所组成，每个数据项可以是简单数据项（即不可再分，如一个数值、一个字符等），也可以是组合数据项（即数组或记录）。

表1-1在一个表或文件中，若所有记录的某个数据项的对应的值均不同，也就是说，每个值都能够唯一地标识一个记录时，则可把这个数据项称为表或文件的关键数据项，简称关键项（key Item），关键项中的每一个值称做所在记录的关键字（key word或key）。

在一个表或文件中，能作为关键项的数据可能没有，可能只有一个，也可能多于一个。

当没有时，可把多个有关的数据联合起来，构成一个组合关键项，用组合关键项中的每一个组合值来唯一地标识一个记录，该组合值就是所在记录的关键字。

引入了记录的关键项和关键字后，为简便起见，在以后的讨论中，经常利用关键项中的所有值代替所有记录，而忽略其它非关键数据项。

数据处理(Data Processing)是指对数据进行存储、检索、插入、删除、合并、拆分、排序、统计、计算、转换、输入、输出等的处理过程。

数据结构(Data Structure)，是指数据以及相互之间的联系。

它是根据人们解决实际问题的需要和问题本身所含数据之间的内在联系而抽象出来的。

这种数据结构与如何利用计算机存储和处理无关，被称、树、图等基本结构，由它们的组合和嵌套可以形成较复杂的结构。

一种数据结构必须被存储到计算机的存储器中才能利用计算机处理。

存储数据结构有各种不同的方法，大体上有顺序、链接、索引、散列等基本方法，每存储方法都使数据在存储器中表现出相应的结构，称此为数据物理结构或存储结构。

第1章绪论教材中练习题及参考答案1. 简述数据与数据元素的关系与区别。

答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。

数据元素是数据的基本单位，是数据的个体。

数据元素与数据之间的关系是元素与集合之间的关系。

2. 采用二元组表示的数据逻辑结构S=<D，R>，其中D={a，b，…，i}，R={r}，r={<a，b>，<a，c>，<c，d>，<c，f>，<f，h>，<d，e>，<f，g>，<h，i>}，问关系r是什么类型的逻辑结构？哪些结点是开始结点，哪些结点是终端结点？答：该逻辑结构为树形结构，其中a结点没有前驱结点，它是开始结点，b、e、i和g、结点没有后继结点，它们都是终端结点。

3. 简述数据逻辑结构与存储结构的关系。

答：在数据结构中，逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在计算机中的表示。

存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还要在内存中存储各数据元素间的逻辑关系。

通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采用顺序存储结构或链式存储结构表示。

4. 简述数据结构中运算描述和运算实现的异同。

答：运算描述是指逻辑结构施加的操作，而运算实现是指一个完成该运算功能的算法。

它们的相同点是，运算描述和运算实现都能完成对数据的“处理”或某种特定的操作。

不同点是，运算描述只是描述处理功能，不包括处理步骤和方法，而运算实现的核心则是设计处理步骤。

5. 数据结构和数据类型有什么区别？答：数据结构是相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。

而数据类型是一个值的集合和定义在这个值集上的一组运算的总称，如C语言中的short int数据类型是由-32768～32767（16位机）的整数和+、-、*、/、%等运算符构成。