复件计算机二级公共基础知识辅导.ppt

《复件计算机二级公共基础知识辅导.ppt》由会员分享，可在线阅读，更多相关《复件计算机二级公共基础知识辅导.ppt（69页珍藏版）》请在三一文库上搜索。

1、国家计算机等级考试二级公共基础部分真题串讲,网络中心 ：张鹤飞 讲师,推荐参考书,全国计算机等级考试考点分析、题解与模拟(二级公共基础知识)(最新大纲) 全国计算机等级考试命题研究组 编著 飞思教育产品研发中心 飞腾教育考试研究中心 联合监制 电子工业出版社 ￥19.8,公共基础部分考试大纲,基本要求 1.掌握算法的基本概念。 2.掌握基本数据结构及其操作。 3.掌握基本排序和查找算法。 4.掌握逐步求精的结构化程序设计方法。 5.掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。 6.掌握数据库的基本知识，了解关系数据库的设计。,考试内容 一、基本数据结构与算法 1.算法的基本

2、概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。,4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5.线性单链表、双向链表与循环链表的结构及其基本运算。 6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。,二、程序设计基础 1.程序设计方法与风格。 2.结构化程序设计。 3.面向对象的程序设计方法，对象，方法，属性及

3、继承与多态性。,三、软件工程基础 1.软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。 2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。 3.结构化设计方法，总体设计与详细设计。 4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。 5.程序的调试，静态调试与动态调试。,四、数据库设计基础 1.数据库的基本概念：数据库，数据库管理系统，数据库系统。 2.数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。 3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。 4.数据库设计方法和步骤：需求分析

4、、概念设计、逻辑设计和物理设计的相关策略。,考试方式 公共基础知识有10道选择题和5道填空题共三十分。,数据结构部分,05.9.2 （2）下列数据结构中,能用二分法进行查找的是 A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表,A,数据结构部分,查找技术：顺序查找、二分查找 顺序查找基本思想：从表的一端开始顺序扫描线性表，依次将扫描的节点关键字和待找的值做比较，若相等，查找成功；若整个表扫描完毕，仍未找到，则查找失败。 对表结构无要求，效率低,数据结构部分,二分查找基本思想：有序线性表长度为n，被查找元素为x，则查找过程如下： 将x与线性表的中间项比较 若相等，则找到，查

5、找结束； 若x中间项的值，则在线性表的后半部分以相同方式查找； 查找的子表为0，说明无此元素。,A,数据结构部分,8，17，25，44，68，77，98，100，115，125,Mid,8，17，25，44,Mid,第一次比较,第二次比较,查找17,数据结构部分,对二分法查找的限制： 要求表必须用顺序存储结构，且表中元素必须按关键字有序（升序或降序）排列。,数据结构部分,05.9.3 （3）下列关于栈的描述正确的是 A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表,只能在一端插入或删除元素 D）栈是特殊的线性表,只能在一端插入元素,而在另一端删除

6、元素,c,数据结构部分,栈： 是一种特殊的线性表，只能在表的一端进行插入和删除运算的线性表。进行插入和删除的这端为栈顶（Top），另一端为栈底（Bottom）。栈顶元素总是被最后插入和最先删除。（后进先出LIFO）,a0,a1,a2,an,.,数据结构部分,05.9.4 （4）下列描述正确的是 A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率 D）一个逻辑结构可以有多种存储结构,且各种存储结构影响数据处理的效率,D,数据结构部分,数据的逻辑结构：是对数据元素之间的逻辑关系的

7、描述。包括集合、线性结构、树型结构和图形结构四种。 数据的存储结构：数据的逻辑结构在计算机存储空间的存放形式。 一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等。采用不同的存储结构，其数据处理的效率是不同的。,数据结构部分,06.4.4 （4）按照“后进先出”原则组织数据的数据结构是 A）队列 B）栈 C）双向链表 D）二叉树,B,数据结构部分,队列：只允许在一端删除，在另一端插入的顺序表。 删除一端叫对头，插入一端叫队尾（先进先出FIFO）。,入队,出队,头,尾,数据结构部分,单向链表(只有一个指向后继的指针域) 双向链表(有两个指针域，一个指向后继一个指

8、向前驱),B,data,next,data,next,A,B,C,- - -,数据结构部分,队列和栈都属于线性表，他们具有顺序存储的特点，所以有后进先出和先进先出的数据组织方式； 双向链表使用链式存储方式，二叉树通常也用链式存储，他们的存储空间可以是不连续的。,B,数据结构部分,06.4.5 （5）下列叙述中正确的是 A）线性链表是线性表的链式存储结构 B）栈与队列是非线性结构 C）双向链表是非线性结构 D）只有根结点的二叉树是线性结构,A,数据结构部分,线性结构： 一个非空的数据结构如果满足以下两个条件：1，有且只有一个根节点；2，每个节点最多有一个前件，最多有一个后件，称为线性结构。 线性

