全国计算机等级考试二级公共基础知识总结

全国计算机等级考试二级公共基础知识总结第一章数据结构与算法1.1算法1．算法的基本特征：可行性；确定性，有穷性；拥有足够的情报。2．确定性：算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性。3．算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。4．归纳法：通过观察一些简单而特殊的情况，最后总结出一般性的结论的算法的设计方法。5．如果算法P调用另一个算法Q，而算法Q又调用算法P，则称为间接递归调用。6．一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程慢。7．工程上常用的分治法是减半递推技术。8．例如：如果查找的x一定在数组中，此时q=1，则A(n)=(n+1)/2。也就是说，在这种情况下，用顺序搜索法在长度为n的一维数组中查找值为x的元素，在平均的情况下需要检查数组中一半的元素。如果已知需要查找的x有一半机会在数组中，此时q=1/2。则A(n)=[(n+1)/4]+n/2=3n/4。x不在数组中时，A(n)=n。9．算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。10．算法复杂度：算法时间复杂度和算法空间复杂度。11．算法的时间复杂度：是指执行算法所需要的计算工作量。可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。12．算法时间复杂度取决于问题的规模和待处理的数据的初态。13．例如：下面程序段的时间复杂度是for(inti=0;in;i++)for(intj=1;j=m;j++)A[i][j]=0;语句的频度指的是该语句重复执行的次数，一个算法中所有语句的频度之和构成了该算法的运行时间。本例中语句:A[i][j]=0;的频度是n*m，所以该程序段的时间复杂度是：O(m*n).14．算法的空间复杂度：是指执行这个算法所需要的内存空间。1.2数据结构的基本基本概念1．数据结构研究的三个方面：数据的逻辑结构；数据的存储结构（物理结构）；数据运算。2．逻辑结构是数据元素间关系的描述，与所用的计算机无关。3．数据的逻辑关系是指数据元素的关联。4．数据的不可分割的基本单位是数据项。5．数据结构是指相互有关联的数据元素的集合。6．一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。7．数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式，与所使用的计算机密切相关。8．根据数据结构中各数据元素之间前后件关系的复杂度，一般将数据结构分为两大类型：线性结构与非线性结构。9．在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点或结点。10．插入和删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。11．在数据结构中，用一组地址连续的存储单元依次存储数据元素的方式是线性结构。12．一个数据结构除了用二元关系表示外，还可以直观地用图形表示。1.3线性表及其顺序存储结构1．数据元素的位置只取决于自己的序号。2．线性表是由n个数据元素组成的一个有限序列。删除一个元素，平均移动的元素的个数为(n-1+n-2+......+0)/n=(n-1)/2；插入一个元素，平均移动元素个数为(n+n-1+n-2+......+1)/n=(n+1)/2，所以总体移动元素个数为n/2。3．线性表是一种线性结构，数据元素之间的相对位置是线性的。4．线性表可以是空表。5．非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。6．线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。7．ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。例如：一个矢量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是108数据元素的存储位置均取决于第一个数据元素的存储位置，即：ADR(ai)=ADR(a1)+(i-1)k第5个元素的地址：ADR(a5)=100+(5-1)X2=1088．在线性表的顺序存储结构下，可以对线性表进行各种处理。主要的运算有：线性表的插入、线性表的删除、线性表的查找、线性表的排序、线性表的分解、线性表的合并、线性表的复制、线性表的逆转等。9．线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单。10．采用顺序存储的线性表，顺序存储结构必须占用一片连续的存储单元，当对其进行插入和删除操作时需要移动大量的元素，优点是存储密度大，由于数组的存储方式是采用顺序存储的，即占用连续的存储空间，所以可以用数组的下标直接存取。11．查找第i-1个结点和第i个结点，在顺序表中查找的时间复杂度为O(1)速度最快。由于链表结构在空间存储上的不连续性，在查找某个结点时，需要从当前结点开始向前或者向后逐个比较查找，浪费时间，查找结果的时间复杂度均为O(n)。12．链接存储不是占用一片连续的存储空间，所以便于进行插入和删除操作。13．线性表的链式存储结构中的每一个存储结点不仅含有一个数据元素，还包括指针，每一个指针指向一个与本结点有逻辑关系的结点，此类存储方式属于顺序存储。1.4栈和队列1．栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。2．栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。3．当一个栈ST（最多元素为MaxSize）时，ST-top=-1是判断顺序栈为空的条件。ST-top=MaxSize-1是判断顺序栈为满的条件。4．栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。5．通常元素出栈的顺序是先取出栈顶元素再移动栈顶指针，使之指向新的栈顶元素。从一个循环队列中删除一个元素，通常是先取出元素再移动栈顶指针。6．例如：栈的基本操作。一个栈的入栈序列是1,2,3,...,n,其输出序列为P1，P2，P3，。。。，Pn，若P1=n，则Pi为n-i+1。当p1=n，即n是最先出栈的，根据栈的运算原理，n必定是最后入栈的，那么输入顺序必定是1,2,3,...,n,则出栈的序列是n,n-1,n-2,...,1。例如：设初始输入序列为1，2，3，4，5，利用一个栈产生输出序列，下列序列是不可能通过栈产生的。由于栈的压入和退出只能在栈顶进行，所以要使出栈的第一个数是序列的最后一个数5，只能先把序列所有元素都压入栈，但这时出栈序列只能是（A5，4，3，2，1），所以（B5，3，4，1，2）选项的出栈序列是错误的，应选（B）。当初始序列压入一个时，就退出一个元素，这样就得到（A）选项的出栈序列1，2，3，4，5；先压入1，2，3，4四个元素，再退出所有元素，最后压入5，并退栈这时得到（C）选项的出栈序列4，3，2，1，5；压入1，2后对后面的元素3，4，5分别压入一个退出一个，这时便得到（D）选项的出栈序列3，4，5，2，1。7．队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。8．队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。9．队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。10．循环队列：s=0表示队列空，s=1且front=rear表示队列满，当循环队列为空（S=0）时，不能进行退队运算，这种情况称为下溢。11．在一个容量为25的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有3个元素。1.5线性链表1．数据结构分为逻辑结构与存储结构，线性链表属于存储结构。2．数据结构中的每一个结点对应于一个存储单元，这种存储单元（一个一个小块）称为存储结点，简称结点。3．结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。4．在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。因此，链式存储结构是散列存储。5．带头结点的双向循环链表L为空的条件是：只有该头结点，即L-next==L或者L-prior==L。6．对于链式队列结构，插入元素是在队尾进行的，只需修改队尾指针，不需修改队头指针。向链式队列中插入一个结点就是在单链表表尾插入一个结点，同时新插入的结点成为表尾结点。例：在一个链式队列中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是r-next=s;r=s。7．向链式栈中插入一个结点，就是在单链表的表头插入一个结点，同时将新结点的位置赋予栈顶指针。例：向一个栈顶指针为HS的链式栈中插入一个s所指的结点时，则执行s-next=HS;HS=s。8．线性链表的基本操作：插入、删除、查找、排序。9．双向链表每个结点有两个指针域，这两个指针分别指向它的前驱结点和后继结点。10．单链表中，每个结点都含有一个指针域，这个指针指向它的下一个结点。因此访问单链表中的结点时，必须沿着它的指针逐个进行。11．由于双向链表比单链表结构复杂，所以在插入和删除元素时，要修改更多的指针域，相对比较复杂，单向链表和双向链表在空间存储上的不连续性决定了两者都不可以随机访问，在双向链表中由于每个结点包括两个指针域，其中一个指向该结点的前驱结点，另一个指向该结点的后继结点，因此它既可以直接访问前驱结点，又可以直接访问后继结点，而单链表每个结点只有一个指针域，指向它的后继结点，所以它只能直接访问它的下一个结点，而无法直接访问它的前一个结点。所以双向链表顺序访问相邻结点更加灵活。12．链表的特点：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。链表结构是一些逻辑上相邻，而空间上并不一定相邻的数据元素的集合，相邻的结点之间通过指针相互联系，在插入和删除元素时，只需修改结点指针即可，不需要移动数据元素。当存储空间不足时，可以动态为其分配内存空间，所以不必事先估计存储空间的大小。所需空间与其长度成正比。13．用带头结点的链表表示线性表时，空表和非空表的插入、删除是相同的。当往空链表插入元素时，只要把待插入元素的指针域指向头结点的指针域，把头结点的指针域指向新增元素即可，当往非空链表插入元素时只要找到插入的位置，执行同样的操作即可完成插入。当链表只有一个元素时，删除操作只要修改指针指向下一个元素的指针所指的元素即可，跟一般的链表删除操作是一样的。带头结点的链表并不能加快对链表的遍历，带头结点的链表反而要增加一个用于存储头结点的空间，并不能节省存储空间，用带头结点的链表跟存取元素的速度无关。14．忽略了最后结点或头结点的指针，在n个结点的单向链表（无表头结点）中，每个结点都有一个指针单元（即指针域），加上头指针，至少需要n+1个指针单元。1.6树与二叉树1．树是一种简单的非线性结构，所有元素之间具有明显的层次特性。栈和队列都是线性结构。2．在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。