全国计算机二级考试基础知识讲义
需积分: 9 10 浏览量
2011-06-17
22:29:54
上传
评论
收藏 592KB DOC 举报
全国二级公共基础知识
从 年开始全国二级考试增设了公共基础知识，在理论考试中，分值 分，题型为
选择 题，填空 题。
数据结构
时间 选择题数 填空题数 总题数
2005 年 4 月
5 2 7
2005 年 9 月
3 3 6
2006 年 4 月
4 1 5
2006 年 9 月
3 2 5
2007 年 4 月
4 1 5
2007 年 9 月
4 2 6
2008 年 4 月
3 2 5
2008 年 9 月
4 1 5
一、算法
、算法的基本特征
（）可行性。针对实际问题而设计的算法，执行后能够得到满意的结果。
（）确定性。每一条指令的含义明确，无二义性。
（）有穷性。算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为
有限个，二是每个步骤都能在有限时间内完成。
（）拥有足够的情报。
、算法复杂度
算法复杂度主要包括时间复杂度和空间复杂度。我们通常讨论最坏情况复杂度。
（）算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所
需基本运算的执行次数来度量。它与所使用的算法、问题的规模等有关。
（）算法空间复杂度是指执行这个算法所需要的内存空间。
二、数据结构的基本概念
、数据结构是指相互有关联的数据元素的集合。
、数据结构主要研究和讨论以下三个方面的问题：
（）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。数据的逻辑
结构有线性（主要有线性表、栈、队列等）、非线性（主要有树、图等）。
（）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。
数据的存储结构有顺序、链接、索引等。
数据的逻辑结构反映数据元素之间的逻辑关系，数据的存储结构（也称数据的物理结
构）是数据的逻辑结构在计算机存储空间中的存放形式。同一种逻辑结构的数据可以
采用不同的存储结构，但影响数据处理效率。
（）对各种数据结构进行的运算。
、数据的逻辑结构还可表示为（，）， ：数据元素的集合；：各数据元素之
间的关系的集合；
三、线性表
、线性表是由 个具有相同特性的数据元素组成的线性序列。
、逻辑结构：线性结构
、存储结构：顺序存储结构链式存储结构
年 月
剩余25页未读，继续阅读
资源评论
nnuzhao
- 粉丝: 18
- 资源: 53
