1算法。
考试的内容：
1.1 算法的基本概念。
1．算法的概念(必记)：
算法是指解题方****而完整的描述。
分析：要用计算机实现某一任务时，先应设计出一整套解决问题的指导方案，然后具体实现。
整套的指导方案称之为算法，而具体的实现称之为程序。并且在设计指导方案时，可不用过多考虑到实现程序的具体细节(即可以一点点的理想化)，但在程序实现时，必须受到具体环境的约束(现实不同于理想)。
结论：算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。
2．算法的基本特征(必记)：
a.可行性：由于算法总是在某个特定的计算工具上实现并执行的，因而受到计算工具的限制，所以在设计算法时，要考虑到设计的算法是否是可性的。
b.确定性：算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允。
许有多义性。
c.有穷性：算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。
d.拥有足够的情报：算法有相应的初始数据。
3．算法的基本要素：
一个算法通常由两个基本要素所组成：一是对数据对象的运算和操作，二是算法的控制结构。
基本运算和操作分为四类：
a. 算术运算： (加、减、乘、除等运算)
b. 逻辑运算： (与、或、非等运算)
c. 关系运算： (大于、小于、等于、不等于等运算)
d. 数据传输： (赋值、输入、输出等操作)
算法的控制结构：
算法中各操作之间的执行顺序称之为算法的控制结构。一个算法一般都可以用顺序、选择、
循环三种基本控制结构组合而成。
注意：一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。
4．算法设计基本方法：
列举法、归纳法、递推、递归、减半递推技术、回溯法。
1.2 算法的复杂度 (必记)
算法的复杂度主要包括时间复杂度和空间复杂度。
1．算法的时间复杂度：
是指执行算法所需要的计算工作量，是由算法所执行的基本运算次数来度量。
可用平均性态和最坏情况两种分析方法。其中平均性态分析是指用各种特定输入下的基本运。
算次数的加权平均值来度量算法的工作量；而最坏情况分析是指在所有特定输入下的基本运算次数据的最大次数。
2．算法的空间复杂度：
一个算法的空间复杂度，是指执行这个算法所需要的内存空间。包含有三部分所组成：算法。
程序所占的空间+输入的初始数据所占的存储空间+算法执行过程中所需要的额外空间。
1.2数据结构与算法。
考试的内容：
数据结构作为计算机的一门学科，主要研究以下三个方面的问题：
a．数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
b．在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；
c．对各种数据结构进行的运算。
注意：讨论以上问题主要目的是为了提高数据处理的效率。提高效率包括两个方面：一是提。
高数据处理的速度，二是节省在数据处理过程中所占用的计算机存储空间。
2.1 什么是数据结构。
简单地说，数据结构是指相互有关联的数据元素的集合。 而数据元素之间的关联通常是指。
其前后件关系(即先后顺序关系)，如春、夏、秋、冬之间的先后顺序关系。
因此，一个数据结构应包含以下两方面的信息：a.表示数据元素的信息； b.表示各数据元素。
之间的前后件关系。
1．数据的逻辑结构。
所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。注意：这种逻辑关系仅。
指元素之间的固有的一个先后顺序关系，而与它们在计算机中的存储顺序无关。
2．数据的存储结构。
数据的存储结构的概念：数据的逻辑结构在计算机存储空间中的存放形式 (也称数据的物理。
结构)。注意：
a、数据元素在计算机中存储空间中的位置关系可以与它们的逻辑关系相同，也可以不相同。
b、数据的存储结构有顺序、链接、索引等。
c、数据元素采用不同的存储结构，其数据处理的效率是不同的。
2.2 数据结构的图形表示。
一般用一个中间标有元素值的方框表示一个数据元素，用一条有向线段从前件结点指向后件。
结点。在数据结构中，没有前件的结点成为根结点(如上图中的春与父亲)；没有后件的结点称为终。
端结点 (也称为叶子结点，如上图中的冬与儿子和女儿)。
注意：在进行处理时，一个数据结构中的元素结点可能是在动态变化的。这种变化可能是元。
素结点的个数发生变化，也可以是元素结点的先后顺序发生变化。
2.3 线性结构与非线性结构。
空的数据结构是：一个数据元素都没有的数据结构。
根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分为二大类：线性结。
构和非线性结构。
一个非空的数据结构满足下列两个条件，则为线性结构，线性结构又称为线性表。
a. 有且只有一个根结点； b.每一个结点最多有一个前件，也最多有一个后件。
在上图中，左边的是线性结构，而右边的是非线性结构。
注意：线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟属于线性结构。
还是属于非线性结构，要根据具体情况来确定。如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。
1.3线性表及其顺序存储结构。
考试的内容：
3.1 线性表的基本概念。
非空线性表的结构特征如下：
a.有且只有一个根结点，它无前件； b.有且只有一个终端结点，它无后件； c.除根结点与。
终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
线性表中结点的个数 n 称为线性表的长度。当n=0 时，称为空表。
3.2 线性表的顺序存储结构。
线性表的顺序存储结构具有以下两个基本特点：
a.线性表中所有元素所占的存储空间是连续的；
b.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
注意：**性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素。
一定在后件元素的前面。
**性表的顺序存储结构中，如第一个元素的地址为adr(a1)，每个元素占用的存储空间大。
小为k 个字节，则线性表中第i个元素的存储地址为：adr(a1)+(i-1)*k。
3.3 顺序表的插入运算。
**性表的顺序存储结构中，当插入元素时，插入点后的元素都要向后移动一位，以让出一。
个存储空间。
在平均情况下，要**性表中插入一个新元素，需要移动表中一半的元素。因此，**性表。
顺序存储的情况下，要插入一个新元素，其效率是很低的。
3.4 顺序表的删除运算。
**性表的顺序存储结构中，当删除元素时，删除点后的元素都要向前移动一位，以保证元。
素都是相邻存储的。
在平均情况下，要**性表中删除一个元素，需要移动表中一半的元素。因此，**性表顺。
序存储的情况下，要删除一个元素，其效率是很低的。
1.4栈和队列。
注意的考点：
4.1 栈及其基本运算。
1．什么是栈。
栈是一种特殊的线性表。栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端。
称为栈顶，不允许插入与删除的一端称为栈底。
栈按照"先进后出" (filo)或"后进先出" (lifo)组织数据，栈具有记忆作用。用top 表示栈顶。
位置，用botton表示栈底。
2．栈的顺序存储及其运算。
栈的基本运算有三种：.入栈运算、退栈运算和。读栈顶元素。
4.2 队列及其基本运算。
1．什么是队列。
队列是允许在一端进行插入、而在另一端进行删除的特殊的线性表。允许插入的一端称为队。
尾，允许删除的一端称为排头(或队头)。
队列又称为"先进先出"(fifo)或"后进后出"(lilo)的线性表，它体现了"先来先服务"的原则。
往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。
2．循环队列及其运算。
所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空。
间，供队列循环使用。
队列空和队列满的条件如下：
队列空的条件为 s=0 ;
队列满的条件为 s=1 且front=rear.
循环队列主要有两种基本运算：入队运算和退队运算。
a.入队运算：在循环队列的队尾加入一个新元素，首先将队尾指针进一(即rear=rear+1)，并当rear=m+1 时置rear=1；然后将新元素插入到队尾指针指向的位置。
注意：当循环队列非空 (s=1)且队尾指针等于排头指针时，说明循环队列已满，不能进行入。
队运算，这种情况称为"上溢"。
b.退队运算：指在循环队列的排头位置退出一个元素并赋给指定的变量。首先将排头指针进。
一(即front=front+1)，并当front=m+1 时置front=1;然后将排头指针指向的元素赋给指定的变量。
注意：当循环队列为空 (s=0)时，不能进行退队运算，这种情况称为"下溢" 。
1.5线性链表。
注意的考点：
5.1 线性链表的基本概念。
1.链式存储。
在顺序存储方式中所有的数据元素在内存中是相邻存放的，从而造成了在插入与删除数据元。
素时，需要大量移动相应的数据元素。为了解决这种问题，可以将每个数据元素存储在内存中不相邻的不同位置，并利用上一个数据元素在存有数据的同时，也存放下一个数据元素所在的位置地址(称为一个存储单元，即结点)，以便查找。这就是链式存储方式。
在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；
另一部分用于存放地址，称为指针域。其中指针用于指向该结点的前一个或后一个结点 (即前件或后件)。
注意：a、在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与。
数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
b、链式存储方式既可以用于表示线性结构，也可以用于表示非线性结构。在用链式结构表。
示较复杂的非线性结构时，其指针域的个数要多一些。
2．线性链表。
线性表的链式存储结构称为线性链表。 如果结点中有两个指针，一个用于指向前一个结点，而另一上用于指向后一个结点，则称之为双向链表。
3．带链的栈：栈的链式存储结构称为带链的栈。
4．带链的队列：队列的链式存储结构称为带链的队列。
5.2 线性链表的基本运算 ：查找、插入、删除。
1.6树与二叉树。
注意的考点：
6.1 树的基本概念。
树是一种简单的非线性结构，所有元素之间具有明显的层次特性。
a.在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树。
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...