没有合适的资源?快使用搜索试试~ 我知道了~
全国计算机二级公共基础知识汇总.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 106 浏览量
2021-11-24
09:59:10
上传
评论
收藏 240KB PDF 举报
温馨提示
全国计算机二级公共基础知识主要涵盖计算机应用专业的核心课程,如算法及数据结构、程序设计基础、软件工程基础和数据库。在复习策略上,考生应遵循"80/20原则",集中精力掌握20%的重点知识点,以应对80%的考试题目。备考时,考生需准确判断和熟悉常见考点,例如算法的复杂度、数据结构的基本概念、程序设计的基本要求、软件工程的基础知识和数据库的基本概念。 算法是解决问题的精确描述,包括顺序、选择和循环结构。其关键要素是运算和操作以及控制结构。算法的复杂度分为时间复杂度和空间复杂度,分别衡量执行时间和所需内存。数据结构是逻辑和物理存储方式的研究,包括线性和非线性结构。线性表是最简单的数据结构之一,其中数据元素按照线性顺序排列,可以采用顺序存储或链接存储。 数据结构的逻辑结构包含数据元素及其关系,而存储结构则关注如何在内存中表示这些结构。线性结构如链表和数组,非线性结构如树和图。线性表的顺序存储结构是指元素按线性顺序存放在连续的内存单元中,便于直接访问和操作。 复习公共基础知识部分时,考生应重点记忆划线和框选的关键词,因为它们往往是填空题的常见词汇。考试时,对于两分钟内无法解答的题目,建议迅速跳过,确保在简单题目上的得分率。通过反复背诵和理解,考生可以逐步掌握并灵活运用这些基础知识。 在准备二级考试时,考生不必过于追求难题和灵活性,而是要确保对基本概念和原理的扎实掌握。随着对基础知识的深入理解,考生在解决实际问题时自然会变得更加灵活和高效。通过这样的复习方法,考生可以有效地应对全国计算机二级公共基础知识的考试,提高通过率。
资源推荐
资源详情
资源评论
公共基础知识
1
二级公共基础知识总结 (30 分:10 选择 +5 填空 )
复习及应试建议:
1.考生的复习必须遵守: “80/20的原则 ”
二级考试的公共知识部分的覆盖面广,至少涵盖了计算机应用专业的四门核心课程:算
法及数据结构、程序设计基础、软件工程基础和数据库。事实上,这些课程本身的涉及面就
很广,难度系数较大。因此,这些课程甚至也是计算机专业学生最头疼的课程,对大多数考
生来说其难度之大不言而喻。
所以,考生应把 80%的时间用在 20%的重点知识点上,争取用 20%的重点知识点来答对
80%的考题,这是考生复习二级考试的公共知识部分的总体思路。
2.复习的关键是考生必须准确判断和掌握常见考点
考生必须能够准确判断和掌握常见考点,例如:算法部分主要考查算法的概念及算法的
复杂度;数据结构部分主要考查最基本的概念、最典型的数据结构和最常见的操作;程序设
计部分主要考查程序设计风格的基本要求、结构化程序设计的最基本知识和面向对象程序设
计的最常见概念;软件工程基础部分主要考查软件工程的基本概念及软件生命周期的各个阶
段的基础知识;数据库基础部分主要考查数据库基本概念、数据模型、关系代数基础知识、
数据库设计方法和步骤。对常见考点的准确把握会使考生避免盲目学习,从而能够轻松面对
考试。
二级考试中要求的知识点都是最基本的、最简单的,真正需要 “灵活 ”掌握的考点极少。
很多考生在考试过程中可能已经发现,该部分的题目 “会做就是不懂 ”。所以建议在复习过程
中不要急于 “灵活”,其实等到把基本的知识点掌握后自然就 “灵活 ”了。
公共知识部分仅占 30%分,题目相对简单。因此,在答题过程中,这部分要争取速度快、
准确度高。
总的原则是如果一道题在两分钟内没有任何思路,就应该跳过此题,把时间给后面的题
目。记住:二级考试是一种合格考试,不是竞赛,及格就行了。
使用说明:
公共基础的复习没有技巧,就是背诵、背诵、再背诵, 就是要把这 10 页纸背下来。
划线字体是至关重要的部分,框起来的字体为填空题的常考词汇,一定要背熟牢记,这里面
有 100 分里 30 分的原题。
第一章 数据结构与算法
1.1 算法
算法 :是一组有穷指令集, 是解题方案的准确而完整的描述。 通俗地说,算法就是计算机解
题的过程。算法不等于程序,也不等于计算方法,程序的编制不可能优于算法的设计。
算法是一组严谨地定义运算顺序的规则,每一个规则都是有效的,且是明确的,此顺序将在
有限的次数下终止。所以其四个基本特征包括:
(1 )确定性,算法中每一步骤都必须有明确定义, 不允许有模棱两可的解释, 不允许有多义
性;
(2 )有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止;
公共基础知识
2
(3 )可行性,算法原则上能够精确地执行;
(4 )拥有足够的情报。
算法的基本要素 :一是 对数据对象的运算和操作 ;二是 算法的控制结构 。
指令系统:一个计算机系统能执行的所有指令的集合。
基本运算和操作包括: 算术运算、逻辑运算、关系运算、数据传输 。
算法的三种基本控制结构 :顺序结构、选择结构、循环结构 。
算法基本设计方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。
算法效率的度量— 算法复杂度 :算法时间复杂度 和 算法空间复杂度 。
算法时间复杂度:指执行算法所需要的计算工作量。 即算法执行过程中所需要的基本运算次
数。通常,一个算法所用的时间包括编译时间和运行时间。
算法空间复杂度:指执行这个算法所需要的内存空间。 包括算法程序所占的空间,输入的初
始数据所占的空间,算法执行过程中所需的额外空间。
1.2 数据结构的基本概念
数据结构:指相互有关联的数据元素的集合。
数据结构研究的三个方面:
(1 )数据集合中各数据元素之间所固有的逻辑关系,即 数据的逻辑结构 ;
(2 )在对数据进行处理时,各数据元素在计算机中的存储关系,即 数据的存储结构 ;
(3 )对各种数据结构进行的运算。
数据的逻辑结构应包含:
(1 )表示数据元素的信息;
(2 )表示各数据元素之间的前后件关系 (指逻辑关系,与存储位置无关 ) 。
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构 ,也称数据物理结构。
数据的存储结构有顺序、链接、索引等。
线性结构的条件, ( 一个非空数据结构 ) :
(1 )有且只有一个根结点 ; (2 )每一个结点最多有一个前件,也最多有一个后件 。
非线性结构:不满足线性结构条件的数据结构。
1.3 线性表及其顺序存储结构
线性表 是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置
是线性的。
在复杂线性表中,由若干项数据元素组成的数据元素称为 记录 ;
由多个记录构成的线性表称为 文件 。
非空线性表的结构特征:
(1 )且只有一个根结点 a1 ,它无前件;
(2 )有且只有一个终端结点 an ,它无后件;
(3 )除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。
结点个数 n 称为 线性表的长度 ,当 n=0 时,称为 空表 。
公共基础知识
3
线性表的顺序存储结构具有以下两个基本特点:
(1)线性表中所有元素所占的存储空间是连续的;
(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
元素 ai 的存储地址为: ADR(ai)=ADR(a1)+(i-1)k ,
ADR(a1) 为第一个元素的地址, k 代表每个元素占的字节数。
顺序表的运算:查找、插入、删除。
1.4 线性链表
数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称 结点 。
结点由两部分组成: (1) 用于存储数据元素值,称为 数据域 ;
(2) 用于存放指针,称为 指针域 ,用于指向前一个或后一个结点。
在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点
的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域
来确定的。
链式存储方式即可用于表示线性结构,也可用于表示非线性结构。
线性单链表中, HEAD 称为头指针, HEAD=NULL (或 0 )称为 空表。
如果是双项链表的两指针: 左指针 (Llink )指向前件结点, 右指针 (Rlink )指向后件结点。
线性链表的基本运算:查找、插入、删除。
1.5 栈和队列
栈:限定在一端进行插入与删除的线性表。
其允许插入与删除的一端称为栈顶, 用指针 top 表示栈顶位置。
不允许插入与删除的另一端称为栈底 ,用指针 bottom 表示栈底。
栈按照 “先进后出 ”(FILO )或 “后进先出 ”(LIFO )组织数据,栈具有记忆作用。
栈的存储方式有顺序存储和链式存储。
栈的基本运算: (1) 入栈运算,在栈顶位置插入元素;
(2) 退栈运算,删除元素 ( 取出栈顶元素并赋给一个指定的变量 ) ;
(3) 读栈顶元素,将栈顶元素赋给一个指定的变量,此时指针无变化。
队列 :指允许在一端(队尾)进入插入,而在另一端(队头)进行
删除的线性表。
用 rear 指针指向队尾,用 front 指针指向队头元素的前一个位置。
队列是 “先进先出 ”(FIFO )或 “后进后出 ”(LILO )的线性表。
队列运算包括: (1) 入队运算:从队尾插入一个元素; (2) 退队运算:从队头删除一个元
素。
队列的顺序存储结构一般采用队列循环的形式。
循环队列 s=0 表示队列空; s=1 且 front=rear 表示队列满。
公共基础知识
4
计算循环队列的元素个数: “尾指针减头指针”,若为负数,再加其容量即可。
1.6 树与二叉树
树是一种简单的非线性结构 ,其所有元素之间具有明显的层次特性。
在树结构中,每一个结点只有一个前件,称为父结点。
没有前件的结点只有一个,称为 树的根结点 ,简称树的根。
每一个结点可以有多个后件,称为该结点的 子结点 。没有后件的结点称为叶子结点。
在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的
度。树的最大层次称为树的深度。
二叉树 的特点 :(1) 非空二叉树只有一个根结点;
(2) 每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
满二叉树 是指除最后一层外,每一层上的所有结点有两个子结点,则 k 层上有 2
k-1
个结点深
度为 m 的满二叉树有 2
m
-1 个结点。
完全二叉树 是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边
的若干结点。
二叉树基本性质:
(1) 在二叉树的第 k 层上,最多有 2
k-1
(k ≥1) 个结点;
(2) 深度为 m 的二叉树最多有 2
m
-1 个结点;
(3) 度为 0 的结点(即叶子结点)总是比度为 2 的结点多一个;
(4) 具有 n 个结点的二叉树, 其深度至少为 [log
2
n]+1, 其中[log
2
n] 表示取 log
2
n 的整数部分
(5) 具有 n 个结点的完全二叉树的深度为 [log
2
n]+1 ;
(6) 设完全二叉树共有 n 个结点。如果从根结点开始,按层序(每一层从左到右)用自然数
1,2, …n 给结点进行编号( k=1,2 … .n),有以下结论:
①若 k=1 ,则该结点为根结点,它没有父结点;若 k>1 ,则该结点的父结
点编号为 INT(k/2) ;
②若 2k ≤n ,则 k 结点的左子结点编号为 2k ;否则该结点无左子结点 (也
无右子结点);
③若 2k+1 ≤n ,则编号为 k 的结点的右子结点编号为 2k+1 ;否则该结点
无右子结点。
补充:增加度为 1 的结点不会影响二叉树的叶子结点数, 每增加一个度为 2 的结点便会增加
一个叶子结点,没有度为 2 的结点时叶子结点数为 1 。
已知完全二叉树有 x 个结点,求其叶子结点数:
①确定层数为 k ; ②第 k 层的结点数 y=x-(2
k-1
-1) ;
③第 k-1 层的叶子结点数 n=2
(k-1)-1
-y/2< 若 y/2 有余,则要加 1> ; ④最后 y+n 。
二叉树存储结构采用 链式存储结构 ,对于满二叉树与完全二叉树可以按层序进行顺序存储。
二叉树的遍历:
(1 )前序遍历 (DLR),首先访问根结点,然后遍历左子树,最后遍历右子树;
(树根在第一,下走不跳结点)
(2) 中序遍历 (LDR ),首先遍历左子树,然后访问根结点,最后遍历右子树;
剩余16页未读,继续阅读
资源评论
fuhongy
- 粉丝: 0
- 资源: 4万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- ExcUserFault_ScreenshotServicesService-2024-10-24-083756.ips
- 物业服务收费通知书.pdf.download
- 基于51单片机的公交报站系统仿真设计
- War of Plane(飞机大战)(Python Pygame制作)
- ELK-相关笔记内容-自己使用
- Scheme例子.js
- 配备Gen AI优化软件开发:企业利用生成式人工智能提升软件工程技术的应用与前景
- 首席安全官视角下的生成式人工智能对网络安全的影响
- chatbot_open_api.postman_collection.json
- LIP8n0ettnbQjXVELUmLx-T2iMXF8oZPcwgD2248WJWNm0X6QYEQ_3kgq7r28WxC
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功