数据结构中常用的逻辑结构和存储结构

malloc函数为动态分配空间；原型为: void * malloc(int size);使用方法一般为：假设你要定义一个名为a的Node类型的指针变量，使用以下语句：Node * a=（Node *）malloc(sizeof(Node))；其中（Node *）为强制转换，把返回类型void *转换为Node *，sizeof（Node）为获取Node 类型占据空间的大小，如在我机子上int类型占4字节，sizeof（int）就返回4；使用malloc需要包含＃include <malloc.h>学习数据结构有什么用？计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。

同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。

程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。

而好的算法在很大程度上取决于描述实际问题的数据结构。

程序=数据结构+算法(尼克劳斯.沃尔斯）目标：“数据结构” 课程的教学目标是要求学生学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。

意义1. 算法和数据结构是计算机科学的两大支柱2.数据结构是程序设计的基础程序=数据结构+算法--图灵奖获得者：Nicklaus Wirth（瑞士）数据结构是设计OS、DBMS、编译等系统程序和各种应用程序的重要基础数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。

术语：数据(Data):是对信息的一种符号表示。

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

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

一个数据元素可由若干个数据项组成。

2007 C C C 语言的特点，简单的C 程序介绍，C 程序的上机步骤。

1 、算法的概念2、简单的算法举例3、算法的特性4、算法的表示（自然语言、流程图、N-S 图表示） 1 、 C 的数据类型、常量与变星、整型数据、实型数据、字符型数据、字符串常量。

2、 C 的运算符运算意义、优先级、结合方向。

3、算术运算符和算术表达式，各类数值型数据间的混合运算。

4、赋值运算符和赋值表达式。

5、逗号运算符和逗号表达式。

1 、程序的三种基本结构。

2、数据输入输出的概念及在C 语言中的实现。

字符数据的输入输出，格式输入与输出。

1 、关系运算符及其优先级，关系运算和关系表达式。

2、逻辑运算符及其优先级，逻辑运算符和逻辑表达式。

3、if语句。

if语句的三种形式，if语句的嵌套，条件运算符。

4、switch 语句. 1 、while 语句。

2、do/while 语句。

3、for 语句。

4、循环的嵌套。

5、break 语句和continue 语句。

1 、一维数组的定义和引用。

2、二维数组的定义和引用。

3、字符数组。

4、字符串与字符数组。

5、字符数组的输入输出。

6、字符串处理函数1 、函数的定义。

2、函数参数和函数的值，形式参数和实际参数。

3、函数的返回值。

4、函数调用的方式，函数的声明和函数原型。

5、函数的嵌套调用。

6、函数的递归调用。

7、数组作为函数参数。

8、局部变量、全局变量的作用域。

9、变量的存储类别，自动变星，静态变量。

1 、带参数的宏定义。

2、“文件包含”处理。

1 、地址和指针的概念。

2、变量的指针和指向变量的指针变量。

3、指针变量的定义和引用。

4、指针变量作为函数参数。

5、数组的指针和指向数组的指针变量。

6、指向数组元素的指针。

7、通过指针引用数组元素。

8、数组名作函数参数。

9、二维数组与指针。

1 0、指向字符串的指针变星。

字符串的指针表示形式，字符串指针作为函数参数。

11 、字符指针变量和字符数组的异同。

数据结构中常用的逻辑结构和存储结构一、概念数据是指由有限的符号（比如，"0"和"1"，具有其自己的结构、操作、和相应的语义）组成的元素的集合。

结构是元素之间的关系的集合。

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。

数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。

数据结构有逻辑上的数据结构和物理上的数据结构之分。

逻辑上的数据结构反映成分数据之间的逻辑关系即逻辑结构，而物理上的数据结构反映成分数据在计算机内部的存储安排即存储结构。

数据结构是数据存在的形式。

数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。

因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。

通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。

因而研究数据结构的逻辑结构与存储结构显得十分重要。

二、结构分析（一）逻辑结构数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。

逻辑结构形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。

逻辑结构元素决定输入、存储、发送、处理和信息传递的基本操作功能，常将逻辑结构元素称为逻辑模块。

逻辑结构元素可以是计算机操作系统、终端模块、通信程序模块等。

逻辑结构元素还可以是相关的几个逻辑模块联合起来的更复杂的实体。

分析逻辑结构元素的相互作用，应考虑整个系统的操作，研究处理与信息流有关的进程（操作系统中的一个概念，表示程序的一次执行），并决定系统的逻辑资源。

逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。

表和树是最常用的两种高效数据结构，许多高效的算法能够用这两种数据结构来设计实现。

数据结构复习笔记作者: 网络转载发布日期: 无数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。

数据项是具有独立含义的最小标识单位。

如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。

数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。

这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。

比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。

那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。

而存储结构则是指用计算机语言如何表示结点之间的这种关系。

如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。

(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。

)第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。

弄清了以上三个问题，就可以弄清数据结构这个概念。

--------------------------------------------------------------------------------通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解)数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。

