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

全国计算机等级考试二级公共基础知识公共基础知识内容：•考试大纲•数据结构与算法•程序设计基础•软件工程基础•数据库设计基础考试大纲考试内容一、基本数据结构与算法1、算法的基本概念；算法复杂度的概念和意义(空间复杂度与时间复杂度)。2、数据结构的定义；数据的逻辑结构和存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3、线性表的定义；线性表的顺序存储结构及其插入删除运算。4、栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5、线性单链表，双向链表与循环链表的结构及其基本运算。6、树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7、顺序查找与二分查找算法；基本排序算法(交换类排序、选择类排序、插入类排序)。考试大纲考试内容二、程序设计基础1、程序设计方法与风格。2、结构化程序设计。3、面向对象的程序设计方法，对象，方法，属性及继承与多态性。考试大纲考试内容三、软件工程基础1、软件工程的基本概念；软件生命周期概念；软件工具与软件开发环境。2、结构化分析方法；数据流图，数据字典，软件需求规格说明书。3、结构化设计方法；总体设计，详细设计。4、软件测试的方法；白盒测试，黑盒测试，测试用例设计；软件测试的实施；单元测试，集成测试，系统测试。5、程序的调试，静态调试与动态调试。考试大纲考试内容四、数据库设计基础1、数据库的基本概念；数据库，数据库管理系统，数据库系统。2、数据模型；实体联系模型及E-R图，从E-R图导出关系数据模型。3、关系代数运算，包括集合运算及选择、投影、连接运算；数据库规范化理论。4、数据库设计方法和步骤；需求分析、概念设计、逻辑设计和物理设计的相关策略。考试大纲考试题型选择题10题每题2分共20分填空题5题每题2分共10分合计30分数据结构与算法关键考点•算法基本概念及算法复杂度•数据的存储结构•栈和队列•线性链表•二叉树基本概念及其特性•查找技术第1节数据结构与算法算法的基本概念1、算法算法是指解题方案的准确而完整的描述。注意：算法与数学上的计算方法不是同一个概念。算法要考虑计算机的特点，要考虑计算方法的可行性。算法也不等于程序。算法不考虑具体的机器及编程语言。解决问题时，总是先设计算法，然后进行编程。2、算法的基本特征可行性确定性有穷性拥有足够的情报算法是一个动态概念，强调实际的执行过程。数学上的计算方法是一个静态概念，注重理论上的正确性。数学上的计算方法是设计算法的基础。例题：1.算法的有穷性是指A．算法程序的运行时间是有限的B．算法程序所处理的数据量是有限的C．算法程序的长度D．算法只能被有限的用户使用1.算法的基本概念第1节数据结构与算法算法的基本概念3、算法的基本要素算法中对数据的运算和操作基本的运算和操作有：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构控制结构决定操作的执行顺序。要求符合结构化原则，强调易读性。4、算法设计基本方法列举法列举所有可能情况，检测其中符合条件的结果。归纳法列举若干特殊情况，分析归纳出一般规律。递推从已知初始条件出发，逐步推导出中间及最后结果。递归将复杂问题归结为简单问题，在归结为更简单问题，…。减半递推技术将问题规模“减半”，并重复该“减半”的过程。回溯法分析问题，找出某些线索，沿线索逐步试探。若试探成功，则继续，若试探失败，则回退。直至问题解决。第1节数据结构与算法算法的基本概念5、算法的时间复杂度指执行算法所需要的计算工作量算法工作量的度量应与计算机、编程语言、编程细节等无关。算法的工作量用算法所执行的基本运算次数衡量。算法工作量是问题规模的函数：算法的工作量=f(n)度量方法有：平均性态分析计算其加权平均值最坏情况分析计算其基本运算的最大次数6、算法的空间复杂度指执行算法所需要的存储空间包括：算法程序所占据的存储空间待处理数据所占据的存储空间算法程序执行中所需要的额外存储空间如果额外存储空间大小不随问题规模变化，则称之为算法原地工作。降低算法的空间复杂度，应从数据的存储空间和额外空间入手。例题：2.下列叙述中正确的是A．算法的效率只与问题的规模有关，而与数据的存储结构无关B．算法的时间复杂度是指执行算法所需要的计算工作量C．数据的逻辑结构与存储结构是一一对应的D．算法的时间复杂度与空间复杂度一定相关3.算法的空间复杂度是指A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句货指令条数D.算法在纸箱过程中所需要的临时工作单元数4.算法的时间复杂度是指A.算法的执行时间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的基本运算次数第2节数据结构的基本概念•计算机处理数据，主要考虑两个方面：一、提高数据处理的速度？二、节省存储空间？•数据结构主要研究三个方面的问题：•（1）数据的逻辑结构：各数据元素间所固有的逻辑关系•（2）数据的存储结构（物理结构）：各数据元素在计算机中的存储关系•（3）对各种数据结构进行的运算。根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图•数据的逻辑结构——只抽象反映数据元素的逻辑关系•数据的存储（物理）结构——数据的逻辑结构在计算机存储器中的实现数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：数据结构与算法数据结构的基本概念数据结构的表示二元关系表示：两个要素：数据元素的集合D，该集合上的关系R。即：B=(D,R)如：D={春,夏,秋,冬}R={(春,夏),(夏,秋),(秋,冬)}图形表示：标有元素值的方框表示结点，有向线段表示逻辑关系。春→夏→秋→冬线性结构和非线性结构线性结构：一个非空的线性结构有且只有一个根结点，每个结点最多只有一个直接前驱、最多只有一个直接后继。非线性结构：不是线性结构的数据结构。1.下列叙述中正确的是A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间2.下列数据结构中，属于非线性结构的是A.循环队列B.带链队列C.二叉树D.带链栈3.数据的存储结构是指______。A.数据所占的存储空间量B.数据的逻辑结构在计算机中的表示C.数据在计算机中的顺序存储方式D.存储在外存中的数据第3节线性表和顺序存储结构1线性表的基本概念线由一组数据元素组成。是最简单、最常用的一种数据结构.线性表是一种线性结构。非空线性表有如下结构特征：（1）有且只有一个根结点（2）有且只有一个终结节点（3）除以上二结点外，每个结点有且只有一个前件，也有且只有一个后件。d1d2d3春夏秋冬姓名性别数学英语张三女7070李四男6590王五女68802线性表的顺序存储结构具有如下特点——逻辑相临，物理相临（1）线性表中所有元素所占的存储空间是连续的。（2）数据元素在存储空间中是按逻辑顺序依次存放的。姓名数学英语张三7070李四6590王五6880张三7070李四6590王五6880线性表的顺序存储结构是一种随机存取的存储结构。可随机访问任意一个结点3线性表的插入运算2597143、线性表的插入运算2597143、线性表的插入运算2597143、线性表的插入运算2597143、线性表的插入运算214597结论：（1）如果在线性表的末尾进行，即在第n个元素之后插入新元素，则只要增加一个元素即可，不需要移动元素（2）如果要在线性表的第1个元素之前插入，则需要移动表中n个的元素。（3）在一般情况下，如果在第i个元素之前进行，则第i个元素之后的所有元素都必须移动。在平均情况下，需要移动表中一半的元素。因此算法的平均时间复杂度为O(n).4、线性表的删除运算2145974、线性表的删除运算25974、线性表的删除运算25974、线性表的删除运算25974、线性表的删除运算2597注意：如果为线性表开辟的存储空间已经满了，不能再插入元素，否则会造成“上溢”错误1如果删除第n个元素，则不需要移动其他元素；2如果删除第1个元素，则需要移动所有的元素。3在一般情况下，若要删除第i个元素，则原来第i个元素之后的所有元素都必须依次往前移动一个位置。平均要移动表中一半的元素。算法的平均时间复杂度为O(n).结论：线性表顺序存储，插入或删除一个元素，效率很低，特别是线性表比较大的情况，由于数据元素的移动而消耗较多的处理时间。线性表的顺序存储结构对于小线性表或者元素不常变动的线性表来说是合适的，因为顺序存储结构比较简单。对线性表，描述的是（）A存储空间不一定连续，且各元素的存储顺序是任意的B存储空间不一定连续，且前件元素一定存储在后件元素前面C存储空间必须连续，且前件元素一定存储在后件元素后面D存储空间必须连续，且各元素的存储顺序是任意的数据结构与算法线性链表1、链式存储方式①结点由两部分组成：数据域(存储数据)、指针域(指向其前件或后件)。②数据结构的存储空间可以不连续，存储顺序与逻辑关系可以不一致。③链式存储方式既可以用来表示线性结构，也可以表示非线性结构。2、线性链表线性表的链式存储结构称为线性链表。(栈的链式存储结构称为链栈、队列的链式存储结构称为链队列)常用的线性链表有：单链表(一个指针域，指向直接后继)双向链表(两个指针域，指向直接后继及后继)循环链表(所有结点的指针构成循环链)3、线性链表的基本运算查找：在线性链表中查找指定元素。插入：在线性链表中插入新结点。删除：在线性链表中删除指定结点。例题：1.线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的链式存储结构。2.下列叙述中正确的是A.线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B.线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C.线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D.上述三种说法都不对数据结构逻辑结构存储（物理）结构线性结构非线性结构顺序结构链式结构3.线性表的顺序存储结构和线性表的链式存储结构分别是______。A.顺序存取的存储结构、顺序存取的存储结构B.随机存取的存储结构、顺序存取的存储结构C.随机存取的存储结构、随机存取的存储结构D.任意存取的存储结构、任意存取的存储结构4.用链表表示线性表的优点是______。A.便于插入和删除操作B.数据元素的物理顺序与逻辑顺序相同C.花费的存储空间较顺序存储少D.便于随机存取5.在单链表中，增加头结点的目的是______。A.方便运算的实现B.使单链表至少有一个结点C.标识表结点中首结点的位置D.说明单链表是线性表的链式存储实现数据结构与算法栈及其基本运算1、栈栈(stack)是限定在一端进行插入和删除的线性表允许进行插入或删除的一端称为栈顶。不允许进行插入或删除的另一端称为栈底。其特点为“先入后出”(FILO)或“后入先出”(LIFO)。(记忆作用)通常设置指针top指向栈顶，指针bottom指向栈底。2、栈的顺序存储结构栈的各个数据元素按其逻辑顺序依次连续存储。由于插入删除操作只能在栈顶一端进行，所以不需要移动数据元素。3、栈的基本运算入栈：在栈顶位置插入新元素。出栈：取出栈顶位置的元素。读栈顶元素：读出栈顶位置的元素。“上溢”：入栈时堆栈已满。“下溢”：出栈时堆栈已空。第4节栈和队列1栈及其运算栈是限定在一端进行插入与删除的线性表。入栈原则：先进后出，后进先出。597栈顶栈底64入栈（插入数据）4597栈顶栈底664597栈顶栈底入栈（插入数据）64597栈顶栈底出栈（删除数据）4597栈顶栈底出栈（删除数据）597栈顶栈底出栈（删除数据）2栈的特点1栈顶元素总是最后被插入的元素，也是最早被删除的元素。2栈底元素总是最早被插入的