下载文档原格式
严蔚敏 数据结构C 语言版答案详解第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 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。
解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={<r,i>} 基本操作： InitComplex(&C,re,im)操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)操作结果：销毁复数C Get(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 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语言版）笔记和习题（含考研真题）详解第1章绪论一、什么是数据结构数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
二、基本概念和术语1数据数据是对客观事物的符号表示，是计算机科学中所有能输入到计算机中并能被计算机程序处理的符号的总称。
2数据元素数据元素是数据的基本单位。
3数据对象数据对象是性质相同的数据元素的集合，是数据的一个子集。
4数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
（1）数据结构的基本结构根据数据元素之间关系的不同特性，通常有下列四类基本结构：①集合。
数据元素属于“同一个集合”，并无其他复杂关系。
②线性结构。
数据元素之间存在一个对一个的关系。
③树形结构。
数据元素之间存在一个对多个的关系。
④图状结构或网状结构。
数据元素之间存在多个对多个的关系。
【注意】区分这四种基本结构可以根据元素间的对应关系。
如图1-1所示为上述四类基本结构的关系图。
图1-1 四类基本结构的关系图（2）数据结构的形式定义数据结构的形式定义为：Data_Structure=(D,S)其中：D表示数据元素的有限集，S表示D上关系的有限集。
（3）数据结构在计算机中的表示数据结构包括数据元素的表示和关系，在计算机中称为数据的物理结构（又称存储结构）。
其中，关系有两种表示方法：顺序映象和非顺序映象。
这两种表示方法对应两种存储结构：顺序存储结构和链式存储结构。
a．顺序映象：用相对位置来表示数据元素之间的逻辑关系。
b．非顺序映象：用指针表示数据元素之间的逻辑关系。
5数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
6抽象数据类型抽象数据类型（ADT）由一个值域和定义在该值域上的一组操作组成。
【注意】抽象数据类型是对数据类型架构的一种全局体现，使我们能够更加清晰地看待某一数据类型。
7多形数据类型多形数据类型是指其值的成分不确定的数据类型。
期末复习 第一章 绪论 复习1、计算机算法必须具备输入、输出、可行性、确定性、有穷性５个特性。
2、算法分析的两个主要方面是空间复杂度和时间复杂度。
3、数据元素是数据的基本单位。
4、数据项是数据的最小单位。
5、数据结构是带结构的数据元素的集合。
6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。
基础知识数据结构算 法概 念逻辑结构 存储结构数据运算数据：计算机处理的信息总称 数据项：最小单位 数据元素：最基本单位数据对象：元素集合数据结构：相互之间存在一种或多种特定关系的数据元素集合。
概念：数据元素之间的关系 线性结构：一对一非线性结构 树：一对多 图：多对多顺序存储结构 链表存储结构 索引。
散列。
算法描述：指令的有限有序序列算法特性 有穷性 确定性 可行性 输入 输出 算法分析时间复杂度 空间复杂度第二章 线性表 复习1、在双链表中，每个结点有两个指针域，包括一个指向前驱结点的指针 、一个指向后继结点的指针2、线性表采用顺序存储，必须占用一片连续的存储单元3、线性表采用链式存储，便于进行插入和删除操作4、线性表采用顺序存储和链式存储优缺点比较。
5、简单算法第三章 栈和队列 复习线性表顺序存储结构链表存储结构概 念基本特点基本运算定义逻辑关系：前趋 后继节省空间 随机存取 插、删效率低 插入 删除单链表双向 链表 特点一个指针域+一个数据域 多占空间 查找费时 插、删效率高 无法查找前趋结点运算特点：单链表+前趋指针域运算插入删除循环 链表特点：单链表的尾结点指针指向附加头结点。
运算：联接1、 栈和队列的异同点。
2、 栈和队列的基本运算3、 出栈和出队4、 基本运算第四章 串 复习栈存储结构栈的概念：在一端操作的线性表 运算算法栈的特点：先进后出 LIFO初始化 进栈push 出栈pop队列顺序队列 循环队列队列概念：在两端操作的线性表 假溢出链队列队列特点：先进先出 FIFO基本运算顺序：链队：队空：front=rear队满：front=(rear+1)%MAXSIZE队空：frontrear ∧初始化 判空 进队 出队取队首元素第五章 数组和广义表 复习串存储结构运 算概 念顺序串链表串定义：由n(≥1)个字符组成的有限序列 S=”c 1c 2c 3 ……cn ”串长度、空白串、空串。
期末复习复习第一章绪论数据：计算机处理的信息总称数据项：最小单位数据元素：最基本单数据对象：元素集合数据结构：相互之间存在一种或多种特定关系的数据元素集合。
概念：数据元素之间的关系线性结构：一对逻辑结构非线性结构数据结构树：一对多图：多对多顺序存储结构链表存储结构存储结构。
索引。
基。
散列。
础知数据运算识算法描述：指令的有限有序序列有穷性确定性算法特性可行性算法输入输出时间复杂度算法分析空间复杂度、计算机算法必须具备输入、输出、可行性、确定性、有穷性５个特性。
1 2、算法分析的两个主要方面是空间复杂度和时间复杂度。
3、数据元素是数据的基本单位。
4、数据项是数据的最小单位。
5、数据结构是带结构的数据元素的集合。
6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。
线性表复习第二章定义逻辑关系：前趋后继节省空间基本特点随机存取插、删效率低顺序存储结构插入基本运算删除一个数据一个指针多占空特查找费插、删效率无法查找前趋结单链运算特点：单链表+前趋指针域链表存储双向结构链表插入运算删除特点：单链表的尾结点指针循环指向附加头结点。
链表运算：联接1 、一个指向后继结点的指针、在双链表中，每个结点有两个指针域，包括一个指向前驱结点的指针 2、线性表采用顺序存储，必须占用一片连续的存储单元、线性表采用链式存储，便于进行插入和删除操作3 、线性表采用顺序存储和链式存储优缺点比较。
4 5、简单算法复习栈和队列第三章．栈的概念：在一端操作的线性表LIFO栈的特点：先进后出存储结初始化push 进栈运算算法pop出栈队列概念：在两端操作的线性表FIFO队列特点：先进先出假溢出顺序队列front=rear队空：循环队列front=(rear+1)%MAXSIZE队满：队列front∧队空：链队列rear初始化判空顺序：进队基本运算链队：出队取队首元素1栈和队列的异同点。
、、2栈和队列的基本运算出栈和出队、3 、4基本运算复习串第四章．n(≥)个字符组成的有限序列1定义：由”c……cS=”cc n231串长度、空白串、空串。
第1章绪论1.1复习笔记一、数据结构的定义数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
二、基本概念和术语数据数据（data）是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称，它是计算机程序加工的“原料”。
2.数据元素数据元素（data element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
3.数据对象数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。
4．数据结构数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的集合。
（1）数据结构的基本结构根据数据元素之间关系的不同特性，通常有下列四类基本结构：① 集合。
数据元素之间除了“同属于一个集合”的关系外，别无其它关系。
② 线性结构。
数据元素之间存在一个对一个的关系。
③ 树形结构。
数据元素之间存在一个对多个的关系。
④ 图状结构或网状结构。
数据元素之间存在多个对多个的关系。
如图1-1所示为上述四类基本结构的关系图。
图1-1 四类基本结构的关系图（2）数据结构的形式定义数据结构的形式定义为：数据结构是一个二元组Data_Structure==（D，S）其中：D表示数据元素的有限集，S表示D上关系的有限集。
（3）数据结构在计算机中的表示数据结构在计算机中的表示（又称映象）称为数据的物理结构，又称存储结构。
它包括数据元素的表示和关系的表示。
① 元素的表示。
计算机数据元素用一个由若干位组合起来形成的一个位串表示。
② 关系的表示。
计算机中数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象。
并由这两种不同的表示方法得到两种不同的存储结构：顺序存储结构和链式存储结构。
a.顺序映象的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
b.非顺序映象的特点是借助指示元素存储地址的指针（pointer）表示数据元素之间的逻辑关系。
