著名计算机科学家Edsger Dijkstra曾经指出:“计算机科学就像天文学不仅仅是计算机,而是望远镜一样。” 以下是计算机二级公共基础知识常见知识点的总结。 请作为参考
数据结构和算法
经过对部分考生的调查和对近年真题的总结分析,笔试部分仔细考查了算法的复杂性、数据结构概念、堆栈、二叉树遍历、二分法搜索,读者应重点学习这一部分。
深入学习知识点:
1 .算法概念、算法时间复杂度和空间复杂度概念
2 .数据结构的定义、数据逻辑结构及物理结构的定义
3 .栈的定义及其运算、线性链表的存储方式
4 .树和二叉树概念、二叉树的基本性质、完全二叉树概念、二叉树遍历
5 .二分搜索法
6 .鼓泡排序法
1.1算法
考点1算法的基本概念
试验链接:
考点1笔试考核概率为30%,主要表现为填空题形式,分数为2分,该考点为知识符号内容,读者还应了解算法中对数据的基本运算。
计算机解决问题的过程实际上正在实施某种算法,该算法称为计算机算法。
1 .算法的基本特点:具有可行性、确定性、穷举性,有足够的信息。
2 .算法的基本要素:
(1)算法中数据的运算和操作
一个算法由两个基本要素组成。 一个是数据对象的运算和操作。 二是算法的控制结构。
在一般的计算机系统中,基本的运算和操作有算术运算、逻辑运算、关系运算、数据传输四种。
)算法的控制结构)算法中各操作之间的执行顺序称为算法的控制结构。
描述算法的工具通常包括传统流程图、N-S结构化流程图、算法描述语言等。 一种算法通常可以组合顺序、选择、循环三种基本控制结构来构成。
考点2算法的复杂性
试验链接:
考点2是笔试中经常查的内容,笔试出现的概率为70%,主要表现为选择形式,分数为2分,以该考点为重点识别内容,读者还应识别算法的时间复杂度和空间复杂度概念。
1 .算法的时间复杂性
算法的时间复杂度是指运行算法所需的计算工作量。
使用不同的语言实现相同的算法、使用不同的编译器编译或在不同的计算机上运行时,效率会不同。 这表明,以绝对时间为单位测量算法效率是不合适的。 除了这些与计算机硬件、软件相关的要素之外,某个特定的算法“执行工作量”的大小仅依赖于问题的规模(通常用整数n表示),被认为是问题的规模的函数。 也就是说
的计算量=f(n ) ) ) ) ) ) ) ) ) ) ) ) )。
2 .算法的空间复杂性
算法的空间复杂性是指运行该算法所需的内存空间。