1.一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。

1. 算法的复杂度主要包括时间复杂度和空间复杂度。

2. 实现算法所需的存储单元多少和算法的工作量大小分别称为算法的空间复杂度和时间复杂度。

3.所谓数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。

4.数据结构是指相互有关联的数据元素的集合。

5.数据结构分为逻辑结构与存储结构，线性链表属于存储结构。

6.数据结构包括数据的逻辑结构和数据的存储结构。

7. 数据结构包括数据的逻辑结构、数据的存储结构以及对数据的操作运算。

8.数据元素之间的任何关系都可以用前趋和后继关系来描述。

9.数据的逻辑结构有线性结构和非线性结构两大类。

10.常用的存储结构有顺序、链接、索引等存储结构。

11. 顺序存储方法是把逻辑上相邻的结点存储在物理位置相邻的存储单元中。

12. 栈的基本运算有三种：入栈、退栈与读栈顶元素。

13. 队列主要有两种基本运算：入队运算与退队运算。

14. 在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。

15.栈和队列通常采用的存储结构是链式存储和顺序存储。

16.当线性表采用顺序存储结构实现存储时，其主要特点是逻辑结构中相邻的结点在存储结构中仍相邻。

17. 循环队列主要有两种基本运算：入队运算与退队运算。

每进行一次入队运算，队尾指针就进1 。

18.当循环队列非空且队尾指针等于对头指针时，说明循环队列已满，不能进行入队运算。

这种情况称为上溢。

19.当循环队列为空时，不能进行退队运算，这种情况称为下溢。

20. 在一个容量为25的循环队列中，若头指针front=16，尾指针rear=9，则该循环队列中共有18 个元素。

注：当rear当rear>front时，元素个数＝rear－front。

21. 在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有3 个元素。

数据结构是指同一数据元素类中各数据元素之间存在的关系。

数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。

数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。

逻辑结构形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。

数据元素相互之间的关系称为结构。

有四类基本结构：集合、线性结构、树形结构、图状结构（网状结构）。

树形结构和图形结构全称为非线性结构。

集合结构中的数据元素除了同属于一种类型外，别无其它关系。

线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

在图形结构中每个结点的前驱结点数和后续结点数可以任意多个。

数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。

它包括数据元素的表示和关系的表示。

数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。

顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。

顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。

链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。

由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。

索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。

散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。

线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。

线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

数据结构的三个方面
数据结构包括数据的逻辑结构、数据的物理结构、数据存储结构三个方面。

1、数据的逻辑结构
指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。

2、数据的物理结构
数据的物理结构是数据结构在计算机中的表示(又称映像)，它包括数据元素的机内表示和关系的机内表示。

由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成—种或多种存储结构。

3、数据存储结构
数据的逻辑结构在计算机存储空问中的存放形式称为数据的物理结构（也称为存储结构)。

一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。

数据结构的逻辑结构及物理结构数据结构是计算机科学的重要基础，它研究了数据的组织方式和存储结构，为解决实际问题提供了有效的数据处理方法。

数据结构的逻辑结构和物理结构是数据结构的两个重要方面，它们分别描述了数据之间的关系和数据在存储器中的表示方式。

一、逻辑结构逻辑结构是指数据元素之间的关系，描述了数据元素之间的逻辑关系，不涉及具体的存储方式。

常见的逻辑结构有线性结构、树形结构和图形结构。

1. 线性结构线性结构是最基本的逻辑结构，数据元素之间是一对一的关系。

其中，线性表是最简单的线性结构，数据元素之间只有"前驱"和"后继"的关系，比如数组和链表。

栈和队列是线性表的特殊形式，它们分别满足"先进后出"和"先进先出"的原则。

2. 树形结构树形结构是由节点和边组成的非线性结构，节点之间存在着一对多的关系。