9、链表是线性表的链式存储结构,数据结构部分,栈和队列是特殊的线性表，是线性结构； 双向链表是线性表的链式存储结构，所以其逻辑结构是线性结构； 二叉树是非线性结构。 答案是A,数据结构部分,06.4.6 （6）对如下二叉树 进行后序遍历的结果为 A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA,D,数据结构部分,遍历二叉树： 按照某种次序，访问二叉树中的所有节点，使得每个节点仅被访问一次。 包括前序遍历、中序遍历、后序遍历。,数据结构部分,前序遍历： 根节点左子树右子树 中序遍历： 左子树根节点右子树 后序遍历： 左子树右子树根节点,数据结构部分,06.4.7 （7）在深度为

10、7的满二叉树中，叶子结点的个数为 A）32 B）31 C）64 D）63,c,数据结构部分,数据的逻辑结构：集合、线性、树型、图形 二叉树：是树型结构 是由n个节点的有限集合构成。 二叉树特点： 非空二叉树只有一个根节点； 每个节点最多由两棵子树，称为左子树和右子树。 在二叉树中不存在度大于2的节点。,数据结构部分,满二叉树： 必须是二叉树的每一层上的节点数都达到最大，否则就不是满二叉树。 深度为m的满二叉树有2m-1个叶子节点,1,2,3,4,5,6,7,数据结构部分,06.9.7 （7）下列叙述中正确的是_。 A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，

11、则其时间复杂度必定小 C）一个算法的时间复杂度大，则其空间可复杂度必定小 D）上述三种说法都不对,数据结构部分,算法的时间复杂度：执行算法所需要的计算工作量，是一个算法执行时间的相对度量。 算法的空间复杂度：执行这个算法所需要的内存空间。 希望既省空间又省时间，但是二者无必然联系，所以答案是D。,数据结构部分,06.9.8 （8）在长度为64 的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。 A）63 B）64 C）6 D）7,B,数据结构部分,最坏情况为不含此元素或此元素在最后一个位置上。 两种情况都需要比较n次（n为长度）。,B,数据结构部分,06.9.10 （10）对下列二叉树

12、 进行中序遍历的结果是_。 A）ACBDFEG B）ACBDFGE C）ABDCGEF D）FCADBEG,A,软件工程部分,05.9.1 （1）下列正确的是： A）程序设计就是编制程序 B）程序的测试必须由程序员自己去完成 C）程序经调试该错后还应进行再测试 D）程序经调试该错后不必进行再测试,c,软件工程部分,程序设计： 是一门技术，需要相应的理论、技术、方法和工具来支持，主要包括结构化设计和面向对象的程序设计。,软件工程部分,05.9.5 （5）下列描述中正确的是： A)软件工程只是解决软件项目的管理问题 B)软件工程主要解决软件产品的生产率问题 C)软件工程的主要思想是强调在软件开发过

13、程中需要应用工程化原则 D)软件工程只是解决软件开发中的技术问题,c,软件工程部分,软件工程： 应用计算机科学、数学及管理科学等原理开发软件的工程。 (百科全书) 主要研究内容：软件开发技术和软件工程管理。,软件工程部分,05.9.6 （6）在软件设计中,不属于过程设计工具的是： A）PDL(过程设计语言) B）PAD图 C）N-S图 D）DFD图,D,软件生命周期,项目计划,需求分析,概要设计,详细设计,实现,测试,使用,维护,退役,软件工程部分,需求分析常用工具： 数据流图（DFD图） 数据字典 判定树 判定表,需 求 分 析,库房主任负责： (1) 按物品编号查询该物品的库存金额； (品

14、名、 编号、生产厂家、数量、单价、日期)录入物品信息； (2) 年终打印库存金额及各种物品库存情况表 (品 名、编号、库存量、库存金额)。 试用结构化分析方法给出： 1. 该系统顶层的DFD； 2. 顶层DFD的数据字典； 3. 最后可用的DFD。,需 求 分 析 练 习,1. 顶层的DFD图 (要点：DD基本元素不可缺；仅一 个处理逻辑),库存信息,库存文件,库房管理人员,库房管 理 MIS,库房管理人员,入库单,出库单,2 . 顶层DFD的DD： 入库单DD,出库单DD,库存信息DD,库存文件的DD,软件工程部分,详细设计（过程设计）常用工具： 程序流程图、N-S、PAD和HIPO； 判定

