公共基础打印.doc

算法与数据结构 算法 算法的基本概念 1.算法的概念 算法是指解题方案的准确而完整的描述。算法的基本特征可行性②确定性有穷性算法复杂度时间复杂度和空间复杂度。时间复杂度算法时间复杂度是指执行算法所需要的计算工作量空间复杂度空间复杂度是指执行这个算法所需要的内存空间。数据结构是指相互有关联的数据元素的集合数据结构研究三个方面数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构对各种数据结构进行的运算数据的逻辑结构表示数据元素的信息表示各数据元素之间的前后件关系。存储结构有顺序、链接、索引等非线性结构：线性结构。栈是限定在一端进行插入与删除的线性表允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”或“后进先出”组织数据。栈的基本运算插入元素称为入栈运算；删除元素称为退栈运算；读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。图 10.1图 10.1队列是指允许在一端队尾进入插入，而在另一端队头进行删除的线性表。指针Rear)指向队尾，指针front)指向。队列是“先进出”或“后进后出”的线性表。入队运算：从队尾插入一个元素退队运算：从队头删除一个元素。图 10.2 图 10.2循环队列由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的线性表的顺序存储结构具有两个基本特点：线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。线性链树是一种简单的非线性结构所有元素之间具有明显的层次特性。图 10.3 图 10.3在树结构中，每一个结点只有一个前件，称为父结点没有前件的结点只有一个，称为树的根结点，简称树的根。图 10.3每一个结点可以有多个后件，称为该结点的子结点没有后件的结点称为叶子结点。图 10.3在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。图 10.3树的最大层次称为树的深度。图 10.3二叉树的特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。图 10.4 图 10.4图 10.5 图 10.5二叉树的基本性质 图 10.6 图 10.6图 10.7 图 10.7二叉树的遍历 前序遍历（DLR）中序遍历（LDR）后序遍历（LRD）图 10.8 图 10.8二叉树存储结构二分法查找只适用于顺序存储的有序表，对于排序是指将一个无序序列整理成按值顺序排列的有序序列表 10.1表 10.1n(n-1)/2 快速排序 选择基准元素，通过交换划分成两个子序列 n(n-1)/2 插入类 简单插入排序 将待排序的元素看成为一个有序表和无序表，将无序表中的元素插入到有序表中 n(n-1)/2 希尔排序 分割成若干子序列分别进行直接插入排序 O(n1.5) 选择类 简单选择排序 扫描整个线性表，从中选取最小的元素，将它交换到线性表的最前面 n(n-1)/2 堆排序 先建堆，然后将堆顶元素与最后一个元素交换，再调整为堆 O(nlog2n)  理论习题10 选择题 1.算法的有穷性是指( ) A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用 2.算法的时间复杂度是指( ) A）执行算法程序所需的时间 B）算法程序的长度 C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数 3.算法的空间复杂度是指( ) A）算法程序的长度 B）算法程序中的指令条数 C）算法程序所占的存储空间 D）算法执行过程中所需要的存储空间 4.下列叙述中正确的是( ) A）算法的效率只与问题的规模有关，而与数据的存储结构无关 B）算法的时间复杂度是指执行算法所需要的计算工作量 C）数据的逻辑结构与存储结构是一一对应的 D）算法的时间复杂度与空间复杂度一定相关 5.下列叙述中正确的是 A）一个算法的空间复杂度大,则其时间复杂度也必定大B）一个算法的空间复杂度大,则其时间复杂度必定小C）一个算法的时间复杂度大,则其空间可复杂度必定小D）上述三种说法都不对 下列关于栈的描述正确的是 A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素下列叙述中正确的是( )A）线性链表是线性表的链式存储结构 B）栈与队列是非线性结构C）双向链表是非线性结构 D）只有根结点的二叉树是线性结构 下列叙述中正确的是( )A）