其中，树是最常用的树形结构，它是由一个根节点和若干个子树组成，每个子树也是一棵树。

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

3. 图形结构图形结构是由顶点和边组成的非线性结构，顶点之间可以存在任意关系。

图是最常用的图形结构，它分为有向图和无向图，顶点之间通过边连接。

图的常用算法有深度优先搜索和广度优先搜索。

二、物理结构物理结构是指数据在计算机存储器中的表示方式，也称为数据的存储结构。

常见的物理结构有顺序存储结构和链式存储结构。

1. 顺序存储结构顺序存储结构将数据元素逐个存放在计算机存储器的连续存储单元中，数据元素的逻辑关系由元素在存储器中的相对位置来表示。

数组是常用的顺序存储结构，它具有随机访问的特点，可以通过索引直接访问任意位置的元素。

2. 链式存储结构链式存储结构使用指针将数据元素连接在一起，每个元素包含数据和指向下一个元素的指针。

链表是常用的链式存储结构，它灵活地插入和删除节点，但访问元素需要通过指针遍历。

三、逻辑结构与物理结构之间的映射关系逻辑结构和物理结构之间存在着一一对应的映射关系。

第一章绪论考点1 数据结构基础知识1.数据的逻辑结构是指（），数据的存储结构是指（）分析：数据结构包括三方面的内容：数据的逻辑结构、存储结构和数据的运算。

其中，逻辑结构是指各数据元素之间的逻辑关系，存储结构是指逻辑结构用计算机语言的实现。

解答：数据元素之间的逻辑关系；数据的逻辑结构用计算机语言的实现。

2.在数据结构中，从逻辑上可以把数据结构分为：（A）A 线性和非线性结构B 紧凑和非紧凑结构C 动态和静态结构D 内部和外部结构分析：数据结构中，逻辑上可以把数据结构分成线性结构和非线性结构。

线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存储结构。

线性表若采用链式存储表示时，所有结点之间的存储单元地址可连续可不连续。

逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数无关。

关键考点点评：线性结构的特征，有且仅有一个开始结点和终端结点，所有结点最多只有一个直接前驱和后继。

栈和队列。

非线性结构的结点有多个前驱或后继，树和图。

3.数据结构在物理上可以分为（）存储结构和链式存储结构。

分析：物理存储解答：顺序4.下列术语中，（）与数据的存储结构无关A 循环队列B 堆栈C 散列表D 单链表解答： A5.（）不是算法所必须具备的特性A 有穷性B 确定性C 高效性D 可行性分析：算法的五个重要特征：有穷性、确定性、可行性、输入和输出。

解答：C考点2 时间复杂度计算1.设n是描述问题规模的非负整数，下面程序段的时间复杂度是（）2.第二章线性表考点1 线性表的基本概念1.线性表是n个（）的有限序列。

A 字符B数据元素 C 由数据项 D 信息项解析：解答 B2.线性表是一个（）。

A 有限序列，可以为空B 有限序列，不能为空C 无限序列，可以为空D 无限序列，不能为空解答 A关键考点点评：对于非空线性表1.有且仅有一个开始结点，没有直接前驱，有且仅有一个直接后继；2.有且仅有一个终结结点，没有直接后继，有且仅有一个直接前驱；3.其余的内部结点都有且仅有一个直接前驱和后继3.单链表不能随机存取元素原因是：要得到元素的存储地址，必须（）解答：从起始结点开始扫描以得到其地址注：顺序表可以，但是链表不行考点2 线性表的顺序存储结构1.下述（）是顺序存储结构的优点A 插入运算方便B 可方便地用于各种逻辑结构的存储表示C 存储密度大D 删除运算方便解答： C2.线性表的（）存储结构是随机存储结构。

习题六一、用适当内容填空1．数据结构是指具有相同特征、相互关联的数据集合。

2．数据结构主要研究数据的逻辑结构、数据的存储结构，以及算法。

3．数据之间有四种逻辑结构，分别是集合、线性、树形和图形。

4．根据数据结构中数据元素之间前件与后件关系的复杂程度，将数据的逻辑结构分为线性结构和非线性结构。

5．在数据的存储结构中，不仅要存放各个数据元素，还要存放数据元素之间前后件关系信息。

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

6．数据元素在计算机中通常有4种存储方式，即顺序、链式、索引和散列。

7．顺序存储结构是指在内存中开辟一块连续的单元用于存放数据，逻辑上相邻的结点在物理位置上也邻接，结点之间的逻辑关系由存储单元的相邻关系来体现。

