计算机二级公共基础知识总结
数据结构与算法
1.1 算法
算法:是指解题方案的准确而完整的描述。
算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。
算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括:
(1)可行性;
(2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性;
(3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义;
(4)拥有足够的情报。
算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。
指令系统:一个计算机系统能执行的所有指令的集合。
基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构:顺序结构、选择结构、循环结构。
算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度:算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本基本概念
数据结构研究的三个方面:
(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;
(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;
(3)对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含:
(1)表示数据元素的信息;
(2)表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。等等
【【上 学 吧】】 有详细的资料 自己去看看
计算机二级公共基础知识是计算机中综合性知识,占30分。
包含的科目有数据结构,软件工程,算法设计与分析,数据库设计等。而这些科目都属于计算机专业必修课,也是一个程序员的必备理论基础。
我们知道二级的目标定位就是程序员的水平,所以这些科目都是必考内容。 那么如何备考呢?实际上很简单,只要买一本教育部考试中心出版的计算机二级考试公共基础知识大纲级指导书(一定是教育部出版发行的那种),回来抽个时间仔细研读一番就可以了,而且无须做大量练习题,因为二级要求不高,停留在概念的阶段。
复习时,不要将其看的太重,因为大家的水平都差不多,除非计算机专业的。 ========================================== 全国计算机等级考试二级公共基础知识考试大纲 基本要求 1。
掌握算法的基本概念。 2。
掌握基本数据结构及其操作。 3。
掌握基本排序和查找算法。 4。
掌握逐步求精的结构化程序设计方法。 5。
掌握软件工程的基本方法,具有初步应用相关技术进行软件开发的能力。 6。
掌握数据的基本知识,了解关系数据库的设计。 考试内容 一、基本数据结构与算法 1。
算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。 2。
数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。 3。
线性表的定义;线性表的顺序存储结构及其插入与删除运算。 4。
栈和队列的定义;栈和队列的顺序存储结构及其基本运算。 5。
线性单链表、双向链表与循环链表的结构及其基本运算。 6。
树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。 7。
顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序)。 二、程序设计基础 1。
程序设计方法与风格。 2。
结构化程序设计。 3。
面向对象的程序设计方法,对象,方法,属性及继承与多态性。 三、软件工程基础 1。
软件工程基本概念,软件生命周戎概念,软件工具与软件开发环境。 2。
结构化分析方法,数据流图,数据字典,软件需求规格说明书。 3。
结构化设计方法,总体设计与详细设计。 4。
软件测试的方法,白盒测试与黑盒测试,测试用例设计,软件测试的实施,单元测试、集成测试和系统测试。 5。
程序的调试,静态调试与动态调试。 四、数据库设计基础 1。
数据库的基本概念:数据库,数据库管理系统,数据库系统。 2。
数据模型,实体联系模型及E-R图,从E-R图导出关系数据模型。 3。
关系代数运算,包括集合运算及选择、投影、连接运算,数据库规范化理论。 4。
数据库设计方法和步骤:需求分析、概念设计、逻辑设计和物理设计的相关策略。 。
二级公共基础知识考试大纲
基 本 要 求
(1)掌握算法的基本概念。
(2)掌握基本数据结构及其操作。
(3)掌握基本排序和查找算法。
(4)掌握逐步求精的结构化程序设计方法。
(5)掌握软件工程的基本方法,具有初步应用相关技术进行软件开发的能力。
(6)掌握数据库的基本知识,了解关系数据库的设计。
考 试 内 容
1. 基本数据结构与算法
(1)算法的基本概念:算法复杂度的概念和意义(时间复杂度与空间复杂度)。
(2)数据结构的定义:数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。
(3)线性表的定义:线性表的顺序存储结构及其插入与删除运算。
(4)栈和队列的定义:栈和队列的顺序存储结构及其基本运算。
(5)线性单链表、双向链表与循环链表的结构及其基本运算。
(6)树的基本概念:二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。
(7)顺序查找与二分法查找算法:基本排序算法(交换类排序,选择类排序,插入类排序)。
2. 程序设计基础
(1)程序设计方法与风格。
(2)结构化程序设计。
(3)面向对象的程序设计方法,对象,方法,属性及继承与多态性。
3. 软件工程基础
(1)软件工程基本概念,软件生命周期概念,软件工具与软件开发环境。
(2)结构化分析方法,数据流图,数据字典,软件需求规格说明书。
(3)结构化设计方法,总体设计与详细设计。
(4)软件测试的方法,白盒测试与黑盒测试,测试用例设计,软件测试的实施,单元测试、集成测试和系统测试。
(5)程序的调试,静态调试与动态调试。
4. 数据库设计基础
(1)数据库的基本概念:数据库,数据库管理系统,数据库系统。
(2)数据模型:实体联系模型及E-R图,从E-R图导出关系数据模型。
(3)关系代数运算:包括集合运算及选择、投影、连接运算,数据库规范化理论。
(4)数据库设计方法和步骤:需求分析、概念设计、逻辑设计和物理设计的相关策略。
考 试 方 式
(1)公共基础知识的考试方式为笔试,与C语言程序设计(C++语言程序设计、Java语言程序设计、Visual Basic语言程序设计、Visual FoxPro数据库程序设计、Access数据库程序设计或Delphi语言程序设计)的笔试部分合为一张试卷。公共基础知识部分占全卷的30分。
(2)公共基础知识有10道选择题和5道填空题。
试读结束,如需阅读或下载,请点击购买>原发布者:xiaobaizhua2二级公共基础知识总结第一章数据结构与算法1.1算法算法:是指解题方案的准确而完整的描述。
算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。
特征包括:(1)可行性;(2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性;(3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义;(4)拥有足够的情报。算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。
指令系统:一个计算机系统能执行的所有指令的集合。基本运算包括:算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构:顺序结构、选择结构、循环结构。算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度:算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。1.2数据结构的基本基本概念数据结构研究的三个方面:(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构4.3。
二级公共基础知识考试大纲基 本 要 求(1)掌握算法的基本概念。
(2)掌握基本数据结构及其操作。(3)掌握基本排序和查找算法。
(4)掌握逐步求精的结构化程序设计方法。(5)掌握软件工程的基本方法,具有初步应用相关技术进行软件开发的能力。
(6)掌握数据库的基本知识,了解关系数据库的设计。考 试 内 容1. 基本数据结构与算法(1)算法的基本概念:算法复杂度的概念和意义(时间复杂度与空间复杂度)。
(2)数据结构的定义:数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。(3)线性表的定义:线性表的顺序存储结构及其插入与删除运算。
(4)栈和队列的定义:栈和队列的顺序存储结构及其基本运算。(5)线性单链表、双向链表与循环链表的结构及其基本运算。
(6)树的基本概念:二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。(7)顺序查找与二分法查找算法:基本排序算法(交换类排序,选择类排序,插入类排序)。
2. 程序设计基础(1)程序设计方法与风格。(2)结构化程序设计。
(3)面向对象的程序设计方法,对象,方法,属性及继承与多态性。3. 软件工程基础(1)软件工程基本概念,软件生命周期概念,软件工具与软件开发环境。
(2)结构化分析方法,数据流图,数据字典,软件需求规格说明书。(3)结构化设计方法,总体设计与详细设计。
(4)软件测试的方法,白盒测试与黑盒测试,测试用例设计,软件测试的实施,单元测试、集成测试和系统测试。(5)程序的调试,静态调试与动态调试。
4. 数据库设计基础(1)数据库的基本概念:数据库,数据库管理系统,数据库系统。(2)数据模型:实体联系模型及E-R图,从E-R图导出关系数据模型。
(3)关系代数运算:包括集合运算及选择、投影、连接运算,数据库规范化理论。(4)数据库设计方法和步骤:需求分析、概念设计、逻辑设计和物理设计的相关策略。
考 试 方 式(1)公共基础知识的考试方式为笔试,与C语言程序设计(C++语言程序设计、Java语言程序设计、Visual Basic语言程序设计、Visual FoxPro数据库程序设计、Access数据库程序设计或Delphi语言程序设计)的笔试部分合为一张试卷。公共基础知识部分占全卷的30分。
(2)公共基础知识有10道选择题和5道填空题。
为了方便计算机等级试,特意整理出来的。
第一章数据结构与算法1算法是解题方案的准确而完整的描述,它不等于程序,也不等于计算方法。基本特征:可行性、确定性、有穷性、拥有足够的情报。
2算法复杂度主要包括时间复杂度和空间复杂度。时间复杂度:用来衡量算法执行过程中所需要的基本运算次数。
空间复杂度:用来衡量算法执行过程中所需要的存储空间。3数据结构研究的主要内容:(1)数据的逻辑结构(2)数据的存储结构(3)对各种数据结构进行的运算4研究数据结构的主要目的:提高数据处理的效率。
5数据结构的定义:指相互关联的数据元素的集合。6数据的逻辑结构反映数据元素之间的逻辑关系,数据的存储结构是数据的逻辑结构在计算机存储空间的存放形式。
同一种逻辑结构可以采用不同存储结构,但影响数据处理效率。7数据结构分为两大类型:线性结构与非线性结构常见线性结构:线性表、栈、队列、线性链表常用非线性结构:树、二叉树、图8线性表示由n(n>=0)个相同类型的数据元素构成的有限序列。
结构特征:(1)数据元素在表中的位置由序号决定,数据元素之间的相对位置是线性的(2)对于一个非空线性表,有且只有一个根节点a1,它无前件,有且只有一个终端结点an,它无后件,除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。基本存储结构:(1)顺序存储(2)链式存储9顺序表的插入运算时需要移动元素,在等概率情况下,平均需要移动n/2个元素。
10进行顺序表的删除运算时也需要移动元素,在等概率情况下,平均移动(n-1)/2个元素。11栈只能在栈顶插入或删除元素,是一种先进后出FILO(或称为后入先出LIFO)的线性表。
12队列是只能从队尾插入元素,在队头删除元素,是一种先进先出FIFO(或后入后出LILO)的线性表。13线性链表不能随机存取。
14在线性链表中插入元素时,不需要移动数据元素,只需要修改相关结点指针即可,也不会出现“上溢”现象。15在线性链表中删除元素时,也不需要移动数据元素,只需要修改相关结点指针即可。
16循环链表实单链表基础上增加了一个表头结点,其插入和删除运算与单链表相同,可以从任意结点出发来访问表中其他所有结点,并实现空表与非空表的运算。17一般二叉树通常采用链式存储结构,对于满二叉树与完全二叉树来说,可以按层序进行顺序存储。
18二分查找知识用于顺序存储的线性表,对于无序线性表和线性表的链式存储结构只能用顺序查找。19冒泡排序是每一趟都会把较小的元素先前移动,最坏比较次数是n(n-1)/2。
20简单插入排序法是将无序序列中的各元素依次插入到已经有序的线性表中,最坏比较次数为n(n-1)/2。21希尔排序法的基本思想:将无序序列划分成若干个子序列(又相隔某个增量h的元素组成)分别进行直接插入排序,待整个序列中的元素基本有序(增量足够小)时,在对全体元素进行一次直接插入排序。
因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的。22选择排序每一趟都是找出无序序列中的最小一个元素,最坏比较次数为n(n-1)/2。
23排序技术:(1)交换排序法:冒泡排序、快速排序(2)插入排序法:简单插入排序法、希尔排序(3)选择排序法:简单选择排序法、堆排序法。
声明:本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
蜀ICP备2020033479号-4 Copyright © 2016 学习鸟. 页面生成时间:4.349秒