全国计算机等级考试二级基础部分.ppt

《全国计算机等级考试二级基础部分.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全国计算机等级考试二级考试方式1.笔试：90分钟，满分100分，其中含公共基础知识部分的30分。2.上机操作：90分钟，满分100分上机操作包括：　　　（1）基本操作。　　　（2）简单应用。　　　（3）综合应用。公共基础知识部分第一章数据结构与算法【本章考试要点】算法的基本概念；算法复杂度的概念和意义（时间复杂度和空间复杂度）。数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构。线性表的定义；线性表的顺序存储结构及其插入与删除。栈和队列的定义；栈和队列的顺序存储结构有其基本运算。线性单链表、双向链表与循环链表的结构及其基本运算。树的

2、基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。顺序查找与二分法查找算法；基本排序算法（交换类排序、选择类排序、插入类排序）。1.1算法1、算法的基本特征▲可行性算法的每一条指令都必须是基本的，可执行的。▲确定性算法的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。▲有穷性算法必须在有限的时间内完成，即算法必须能在执行有限个步骤之后终止。▲拥有足够的情报不同的输入将会有不同的结果。当算法拥有足够的情报时，算法才有效。算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。2、算法的

3、基本要素▲数据对象的运算和操作基本运算和操作包括以下四类：算术运算逻辑运算关系运算数据传输▲算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构。一个算法通常由顺序、选择、循环三种基本控制结构组合而成。3、算法设计基本方法列举法归纳法递推递归减半递推技术回溯法4、算法复杂度算法的时间复杂度指执行算法所需要的计算工作量（用基本运算的次数来度量）。算法的空间复杂度指执行算法所需要的内存空间。【例1】下列叙述中正确的是（D）A)算法就是程序B)设计算法时只需要考虑数据结构的设计C)设计算法时只需要考虑结果的可靠性D)以上三种说法都不对分析：算法的

4、基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。算法不等于程序，程序不可能优于算法。答案：D11.9【例2】下面叙述正确的是(C)A.算法的执行效率与数据的存储结构无关B.算法的空间复杂度是指算法程序中指令（或语句）的条数C.算法的有穷性是指算法必须能在执行有限个步骤之后终止D.以上三种描述都不对【例3】下列叙述中正确的是(B)A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关【例4

5、】算法的时间复杂度是指（D）A)算法的执行时间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数10.3【例5】算法的空间复杂度是指（    ）。A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数答案A解析:算法的空间复杂度是指执行算法所需要的内存空间,包括算法程序所占空间,输入的初始数据所占空间和执行过程中所需要的额外空间.09.91.2数据结构的基本概念1、数据结构的定义数据结构是指相互有关联的数据元素的集合。在数据处理领域里，每一个需

6、要处理的对象都可以抽象数据元素（元素）。在具有相同牲的数据元素集合中，各个数据之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继）来描述。数据结构是指反映数据元素之间关系的数据元素集合的表示。或者说，数据结构是指带有结构的数据元素的集合。所谓结构实际上就是指数据元素之间的前后件关系。（1）数据的逻辑结构一个数据结构应包含两个方面的信息：表示数据元素的信息表示各数据元素之间的前后件关系（逻辑关系，与数据在计算机中的存储位置无关）所谓数据的逻辑结构，是指反映数据元素之

7、间逻辑关系的数据结构。（2）数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（物理结构）。在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系。常用的存储结构有顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。插入与删除是对数据结构的两种基本运算。2.数据结构的图形表示每一个数据元素用中间标有元素值的方框表示，称之为数据结点。用一条有向线段从前件指向后件，以表示数据元素之间的前后件关系。没有前件的结点称为根结点；没有后件的结点称为终端结点（叶子结点