二年级公共基础知识教材精讲HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】目 录视频讲解教师简介 ....................................................................教材精讲部分[视频讲解] ..............................................................第1章 数据结构与算法[视频讲解] ................................................1.1 算 法 .................................................................1.2 数据结构的基本概念 .....................................................1.3 线性表及其顺序存储结构 .................................................1.4 栈和队列 ...............................................................1.5 线性链表 ...............................................................1.6 树与二叉树 .............................................................1.7 查找技术 ...............................................................2018年9月全国计算机等级考试《二级公共基础知识》【教材精讲＋真题解析】讲义与视频课程最新资料，WORD 格式，可编辑修改！1.8 排序技术............................................................... 第2章程序设计基础[视频讲解] ..................................................2.1 程序设计方法与风格.....................................................2.2 结构化程序设计.........................................................2.3 面向对象的程序设计..................................................... 第3章软件工程基础[视频讲解] ..................................................3.1 软件工程基本概念.......................................................3.2 结构化分析方法.........................................................3.3 结构化设计方法.........................................................3.4 软件测试...............................................................3.5 程序的调试............................................................. 第4章数据库设计基础[视频讲解] ................................................4.1 数据库系统的基本概念...................................................4.2 数据模型...............................................................4.3 关系代数...............................................................4.4 数据库设计与管理....................................................... 真题解析部分........................................................................全国计算机等级考试《二级公共基础知识》真题精选（一）............................全国计算机等级考试《二级公共基础知识》真题精选（二）............................考试形式1．公共基础知识不单独考试，与其他二级科目组合在一起,作为二级科目考核内容的一部分。

2．考试方式为上机考试，10道选择题，占10分。

大纲基本要求1．掌握算法的基本概念。

2．掌握基本数据结构及其操作。

3．掌握基本排序和查找算法。

4．掌握逐步求精的结构化程序设计方法。

5．掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。

6．掌握数据库的基本知识，了解关系数据库的设计。

知识点分布1．数据结构与算法2．程序设计基础3．软件工程基础4．数据库设计基础第1章数据结构与算法[视频讲解]1.1 算法1.2 数据结构的基本概念1.3 线性表及其顺序存储结构1.4 栈和队列1.5 线性链表1.6 树与二叉树1.7 查找技术1.8 排序技术本章考点1．算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。

2．数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。

3．线性表的定义；线性表的顺序存储结构及其插入与删除运算。

4．栈和队列的定义；栈和队列的顺序存储结构及其基本运算。

5．线性单链表、双向链表与循环链表的结构及其基本运算。

6．树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。

7．顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。

1.1 算法一、算法的基本概念1．算法的定义算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。

*算法不等于程序，也不等于计算方法。

2．算法的基本特征（1）可行性（Effectiveness）①算法中的每一个步骤必须能够实现。

②算法执行的结果要能够达到预期的目的。

（2）确定性（Definiteness）算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。

（3）有穷性（Finiteness）算法的有穷性是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。

*算法的有穷性还应包括合理的执行时间（4）拥有足够的情报①输入是否足够并正确，输出是否合理。

②初始状态是否正确。

二、算法设计基本方法1．列举法（1）基本思想根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。

（2）特点简单，方便用计算机进行大量列举；情况较多时，工作量将会很大。

（3）使用将与问题有关的知识条理化、完备化、系统化，从中找出规律，进行分类，减少列举量。

例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 DO{IF（（I+J+K==100）AND（3*I+2*J+0.5*K==100.0））THENPRINT I，J，K}END共有三层循环，每层循环各需要循环101次，大约为100万次。

优化后的算法FOR I=0 TO 33 STEP 1DOFOR J=0 TO 50-1.5*I STEP 1 DO{K=100-I-JIF（3*I+2*J+0.5*K==100.0）THENPRINT I，J，K}END共有两层循环，循环次数为2．归纳法（1）基本思想通过列举少量的特殊情况，经过分析最后找出一般的关系。

（2）特点归纳是一种抽象，即从特殊现象中找出一般关系。

（3）使用由于在归纳的过程中不可能对所有的情况进行列举。

因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。

实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。

3．递推（1）基本思想从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。

（2）特点本质上属于归纳法，递推关系式往往是归纳的结果。

（3）使用递推算法在数值计算中是极为常见的。

但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。

4．递归 *（1）基本思想为了降低问题的复杂程度，将问题逐层分解，最后归结为一些最简单的问题，这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合。

（2）特点结构清晰，可读性强。

（3）使用递归在可计算性理论和算法设计中占有很重要的地位。

（4）分类直接递归（自己调用自己）和间接递归（P调用Q，Q又调用P）。

例1.2 编写一个过程，对于输入的参数n，依次打印输出自然数1到n。

非递归算法：wrt（int n）{FOR k=1 TO n STEP 1 DO PRINT kRETURN}递归算法：wrt1（int n）{IF（n≠0）THEN{wrt1（n-1）PRINT n}RETURN}5．减半递推技术所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。

例1.3 设方程f（x）=0在区间[a，b]上有实根，且f（a）与f（b）异号。

利用二分法求该方程在区间[a，b]上的一个实根。

用二分法求方程实根的减半递推过程如下：首先取给定区间的中点c=（a+b）／2。

然后判断f（c）是否为0。

若f（c）=0，则说明C即为所求的根，求解过程结束；如果f（c）≠0，则根据以下原则将原区间减半：若f（a）f（c）<0，则取原区间的前半部分；若f（b）f（c）<0，则取原区间的后半部分。