第一章数据结构与算法.doc

1.1 算法1.1.1 算法的基本概念算法：是指解题方案的准确而完整的描述1、算法的基本特性（1） 可行性：针对实际问题设计的算法，人们总希望能够得到满意的结果。在设计算法时，必须要考虑它的可行性，否则是不会得到满意结果的。（2） 确定性 ：是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。 （3）有穷性：是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。 （4）拥有足够的情报：一个算法是否有效，还取决于为算法所提供的情报是否足够。2、算法的基本要素（1） 算法中对数据的运算和操作（2） 算法的控制结构 3、算法设计的基本方法（1） 列举法 思想是：根据提出的问题，列举所有可能的情况。（2） 归纳法思想是：通过列举少量的特殊情况，经过分析，最后找出一般的关系。（3） 递推是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。（4） 递归 为了降低问题的复杂程度，将问题逐层分解，最后归结为一些最简单的问题。（5） 减半递推技术1.1.2 算法复杂度 1、算法的时间复杂度是指执行算法所需要的计算工作量 2、算法的空间复杂度是指执行这个算法所需要的内存空间* 算法分析的目的：分析算法的效率以求改进 1.2数据结构的基本概念1.2.1 什么是数据结构杂乱无章的数据是不便于处理的数据的逻辑结构：数据集和中各数据元素之间所固有的逻辑关系。是指反映数据元素之间逻辑关系的数据结构数据的存储结构：在对数据进行处理时，各数据元素在计算机中的存储关系。是指数据的逻辑结构在计算机中的表示 数据结构：是指反映数据元素之间关系的数据元素集合的表示1.2.2 数据结构的图形表示（11页）1.2.3 线性结构与非线性结构 如果一个非空的数据结构满足下列两个条件： （1） 有且只有一个根结点（2） 每一个结点最多有一个前件，也最多有一个后件则称该数据结构为线性结构。又称线性表如果一个数据结构不是线性结构，则称之为非线性结构1.3 线性表及其顺序存储结构1.3.1 线性表的基本概念 线性表是一种线性结构。非空线性表有如下结构特性：（1） 有且只有一个根结点a1,它无前件（2） 有且只有一个终端结点an ,它无后件（3） 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点个数n称为线性表的长度。当n=0时，称为空表1.3.2 线性表的顺序存储结构有以下两个基本特点：（1） 线性表中所有元素所占的存储空间是连续的（2） 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。1.3.3 顺序表的插入和删除运算（14页） 1.4栈和队列1.4.1 栈及其基本运算 1、什么是栈实际也是线性表，只不过是一种特殊的线性表。一端是封闭的，不允许进行插入与删除元素，另一端是开口的，允许插入与删除元素。在顺序存储结构下，对这种类型线性表的插入与删除运算是不需要移动表中其他数据元素的。这种线性表称为栈 在栈中，允许插入与删除的一端称为栈顶，不允许插入和删除的另一端称为栈底。栈是按照“先进后出“或“后进先出“的原则组织数据的。 2、栈的顺序存储及其运算三种运算：入栈、退栈与读栈（1） 入栈：首先将栈顶指针进一（即top加1），然后将新元素插入到栈顶指针指向的位置。（2） 退栈：首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针退一（即top减1）（3） 读栈：这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中，栈顶指针不会改变。1.4.2 队列及其基本运算 1、什么是队列：需要加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出（删除）元素。这种线性表称为队列。 队列是“先进先出”或“后进后出“的线性表。它体现了“先来先服务”的原则。 在队列的末尾插入一个元素（入队运算）只涉及队尾指针rear的变化，而要删除队列中的排头元素（退队运算）只涉及排头指针front的变化。 2、循环队列及其运算 是指将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。 两种基本运算：入队与退队 （1）入队运算是指在循环队列的队尾加入一个新元素。首先将队尾指针进一（即rear=rear+1）,并当rear=m+1时置rear=1;然后将新元素插入到队尾指针指向的位置（3） 退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。首先将排头指针进一（即front=front+1）,并当front=m+1时置front=1;然后将排头指针指向的元素赋给指定 的变量。1.5.线性链表 线性表的顺序存储存在的缺点：a)插入和删除会引起大量结点的移动，运算效率低。b) 线性表的存储空间不便于扩充 c)不便于对存储空间的动态分配 (1). 线性链表的基本概念：线性表的链式存储结构称为线性链表。1. 线性链表线性链表的链式存储结构：线性链表的每个结点中数据域存放数据元素的值，指针域存放后件结点的存储地址。 双向链表的链式存储结构：双向链表的链式存储结构比线性链表的链式存储结构多出一个指针域，它用来存放前件结点的存储地址。注：线性链表的存储空间不一定是连续的。且各元素的存储顺序是任意的。2 带链的栈栈的链式结构：栈的链式结构基本上和线性链表的链式存储结构相同。只是线性链表的链式存储结构的头指针变成了栈的链式结构的栈顶指针。3 带链的队列队列的链式结构：队列的链式结构和线性链表的链式存储结构也基本相同。只不过队列的链式结构保持有两个指针：一个指向队列头的头指针和一个指向队列尾的尾指针。 (2). 线性链表的基本运算线性链表的主要运算：线性链表的主要运算有线性链表的插入、线性链表的删除、线性链表的合并、线性链表的分解、线性链表的逆转、线性链表的复制、线性链表的排序、线性链表的查找。线性链表的查找：线性链表的查找过程是从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为搜索值x为止。线性链表的插入：线性链表的插入是先从栈中为新元素分配一个新的结点p，并赋值。然后利用线性链表的查找算法找到待插入位置的前一个结点的指针q，先将p指向q的后件，然后将p挂接在q结点后面。线性链表的删除：利用线性链表的查找算法找到待删除元素的前一个结点p，用另一个指针q暂时保存p的后续结点（即待删除结点），然后把q结点的后续链直接挂接在p的后面。最后归还q结点所分配的栈空间。(3) 循环链表及其基本运算 循环链表有如下几个特点：在循环链表中增加一个表头结点，使得循环链表对空表和非空表的操作实现统一。循环链表中最后一个结点的指针域不是空，而是指向表头结点。判断循环链表是否为空的办法不是看表头指针为空，而是看表头结点的后续结点是否还是表头结点。在循环链表中，从任何一个结点出发可以访问到表中其他所有的结点。1.6树与二叉树(1) 树的基本概念基本术语：父结点：在树结构中，每一个结点只有一个前件称为父结点。根结点：没有前件的结点只有一个，称为树的根结点。子结点：在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。叶子结点：没有后件的结点称为叶子结点。结点的度：一个结点所拥有的后件个数称为该结点的度。树的度：所有结点中的最大的度称为树的度树的深度：树的最大层次称为树的深度。根结点在第一层。子树：以某结点的一个子结点为根构成的树称为该结点的一棵子树。叶子结点没有子树。要求考生掌握用树表示算术表达式的方法（具体见试题分析部分的解答过程）。（2）二叉树及其基本性质二叉树的特点：二叉树具有以下两个特点，一是非空二叉树只有一个根结点，二是每一个结点最多有两棵子树。二叉树的基本性质：性质1 在二叉树的第k层上，最多有2k-1(k=1)个结点。性质2 深度为m的二叉树是指二叉树最多有2m 1个结点。性质3 在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。性质4 具有n个结点的二叉树，其深度至少为log2n+1，其中log2n表示log2n的整数部分。（3）满二叉树和完全二叉树性质5 满二叉树的第k层上有2k-1个结点，且其深度为m的满二叉树有2m 1个结点。性质6 具有n个结点的完全二叉树的深度为log2n+1。（4）二叉树的存储结构L(i)V(i)R(i)L(i)：左指针域，指向该结点的左子结点。（存放左子结点的存储地址）R(i)：右指针域，指向该结点的右子结点。（存放右子结点的存储地址）V(i)：数据域，存放结点的值。 （5）二叉树的遍历二叉树的遍历集中用到了递归的思想，它主要有以下三种遍历方式：前序遍历（DLR）：先访问根结点，后访问遍历左子树，再访问遍历右子树。中序遍历（LDR）：先访问遍历左子树，后访问根结点，再访问遍历右子树。后序遍历（LRD）：先访问遍历左子树，后访问遍历右子树，再访问根结点。1.7 查找技术（1）顺序查找查找方法：从表头到表尾逐个比较，若相同则结束查找，否则一直继续比较下一个表中元素直到整个表都遍历完。适用场合：无序表或链式存储的有序表。（2）二分查找查找方法：每次把待查找值与表中间元素比较，以减半的方式缩小搜索范围。适用场合：顺序存储的有序表。排序技术（1）交换类排序 常用的交换类排序有：冒泡排序法；快速排序法。（2）插入类排序 常用的插入类排序有：简单插入排序法；希尔排序法。（3）选择类排序法 常用的选择类排序有：简单选择排序法；堆排序法算法类型排序算法最好时间复杂度最坏时间复杂度平均时间复杂度交换类排序冒泡排序法NN(N-1)/2N(N+1)/4快速排序法Nlog2NN(N-1)/2O(Nlog2N)插入类排序简单插入排序法NN(N-1)/2N(N+1)/4希尔排序法O(n1.5)O(n1.5)O(n1.5)选择类排序法单选择排序法N(N-1)/2N(N-1)/2N(N-1)/2堆排序法nO(Nlog2N)O(Nlog2N)试题分析（1）下面叙述正确的是_。(C)A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令（或语句）的条数C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止D. 以上三种描述都不对(2) 以下数据结构中不属于线性数据结构的是_。(C)A. 队列B. 线性表C. 二叉树D. 栈(3) 在一棵二叉树上第5层的结点数最多是_。(B)A. 8B. 16C. 32D. 15(4) 算法的时间复杂度是指_。(C)A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数(5) 下列叙述中正确的是_。(A)A. 线性表是线性结构B. 栈与队列是非线性结构C. 线性链表是非线性结构D. 二叉树是线性结构(6) 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为_。(B)A. 349B. 350 C. 255D. 351(7) 算法的空间复杂度是指_。(D)A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 算法执行过程中所需要的存储空间(8) 下列关于栈的叙述中正确的是_(D)A. 在栈中只能插入数据B. 在栈中只能删除数据C. 栈是先进先出的线性表D. 栈是先进后出的线性表(9) 在深度为5的满二叉树中，叶子结点的个数为_。(C)A. 32B. 31C. 16D. 15(10) 算法一般都可以用哪几种控制结构组合而成_。(D)A. 循环、分支、递归B. 顺序、循环、嵌套C. 循环、递归、选择D. 顺序、选择、循环(11) 数据的存储结构是指_。(B)A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据(12) 在下列选项中，哪个不是一个算法一般应该具有的基本特征_。(C)A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报(13) 希尔排序法属于哪一种类型的排序法_。(B)A. 交换类排序法B. 插入类排序法C. 选择类排序法D. 建堆排序法(14) 下列关于队列的叙述中正确的是_。(C)A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表(15) 对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为_(B)A. N+1B. NC. (N+1)/2D. N/2(16) 在计算机中，算法是指_。(C)A. 查询方法B. 加工方法C. 解题方案的准确而完整的描述D. 排序方法(17) 栈和队列的共同点是_。(C)A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点(18) 已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。(A)A. cedbaB. acbedC. decabD. deabc(19) 在下列几种排序方法中，要求内存量最大的是_。(D)A. 插入排序B. 选