【文档说明】二级c语言课件.ppt，共(29)页，318.500 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-44663.html

以下为本文档部分文字说明：

全国计算机二级考试公共基础知识主讲人：侯清兰公共基础知识考试范围❖单选2*10=20分，填空2*5=10分，共30分❖数据结构与算法❖程序设计基础❖软件工程基础❖数据库设计基础算法❖算法：解题方案的准确而完整的描述。❖5个特

性：❖有穷性：while(1);❖确定性：inta=3,b,n;b=a*n;❖可行性:floata=15,b;b=a/0;❖有输入：一个算法应有零个或多个输入。❖有输出：一定要有一个或多个输出。×××算法的特性❖算法

的有穷性是指（）。（2008年4月二级C真题）❖A）算法程序的运行时间是有限的❖B）算法程序所处理的数据量是有限的❖C）算法程序的长度是有限的❖D）算法只能被有限的用户使用A算法❖算法的时间复杂度：执行算法所需要的计算工作量

。❖算法的时间复杂度是指（）。(二级C真题)❖A）执行算法程序所需要的时间❖B）算法程序的长度❖C）算法执行过程中所需要的基本运算次数❖D）算法程序中的指令数C算法❖算法的空间复杂度：执行算法所需要的内存空间。❖算法的空间复杂度是指（）（2009

年9月二级C真题）❖A）算法在执行过程中所需要的计算机存储空间❖B）算法所处理的数据量❖C）算法程序中的语句或指令条数❖D）算法在执行过程中所需要的临时工作单元数A数据结构❖数据结构+算法=程序❖数据结

构是指数据元素的集合及数据元素之间的关系的集合（a）集合结构（b）线性结构（c）树型结构（d）图状结构一对一一对多多对多线性结构❖线性表顺序存储：指在内存中用地址连续的一块存储空间顺序存放线性表的各元素。12354a1an∧H…a2❖线性表链式存储：逻辑上相邻的两个数据元素物理上不一定

相邻。注意：顺序存储和链式存储可以表示线性、非线性结构顺序存储和链式存储下列叙述中正确的是（）（2008年9月二级C真题）A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，

链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间A线性表——栈和队列❖栈——先进后出表。栈顶入栈出栈栈底a3a2a1栈一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依

次出栈，则元素出栈的顺序是（）。（2008年9月二级C真题）A）12345ABCDEB）EDCBA54321C）ABCDE12345D）54321EDCBA假设用一个长度为50的数组(数组元素的下标从0到49)作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素

，如果bottom=49，top=30(数组下标)，则栈中具有个元素。（2009年3月二级C真题）B20队列❖队列——先进先出a1a2a3a4a5入队出队65432110CBA…rearfront循环队列：队头出、队尾进。队头标志front指向队头元素的前一个；队尾标志rear指向最

后一个元素。3E队列对于循环队列，下列叙述中正确的是()。（2009年9月二级C真题）A）队头指针是固定不变的B）队头指针一定大于队尾指针C）队头指针一定小于队尾指针D）队头指针可以大于队尾指针，也可以小于队尾指针设某循环队列

的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有个元素。（2008年4月二级C真题）24D二叉树❖结点的度：结点所拥有的子树的个数称为该结点的度。❖叶结点：度为0的结点称为叶结点

，或者称为终端结点。❖分枝结点：度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。❖左孩子、右孩子、双亲、兄弟。❖祖先、子孙。❖结点的层数（深度）。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。ABCEDFIGH二叉树❖满二叉

树完全二叉树ABCEDFIHKGJLMNOABCEDFIHGJ××二叉树的性质❖性质1一棵非空二叉树的第k层上最多有2k﹣1个结点（i≥1）。❖性质2一棵深度为k的二叉树中，最多具有2k﹣1个结点。❖性质3对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，

则有：n0＝n2＋1。ABCEDFIGH二叉树特性❖例1：某二叉树有5个度为2的结点以及3个度为1的结点，则该二叉树中共有个结点。（2009年9月二级C真题）❖【解析】：由性质3可知叶子结点的个数是度为2的结点个数加1，即为6，又因为二叉树只可能有度为0、度

