全国计算机等级考试《二级公共基础知识》【教材精讲+真题解析】讲义与视频课程【12小时高清视频】.docx

内容简介为了带助考生以利通过全国计算机等级考试.我们根据全国计算机等级考试最新公告、考试大纲以及相关考试用书,精心编写制作了全国计算机等级考试“二徼公共基础知识”辅导系列：1 .全国计算机等级考试i.:级公共堪础知识3【教材精讲+直册解析】讲义与视频课程【12小时高清视翔】2 .全国计算机等级考试二级公共基Bh知识题库【历年JX题+章节题库+模拟试题】3 .全国计算机等级考试二级公共基础知识专用教材【考纲分析+考点精讲+真题演燎+强化习题】本书主要包括以下两部分内容：1 .教材精讲【含12小时视频讲解】，遵循”:线公共基础知识考试大纲(20I8/&)"的考察要求及指定参考教材和相关法律法规，Z师而清视领深入剖析考试大纲，全面讲解教材重点难点内容，帮助学员巩固知识,梳理逻辑,轻松应考.2 .其应解析,新选历年考试真遨.每道真应均提供详尽答案解析，学员可以熟悉观阳的考试特点，巩固知识点弁测试自己的水平。圣才电子书编辑部公共基础知识网授精讲班主讲效邦：赵亮（二级）M光,毕业于中科院研究生院的计算机科学与技术专业.常年从事计算机学科的研究和教学.有较强的专业知识和教学能力，能膨根据学科特点，深入浅出的讲解课程内容，使学生快速理好掌握.达到教学目标.授课特点：亲和力强，课堂城It1.轻松，授课思路明朗，能够让枯煤的知识形象生动，M助学员轻松掌握核心知识点,深受广大学员喜姿.教材精讲部分视版讲解15第I章数据结构与算法视频讲解61.1 算法61.2 数据结构的卷本概念101.3 线性表及其顺序存储结构121.4 栈和队列151.5 线性链表191.6 树与二叉树241.7 查找技术301.8 排序技术32第2章程序设计基础视频讲解392.1 程序设计方法与风格392.2 结构化程序设计402.3 面向对象的程序设计44第3章软件工程基础视频讲解1493.1 软件工程基本概念493.2 结构化分析方法533.3 结构化设计方法583.4 软件测试683.5 程序的调试77第4章数据库设计基础视频讲解794.1 数据库系统的基本概念794.2 数据模型844.3 关系代数904.4 数据库设计与管理98立即解析部分107全国计算机等级考试二级公共加础知识-SS精选(一)107全国计算机等级考试二级公共基础知识3口即精选(二)109考试形式I.公共法础知识不单独考试，与其他二级科目组合在一起，作为：线科11考核内容的一部分,2.考试方式为上机考试,10道选择起.占10分.知识点分布1 .数据结构与算法2 .程序设计法础3 .软件工程基础4 .数据库设计法础大纲星本要求1 .掌握算法的她本概念，2 .掌旌基本数楙结构及其操作.3,掌握般本排序和杳找算法。4 .常旌逐步求精的结构化程序设计方法.5 .掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。家旌数据庠的基本知识,了解关系数据库的设计.第1章数据结构与算法1«MK讲解I1 .算法的基本概念：算法更杂度的概念和意义(时间更杂度与空间更杂度).2 .数据结构的定义；数据的定轨结构与存储结构；数据结构的图形表示：线性结构与非践性结构的概念。3 .线性表的定义：线性表的项序存储结构及其插入与捌除运算.4 .栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5 .线性单鞋表、双向性表与循环鞋表的结构及其基本运算.6 .树的范本概念；二叉树的定义及其存储结构；：乂树的前序、中序和后序遗历，7 .顺序查找与二分法查找©法：基本排序以法交换类排序,选择类排序,辅人类排序).1.1算法一、算法的基本概念1 .算法的定义豫法是指解题方案的准确而完整的描述，即除法是对特定向理求解步骤的一种描述“【注意】算法不等于程序，也不等于计算方法。2 .算法的基本特征(I)可行性(Effecdveness):算法中的特一个步骤必须能朝实现，执行的站果要能够达到预期的目的。<2)确定性(Dd1.nitencss):算法中的母个步骤都必须是有明确定义的，不允许有模棱两可的解择或多义性，<3)有穷性(FiniIenCss)：徵法必须能在有限的时间(合理的时间)内做完，即算法必须能在执行有限个步.骤之后终止.<4)拥有足够的情Hb输入是否足鹿井正确，领出是否合理.初始状态是否正确.二、算法设计基本方法I.列举法<1)基本思想根据提出的问遨，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的.<2)特点简单.方使用计尊机进行大量列举：情况较多时工作量将会很大.<3)使用将马向SS有关的知识条理化、完备化、系统化，从中找出规律，行分类,减少列举最。【例1】今有鸡母一，值钱三：鸡翁一，假钱二；鸡雏一，值钱半.凡百钱买百鸡,问鸡母、鸡翁、鸡维各几何？假设买母鸡I只、公鸡J只、小璃K只.根据SS速，林略的列举算法描述如下：FORI=OTO100STEPIDOFORJ-OTOI(K)STEPIIX)FORK=OTOI(X)STEPIDOI1R(1+J+K=1OO)AND(3*I+2*J-M).5*K=100.O)THENPRINTU.K)END共有三层砧环，降层循环各制要循环IOI次，大约为100万次。优化后的算法FORI=OTO33STEPIDOFORJ=OTO50-1.5*ISTEPIDOK=!-I-J1F(3+I+2J+O.5*K=1.(X).()THENPRINTU.KEND共有两层循环循环次数为33£(51-1.5/)894I=Q2.归纳法<1)基本思想通过列举少出的特殊情况,经过分析最后找出一般的关系.<2)特点归纳是一种抽象，即从特殊现象中找出一做关系，<3)使用由于在切纳的过程中不可能对所行的情况进行列举.因此,最后由归纳得到的结论还只是种物冽,还需要时这种猜冽加以必要的证明.实际上.通过精心观察而得到的猜测解不到证实或以后证明猜测玷错的，也是常H的事.3 .递推(1)基本思想从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果.(2)特点本质上同尸归纳法，递推关系式往往是归纳的结果。(3)使用速推算法在数值计算中是极为常见的.但是,对于数值型的递推算法必须要注意数值计算的稳定件问起.4 .递归(1)基本思想为了降低问遨的复杂程度,符问题逐层分解,最后归结为一些最简单的何麴,这种符问题逐层分解的过程,实际上并没有对问题进行求解，而只是当解决了靛后那些最简雎的问胆后，再沿着原来分解的逆过程逐步进行综合.(2)特点结构清晰.可读性强，<3)使用递归在可计算性理论和算法设计中占有很虫要的地位。(4)分类直接递归(自己调用自己)和间接递归(P陶用Q.Q乂调用P).【例2】编写一个过程，对于输入的参数n,依次打印输出自然数I到n.非递归算法:wt(in(n)FORk=1.TOnSTEPIDOPRINTkRETURNI递归算法：witHintn)(IF(n0)THENWrtKn-DPRINTnIRET1.RN5,减半递推技术所谓“减半是指将问题的序模减半,而问题的性质不变：所谓“递推是指重复“减半”的过程.【例13设方程f<x>=O在区间a,b上有实根，且f（八）与f(b>界号.利用二分法求该方程在区间同b)上的一个实根，用二分法求方程实根的减半递推过程如下：(1)首先取给定区间的中点C=<a+b)/2.<2)然后判断f(C)是否为0：如果f(c)=0,则说明C即为所求的根，求解过程结束：如果f(c)0,则根据以下原则将原区间减半：若f（八）f(c)<0,则取原区间的前半部分：若f(b)f8)<0.则取原区间的后半部分.(3)班后判断战半后的区间长度是否己羟很小：若a-bVe,则过程结束，取(a+b)/2为根的近似值：若a-b妾e,则Hi复上述的减半过程,6.回溯法(1)基本思想通过时问题的分析，找出一个解决问时的线索，然后沿希这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退,换别的路线再进行试探.这种方法称为回溯法。(2)特点在工程上，有些实际问超很难归纳出一组简单的递推公式或直观的求解步骡，并旦也不能进行无限的列举.对于这类向SS,一种有效的方法是“试”。三、算法复杂度主要包括时间坡杂度和空间更杂度.1 .以法的时间史杂度<1)定义执行算法所需要的计算工作量.(2)衡量标准通常用算法在执行过程中所需基本运算的执行次数来度量笄法的工作量，律法所执行的基本运算次数还与问题的规模有关.综上所述.算法的工作限用算法所执行的基本运算次数来度限,而算法所执行的基本运豫次数是何时规模的函数，即算法的工作录=f(1).(3)存在问题算法所执行的基本运尊次数还可能与特定的输入行关.而实际上又不可能将所有可能情况下算法所执行的基本运算次数都列举出来.(4)解决方法平均性态(AverageBehavior)用各种制定输入下的基本运算次数的加权平均值来度量算法的工作量：&)=PC(X)XdSt坏情况红杂性(WOrStC3$CComp1.exity>规模为n时，算法所执行的般本运獴的坡大次数：W(n)=maxr(x)wd“2 .豫法的空间更杂度【定义】执行这个算法所需要的内存空间.< 1)匏法程序所占的空间：< 2)输入的初始数据所占的存储空间；< 3)算法执行过程中所需要的额外空间。【注意】如果额外空间量相对于问区规模来说是常数，则称该算法是像地r作的.在许多实际问遨中，为了M少饵法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间,【考即1】打法的时间复杂度是指().A,执行算法程序所衙要的时间B.蚱法程序的长度1 .数据的逻帆结构<1）定义反映数据元素之间逻辑关系的数捌结构.一个数据结构应包含以下两方面的信息：表示数据元素的佶息：表示各数据元素之间的前后件关系，<2）数据的逻轼结构有两个要素：一是数据元素的集合,通常记为D：二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R：即一个数据结构可以表示成B=（D.R）,【例4】一年四季的数据结构Ur以表示成B=（D.R）D=1.夏，秋，冬R=（#,熨），（夏，秋），（秋，冬2 .数据的存储结构定义：数据的逻辑结构在计算机存储空间中的存放形式.【注意】各数据元素在计徵机存储空间中的位置关系与它们的能卷关系不一定是相同的，而且一般也不可能相同.在数据的存储结构中,不仅要存放各数据元案的信息.还需要存放各数据元素之间的前后件关系的信息.常用的存储结构书1顺序、t接、索引等存储结构.采用不同的存储结构，其数据处理的效率是不同的.二、数据结构的图形式示一个数据结构除了用二元关系我示外，还可以直观地用图形发示.<1）时于数据集合D中的绿一个数据元素用中间标有元素例的方框表示，一般称之为数据结点，并简称为结点：<2）对于关系R中的每一个二元组,用一条目向线段从前件结点指向后件结点,有时箭头可省去.