8．在链式存储结构中，结点由两部分组成：一部分用于存放数据元素的值，称为数据域；另一部分用于存放前件或后件的存储地址，称为指针域。

链式存储结构是通过指针反映出数据元素之间的逻辑关系。

9．算法的设计基于数据的逻辑结构，而算法的实现依赖于数据的存储结构。

10．一个算法应该具有的基本特征有可行性、确定性、有穷性、输入性和输出性。

11．算法的复杂度有时间复杂度和空间复杂度。

12．栈是在表的同一端进行插入运算和删除运算的线性表。

将允许进行插入运算和删除运算的一端称为栈顶，另一端称为栈底。

栈遵循先进后出或后进先出的原则。

13．队列是在一端进行插入运算，而在另一端进行删除运算的线性表。

允许删除的一端称为队头，允许插入一端称为队尾。

队列遵循先进先出或后进后出的原则。

14．所谓循环队列是将队列的存储空间想象成一个首尾相连的环状空间。

15．判断循环队列为满的条件是(rear+1)%n = front 。

16．判断循环队列为空的条件是front = rear 。

17．树是一种常用的非线性结构，树结构中结点之间即具有分支关系又具有层次关系。

18．在树结构中，有且只有一个根结点，根结点有0 个前件，其他结点有 1 个前件。

数据结构各章概要第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，可以由若干个数据项组成。

数据项是具有独立含义的最小标识单位。

************************************************************数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。

·线性结构：一对一关系。

·非线性结构：一对多关系，多对多关系。

·存储结构：是逻辑结构用计算机语言的实现。

·顺序存储结构：如数组。

·链式存储结构：如链表。

·索引存储结构：·稠密索引：每个结点都有索引项。

·稀疏索引：每组结点都有索引项。

·散列存储结构：如散列表。

·数据运算。

·对数据的操作。

定义在逻辑结构上，每种逻辑结构都有一个运算集合。

·常用的有：检索、插入、删除、更新、排序。

************************************************************数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

·原子类型：由语言提供。

·结构类型：由用户借助于描述机制定义，是导出类型。

抽象数据类型ADT：·是抽象数据的组织和与之的操作。

相当于在概念层上描述问题。

·优点是将数据和操作封装在一起实现了信息隐藏。

************************************************************程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。

算法取决于数据结构。

************************************************************算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。

数据结构类型数据的逻辑结构：数据的逻辑结构指元素之间的逻辑关系(和现实⽆关)。

分类⼀：线性结构和⾮线性结构 线性结构：有且只有⼀个开始结点和⼀个终端结点，并且所有结点都最多只有⼀个直接前驱和⼀个直接后继。

线性表就是⼀个典型的线性结构，它有四个基本特征： 1.集合中必存在唯⼀的⼀个"第⼀个元素"； 2.集合中必存在唯⼀的⼀个"最后的元素"； 3.除最后元素之外，其它数据元素均有唯⼀的"直接后继"； 4.除第⼀个元素之外，其它数据元素均有唯⼀的"直接前驱"。

⽣活中的案例：冰糖葫芦、排队上地铁⾮线性结构： 相对应于线性结构，⾮线性结构的逻辑特征是⼀个结点元素可能对应多个直接前驱和多个直接后继。

常见的⾮线性结构有： 树(⼆叉树等)，图(⽹等)。

树：⼀个结点可以对应多个直接后继，但每个结点只能对应⼀个直接前驱(⼀对多) 图(⽹)：⼀个结点可以对应多个直接后继和直接前驱(多对多)　树：⽣活案例 单位组织架构、族谱技术案例：⽂件系统图：⽣活案例 交通线路图、地铁线路图分类2：集合结构、线性结构、树状结构、⽹络结构 逻辑结构有四种基本类型：集合结构、线性结构、树状结构和⽹络结构。

　表和树是最常⽤的两种⾼效数据结构，许多⾼效的算法能够⽤这两种数据结构来设计实现。

1.集合结构： 就是数学中所学的集合，集合中的元素有三个特征： 1).确定性(集合中的元素必须是确定的) 2).唯⼀性(集合中的元素互不相同。

例如：集合A={1,a},则a不能等于1) 3).⽆序性(集合中的元素没有先后之分。

例如：集合{3,4,5}和{3,5,4}算作同⼀个集合)　该结构的数据元素之间的关系是"属于同⼀个集合"，此外⽆其他关系。

