计算机二级ACCESS公共基础知识.pdfVIP

第一章数据结构及算法

经过对部分考生的调查以及对近年真题的总结分析，笔试部分常常考查的是算法难

度，数据结构的概念，栈，二叉树的遍历，二分法查找，读者应对此部分进行重点学

习。

具体用点学习知识点：

1.算金的概念，底法时间难度及空间难度的概念

2.数据结构的定义，数据逻辑结构及物理结构的定义

3.栈的定义及其运算，线性链表的存储方式

4.树及二叉树的概念，二叉树的基本性质，完全二叉树的概念，二叉树的遍历

5.二分查找法

6.冒泡排序法

1.1算法

考点1算法的基本概念

考试链接；

考点1在笔试考试中考核的几率为30%,主要是以填空题的形式出现，分值为2分，此考

点为识记内容，读者还应当了解算法中对数据的基本运算。

计算机解题的过程事实上是在实施某种算法，这种算法称为计算机算法。

1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。

2.算法的基本要素：

(1)算法中对数据的运算和操作

一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的限制结构。

在一般的计算机系统中，基本的运算和操作有以下4类：算术运算，逻辑运算，关系运

算和数据传输。

(2)算法的限制结构：算法中各操作之间的执行依次称为算法的限制结构。

描述算法的工具通常有传统流程图，N-S结构化流程图，算法描述语言等。一个算法

一般都可以用依次，选择，循环3种基本限制结构组合而成。

考点2算法难度

考试链接：

考点2在笔试考试中，是一个常常考查的内容，在笔试考试中出现的儿率为70%,主要

是以选择的形式出现，分值为2分，此考点为重点识记内容，读者还应当识记算法时间

难度及空间难度的概念。

1.算法的时间难度

算法的时间难度是指执行算法所须要的计算工作量。

同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算

机上运行，效率均不同。这表明运用肯定的时间单位衡量算法的效率是不合适的。撇开这

些及计算机硬件，软件有关的因素，可以认为一个特定算法〃运行工作量〃的大小，只依

靠于问题的规模通（常用整数n表示），它是问题规模的函数。即

算法的工作量二fn（）

2.算法的空间难度

算法的空间难度是指执行这个算法所须要的内存空间。

一个算法所占用的存储空间包括算法程序所占的空间，输入的初始数据所占的存储

空间以及算法执行过程中所须要的额外空间。其中额外空间包括算法程序执行过程中的工

作单元以及某种数据结构所须要的附加存储空间-假如额外空间量相对于问题规模来说是

常数，则称该算法是原地工作的。在很多实际问题中，为了削减算法所占的存储空间，通

常采纳压缩存储技术，以便尽量削减不必要的额外空间。

❷疑难解答：算法的工作量用什么计算？

算法的工作量用算法所执行的基本运算次数计算，而算法所执行的基本运算次数是

问题规模的函数，即算法的工作量二fn（）,其中n是问题的规模。

1.2数据结构的基本概念

考点3数据结构的定义

考试链接：

考点3在笔试考试中，是一个常常考查的内容，在笔试考试中出现的几率为70%,主要

是以选择的形式出现，分值为2分，此考点为识记内容，读者还应当识记数据的逻辑结构

和存储结构的概念。

数据结构作为计算机的一门学科，主要探讨和探讨以下三个方面：

（1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；

2（）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储

结构；

3（）对各种数据结构进行的运算。

数据：是对客观事物的符号表示，在计算机科学中是指全部能输入到计算机中