VF知识点总结复习.doc
《VF知识点总结复习.doc》由会员分享,可在线阅读,更多相关《VF知识点总结复习.doc(22页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、计算机二级VF复习笔记一、算法1、算法:问题处理方案的正确而完整的描述称为算法。2、算法的基本特征:(1)可行性:针对实际问题而设计的算法,执行后能够得到满意的结果。(2)确定性:每一条指令的含义明确,无二义性。并且在任何条件下,算法只有唯一的一条执行路径,即相同的输入只能得出相同的输出。(3)有穷性:算法必须在有限的时间内完成。有两重含义,一是算法中的操作步骤为有限个,二是每个步骤都能在有限时间内完成。(4)拥有足够的情报:算法中各种运算总是要施加到各个运算对象上,而这些运算对象又可能具有某种初始状态,这就是算法执行的起点或依据。因此,一个算法执行的结果总是与输入的初始数据有关,不同的输入将
2、会有不同的结果输出。当输入不够或输入错误时,算法将无法执行或执行有错。一般说来,当算法拥有足够的情报时,此算法才是有效的;而当提供的情报不够时,算法可能无效。3、算法复杂度包括:(1)算法的时间复杂度:指执行算法所需要的计算工作量。(算法在执行过程中所需要的基本运算次数)(2)算法的空间复杂度:指执行这个算法所需要的内存空间。二、数据结构1、数据结构包括:逻辑结构:数据集合中各数据元素之间所固有的逻辑关系。存储结构(又称为物理结构):各数据在计算中的存储关系。2、常用的存储结构包括:顺序、链接和索引等存储结构。3、数据逻辑结构分为:(1)线性结构(又称线性表):有且只有一个根节点;每个结点最多
3、有一个前件,也最多有一个后件。在一个线性结构中插入或删除任何一个结点后还应是线性结构。(2)非线性结构:如果一个数据结构不是线性结构,则称之为非线性结构。如果一个空的数据结构的算法是按线性结构的规则来处理的,则属于线性结构;否则属于非线性结构。4、线性链表线性表的链式存储结构称为线性链表。5、循环链表和双向链表都属于线性链表。三、栈和队列及其运算1、栈:是限定只在一端进行插入和删除的线性表。(按“先进后出”或“后进先出”原则组织数据)2、队列:指在一端插入,而在另一端删除的线性表。(“先进先出”)计算队列中元素个数的公式:(队尾指针-对头指针+对容量)%对容量。即是:对头到队尾的元素个数。(注
4、意:非队尾到对头)3、链式存储结构包括两个部分:数据域和指针域。4、栈的基本运算:(1)入栈:指在栈顶位置插入一个新元素。首先将栈顶指针加1(即top加1),然后将新元素插入栈顶指针指向的位置。插入一个新元素称为一次入栈。当栈顶指针已经指向存储空间的最后一个位置时,说明栈控件已满,不可能再进行入栈操作。这种情况称为“上溢”错误。(2)退栈:指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量,然后将栈顶指针减1(即top减1)。当栈顶指针为0时,说明栈空,不可进行退栈操作。这种情况称为栈的“下溢”错误。(3)读栈顶元素:指将栈顶元素赋给一个指定的变量,栈顶
5、指针不会改变。四、树和二叉树1、树:是一种非线性结构。2、树的性质:树的结点数等于所有结点的度与对应的结点个数乘积之和加1。3、度:在树结构中,一个结点所拥有的后件个数称为该结点的度,叶子结点的度为0。4、树的度:在树中,所有结点中的最大的度称为树的度。5、二叉树的性质:(1)二叉树中度为零的结点比度为二的结点多1个。(2)二叉树的总结点数=度为0的结点(叶子结点)个数+度为1的结点个数+度为2的结点(由叶子结点-1所得)个数。(3)在二叉树的第k层上,最多有2k-1(k1)个结点。分析:最多的情况为满二叉树的情况:第1层,第2层,第3层,第n层。分别有结点数:1,2,4,8,2k-1。(4)
6、深度为m的二叉树最多有2m-1个结点。分析:最多的情况为满二叉树的情况:第1层,第2层,第3层,第n层。分别有结点数:1,2,4,8,2k-1。(K项等比数列)则总共有结点数为:1+2+4+2k-1=1(1-2k)/1-2即:2k-1.(5)具有n个结点的二叉树,其深度至少为log2n+1.(6)设完全二叉树共有n个结点。如果从根节点开始,按层次(每一层从左到右)用自然数1,2,3,n给结点进行编号,则对于编号为k(k=1,2,3,n)的结点有一下结论:若k=1,则该结点为根节点,它没有父节点;若k1,则该结点的父节点编号为INT(k/2)。若2kn,则编号为k的结点的左子节点编号为2k;否则
7、,该结点的无左子节点(显然也没有右子节点)。解析:为什么需要限定条件2kn ?对于有左右子树的二叉树来说,每一个父节点的下一层均比自身多两个结点。所以,每一个父节点的编号的下一层的左右子节点的编号分别为2k和2k+1。如果2kn,则表示计算出来的结点数比总共给出的结点数还多,这种情况不符合要求。若2k+1n,则编号为k的结点的右子节点编号为2k+1;否则该结点无右子节点。(7)深度为k的完全二叉树至少有2(k-1)个结点,至多有2k-1个结点。解析:至少的情况是:根据完全二叉树的定义,深度为k的完全二叉树的结点最少的情况为:第k-1层及以上形成满二叉树,再在第k层加1个结点。则有总结点数为:(
8、2(k-1)-1)+1个结点,即有2(k-1)个结点。 至多的情况为满二叉树的情况。5、二叉树的遍历:根据访问根节点的次序,分为三类:1)前序遍历:(根左右)2)中序遍历:(左根右)3)后序遍历:(左右根)在二叉树的遍历中,无论是前序遍历、中序遍历和后序遍历,二叉树的叶子结点的先后顺序都是不变的。例:1)前序遍历:ABDECFGH解析:(根A左到B,到B时也得按根左右的顺序,相对于BDE又说,B是根,D是左,E是右。所以是根B左D右E),此时,完成了A的左这部分如图 ,接着是A的右(也就是如下图的部分:)同样,也得按根左右的顺序:对于CFGH来说,C 是根,F是左,G是右。所以,是CF.但对于
9、GH来说,G是根,H是左,照样按根左右的顺序,是GH.所以,顺序为ABDECFGH2)中序遍历:DBEAFCHG解析:按左根右的顺序,从A的左B开始,但对于此时的B来说,B是BDE的根。所以,得从D(左)开始,B(根),E(右)。到此,完成了A的左,按左根右的顺序,就到A(根)。接着,到A的右部分了C,同样,C的左F,根C.接着,到右G,但G是GH的根,H是左。所以是HG总顺序为:DBEAFCHG3)后序遍历:DEBFHGCA解析:按左右根的顺序,从A的左,如下图部分开始。到B,但对于BDE来说,B 是根,D是左,E是右。所以,应该从D开始。顺序为:DEB.此时,完成了A左的部分,该到A的右部
10、分了,即如下图所示的部分同样,按左右根的顺序,该到C,但对于CFG来说,C是根,F是左,H右。所以顺序是:F到G,然而,对于GH来说,G 又是根,H是左。所以,顺序为:FHGCA(A是大的二叉树的根)最后,总顺序为:DEBFHGCA.五、查找查找指在一个给定的数据结构中查找某个指定的元素,查找包括顺序查找和二分查找。1、顺序查找:从线性表的第一个元素开始,依次将线性表中的元素与被查找的元素相比较。如果线性表的长度为n,则查找不成功,需比较n+1次。在下列两种情况下只能采用顺序查找:1)如果线性表为无须表,则不管是顺序存储结构还是链式存储结构,只能用顺序查找。2)即使是有序线性表,如果采用链式存
11、储结构,也只能用顺序查找。2、二分查找:(1)适用于顺序存储的有序表。有序表指线性表中元素按值非递减排列(即从小到大,但允许相邻元素值相等)。(2)对于长度为n的有序线性表,在最坏的情况下,二分查找只需要比较log2n次。分析:最坏情况是:直到分到只剩下最后一个元素时才找到结果。设需要比较m次,则有比较第1次、第2次、第3次第n次时,剩下的数的个数分别为:n/2,n/4,n/8,,n/2m个,则当(n/2m)=1个时,不能再分,即2m=n,得m=log2n。对于长度为n的有序线性表,查找不成功时需要比较log2n次。六、排序冒泡排序和快速排序均属于交换类排序。1、冒泡排序:冒泡排序法在最坏的情
12、况下,冒泡排序需要比较次数为n(n-1)/2。分析:最坏情况是:按最大的排在最前,最小的排在最后,则最大的交换到最后需要交换n-1次,倒数第二个需要交换1次。总共交换次数为:1+2+3+(n-1)总共有n-1个数相加。由等差数列前n项和公式得:(n-1)1+(n-1)/2=n(n-1)/2.2、快速排序任取待排序序列中的某个元素作为基准(一般取第一个元素),通过一趟排序,将待排序的元素分为左右两个子序列,左子序列元素的排列码均小于或等于基准元素,右子序列的排序码则大于基准元素的排序码,然后分别对两个子序列继续进行排序,直至整个序列有序。七、程序1、程序设计的两种基本方法:结构化程序设计和面向对
13、象的程序设计。2、结构化程序(20世纪70年代提出)的三种基本控制结构是:顺序结构、选择结构和循环结构。3、结构化程序设计方法的主要原则为:(1)自顶向下,(2)逐步求精,(3)模块化,(4)限制使用GOTO语句。4、对象的基本特点:标识惟一性,分类性,多态性,封装性,模块独立性好。(1)标识惟一性。指对象是可区分的,并且由对象的内在本质来区分,而不是通过描述来区分。(2)分类性。指可以将具有相同属性的操作的对象抽象成类。(3)多态性。指同一个操作可以是不同对象的行为。(4)封装性。从外面看只能看到对象的外部特性,即只需知道数据的取值范围和可以对该数据施加的操作,根本无需知道数据的具体结构以及
14、实现操作的算法。对象的内部,即处理能力的实行和内部状态,对外是不可见的。从外面不能直接使用对象的处理能力,也不能直接修改其内部状态,对象的内部状态只能由其自身改变。*:信息隐蔽是通过对象的封装性来实现的。(5)模块独立性好。对象是面向对象的软件的基本模块,它是由数据及可以对这些数据施加的操作所组成的统一体,而且对象是以数据为中心的,操作围绕对其数据所需做的处理来设置,没有无关的操作。从模块的独立性考虑,对象内部各种元素彼此结合得很紧密,内聚性强。5、程序设计的风格:清晰第一,效率第二。6、对象是类的实例,对象与实例之间是具体与抽象的关系。7、数据流程图是结构化分析方法中使用的工具。8、选择结构
15、:IF ELSE ENDIF若条件成立,则执行语句序列1,否则执行语句序列2。当执行完语句序列2之后转向ENDIF的下一条语句。例:ACCEPT TO AIF A=123S=0ENDIFS=1?S输出结果为1。因为无论A为多少都要执行ENDIF后的语句。9、在循环体DO WHILE EDNDDO、FOR-ENDFOR、SCAN-ENDSCAN中遇到LOOP语句时,程序就结束本次循环,不再执行其后面的语句,而是转回DO WHILE、FOR、SCAN重新判断。如果是在循环体内遇到EXIT语句时,就结束循环,并转去执行ENDDO、ENDFOR、ENDSCAN后面的语句。八、软件1、软件:指程序、数据
16、和相关文档的完整集合。2、根据应用目标的不同,软件可分为:应用软件、系统软件和支撑软件(或工具软件)。3、软件设计是将软件需求转换为软件表示的过程。4、一个优秀的软件设计,应尽量做到高内聚、低耦合。5、 软件生命周期的定义:软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。6、还可以将软件生命周期分为:软件定义、软件开发和软件运行维护3个阶段。可行性研究与计划制定和需求分析属于软件定义阶段。7、使用、维护和退役属于软件维护阶段。软件维护阶段是软件生命周期中花费时间最多的阶段。8、软件测试的目的:发现错误。9、软件测试的过程:单元测试、集成测试、确认测试和系统测试。软件测试贯穿
17、于整个软件生命周期。10、软件调试的任务:诊断并改正程序中的错误。包括三个步骤:1)错误定位;2)修改设计和代码,以排除错误;3)进行回归测试,防止引进新的错误。调试主要在开发阶段进行。11、软件需求分析阶段产生的主要文档:软件需求规格说明书。九、数据库1、在指定字段或表达式中不允许出现重复的索引的是: 主索引和候选索引。2、在定义字段有效性规则时,在规则框中输入的表达式类型是 逻辑型。3、数据完整性:保证数据正确的特性。 包括实体完整性、域完整性和参照完整性。(1)实体完整性是保证表中记录唯一的特性, 主索引和候选索引都是为保证实体完整性的。(2)域完整性 取值、规则等(3)参照完整性 数据
18、库表之间的联系4、数据库系统的核心是开发数据库管理系统。(数据库管理系统是数据系统的核心)。5、集合运算:运算条件(两个关系、结构相同)并:两个关系的元组组成的集合。交:取同属于两个关系的元组组成的集合。差:属于一个关系而不属于另一个关系的元组组成的集合。6、关系运算:选择:从关系中找出满足给定条件的元组(从行的角度)(针对一个表)投影:从关系中指定若干个属性组成新的关系称为投影(从列的角度)(针对一个表)连接:将两个关系模式拼接成一个更宽的关系模式,生成的新关系中包含满足连接条件的元组(针对两个表)7、查询运算:笛卡尔积运算:设有n元关系R及m元关系S,它们分别有p、q个元组,则关系R与S经
19、笛卡尔积记为R*S,该关系是一个n+m元关系,元组个数是p*q,有R与S的有序组组合而成。8、数据库系统(DBS)包括:数据库(DB)和数据库管理系统(DBMS)。9、项目管理器1)“数据”选项卡:包含了一个项目中的所有数据数据库、自由表、查询和视图。2)“文档”选项卡:包含了处理数据是所用的三类文件,输入和查看数据所用的表单、打印表和查询结果所用的报表及标签。3)菜单在“其它”选项卡。10、关系数据库的存取路径对用户透明,查询效率往往不如非关系数据库模型,因此,为了提高效率,关系数据库必须进行查询优化。11、数据流图的类型:变换型和事务型。12、关系的相关概念:(1)关系:一个关系就是一张二
20、维表。(2)元组:在一个二维表中(一个具体关系),水平方向的行称为元组每一行是一个元组。元组对应一个存储文件中的一个具体记录。(3)属性:二维表中垂直方向的列称为属性。每一列有一个属性名,在VFP中表示为字段名。(4)域:属性的取值范围(5)关键字:属性或属性的组合,其值能够惟一的标识一个元组。在VP中,主关键字和候选关键字就起到唯一标识一个元组的作用。(6)外部关键字:如果表中的一个字段不是本表的主关键字或候选关键字,而是另外一个表的主关键字或候选关键字,这个字段(属性)就称为外部关键字。13、每个工作区只能打开一个数据库。14、E-R图用来建立数据模型,在数据库系统中属于概念设计阶段。15
21、、表中所有的备注型和通用型的字段都是统一存放在表达一个备注文件中,并以该文件命名,即emp或emp.fpt,无论有几个,该类字段都一样。16、数据操纵语言负责数据的操纵,包括查询及增加、删除以及修改等操作。17、数据模型:用来抽象、表示和处理现实世界中的数据和信息。分为两个阶段:把现实世界中的客观对象抽象为概念模型;把概念模型转换为某以DBMS支持的数据模型。18、数据模型:层次模型、关系模型和网状模型。19、数据模型所描述的内容有三个部分:数据结构、数据操作与数据约束。20、E-R模型:在E-R图中,矩形表示实体、椭圆形表示属性、菱形表示联系。十、变量1、变量分为内存变量和字段变量。 2、当
22、出现内存变量与字段变量同名时,若简单地用变量名访问,则系统默认为字段变量。如果要访问内存变量,则必须在变量名前加上前缀M.(或M-)3、变量名不能以数字开头, 可以以字母、汉字和下划线开头。后接字母、数字、汉字和下划线构成4、以变量的作用域来分,内存变量可分为:(1)全局变量(public):又称公共变量,在任何模块中都可以使用,先建立后使用。(2)私有变量(private):作用域是建立它的模块及其下属的各层模块,在程序中直接使用,由系统自动隐含建立的变量都是私有变量。(3)局部变量(local):只能在建立它的模块中使用。5、内存变量的赋值:格式1:STORE 表达式 to 内存变量名表如
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- VF 知识点 总结 复习
限制150内