没有合适的资源？快使用搜索试试~ 我知道了~

文库首页行业研究行业报告全国计算机等级考试二级公共基础知识考试要点.doc

全国计算机等级考试二级公共基础知识考试要点.doc

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

0 下载量 153 浏览量 2024-12-14 22:06:04 上传评论收藏 97KB DOC 举报

温馨提示

试读

27页

全国计算机等级考试二级公共基础知识考试要点.doc

资源推荐

资源详情

资源评论

全国计算机等级考试二级公共基础知识考试要点

81 / 27

第一章数据结构与算法

1.1 算法

算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有

效的，是明确的，此顺序将在有限的次数下终止。

特征包括：

（1）可行性；

（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解

释，不允许有多义性；

（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后

终止，包括合理的执行时间的含义；

（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯

法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

一般来说，算法的工作量用其执行的基本运算次数来度量，而算法执行的

基本运算次数是问题规模的函数。在同一个问题规模下，用平均性态和最坏情

况复杂性来分析。一般情况下，用最坏情况复杂性来分析算法的时间复杂度。

全国计算机等级考试二级公共基础知识考试要点

82 / 27

算法空间复杂度是指执行这个算法所需要的内存空间。

1.2 数据结构的基本概念

数据结构研究的三个方面：

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

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

存储结构；

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

数据结构是指相互有关联的数据元素的集合。

数据结构是反映数据元素之间关系的数据元素集合的表示。

数据的逻辑结构包含：

（1）表示数据元素的信息；

（2）表示各数据元素之间的前后件关系。（逻辑关系，与在计算机内的存

储位置无关）

一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系

有可能不同。

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

常用的存储结构有顺序、链接、索引等。

根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构

分为线性结构和非线性结构。

线性结构条件：

（1）有且只有一个根结点；

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

全国计算机等级考试二级公共基础知识考试要点

83 / 27

非线性结构：不满足线性结构条件的数据结构。

1．3 线性表及其顺序存储结构

线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素

之间的相对位置是线性的。

如：一个 N 维向量、矩阵

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个

记录构成的线性表又称为文件。

非空线性表的结构特征：

（1）有且只有一个根结点 a1，它无前件；

（2）有且只有一个终端结点，它无后件；

（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只

有一个后件。结点个数 n 称为线性表的长度，当 0 时，称为空表。

线性表的顺序存储结构具有以下两个基本特点：

（1）线性表中所有元素的所占的存储空间是连续的；

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

的存储地址为：()(a1)+(1)k,，(a1)为第一个元素的地址，k 代表每个元素占

的字节数。

顺序表的运算：插入、删除。

1．4 栈和队列

栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈

顶，不允许插入与删除的另一端称为栈底。

栈按照“先进后出”（）或“后进先出”（）组织数据，栈具有记忆作用。

用表示栈顶位置，用表示栈底。

全国计算机等级考试二级公共基础知识考试要点

84 / 27

栈的顺序存储

用一维数组 S（1）作为栈的顺序存储空间，M 为栈的最大容量。S()表示

栈底元素，s()为栈顶元素，0 表示栈空，表示栈满。

栈的基本运算：

（1）插入元素称为入栈运算；（1;将新元素插入到栈顶指针指向的位置）

上溢

（2）删除元素称为退栈运算；（将栈顶指针指向的元素赋给指定的变量，

1）下溢

（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。

队列

队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的

线性表。指针指向队尾，指针指向队头。

队列是“先进先出”（）或“后进后出”（）的线性表。

队列的顺序存储

与栈类似，用一维数组 Q（1：m）作为队列的顺序存储空间

队列运算

（1）入队运算：从队尾插入一个元素；

（2）退队运算：从队头删除一个元素。

循环队列：

在循环队列结构中，当存储空间的最后一个位置已被使用而要进行入队运

算时，只要存储空间的第一个位置空闲，就可将元素加入到第一个位置，即将

存储空间的第一个位置作为队尾。

全国计算机等级考试二级公共基础知识考试要点

85 / 27

从指针指向的后一个位置直到队尾指针指向的位置之间所有的元素均为队

列中的元素。

循环队列的初始状态为空：

当循环队列满时，

为区别队满还是队空，增加标志 S。

0 表示队列空，1 且表示队列满

1．5 线性链表

对于元素变动频繁的大线性表不宜采用顺序存储结构，而应采用链式存储

结构。

在链式存储结构中，数据结构中的每一个结点对应于一个存储单元，这种

存储单元称为存储结点，简称结点。

结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存

放指针，称为指针域，用于指向前一个或后一个结点。

在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的

存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系

是由指针域来确定的。

链式存储方式既可用于表示线性结构，也可用于表示非线性结构。

线性链表，称为头指针，（或 0）称为空表，如果是两指针：左指针（）指

剩余26页未读，继续阅读

评论收藏

内容反馈

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

平头哥在等你

粉丝: 1578
资源: 1万+

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

全国计算机等级考试二级公共基础知识考试要点.doc

计算机二级公共基础知识考试要点.doc

全国计算机等级考试二级公共基础知识要点.doc

全国计算机二级vfp公共基础知识考试要点.doc

Bvfsri计算机等级考试二级公共基础知识(大纲-要点).doc

全国计算机等级考试一级B知识要点.doc

人力资源管理师二级基础知识考试要点归纳.doc

(完整word)通用计算机二级公共基础知识要点.doc

全国计算机二级公共基础知识汇总.doc

全国计算机等级考试二级C语言考试复习资料与复习计划以与考试要点.doc

全国计算机等级考试二级C语言考试复习资料及复习计划以及考试要点.doc

全国计算机等级考试(二级)——C_语言辅导教材(清华大学出版).doc

二级公共基础知识资料大全（2011-07）

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

计算机等级考试二级office知识点总结.doc

2023年全国计算机等级考试二级教程C语言程序设计.doc

全国计算机等级考试二级VB复习资料_考试要点说明.doc

人力资源管理师二级【基础知识】考试要点归纳.doc

计算机等级考试一级复习要点.doc

全国计算机二级vfp考试要点.doc

(完整word版)2017计算机二级公共基础知识完整.doc

全国计算机等级考试二级C语言考前复习资料.doc

2013年3月全国计算机等级考试二级C机试题库.doc

二级公共知识 二级公共知识.rar

二级C语言考试复习五要点.doc

全国计算机等级考试二级C++笔试题.doc

最新全国计算机等级考试三级数据库技术各章节要点总结资料.doc

更多目录以及详细说明（年份、来源、截图等）

相关实用应用程序（Windows可用）

李飞飞自传 我看见的世界 The World I see

ChatGPT使用总结：150个ChatGPT提示词模板（完整版）

最新资源

二级公共知识二级公共知识.rar

李飞飞自传我看见的世界 The World I see