　因为集合中元素关系很弱，数据结构中不对该结构进⾏研究。

2.线性结构： 数据结构中线性结构指的是数据元素之间存在着"⼀对⼀"的线性关系的数据结构。

栈和队列的共同特点是__________________________.栈通常采用的两种存储结构是______________________.用链表表示线性表的优点是_______________________8.在单链表中，增加头结点的目的是___________________9.循环链表的主要优点是________________________-12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________13.树是结点的集合，它的根结点数目是_____________________14.在深度为5的满二叉树中，叶子结点的个数为_______________15.具有3个结点的二叉树有（_____________________16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。

在计算机中，算法是指_______________________算法一般都可以用哪几种控制结构组合而成_____________________.算法的时间复杂度是指______________________5. 算法的空间复杂度是指__________________________6. 算法分析的目的是__________________________11. 数据的存储结构是指_________________________12. 数据的逻辑结构是指（_______________________________13. 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为__________________________________16. 递归算法一般需要利用_______________________实现。

数据结构课后习题部分参考答案第一章一、选择题1．C 2．C 3．A 4．D 5．B二、判断题1．╳2．╳ 3．╳ 4．╳5．∨三、简答题1．常见逻辑结构：集合结构，数据元素之间的关系仅仅是属于同一个集合。

线性结构，除第一个元素只有一个直接后继、最后一个元素只有一个直接前驱，其余元素有且只有唯一一个直接前驱、有且只有唯一一个直接后继，数据元素之间存在一对一的关系。

树形结构，树中只有唯一一个根元素，除根元素之外，其余元素只有一个直接前驱，但可以有多个直接后继元素，数据元素之间存在一对多的关系。

图形结构，元素之间关系任意，数据元素之间存在多对多的关系。

常用的存储结构：顺序存储，把逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。

通常用数组实现。

链式存储，对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附加的指针字段来表示，由此得到的存储表示称为链式存储结构。

通常用指针来实现。

除上述两种方法外，有时为了查找方便还采用索引存储方法和散列存储方法。

索引存储：在存储结点信息的同时，还建立附加的索引表来标识结点的地址。

散列存储：根据元素的关键码确定元素存储位置的存储方式。

2．算法与程序的区别：程序不一定满足有穷性(如操作系统)；程序中的指令必须是机器可执行的，算法中的指令则无此限制；算法代表了对问题的解，程序则是算法在计算机上的特定的实现(一个算法若用程序设计语言来描述，它才是一个程序);数据结构+算法=程序。

3．例如有一张学生成绩表，记录了一个班的学生各门课的成绩。

按学生的姓名为一行记成的表。

这个表就是一个数据结构。

每个记录就是一个结点，对于整个表来说，只有一个开始结点和一个终端结点，其他的结点则各有一个也只有一个直接前趋和直接后继。

这几个关系就确定了这个表的逻辑结构——线形结构。

那么我们怎样把这个表中的数据存储到里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录（顺序存储）还是随机存放各结点数据再用指针进行链接（链式存储）呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。

数据结构重点知识点第一章概论1. 数据是信息的载体。

2. 数据元素是数据的基本单位。

3. 一个数据元素可以由若干个数据项组成。

4. 数据结构指的是数据之间的相互关系，即数据的组织形式。

5. 数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算①数据元素之间的逻辑关系，也称数据的逻辑结构，数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。

②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。

数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。

③数据的运算，即对数据施加的操作。

最常用的检索、插入、删除、更新、排序等。

6. 数据的逻辑结构分类: 线性结构和非线性结构①线性结构：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。

线性表是一个典型的线性结构。

栈、队列、串等都是线性结构。

②非线性结构：一个结点可能有多个直接前趋和直接后继。

数组、广义表、树和图等数据结构都是非线性结构。

7.数据的四种基本存储方法: 顺序存储方法、链接存储方法、索引存储方法、散列存储方法（1）顺序存储方法：该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

通常借助程序语言的数组描述。

（2）链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。

通常借助于程序语言的指针类型描述。

（3）索引存储方法：该方法通常在储存结点信息的同时，还建立附加的索引表。

索引表由若干索引项组成。

若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引，稠密索引中索引项的地址指示结点所在的存储位置。

若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引稀疏索引中索引项的地址指示一组结点的起始存储位置。

索引项的一般形式是：(关键字、地址)关键字是能唯一标识一个结点的那些数据项。