为1、度为2的结点，所以该二叉树总结点的个数为6﹢3﹢5﹦14。本题正确答案为14。❖例2：深度为5的满二叉树有个叶子结点（2008年4月二级C真题）❖❖【解析】：由性质1得满二叉树的第5层上有25-1个结点。本题的正确答案为16。二叉树的遍历❖前序：根左右；中序：左根右；后序：左右根ABDEF

ZYCX•前：ABDEXCFYZ•中：DBXEAYFZC•后：DXEBYZFCA❖已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为（）A）GEDHFBCAB）D

GEBHFCAC）ABCDEFGHD）ACBFEDHG❖31．已知一棵二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是（）A．acbedB.decabC.deabcD.cedbaBD查找技术比较次数时间复杂度❖顺序查

找最坏nO(n)❖折半查找最坏log2nO(log2n)❖顺序查找：从头到尾一个一个找，可以用于顺序表或链表。❖折半（二分、对分）查找：使用于有序的顺序表，不适用于无序表和链表。下列叙述中正确的是A)对长度为n的有序链表进行查找，最坏情况下需要的比较次数为nB)对长度为n的有序

链表进行对分查找，最坏情况下需要的比较次数为(n/2)C)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)D)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n)A排序技术❖交换类排序比较次数❖冒泡排序n(n-1)/2❖快速排序log2n❖

插入类排序❖直接插入排序n(n-1)/2❖希尔排序n1.5❖选择类排序❖简单选择排序n(n-1)/2❖堆排序nlog2n下列排序方法中，最坏情况下比较次数最少的是__________。（2008年9月二级C真题）A)冒泡排序B)简单

选择排序C)直接插入排序D)堆排序D程序设计基础（记住基础概念）1、结构化程序设计原则：自顶向下，逐步求精，模块化，限制使用goto语句。标准：清晰第一、效率第二3大基本结构：顺序、选择、循环2、面向对象程序设计（略）软件工程❖软件、软件危机、软件工程的定义

❖软件生命周期：可行性研究、需求分析、软件设计、软件实现、软件测试、运行和维护❖软件工程原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完整性、可验证性❖结构化分析常用工具：数据流图（DFD）、数据字典(DD)等❖模块独立化：内聚

性——模块内的紧密程度❖耦合性——模块间的紧密程度软件测试❖软件测试方法：❖静态测试和动态测试❖白盒测试——结构测试、逻辑驱动测试❖方法——逻辑覆盖、基本路径测试等❖黑盒测试——功能测试、数据驱动测试❖方法——等价划分法、边界值分析法、因果法等❖软件测试的实施：单元测试

、集成测试、确认测试、系统测试❖程序的调试数据库设计基础❖概念：数据、数据库、数据库管理系统、数据库系统等❖数据库系统的三级模式：概念模式（唯一）、外模式（多个）、内模式（唯一）❖E-R模型：实体（长方形）、联系（椭圆）、属性（菱形）课程教师参考书讲授编号姓名职称实体与实体之间：一对一一对多多对

多属性中关键属性（关键字）：编号关系模型：二维表S＃SnSdSa2001001200100220010032001004张浩然李一明王伟赵坚强CPCPEEEE18191820元组/记录属性关系运算（重点）❖并RUS差：R-S❖交R∩S笛卡尔积：R×SRABCa1b1c1a1b2c

2a2b2c1SABCa1b2c2a1b3c2a2b2c1R×SR.AR.BR.CS.AS.BS.Ca1b1c1a1b2c2a1b1c1a1b3c2a1b1c1a2b2c1a1b2c2a1b2c2a1b2c2a1b3c2a1b2c2a2b2c1a2b2c1a1b2c2a2b2c

1a1b3c2a2b2c1a2b2c1专门的关系运算❖投影：挑选出关系表中的列（属性）❖选择：挑选出关系表中的行（元组）有两个关系R和T如下：RTABCa12b22c32d32ABCc32d32则由关系R得到关系T的操作是A)选择B）投影C)

交D)并专门的关系运算❖自然连接：有相同属性、把重复属性列去掉有三个关系R、S和T如下：（08年9月）RSTABBCABCm113m13n235由关系R和S通过运算得到关系T，则所使用的运算为（）。A）笛卡尔积B）交C）并D）自然连接