《全国计算机等级考试《二级C++语言程序设计》【教材精讲+真题解析】讲义与视频课程506p》由会员分享,可在线阅读,更多相关《全国计算机等级考试《二级C++语言程序设计》【教材精讲+真题解析】讲义与视频课程506p(50页珍藏版)》请在金锄头文库上搜索。
1、全国计算机等级考试二级 C语言程序设计 【教材精讲真题解析】 讲义与视频课程最新资料, WOR 式,可编辑修改!目 录视频讲解教师简介 .教材精讲部分 视频讲解 .第一部分 公共基础知识 视频讲解 .第 1 章 数据结构与算法 视频讲解 .第 2 章 程序设计基础 视频讲解 .第 3 章 软件工程基础 视频讲解 .第 4 章 数据库设计基础 视频讲解 .第二部分 C+语言程序设计 视频讲解 .第 1 章 C+语言概述 视频讲解 .第 2 章 数据类型、运算符和表达式 视频讲解 .3 章 4 章 5 章 6 章 7 章 8 章 9 章 10 章11 章第 第 第 第 第 第 第 第第基本控制结构
2、 视频讲解 .数组、指针与引用 视频讲解 .函 数 视频讲解 .类和对象 视频讲解 .继承和派生 视频讲解 .运算符重载 视频讲解 .模 板 视频讲解 .C+流 视频讲解 .考试指导 视频讲解 .真题解析部分 .全国计算机等级考试二级 全国计算机等级考试二级 全国计算机等级考试二级全国计算机等级考试二级.C+语言程序设计真题及详解(一)C+语言程序设计真题及详解(二)C+语言程序设计真题及详解(三)C+语言程序设计真题及详解(四)教材精讲部分 视频讲解 第一部分 公共基础知识 视频讲解 考试形式1公共基础知识不单独考试,与其他二级科目组合在一起 , 作为二级科目考核内容的一部分。2 考试方式为
3、上机考试, 10 道选择题,占 10 分。 大纲基本要求1 掌握算法的基本概念。2 掌握基本数据结构及其操作。3 掌握基本排序和查找算法。4 掌握逐步求精的结构化程序设计方法。5掌握软件工程的基本方法, 具有初步应用相关技术进行软件开发的能力。6 掌握数据库的基本知识,了解关系数据库的设计。 知识点分布1数据结构与算法2程序设计基础3软件工程基础4数据库设计基础第 1 章 数据结构与算法 视频讲解 本章考点1算法的基本概念; 算法复杂度的概念和意义 (时间复杂度与空间复杂度) 。2 数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示; 线性结构与非线性结构的概念。3 线性表的定义;线
4、性表的顺序存储结构及其插入与删除运算。4 栈和队列的定义;栈和队列的顺序存储结构及其基本运算。5 线性单链表、双向链表与循环链表的结构及其基本运算。6树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后 序遍历。7 顺序查找与二分法查找算法; 基本排序算法 (交换类排序, 选择类排序,插入类排序)。第一节 算 法一、算法的基本概念1算法的定义算法是指解题方案的准确而完整的描述,即算法是对特定问题求解步骤的 一种描述。* 算法不等于程序,也不等于计算方法。2算法的基本特征( 1)可行性( Effectiveness )算法中的每一个步骤必须能够实现。算法执行的结果要能够达到预期的目的。
5、(2)确定性( Definiteness )算法的确定性,是指算法中的每一个步骤都必须是有明确定义的,不允许有模棱两可的解释,也不允许有多义性。( 3)有穷性( Finiteness )算法的有穷性是指算法必须能在有限的时间内做完,即算法必须能在执行 有限个步骤之后终止。* 算法的有穷性还应包括合理的执行时间(4)拥有足够的情报输入是否足够并正确,输出是否合理。初始状态是否正确。二、算法设计基本方法1列举法( 1)基本思想根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。(2)特点简单,方便用计算机进行大量列举;情况较多时,工作量将会很大。(3)使用将与
6、问题有关的知识条理化、完备化、系统化,从中找出规律,进行分类, 减少列举量。例 1.1 今有鸡母一,值钱三;鸡翁一,值钱二;鸡雏一,值钱半。凡百钱买百鸡,问鸡母、鸡翁、鸡雏各几何?假设买母鸡 I 只、公鸡 J 只、小鸡 K 只。根据题意,粗略的列举算法描述 如下:FOR I=0 TO 100 STEP 1 DOFOR J=0 TO 100 STEP 1 DOFOR K=0 TO 100 STEP 1 DOIF ( I+J+K=100)AND( 3*I+2*J+0.5*K=100.0 ) THENPRINT I ,J, KEND共有三层循环,每层循环各需要循环 优化后的算法FOR I=0 TO
7、33 STEP 1DOFOR J=0 TO 50-1.5*I STEP 1 DO101 次,大约为 100 万次。K=100-I-JIF (3*I+2*J+0.5*K=100.0 )THENPRINT I ,J, KEND共有两层循环,循环次数为2归纳法( 1)基本思想通过列举少量的特殊情况,经过分析最后找出一般的关系。(2)特点归纳是一种抽象,即从特殊现象中找出一般关系。(3)使用由于在归纳的过程中不可能对所有的情况进行列举。因此,最后由归纳得 到的结论还只是一种猜测,还需要对这种猜测加以必要的证明。实际上,通过 精心观察而得到的猜测得不到证实或最后证明猜测是错的,也是常有的事。3递推( 1
8、)基本思想从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。(2)特点本质上属于归纳法,递推关系式往往是归纳的结果。(3)使用递推算法在数值计算中是极为常见的。但是,对于数值型的递推算法必须要注意数值计算的稳定性问题。4递归 *( 1)基本思想为了降低问题的复杂程度,将问题逐层分解,最后归结为一些最简单的问 题,这种将问题逐层分解的过程,实际上并没有对问题进行求解,而只是当解 决了最后那些最简单的问题后,再沿着原来分解的逆过程逐步进行综合。(2)特点结构清晰,可读性强。(3)使用递归在可计算性理论和算法设计中占有很重要的地位。(4)分类直接递归(自己调用自己)和间接递归( 例 1.2
9、 编写一个过程,对于输入的参数非递归算法:wrt ( int n )FOR k=1 TO n STEP 1 DO PRINT kRETURN递归算法:wrt1 ( int n )IF (n0)THENP 调用 Q,Q又调用 P)。n,依次打印输出自然数 1 到 n。wrt1 ( n-1 )PRINT nRETURN5减半递推技术所谓 “减半” ,是指将问题的规模减半, 而问题的性质不变; 所谓 “递推” ,是指重复“减半”的过程。例 1.3 设方程 f (x)=0 在区间 a ,b 上有实根,且 f (a)与 f (b)异号。 利用二分法求该方程在区间 a ,b 上的一个实根。用二分法求方程实
10、根的减半递推过程如下:首先取给定区间的中点 c=(a+b) 2。然后判断 f (c)是否为 0。若 f (c)=0,则说明 C 即为所求的根,求解过程结束;如果 f (c)0,则根据以下原则将原区间减半:若 f (a)f (c)0,则取原区间的前半部分;若 f (b)f (c)0,则取原区间的后半部分。最后判断减半后的区间长度是否已经很小:若|a- b| ,则过程结束,取( a+b) 2 为根的近似值;若|a- b| ,则重复上述的减半过程。6回溯法( 1)基本思想通过对问题的分析,找出一个解决问题的线索,然后沿着这个线索逐步试探,对于每一步的试探,若试探成功,就得 到问题的解,若试探失败,就逐步回退,换别的路线再进行试探。这种方法称为回溯法。(2)特点在工程上,有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤, 并且也不能进行无限的列举。对于这类问题 , 一种有效的方法是“试”。三、算法复杂度主要包括时间复杂度和空间复杂度。1算法的时间复杂度( 1)定义执行算法所需要的计算工作量。(2)衡量标准通常用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。 算法所执行的基本运算次数还与问题的规模有关。综上所述,算法的工作量用算法所执行的基本运算次数来度量,而算法所 执行的基本运算次数是问题规模的函数,即算法的工作量 =f ( n)。(3)存在问题算法所执行的基本运