没有合适的资源?快使用搜索试试~ 我知道了~
全国计算机等级考试二级公共基础知识教程.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
5星 · 超过95%的资源 4 下载量 154 浏览量
2021-11-14
23:01:18
上传
评论 5
收藏 737KB PDF 举报
温馨提示
试读
48页
全国计算机等级考试二级公共基础知识教程
资源推荐
资源详情
资源评论
全国计算机等级考试二级公共基础知识考纲
考试内容
一、 基本数据结构与算法
1. 算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度) 。
2. 数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与
非线性结构的概念。
3. 线性表的定义;线性表的顺序存储结构及其插入与删除运算。
4. 栈和队列的定义;栈和队列的顺序存储结构及其基本运算。
5. 线性单链表、双向链表与循环链表的结构及其基本运算。
6. 树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。
7. 顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排
序)。
二、 程序设计基础
1. 程序设计方法与风格。
2. 结构化程序设计。
3. 面向对象的程序设计方法,对象,方法,属性及继承与多态性。
三、 软件工程基础
1. 软件工程基本概念,软件生命周戎概念,软件工具与软件开发环境。
2. 结构化分析方法,数据流图,数据字典,软件需求规格说明书。
3. 结构化设计方法,总体设计与详细设计。
4. 软件测试的方法,白盒测试与黑盒测试,测试用例设计,软件测试的实施,单元测
试、集成测试和系统测试。
5. 程序的调试,静态调试与动态调试。
四、 数据库设计基础
1. 数据库的基本概念:数据库,数据库管理系统,数据库系统。
2. 数据模型,实体联系模型及 E-R 图,从 E-R 图导出关系数据模型。
3. 关系代数运算,包括集合运算及选择、投影、连接运算,数据库规范化理论。
4. 数据库设计方法和步骤:需求分析、概念设计、逻辑设计和物理设计的相关策略。
考试方式
公共基础的考试方式为笔试, 与 C 语言(VisualBASIC 、Visual FoxPro 、Java、Access、
Visual C++)的笔试部分合为一张试卷。公共基础部分占全卷的 30 分。公共基础
知识有 10 道选择题和 5 道填空题。
第一章 数据结构与算法
一、内容要点
(一)算法
1.算法的基本概念
算法是指解题方案的准确而完整的描述。 即是一组严谨地定义运算顺序的规则, 并且每
一个规则都是有效的,且是明确的,没有二义性,同时该规则将在有限次运算后可终止。
1)算法的基本特征
(1)可行性
由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的, 因
此,它总是受到计算工具的限制,使执行产生偏差。
如:计算机的数值有效位是有限的, 当大数和小数进行运算时, 往往会因为有效位数的
影响而使小数丢失,因此,在算法设计时,应该考虑到这一点。
(2)确定性
算法的设计必须是每一个步骤都有明确的定义, 不允许有模糊的解释, 也不能有多义性。
例如,一个实际的问题,小宝和萍萍共有 12 个苹果,小宝比萍萍多 4 个,请问小宝和
萍萍各有几个苹果?这个问题,我们可以立一个方程
4
12
yx
yx
来求解,要求 x 和 y
的值, 公式是正确的,但如何让计算能够进行计算,我们的算法不能把公式直接输进去,而
应该设计出解题的步骤和过程。
即设计的算法是计算工具所能够正常解决问题的过程。
(3)有穷性
算法的有穷性, 即在一定的时间是能够完成的, 即算法应该在计算有限个步骤后能够正
常结束。
例如,在数学中的无穷级数,在计算机中只能求有限项,即计算的过程是有穷的。
(4)拥有足够的情报
算法的执行与输入的数据和提供的初始条件相关, 不同的输入或初始条件会有不同的输
出结果,提供准确的初始条件和数据,才能使算法正确执行。
2)算法的基本要素
一是数据对象的运算和操作,二是算法的控制结构。
(1)算法中对数据的运算和操作
算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指
令序列。即算法是计算机所能够处理的操作所组成的指令序列。
(2)算法的控制结构
算法的功能不仅取决于所选用的操作,而且还与各操作之间的顺序有关。
在算法中, 操作的执行顺序又称算法的控制结构, 一般的算法控制结构有三种: 顺序结
构、选择结构和循环结构。
在算法描述是, 有相关的工具对这三种结构进行描述, 常用的描述工具有: 流程图、 N-S
结构图和算法描述语言等。
3)算法设计的基本方法
为用计算机解决实际问题而设计的算法,即是计算机算法。
通常的算法设计有如下几种:
(1)列举法(如:假定 for x=1,y=1 2,3 …)
列举法的基本思想是, 根据提出的问题, 列举出所有可能的情况, 并用问题中给定的条
件检验哪些是满足条件的,哪些是不满足条件的。列举法通常用于解决“是否存在”或“有
哪些可能”等问题。
例如,我国古代的趣味数学题: “百钱买百鸡” 、“鸡兔同笼”等,均可采用列举法进行
解决。
使用列举法时, 要对问题进行详细的分析,将与问题有关的知识条理化、完备化、 系统
化,从中找出规律。
(2)归纳法 (Un=Un-1+Un-2, ”天下乌鸦一般黑,如果有只白的?” )
归纳法的基本思想是,通过列举少量的特殊情况, 经过分析, 最后找出一般的关系。归
纳是一种抽象, 即从特殊现象中找出一般规律。 但由于在归纳法中不可能对所有的情况进行
列举,因此,该方法得到的结论只是一种猜测,还需要进行证明。
(3)递推 N!=1*2* …*N
递推, 即是从已知的初始条件出发, 逐次推出所要求的各个中间环节和最后结果。 其中
初始条件或问题本身已经给定,或是通过对问题的分析与化简而确定。
递推的本质也是一种归纳,递推关系式通常是归纳的结果。
例如,裴波那契数列,是采用递推的方法解决问题的。
(4)递归 N!=N*(N-1)!
在解决一些复杂问题时, 为了降低问题的复杂程序, 通常是将问题逐层分解, 最后归结
为一些最简单的问题。 这种将问题逐层分解的过程, 并没有对问题进行求解, 而只是当解决
了最后的问题那些最简单的问题后, 再沿着原来分解的逆过程逐步进行综合, 这就是递归的
方法。
递归分为直接递归和间接递归两种方法。 如果一个算法直接调用自己, 称为直接递归调
用;如果一个算法 A 调用另一个算法 B,而算法 B 又调用算法 A,则此种递归称为间接递归
调用。
(5)减半递推技术 ( 二分法求方程根 )
减半递推即将问题的规模减半,然后,重复相同的递推操作。
例如,一元二次方程的求解。
(6)回溯法
有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤, 也不能使用无限的
列举。对于这类问题,只能采用试探的方法,通过对问题的分析,找出解决问题的线索,然
后沿着这个线索进行试探,如果试探成功,就得到问题的解,如果不成功,再逐步回退,换
别的路线进行试探。这种方法,即称为回溯法。
如人工智能中的机器人下棋。
2.算法复杂度
算法的复杂度包括时间复杂度和空间复杂度。
1)时间复杂度
即实现该算法需要的计算工作量。算法的工作量用算法所执行的基本运算次数来计算。
同一个问题规模下, 如果算法执行所需要的基本次数取决于某一特定输入时, 可以用以
下两种方法来分析算法的工作量:
算法工作量 =f(n)
(1)平均性态
用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
设 x 是某个可能输入中的某个特定输入, p(x) 是 x 出现的概率, t(x) 是算法在输入为 x
时所执行的基本运算次数,则算法的平均性态定义为:
n
Dx
xtxpnA )()()(
D
n
表示当规模为 n 时,
算法执行时所有可能输入
的集合。
(2)最坏情况复杂度
指在规模为 n 时,算法所执行的基本运算的最大次数。它定义为:
)}({max)( xtnW
n
Dx
例如,在具有 n 个元素的数列中搜索一个数 x。
平均性态: nq
qn
nqi
n
q
tpnA
n
i
i
n
i
i
)1(
2
)1(
)1()(
1
1
1
即该数在数列中任何位置出现的数列是相同的,也有可能不存在,存在的概率为 q。
如果有一半的机会存在,则概率 q 为 1/2 ,平均性态:
nn
n
nA
4
3
)
2
1
1(
2
2
1
)1(
)(
如果查找的元素一定在数列中,则每个数存在的概率即为 1 ,则平均性态为:
22
1
)(
nn
nA
最坏情况分析: 即要查找的元素 X 在数列的最后或不在数列中, 显然, 它的最坏情况复
杂度为:
nnitnW
i
}11|max{)(
2)算法的空间复杂度
指要执行该算法所需要的内存空间。算法所占用的内存空间包括算法程序所占的空间、
输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间, 如执行过程中工作
单元以及某种数据结构所需要的附加存储空间等。
(二)数据结构的基本概念
1.概念
数据结构是指相互有关联的数据元素的集合。它包括以下两个方面:
表示数据元素的信息
表示各数据之间的前后件关系
1)数据的逻辑结构
是指反映数据元素之间的逻辑关系的数据结构。
数据的逻辑结构有两个要素:
数据元素的集合,记作 D
数据之间的前后件关系,记作 R
则数据结构 B=(D, R)
2)数据的存储结构
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构, 或数据的物理结
构。
即数据存储时, 不仅要存放数据元素的信息, 而且要存储数据元素之间的前后件关系的
信息。
通常的数据存储结构有顺序、链接、索引等存储结构。
2.数据结构的图形表示
数据结构的图形表示有两个元素:
中间标有元素值的方框表示数据元素,称为数据结点
用有向线段表示数据元素之间的前后件关系, 即有向线段从前件结点指向后件结点
注意: 在结构图中, 没有前件的结点称为根结点, 没有后件的结点称为终端结点, 也称
叶子结点。
3.线性结构与非线性结构
如果一个数据元素都没有, 该数据结构称为空数据结构; 在空数据结构中插入一个新的
元素后数据结构变为非空数据结构; 将数据结构中的所有元素均删除, 则该数据结构变成空
数据结构。
如果一个非空的数据结构满足如下条件,则该数据结构为线性结构:
有且只有一个根结点
每一个结点最多只有一个前件,也最多只有一个后件
线性结构又称线性表。
注意:在线性结构表中插入或删除元素,该线性表仍然应满足线性结构。
如果一个数据结构不满足线性结构,则称为非线性结构。
(三)线性表及其顺序存储结构
1.基本概念
线性表是最常用的数据结构,它由一组数据元素组成。
注意:这里的数据元素是一个广义的数据元素,并不仅仅是指一个数据。如,矩阵、学
剩余47页未读,继续阅读
资源评论
- ZUTIA2022-07-03这个资源总结的也太全面了吧,内容详实,对我帮助很大。
- SilverGeneral2023-04-01资源使用价值高,内容详实,给了我很多新想法,感谢大佬分享~
- Beatriceeeee_2022-01-22用户下载后在一定时间内未进行评价,系统默认好评。
- ahhhhqianqian2022-07-21这个资源内容超赞,对我来说很有价值,很实用,感谢大佬分享~
春哥111
- 粉丝: 1w+
- 资源: 5万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功