15、表； PDL（过程设计语言，伪码）,PDL语言描述： GET(a1,a2,.a10) max=a1; max2=a2; FOR i=2 TO 10 IF aimax max2=max; max=ai; ELSE IF aimax2 max2=ai; ENDIF ENDIF,程序流程图,软件工程部分,05.9.7 （7）下列叙述正确的是： A）软件交付使用后还需要进行维护 B）软件一旦交付使用就不需要再进行维护 C）软件交付使用后其生命周期就结束 D）软件维护是指修复程序中被破坏的指令,A,软件工程部分,软件维护： 为纠正使用中出现的错误而进行的改正性维护； 为适应环境变化而进行的适应性维护；

16、为改进原有软件而进行的完善性维护； 为将来的可维护和可靠而进行的预防性维护。 软件维护不仅包括代码的维护还包括文档的维护。,软件工程部分,06.4.1 （1）下列选项中不属于结构化程序设计方法的是 A）自顶向下 B）逐步求精 C）模块化 D）可复用,D,结构化程序设计方法(详细设计阶段)的主要原则： 自顶向下：从最上层总目标开始设计，逐步使问题具体化； 逐步求精：对于复杂问题，设计一些子目标作为过渡，逐步细化； 模块化：将要解决的总目标分解为分目标，再进一步分解为小目标，每个小目标作为一个模块； 限制使用GOTO语句。,软件工程部分,06.4.2 （2）两个或两个以上模块之间关联的紧密程度称为

17、 A）耦合度 B）内聚度 C）复杂度 D）数据传输特性,A,软件工程部分,模块的独立性： 每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。 模块的独立性程度是评价设计好坏的重要质量标准。 衡量软件的模块独立性使用耦合性和内聚性两个质量标准。,软件工程部分,内聚性： 是度量一个模块功能强度的指标；(一个模块内部各成分彼此结合的紧密程度 ) 耦合性： 用来度量模块之间的相互联系程度。 高内聚低耦合,软件工程部分,06.4.3 （3）下列叙述中正确的是 A）软件测试应该由程序开发者来完成 B）程序经调试后一般不需要再测试 C）软件维护只包括对程序代码的维护 D）以上三种说法

18、都不对,D,软件工程部分,06.9.1 （1）下列选项不符合良好程序设计风格的是_。 A）源程序要文档化 B）数据说明的次序要规范化 C）避免滥用goto 语句 D）模块设主地要保证高耦合、高内聚,D,软件工程部分,编程风格是在不影响性能的前提下，有效的编排和组织程序，提高可读性和可维护性，包括： 1.程序文档化：程序文档包含适当的注解、标识等； 2.数据说明：使模块前的说明语句次序规范化； 3.功能模块化：把源程序代码分为高内聚低耦合的模块； 4.避免使用GOTO语句。,软件工程部分,06.9.2 （2）从工程管理角度，软件设计一般分为两步完成，它们是_。 A）概要设计与详细设计 B）数据设

19、计与接口设计 C）软件结构设计与数据设计 D）过程设计与数据设计,A,软件工程部分,从技术观点看，软件设计包括结构设计、数据设计、接口设计、过程设计； 从工程管理角度看，软件设计分两步完成：概要设计和详细设计。,软件工程部分,06.9.3 （3）下列选项中不属于软件生命周期开发阶段任务的是_。 A）软件测试 B）概要设计 C）软件维护 D）详细设计,C,关系的运算,05.9.9 （9）有如下关系表: 则操作正确的是_。 A）T=RS B）T=RS C）T=RS D）T=R/S,B,关系的运算,06.9.6 （6）设有如下三个关系表 下列操作中正确的是_。 A）T=RS B）T=RS C）T=RS D）T=R/S,C,结束,大家如果有问题可以用QQ（我的QQ号在首页）的方式联系我。 最后祝大家都能顺利通过考试！ 张戈,