第一章数据结构与算法。
1.1算法。
算法：是指解题方****而完整的描述。1
算法特征：1）可行性；
2）确定性：每个步骤必须有明确定义，不能模棱两可；
3）有穷性：在有限个步骤后终止；
4）拥有足够的情报：
算法的基本要素：
1）对数据对象的运算和操作：：包括算术运算；逻辑运算；关系运算；数据传输。
2）算法的控制结构：算法中各操作之间的执行顺序。包括顺序；选择；循环。
常用工具：传统流程图、n－s图、算法描述语言。
算法设计的基本方法：
1）列举法：列举所有可能；
2）归纳法：列举少量可能，经分析，找出一般规律；
3）递推法：从已知条件出发，逐步找结果；
4）递归法：将问题逐层分解，再沿分解的逆过程逐步综合。
自己调用自己叫直接递归；通过别人调用自己叫间接递归调用。
5）减半递推技术：问题规模减半，性质不变。
算法复杂度：4
1）时间复杂度：执行算法所需要的计算工作量。
2）空间复杂度：执行这个算法所需要的内存空间。2
1.2数据结构的基本概念。
数据结构研究的三个方面：
1）数据的逻辑结构：数据元素之间的逻辑关系。
2）数据的存储结构（物理结构）：逻辑结构在计算机中的存放形式。1 常用的有顺序、链接、索引。2
3）对各种数据结构进行的运算。
逻辑结构与存储结构的关系：一种数据的逻辑结构根据需要可以表示成多种存储结构，而采用不同的存储结构，其数据处理的效率是不同的。2
数据结构：相互有关联的数据元素的集合。
数据结构的表示方法：（1）图形；（2）二元关系。
逻辑结构的两要素：（1）数据元素集合（d） （2）d上的关系（r）
线性结构条件： （1）有且只有一个根结点；
2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构条件：不满足线性结构条件的数据结构。
1.3线性表及其顺序存储结构。
线性表：由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置。
是线性的。非空线性表的结构特征：
1）且只有一个根结点a ，它无前件；
2）有且只有一个终端点a ，它无后件；
3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
线性表的长度：结点个数n（当n=0时，称为空表）。
线性表的顺序存储结构的两个基本特点：
1）所有元素的存储空间是连续的；
2）所有元素在存储空间中是按逻辑顺序依次存放的。
顺序表（注意：专指顺序存储的线性表）的基本操作：
1）插入：在n个长的顺序表中第i个元素前插入一个元素，需要移动n-i+1个元素，表长变为n+1。
2）删除：在n个长的顺序表中删除第i个元素，需要移动n-i个元素，表长变为n-1。
1.4栈和队列。
栈：限定在一端进行插入与删除的线性表。
允许插入与删除的一端称为栈顶（top），不允许插入与删除的另一端称为栈底（bottom）。2
栈是“先进后出”3（filo）、“后进先出”（lifo）的线性表。4
栈具有记忆作用。1
栈的基本运算：
1）入栈运算：在栈顶插入一个元素。
2）退栈运算：删除栈顶元素。
3）读栈顶元素：将栈顶元素赋给某个变量。
队列：是指允许在一端进入插入，而在另一端进行删除的线性表。
允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。
队列是“先进先出”（fifo）或“后进后出”（lilo）的线性表。
队列的基本运算：
1）入队运算：从队尾插入一个元素；
2）退队运算：从队头删除一个元素。
1.5线性链表。
线性表的链式存储结构称为线性链表。3
数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。
结点由两部分组成：
1）用于存储据元素值，称为数据域；
2）用于存放指针，称为指针域，用于指向前一个或后一个结点。
链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。1
链式存储方式即可用于表示线性结构，也可用于表示非线性结构。
线性链表的基本运算：查找、插入、删除。
循环链表的特点：
1）增加了一个头结点。
2）链表中最后一个结点指向头结点。
循环链表中所有的结点连成一个环状链，只要指出表中的任意一个结点就能找出其他所有结点。循环链表实现了空表和非空表的统一。
1.6树与二叉树。
树是一种简单的非线性结构，所有元素之间具有明显的层次特性。
树中结点的度：结点后件的个数。度为0的结点称为叶子。
树的度：树中度最大的结点的度。
树的深度：树的层数。
二叉树：度为2的树。
二叉树的基本性质：
1）在二叉树的第k层上，最多有个结点；2
2）深度为m的二叉树最多有个结点；3
3）度为0的结点（即叶子结点）总是比度为2的结点多一个；1
4）具有n个结点的二叉树，其深度至少为；
5）具有n个结点的完全二叉树的深度为；
满二叉树：除最后一层外，每一层上的所有结点有两个子结点，则k层上有n 个结点深度为m的满二叉树有2 -1个结点。
完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
二叉树一般采用链式存储结构，但特别的对于满二叉树与完全二叉树可以按层序进行顺序存储。
二叉树的遍历：
1）前序遍历（dlr），首先访问根结点，然后遍历左子树，最后遍历右子树；
2）中序遍历（ldr），首先遍历左子树，然后访问根结点，最后遍历右子树；4
3）后序遍历（lrd），首先遍历左子树，然后访问遍历右子树，最后访问根结点。3
1.7查找技术。
顺序查找对于长度为n的有序线性表，最坏情况只需比较n次。4
二分法查找只适用于顺序存储的有序表，2对于长度为n的有序线性表，最坏情况只需比较次。1
1.8排序技术。
交换类排序法：（1）冒泡排序法，需要比较的次数为；3
特点：相邻数据元素交换。
2）快速排序法。一般情况；最坏情况为1。
插入类排序法：（1）简单插入排序法，最坏情况需要次比较；
特点：将元素依次插入到表中。
2）希尔排序法，最坏情况需要次比较。
特点：将无序序列分隔成若干小的子序列进行插入排序。
选择类排序法：（1）简单选择排序法，最坏情况需要n(n-1)/2次比较；
特点：找到最小的排到表的最前面。
2）堆排序法，最坏情况需要次比较。
2 (5) 数据结构分为逻辑结构和存储结构，循环队列属于 【5】 结构。
1算法与数据结构
算法与数据结构综合应用。数值计算问题 1 打印所有的 水仙花数 所谓 水仙花数 是指一个三位数，其各位数字立方和等于该数字本身，例如 2 一个数如果恰好等于它的因子之和，这个数就称为 完数 例如 6的因子为 而6 1 2 3，因此6是 完数 编程序找出1000以内的所有完数。3 已知四位数3025有...
算法与数据结构 1 1
第1章 1.3.2 p7 环路复杂度。1.3.3 p9 10 时间复杂度的计算，大o记号 p22 9 第2章 2.2.2 p31 地址计算公式 p49 4 2.2.3 p32 矩阵压缩。2.3.3 p41 模式匹配改进算法next函数值的计算 p50 18 第3章 3.3 p69 栈的考察 p90 ...
考点1数据结构与算法
1 答案 d 解析 算法是指解题方 而完整的描述，算法既不等于程序，也不等于计算方法，因此a 错误。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构，因此b 和c 错误。2 答案 a 解析 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。算法的有穷性是指算法程序的...