第一章_数据.doc

第一章 数据结构与算法11 算法一、 算法的基本概念 算法：是指解题方案的准确而完整的描述。 1、算法的基本特征： （1）可行性。（2）确定性。（3）有穷性。 （4）拥有足够的情报。 2、算法的基本要素 一、对数据对象的运算和操作；算术运算 逻辑运算关系运算 数据传输二、算法的控制结构。 有：顺序、选择、循环3种基本控制结 3、算法设计的基本方法 （1）列举法 （2）归纳法 （3）递推 （4）递归 （5）减半递推技术（6）回溯法 二、算法的复杂度 算法时间复杂度和算法空间复杂度。 1、算法的时间复杂度 算法的时间复杂度，是指执行算法所需要的计算工作量。（不直接衡量时间）即算法执行过程中所需要的基本运算次数。2、算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基本概念 一、 什么是数据结构 数据结构是指反映数据元素之间的关系的数据元素集合的表示，包括数据的逻辑结构和存储结构。 1、数据的逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。2、数据的存储结构数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式。常用的存储结构有顺序、链接、索引等存储结构。二、 数据结构的图形表示 例：一年四季数据结构的图形表示春夏秋冬例：家庭成员数据结构的图形表示父亲女儿儿子方框表示数据元素值，称为结点；有向线段从前件结点指向后件结点，表示为各数据元素之间的前后件关系。没有前件的结点称为根结点；没有后件的结点称为终端结点（也称为叶子结点）。 三、线性结构与非线性结构 P1413 线性表及顺序存储结构 一、线性表的基本概念 线性表是n（n0）个元素构成的有限序列（a1，a2，an）。非空线性表有如下一些结构特征： （1）有且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时称为空表。 二、线性表的顺序存储结构 线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。 Ai=a1=(i-1)ka1a2a3ai-1aian14 栈和队列 一、栈及其基本运算 1、什么是栈 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶（用top表示），不允许插入与删除的另一端称为栈底（用bottom表示）。 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据。 二、 队列及其基本运算 1、什么是队列 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。 16 树与二叉树 一、树的定义 树是由n（ n0）个结点组成的有限集合。若n =0，称为空树；若n0，则： （1）有一个特定的称为根（root）的结点。它只有直接后件，但没有直接前件； （2）除根结点以外的其他结点可以划分为m（m0）个互不相交的有限集合T0，T1，Tm-1，每个集合Ti（i=0，1，m-l）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前件，但可以有0个或多个直接后件。ABCMFDEHLIJKG树型结构具有如下特点： （1）每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根； （2）每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点； （3）一个结点所拥有的后件个数称为结点度； （4）树的最大层次称为树的深度。 二、二叉树的定义及其基本性质 1、什么是二叉树 二叉树（binary tree）是由n（0）个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。2、二叉树的基本性质 性质1：在二叉树的第k层上至多有2k-1个结点（k1）。 性质2：深度为m的二叉树至多有2m-1个结点。 性质3：对任何一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个。 如果叶子结点n0，度为2的结点数为n2，则n0=n2+l。 性质4：具有n个结点的二叉树，其深度至少为log2n+1,其中log2n表示log2n的整数部分。三、二叉树的遍历 所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。1、前序遍历 （根左右）前序遍历是首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。2、中序遍历 （左根右）中序遍历是首先遍历左子树，然后访间根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。 3、后序遍历 （左右根）后序遍历是首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。FCPBEDHGA前序遍历的结果是：FCADBEGHP中序遍历的结果是：ACBDFEHGP后序遍历的结果是：ABDCHPGEFABCEDFHG 前序遍历的结果是：ABCDFGHE中序遍历的结果是：BADGFHCE后序遍历的结果是：BGHFDECA17查找技术一、顺序查找在查找成功时：最好的情况，查找长度为1；最坏的情况，查找长度为n；平均查找长度为 （n+1）/2。 二、二分法查找 二分法查找只适用于顺序存储的有序表（从小到大）。l 对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次。18排序技术一、交换类排序法1、冒泡排序法 假设线性表的长度为n，则在最坏的情况下需要的比较次数为n（n-1）/22、快速排序法快速排序在最坏情况下比较次数：n(n-1)/2，最好情况为nlog2n。二、插入排序法1、简单插入排序法对于具有n个数据元素的序列而言，最坏情况下，元素之间的比较次数为n（n-1）/2，最好情况下元素之间的比较次数为n-1。习题讲解一选择题 1算法的时间复杂度是指（ ） A执行算法程序所需要的时间 B算法程序的长度 C算法执行过程中所需要的基本运算次数 D算法程序中的指令条数 【评析】算法的工作量用算法所执行的基本运算次数来度量，只依赖于问题的规模，它是问题的规模函数。即：算法的工作量=f（n） 【答案】C2算法的空间复杂度是指（ ） A算法程序的长度 B算法程序中的指令条数 C算法程序所占的存储空间 D算法执行过程中所需要的存储空间 【评析】算法的空间复杂度是指执行这个算法所需要的内存空间。包括算法程序占用的空间、输入数据所占用的空间及算法执行过程中所需要的额外空间。 【答案】D3下列叙述中正确的是（ ） A线性表是线性结构 B栈与队列是非线性结构 C线性链表是非线性结构 D二叉树是线性结构 【评析】线性表、栈和队列都是线性结构，树、二叉树、图是非线性结构。【答案】A4数据的存储结构是指（ ） A数据所占的存储空间量 B数据的逻辑结构在计算机中的表示 C数据在计算机中的顺序存储方式 D存储在外存中的数据 【评析】数据的逻辑结构是反映数据元素之间逻辑关系；数据的存储结构是指数据的逻辑结构在计算机存储空间种的存放形式。常用的存储结构有顺序、链接、索引等存储结构。 【答案】B5下列关于队列的叙述中正确的是（ ） A在队列中只能插入数据 B在队列中只能删除数据 C队列是先进先出的线性表 D队列是先进后出的线性表 【评析】队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。 【答案】C6下列关于栈的叙述中正确的是（ ） A在栈中只能插入数据 B在栈中只能删除数据 C栈是先进先出的线性表 D栈是先进后出的线性表 【评析】栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶（用top表示），不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。【答案】DABCEFD7设有下列二叉树：对此二叉树中序遍历的结果为 AABCDEF BDBEAFC CABDECF DDEBFCA【评析】中序遍历是首先遍历左子树，然后访间根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。 【答案】B8在深度为5的满二叉树中，叶子结点的个数为（ ） A32 B31 C16 D15 【评析】在深度为5的满二叉树中，叶结点都位于第五层，共有2416个。【答案】C9对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为（ ） AN+1 BN C（N+1）/2 DN/2 【评析】对线性表进行顺序查找，最坏情况是指要找的是最后一个元素或查找失败，此时需要和线性表中的所有元素都比较一次。【答案】B二填空题 1 对长度为n的有序线性表中进行二分查找，需要的比较次数为（ ）【评析】对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次。【答案】log2n2 设一棵完全二叉树共有700个结点，则在该二叉树中有（ ）个叶子结点 【评析】完全二叉树结点数n为奇数时叶子结点为（n+1）/2,为偶数时叶子结点为n/2。【答案】3503 设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为（DEBFCA ） 【评析】本题内容超过考试范围【答案】4 在最坏情况下，冒泡排序的时间复杂度为（ ） 【评析】在最坏的情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n