全国计算机二级公共基础知识(打印版).pdf

全国计算机二级公共基础知识(重点部分)

第一章数据结构基础

1.1算法

1.1.1算法的基本概念

算法是解题方案的准确而完整的描述，它不等于程序，也不等计算方法。

算法的基本特征

可行性(effectiveness)确定性(definiteness)

有穷性(finiteness)拥有足够的情报

算法的时间复杂度

执行算法所需要的计算工作量

与下列因素有关：

书写算法的程序设计语言,编译产生的机器语言，代码质量

机器执行指令的速度,问题的规模

问题的规模函数算法的工作量=f(n)

算法中基本操作重复执行的频率T(n)，是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))

记号“O”读作“大O”。表示随问题规模n的增加，算法执行时间的增长率和f(n)相应增加。

常见算法复杂度：

O(1)：常数阶O(n)：作线性阶O(n2)：平方阶

O(n3)：立方阶O(logn)：对数阶O(2n)：指数阶

算法的空间复杂度

算法执行过程中所需的最大存储空间

存储量包括以下三部分

算法程序所占的空间,输入的初始数据所占的存储空间,算法执行过程中所要的额外空间

1.2数据结构的基本概念

线性表

A．线性结构栈

队

1．数据的逻辑结构

数

树形结构

据B．非线性结构

结

构图形结构

的

三2、数据的存储结构A顺序存储

个

方B链式存储

面

3、数据的运算：检索、排序、插入、删除、修改等。

数据的逻辑结构

对数据元素之间的逻辑关系的描述

只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关

数据的存储结构

数据的逻辑结构在计算机存储空间中的存放形式

常用的存储结构：顺序,链式,索引

一种数据结构可根据需要采用不同的存储结构。采用不同的存储结构，其数据处理的效率是不同

线性结构

如果一个非空数据结构满足下列两个条件：

有且只有一个根结点；

每一个结点最多有一个前件，也最多有一个后件。

常见的线性结构有：线性表、栈与队列、线性链表

非线性结构

-1-

如果一个数据结构不是线性结构

常见的非线性结构有：树、二叉树、图

1.3线性表及其顺序存储结构

线性表的结构特征

数据元素在表中的位置由序号决定，数据元素之间的相对位置是线性的；

对于一个非空线性表，有且只有一个根结点a1，它无前件，有且只有一个终端结点an，它无后件，除根结点

与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

线性表的存储结构

顺序存储,链式存储

两个基本特点：

线性表中所有元素所占的存储空间是连续的。

线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

存储示意图:逻辑地址数据元素物理地址

…

1aLoc(a)

11