全国计算机二级公共基础知识2

第10章公共基础知识本章属于VFP程序设计扩展内容。主要学习程序算法设计理论思想、软件工程思想、数据库设计应用理论、程序设计方法等内容，以便把这些设计思想应用到VFP程序设计中去。第10章公共基础知识数据结构与算法10.1程序设计基础10.2软件工程基础10.3数据库设计基础10.4本章知识点在笔试考试中的分析明细表(1)知识点考核概率分值分布考试形式难易程度算法的基本概念50%0~2选择或填空★算法复杂度70%0~2选择或填空★★数据结构的基本概念50%0~4选择或填空★★线性表及其顺序存储结构50%0~4选择或填空★栈和队列100%0~6选择或填空★★★线性链表20%0~4选择或填空★★★树和二叉树100%0~6选择或填空★★★★★查找技术80%0~4选择或填空★★排序技术80%0~4选择或填空★★程序设计方法与风格30%0~2选择或填空★结构化程序设计20%0~2选择或填空★★本章知识点在笔试考试中的分析明细表(2)知识点考核概率分值分布考试形式难易程度面向对象的程序设计70%0~2选择或填空★★★★软件工程基本概念80%0~4选择或填空★★★结构化分析方法60%0~4选择或填空★★★结构化设计方法60%0~4选择或填空★★★软件测试的方法80%0~2选择或填空★★程序的调试80%0~4选择或填空★数据库基本概念100%0~2选择或填空★★数据模型90%0~4选择或填空★实体联系模型与E-R图80%0~4选择或填空★★关系代数50%0~4选择或填空★★数据库设计方法和步骤40%0~2选择或填空★★★★★10.1数据结构与算法1.算法1)算法的基本概念算法是对特定问题求解步骤的一种描述。它是指令的有限序列，其中每一条指令表示一个或多个操作。算法的基本特征：有穷性：指算法要在执行有穷步骤之后结束，且每一步都在有穷时间内完成。确定性：指算法中每条指令都有确切的含义，不存在二义性，且相同的输入只能得到相同的输出。可行性：指算法中的操作都是可以通过实现的基本运算执行有限次来实现的。拥有足够的情报：一般地，当为算法所提供的情报足够多时，算法才是有效的。10.1数据结构与算法1.算法1)算法的基本概念算法的基本要素对数据对象的运算和操作指令系统，是指一个计算机系统能执行的所有指令的集合。一个算法即为按照题目要求从指令系统中选择合适的指令组成的一组指令序列。因此算法就是计算机能进行的操作所组成的指令序列。不同的计算机系统，指令系统是有差异的，但一般的计算机系统中都包括一下4类基本运算：算术运算、逻辑运算、关系运算和数据传输。算法的控制结构算法的控制结构是指算法中各操作之间进行的顺序。算法的效果不仅取决于所选用的操作指令，还与各操作之间的进行顺序有关。基本的控制结构包括顺序结构、选择结构和循环结构等。10.1数据结构与算法1.算法1)算法的基本概念算法设计的基本方法算法设计的基本方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法等。不同的方法间存在着联系，在实际应用中，不同方法通常会交叉使用。10.1数据结构与算法2)算法复杂度算法的时间复杂度:是指执行算法所需要的计算工作量.一般地，算法的计算工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即：算法的工作量＝f(n)（其中n是问题规模）例如，两个N×N矩阵相乘所需要的基本预算次数为n3，即计算量为n3，也就是时间复杂度为n3。另外，在同一问题规模下，若算法执行所需的基本运算次数取决于某一特定输入数据时，我们可以用平均性态分析和最坏情况分析两种方法来分析算法的工作量。顾名思义，平均性态分析即输入所有可能的平均值，相应的时间复杂度为算法的平均时间复杂度，最坏情况分析则是以最坏的情况估算算法执行时间的一个上界。一般情况下，后者更为常用。10.1数据结构与算法2)算法的空间复杂度算法的空间复杂度是指，执行此算法期间所需要占用的内存空间。包括3部分：算法程序所占的空间；输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。实际应用中，为了减小算法所占用的存储空间，通常采用压缩存储技术，用于减小不必要的额外空间。10.1数据结构与算法2.数据结构的基本概念1)什么是数据结构数据结构是指相互有关联的数据元素的集合。而数据元素具有广泛含义，一般来说，现实世界中客观存在的一切个体都可以是数据元素。它可以是一个数或一个字符，也可以是一个具体的事物，或者其他更复杂的信息。(1)数据的逻辑结构所谓数据的逻辑结构，是指反映数据元素之间逻辑关系（即前后件关系）的逻辑结构。它包括数据元素的信息和数据元素之间的前后关系两个要素。10.1数据结构与算法2.数据结构的基本概念1)什么是数据结构(2)数据的存储结构所谓数据的存储结构，又称为数据的物理结构，是指数据的逻辑结构在计算机存储空间中的存放方式。因为数据元素在计算机中的存放的位置很可能与逻辑关系不一样，所以在存储数据时，不仅要存放数据的信息，还要存放数据间的前后件的信息。只有这样才能更好表示计算机存储空间中数据之间的逻辑关系。数据结构的存储方式包括顺序存储、链式存储、索引存储和散列存储等方法。而采用不同的存储结构，其数据处理的效率是不同的，所以我们在进行数据处理时，选择合适的存储结构就显得十分重要。10.1数据结构与算法2.数据结构的基本概念2)数据结构的图形表示前后件关系是数据元素之间最基本的关系。所谓前后件关系即每一个二元组，都可以用图形来表示。用中间标有元素值的方框表示数据元素，一般称为数据结点，简称结点。对于每一个二元组，用一条有向线段从前件指向后件。例如，一年四季的数据结构可以用图1所示的图形来表示。10.1数据结构与算法2.数据结构的基本概念2)数据结构的图形表示又例如数据结构的知识体系可以用下图所示的图形来表示。10.1数据结构与算法2.数据结构的基本概念3)线性结构与非线性结构根据数据结构中各数据元素之间前后关系的复杂程度，一般可将数据结构分为两大类型：线性结构和非线性结构。若一非空的数据结构有且只有一个根结点，并且每个结点最多有一个直接前驱后直接后继，则称该数据结构为线性结构，也称线性表。不满足上述条件的数据结构则称为非线性结构。由上我们可以判断，图一为线性结构，图二为非线性结构。10.1数据结构与算法3.线性表及其顺序存储结构1)线性表的基本概念在数据结构中，线性表是最简单也是最常用的一种数据结构。线性表是由n(n≥0)数据结构元素x1，x2，x3，…，xn组成的一个有限序列。除了表中的第一个元素外，有且只有一个直接前驱；除了最后一个元素外，有且只有一个直接前驱。将线性表表示为(x1，x2，x3，…，xn)，其中xi(i=1,2,…n)是线性表的数据元素，也称为为线性表的一个结点。线性表中的数元素必须具有相同的属性，即属于同种数据对象。比如:字母表（A，B，C，…，Z）就是一个长度为26的线性表比如:矩阵可以看做一个比较复杂线性表，在矩阵中，既可以把每一行看成一个数据元素，也可以把每一列看成一个数据元素。10.1数据结构与算法3.线性表及其顺序存储结构2)线性表的顺序存储结构将线性表中的元素在计算机中一段相邻的存储区域中连续存储，称为线性表的顺序存储。线性表的顺序存储结构具有以下两个基本特点：所有元素所占的存储空间必须是连续的；所有元素在存储空间的位置是按逻辑顺序存放的。由其基本特点我们可以看到，线性表中元素之间逻辑上的相邻关系即元素在计算机内物理位置上的相邻关系。所以只要确定了首地址，线性表内所有元素的地址都可以方便地查找出来。10.1数据结构与算法35267……………………↑插入4（a）插入前线性表n=5352467………………（b）插入元素4后线性表n=6图4线性表的顺序存储结构插入前后的状况3.线性表及其顺序存储结构3)线性表的插入运算在对线性表的插入操作时，若在第i个元素之前插入一个新元素，完成插入操作主要有以下３个步骤：原来第n个结点至第i结点依次往后移一个位置；把新结点放在第i个位置上；线性表的结点数加1。如图4所示：10.1数据结构与算法3.线性表及其顺序存储结构3)线性表的插入运算当在线性表尾进行插入运算时，则只需在表的末尾增加一个元素即可，不需要移动线性表中的元素。当在线性表头位置插入新的元素，则需要移动表中所有的元素。一般地，线性表会事先开辟出一个大于线性表长度的空间，但当多次插入运算后，可能出现在存储空间已满的情况下仍继续进行插入运算，此时将会产生错误，此类错误称为“溢出”。10.1数据结构与算法3.线性表及其顺序存储结构4)线性表的删除运算在对线性表的删除操作时，若在第i元素之前插入一个新元素，完成插入操作主要有以下３个步骤：把第i元素之后（不包括第i个元素）的ｎ-i个元素依次前移一个位置；线性表的结点数减1。当删除运算在线性表尾进行时，即删除第n个元素，不需要移动线性表中的元素。当要删除第1个元素时，则需要移动表中所有的元素。10.1数据结构与算法4.栈和队列1)栈及其基本运算(1)栈的基本概念栈，实际上也是一种线性表，只不过是一种特殊的线性表。其特殊性体现在，它的插入和删除运算都只在线性表的一端进行，而另一端是封闭的，不进行任何操作。在栈中，允许进行插入删除操作的一端称为栈顶，另一端则称为栈底。当栈中没有元素时称为空栈。由于其操作的特殊性，栈也被称为“先进后出”表或“后进先出”表。10.1数据结构与算法(2)栈的特点栈底元素总是最早被插入的元素，最晚被删除的元素；栈顶元素总是最后被插入的元素，最早被删除的元素；栈具有记忆作用；顺序栈的插入和删除运算都不需要移动表中其他的数据元素；栈顶指针动态反映了栈中元素的变化情况。10.1数据结构与算法(3)栈的顺序存储及其运算栈的基本运算有3种：入栈运算：即栈的插入，在栈顶位置插入一个新数据。出栈运算：即栈的删除，就是取出栈顶元素赋予指定变量。读栈顶元素：即将栈顶元素（即栈顶指针top指向的元素）的值赋给某个变量。10.1数据结构与算法4.栈和队列2)队列及其基本运算(1)队列的基本概念队列是同栈完全相反的线性结构，它是允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针（rear）的指针指向队尾元素；允许删除的一端称为队头，通常用一个称为头指针（front）的指针指向头元素的前一个位置。队列又称为“先进先出”的线性表。10.1数据结构与算法(2)循环队列及其运算循环队列，顾名思义，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，线性结构供队列循环使用。在循环队列中，用尾指针（rear）指向队列的尾元素，用头指针（front）指向头元素的前一个位置。所以，我们可以知道从头指针（front）所指向的后一个位置直到尾指针（rear）指向的位置之间所有的元素均为队列中的元素。10.1数据结构与算法由此判断队列空和队列满这两种情况：当S=0时，循环队列为空；当S=1时，且front=rear时，循环队列满。(2)循环队列及其运算当rear＝front时，循环队列的状态有两种：可能是队列满，也可能是队列空。为了区分这两种情况，我们通常增加一个标志量S，S值的定义如下：10.1数据结构与算法2)循环队列及其运算循环队列的基本运算主要有两种：入队运算入队运算是指在循环队列的队尾加入一个新元素。首先队尾指针进1（即rear=rear＋1），然后在rear指针指向的位置，插入新元素。当S=1时，且front=rear时，循环队列满。此时进行入队运算，会发生“上溢”错误。出队运算出队运算是指在循环队列的排头位置退出一个元素，并赋给指定的变量。首先，头指针进1（即front=front＋1），然后删除front指针指向的位置上的元素。当S=0时，循环队列为空，此时进行出队运算，会发生“下溢”错误。10.1数据结构与算法5.线性链表前面主要介绍了线性表的顺序存储结构及其基本运算。线性表的顺序存储结构的特点是简单、运算方便，对于小线性表或长度固定的线性表，采用顺序存储结构的优