搜索
全国计算机等级考试二级公共基础知识第1页，共36页数据结构与算法一、基本概念：数据(Data)：信息的载体，能够被计算机识别、存储和加工处理的物理符号。包括文本类型的数据(如：字母、数字、汉字)和多媒体类型的数据(如：声音、动画、图像)。数据元素(DataElement)：是数据的基本单位，有时也称为元素、结点、顶点、记录，可以有若干个数据项（字段、域、属性）组成。数据结构（DataStructure）：指的是数据之间的相互关系，即数据的组织形式。其包括三个部分：1、逻辑结构：数据元素之间的逻辑关系2、存储结构：数据元素及其关系在计算机存储器内的表示。3、数据的运算（算法）：即对数据施加的操作数据的逻辑结构有两大类：全国计算机等级考试二级公共基础知识第2页，共36页1、线性结构：特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点最多只有一个直接前趋和一个直接后继。例：一维数组、链表、栈、队列、串2、非线性结构：特征是：一个结点可能有多个直接前趋和直接后继。例：多维数组、广义表、树、图数据的存储结构有以下基本存储方法：1、顺序存储方法：该方法是将逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，一般通过数组来实现的。2、链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。通过指针类型来实现的。3、索引存储方法：该方法通常是在存储结点信息的同时，还建全国计算机等级考试二级公共基础知识第3页，共36页立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：关键字，地址。4、散列存储方法：该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址，通过散列函数实现。例：除余法散列函数、相乘取整法散列函数算法的基本特征：1、可行性(Effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。2、确定性(Definiteness)：算法中的每一个步骤都必须有明确的定义，不允许出现歧义性。3、有穷性(Finiteness)：算法必须在有限时间内做完，即必须在执行有限个步骤之后终止。时间复杂度：该算法执行的时间耗费，它是该算法所求解问题规模n的函数。空间复杂度：该算法执行时所耗费的存储全国计算机等级考试二级公共基础知识第4页，共36页空间，它也是问题规模n的函数。二、线性表：线性表(LinearList)：是由n(n=0)个数据元素(结点)a1,a2,a3,······,an组成的有限序列。对于非空的线性表，有且仅有一个开始结点a1，它没有直接前趋；有且仅有一个终端结点an，它没有直接后继；其余的结点有且仅有一个直接前趋结点和一个直接后继结点。线性表的存储结构：1、顺序存储(SequentialList)：将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里，用这种方法存储的线性表称为顺序表。2、链式存储(LinkedList)：逻辑上相邻的结点，物理上也相邻，存储单元可以是连续的，也可以是不连续的，在存储每个结点值的同时，还存储指向其后继结点的地址，用这种方法存储的线性表称为链表。常见的运算有：表的初始化、求表的长度、取表中的第i个全国计算机等级考试二级公共基础知识第5页，共36页结点、查找结点、插入新的结点、删除结点。顺序表和链表的比较：1、基于空间的考虑：A、顺序表的存储空间是静态分配的，而链表的存储空间是动态分配的。B、顺序表占的存储空间必须是连续的，而链表占的存储空间可以是连续的，也可是不连续的C、顺序表存储密度为1，而链表中的每个结点，除了数据域外，还要额外的设置指针域，存储密度小于12、基于时间的考虑：A、在链表中的任何位置上进行插入和删除，只需要修改指针，而顺序表中平均将要移动近一半的结点。B、顺序表是随机存取结构，它的存取时间为O(1)，而链表需从头结点顺着链扫描链表。总之，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜全国计算机等级考试二级公共基础知识第6页，共36页采用顺序表作为存储结构；当线性表的长度变化较大，难以估计其存储规模时，以采用链表作为存储结构为好。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；对于频繁进行插入和删除的线性表，宜采用链表做存储结构。例：关于线性表的描述中，错误的是（）A、线性表是线性结构B、线性表的顺序存储结构，必须占用一片连续的存储单元C、线性表是单链表D、线性表的链式存储结构，不必占用一片连续的存储单元用数组表示线性表的优点是（）A、便于插入和删除操作B、便于随机存取C、可以动态地分配存储空间D、不需要占用一片连续的存储空间三、栈：栈(Stack)：是限制仅在表的一端进行插入和删除运算的线性表，通常称插入、删全国计算机等级考试二级公共基础知识第7页，共36页除的这一端为栈顶(Top)，另一端称为栈底(Bottom)。当表中没有元素时称为空栈。是一种后进先出的线性表，又称为LIFO表。栈的基本运算有：栈的初始化、判栈空、判栈满、进栈、出栈等栈的存储：顺序存储、链式存储例：若进栈的输入序列是A、B、C、D、E，并且在它们进栈的过程中可以进行出栈操作，则不可能出现的出栈序列是（）A、EDCBAB、DECBAC、DCEABD、ABCDE四、队列：队列(Queue)：也是一种运算受限的线性表，它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一段称为队头(Front)，允许插入的一段称为队尾(Rear)。（类似于生活中的购物排队）。是全国计算机等级考试二级公共基础知识第8页，共36页一种先进先出的线性表，又称为FIFO表。队列的基本运算：队列的初始化、判队空、判队满、入队、出队队列的存储实现：顺序存储、链式存储例：一个队列的入队序列是1，2，3，4，则队列的输出序列是（）A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，1五、串：串(String)：是零个或多个字符组成的有限序列。串中所包含的字符个数称为该串的长度。串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串注：空串是任意串的子串，任意串是其自身的子串串有串常量、串变量之分：1、串常量在程序中只能被引用但不能改全国计算机等级考试二级公共基础知识第9页，共36页变其值，即只能读不能写。2、串变量其值是可以改变的。串的基本运算：求串长、串复制、串联接、串比较、字符定位、六、树（非线性结构）：树(Tree)：是n(n=0)个结点的有限集T，T(n=0)为空时称为空树，否则它满足如下两个条件：1、有且仅有一个特定的称为根(Root)的结点2、其余的结点可分为m(m=0)个互不相交的子集T1，T2，…….，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subtree)。在树的树形图表示中，结点通常是用圆圈表示的，结点的名字一般是写在圆圈旁边，有时亦可写在圆圈内。度(Degree)：一个结点拥有的子树数称为该结点的度。一棵树的度是指该树中结点的最大度数。全国计算机等级考试二级公共基础知识第10页，共36页叶子(Leaf)：度为零的结点称为叶子或终端结点分支结点(Node)：度不为零的结点称为分支结点。树中某个结点的子树之根称为该结点的孩子(Child)结点或子结点，相应的该结点称为孩子结点的双亲(Parents)结点或父结点。同一个双亲的孩子称为兄弟结点(Sibling)结点的层数(Level)是从根起算,设根的层数为1,其余结点的层数等于其双亲结点的层数加1.树中结点的最大层数称为树的高度(Height)或深度(Depth).森林(Forest)：是m(m=0)棵互不相交的树的集合。删去一棵树的根，就得到一个森林，反之，加上一个结点作树根，森林就变为一棵树。二叉树(BinaryTree)：是n(n=0)个结点的有限集，它或者是空集(n=0)，或者由全国计算机等级考试二级公共基础知识第11页，共36页一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树中，每个结点最多只能有两棵子树，并且有左右之分。二叉树的五种基本形态：例：具有3个结点的二叉树有几种形态。满二叉树(FullBinaryTree)：一棵深度为k且有2k-1个结点的二叉树称为满二叉树完全二叉树(CompleteBinaryTree)：若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。二叉树的性质：性质1：二叉树第i层上的结点数目最多为2i-1(i=1)性质2：深度为k的二叉树至多有2k-1个结点(k=1)性质3：在任意一棵二叉树中，若终端结点全国计算机等级考试二级公共基础知识第12页，共36页的个数为n0，度为2的结点数为n2，则n0=n2+1性质4：具有n个结点的完全二叉树的深度为[lgn]+1(取下整)或[lg(n+1)](取上整)。例：一棵二叉树的结点数为18个，求它的最小高度已知度为2的结点数为15个，求叶子结点数二叉树的遍历：遍历(Traversal)：是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。前序遍历：（又称为先序遍历、先根遍历）若二叉树为空，则执行空操作。否则：1、访问根结点；2、前序遍历左子树；3、前序遍历右子树。中序遍历：（又称为中根遍历）若二叉树为空，则执行空操作。否则：1、中序遍历左子树；全国计算机等级考试二级公共基础知识第13页，共36页2、访问根结点；3、中序遍历右子树。后序遍历：（又称为后根遍历）若二叉树为空，则执行空操作。否则：1、后序遍历左子树；2、后序遍历右子树；3、访问根结点。例：已知一棵二叉树的中序遍历序列是：FDGBACHE，其后序遍历序列是：FGDBHECA求其前序遍历序列。一棵二叉树的前序遍历序列为ABDGCFK，中序遍历序列为DGBAFCK，则结点的后序遍历序列是（）A、ACFKDBGB、GDBFKCAC、KCFAGDBD、ABCDFKG七、排序(Sort)：所谓排序，就是指整理文件中的记录，使之按关键字递增（或递减）次序排列起来。冒泡排序(BubbleSorting)：通过对待排序序列从后向前或从前向后全国计算机等级考试二级公共基础知识第14页，共36页(从下标较大的元素开始)，依次比较相邻元素的排序码，若发现逆序则交换，使排序码较大的元素逐渐从前部移向后部或较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元）。直接选择排序(SelectionSorting)：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。直接插入排序(InsertionSorting)：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。快速排序(QuickSorting)：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。各种内部排序方法的比较全国计算机等级考试二级公共基础知识第15页，共36页排序方法时间复杂度空间复杂度最好时间平均时间最坏时间直接插入O(n)O(n2)O(n2)O(1)直接选择O(n2)O(n2)O(n2)O(1)冒泡O(n)O(n2)O(n2)O(1)快速O(nlgn)O(nlgn)O(n2)O(lgn)堆O(nlgn)O(nlgn)O(nlgn)O(1)例：对一个具有n个元素的序列进行冒泡排序，在最坏情况下，要进行交换的次数是（）A、n(n+1)/2B、n(n-1)/2C、全国计算机等级考试二级公共基础知识第16页，共36页n*n/