全国计算机二级公共基础知识汇总.docx
- 文档编号:9155244
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:52
- 大小:155.85KB
全国计算机二级公共基础知识汇总.docx
《全国计算机二级公共基础知识汇总.docx》由会员分享,可在线阅读,更多相关《全国计算机二级公共基础知识汇总.docx(52页珍藏版)》请在冰点文库上搜索。
全国计算机二级公共基础知识汇总
公共基础知识
二级公共基础知识总结(30分:
10选择+5填空)
复习及应试建议:
1.考生的复习必定遵守:
“80/20的原则”
二级考试的公共知识部分的覆盖面广,最少涵盖了计算机应用专业的四门中心课程:
算法及数据构造、程序设计基础、软件工程基础和数据库。
事实上,这些课程自己的涉及面就很广,难度系数较大。
因此,这些课程甚至也是计算机专业学生最头疼的课程,对大多数考生来说其难度之大不言而喻。
因此,考生应把80%的时间用在20%的重点知识点上,争取用20%的重点知识点来答对80%的考题,这是考生复习二级考试的公共知识部分的整体思路。
2.复习的重点是考生必定正确判断和掌握常有考点
考生必定能够正确判断和掌握常有考点,比方:
算法部分主要观察算法的见解及算法的复杂度;数据构造部分主要观察
最基本的见解、最典型的数据构造和最常有的操作;程序设计部分主要观察程序设计风格的基本要求、构造化程序设计的最
基本知识和面向对象程序设计的最常有见解;软件工程基础部分主要观察软件工程的基本见解及软件生命周期的各个阶段的基础知识;数据库基础部分主要观察数据库基本见解、数据模型、关系代数基础知识、数据库设计方法和步骤。
对常有考点
的正确掌握会使考生防范盲目学习,从而能够轻松面对考试。
二级考试中要求的知识点都是最基本的、最简单的,真切需要“灵便”掌握的考点极少。
很多考生在考试过程中可能已经
发现,该部分的题目“会做就是不懂”。
因此建议在复习过程中不要急于“灵便”,其实等到把基本的知识点掌握后自然就“灵
活”了。
公共知识部分仅占30%分,题目相对简单。
因此,在答题过程中,这部分要争取速度快、正确度高。
总的原则是若是一道题在两分钟内没有任何思路,就应该跳过此题,把时间给后边的题目。
记住:
二级考试是一种合格
考试,不是竞赛,及格就行了。
使用说明:
公共基础的复习没有技巧,就是背诵、背诵、再背诵,就是要把这10页纸背下来。
划线字体是至关重要的部分,框起
来的字体为填空题的常考词汇,必然要背熟牢记,这里面有100分里30分的原题。
第一章数据构造与算法
1.1算法
算法:
是一组有穷指令集,是解题方案的正确而完满的描述。
平时地说,算法就是计算机解题的过程。
算法不等于程序,也不等于计算方法,程序的编制不能能优于算法的设计。
算法是一组慎重地定义运算次序的规则,每一个规则都是有效的,且是明确的,此次序将在有限的次数下停止。
因此其四个基本特点包括:
(1)确定性,算法中每一步骤都必定有明确定义,不同样意有模棱两可的讲解,不同样意有多义性;
(2)有穷性,算法必定能在有限的时间内做完,即能在执行有限个步骤后停止;
(3)可行性,算法原则上能够精确地执行;
(4)拥有足够的情报。
算法的基本要素:
一是对数据对象的运算和操作;二是算法的控制构造。
指令系统:
一个计算机系统能执行的全部指令的会集。
基本运算和操作包括:
算术运算、逻辑运算、关系运算、数据传输。
算法的三种基本控制构造:
次序构造、选择构造、循环构造。
算法基本设计方法:
列举法、概括法、递推、递归、减半递推技术、回溯法。
算法效率的胸襟—算法复杂度:
算法时间复杂度和算法空间复杂度。
算法时间复杂度:
指执行算法所需要的计算工作量。
即算法执行过程中所需要的基本运算次数。
平时,一个算法所用的时间
包括编译时间和运行时间。
算法空间复杂度:
指执行这个算法所需要的内存空间。
包括算法程序所占的空间,输入的初始数据所占的空间,算法执行过
程中所需的额外空间。
1
公共基础知识
1.2数据构造的基本见解
数据构造:
指相互相关系的数据元素的会集。
数据构造研究的三个方面:
(1)数据会集中各数据元素之间所固有的逻辑关系,即数据的逻辑构造;
(2)在对数据进行办理时,各数据元素在计算机中的储藏关系,即数据的储藏构造;
(3)对各种数据构造进行的运算。
数据的逻辑构造应包括:
(1)表示数据元素的信息;
(2)表示各数据元素之间的前后件关系(指逻辑关系,与储藏地址没关)。
数据的逻辑构造在计算机储藏空间中的存放形式称为数据的储藏构造,也称数据物理构造。
数据的储藏构造有次序、链接、索引等。
线性构造的条件,(一个非空数据构造):
(1)有且只有一个根结点;
(2)每一个结点最多有一个前件,也最多有一个后件。
非线性构造:
不满足线性构造条件的数据构造。
1.3线性表及其次序储藏构造
线性表是由一组数据元素组成,数据元素的地址只取决于自己的序号,元素之间的相对地址是线性的。
在复杂线性表中,由若干项数据元素组成的数据元素称为记录;
由多个记录组成的线性表称为文件。
非空线性表的构造特点:
(1)且只有一个根结点a1,它无前件;
(2)有且只有一个终端结点an,它无后件;
(3)除根结点与终端结点外,其他全部结点有且只有一个前件,也有且只有一个后件。
结点个数n称为线性表的长度,当n=0时,称为空表。
线性表的次序储藏构造拥有以下两个基本特点:
(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
公共基础知识
(2)退栈运算,删除元素(取出栈顶元素并赋给一个指定的变量);
(3)读栈顶元素,将栈顶元素赋给一个指定的变量,此时指针无变化。
队列:
指赞同在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。
用rear指针指向队尾,用front指针指向队头元素的前一个地址。
队列是“先进先出”(FIFO)或“后进后出”(LILO)的线性表。
队列运算包括:
(1)入队运算:
从队尾插入一个元素;
(2)退队运算:
从队头删除一个元素。
队列的次序储藏构造一般采用队列循环的形式。
循环队列s=0表示队列空;s=1且front=rear表示队列满。
计算循环队列的元素个数:
“尾指针减头指针”,若为负数,再加其容量即可。
1.6树与二叉树
树是一种简单的非线性构造,其全部元素之间拥有明显的层次特点。
在树构造中,每一个结点只有一个前件,称为父结点。
没有前件的结点只有一个,称为树的根结点,简称树的根。
每一个结点能够有多个后件,称为该结点的子结点。
没有后件的结点称为叶子结点。
在树构造中,一个结点所拥有的后件的个数称为该结点的度,全部结点中最大的度称为树的度。
树的最大层次称为树的深度。
二叉树的特点:
(1)非空二叉树只有一个根结点;
(2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
满二叉树是指除最后一层外,每一层上的全部结点有两个子结点,则k层上有2k-1个结点深度为m的满二叉树有2m-1个
结点。
完满二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。
二叉树基本性质:
(1)在二叉树的第k层上,最多有2k-1(k≥1)个结点;
(2)深度为m的二叉树最多有2m-1个结点;
(3)
度为0
的结点(即叶子结点)总是比度为
2的结点多一个;
(4)
拥有n
个结点的二叉树,其深度最少为
[log2n]+1,其中[log
2n]表示取log2n的整数部分
(5)
拥有n个结点的完满二叉树的深度为
[log2n]+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-(2k-1
-1);
③第k-1层的叶子结点数n=2
(k-1)-1
-y/2<
若y/2
有余,则要加
1>
;④最后y+n。
二叉树储藏构造采用链式储藏构造,关于满二叉树与完满二叉树能够按层序进行次序储藏。
二叉树的遍历:
(1)前序遍历(DLR),第一接见根结点,尔后遍历左子树,最后遍历右子树;(树根在第一,下走不跳结点)
(2)中序遍历(LDR),第一遍历左子树,尔后接见根结点,最后遍历右子树;(有左先左,再寻根,后找右。
最左边的结点最先遍历,最右边的结点最后遍历)
(3)后序遍历(LRD)第一遍历左子树,尔后接见遍历右子树,最后接见根结点。
(有左先左,再找右,后寻根,到最右一路上行,树根在最后)
3
公共基础知识
前序遍历结果为abdehicfg;中序遍历结果为dbheiafcg;后序遍历结果为dhiebfgca
例2:
先序遍历图1.13的二叉树。
图1.13
先接见整棵二叉树的根结点A,尔后再先序遍历左子树T1;在接见T1时,也以先序遍历原则,先接见T1的根结点B,尔后再先序遍历T1的左子树T11;在接见T11时,也以先序遍历原则,先接见T11的根结点D,尔后再先序遍历T11的左
子树。
由于此时T11的左子树只有H结点,因此接见H结点,T11的左子树先序遍历结束,依照先序遍历的原则,进行先
序遍历T11的右子树。
由于T11的右子树只有I结点,故接见此结点后T11的右子树的先序遍历结束。
先序遍历完T11子
树后,返回T1子树,先序遍历T1的右子树。
先序遍历完T1子树后,接着先序遍历根结点A的右子树T2。
先序遍历完T2
后,该二叉树的全部结点都已经接见过,各结点被接见的次序为:
ABDHIECFG
1)中序遍历:
先中序遍历左子树,尔后再接见根结点,最后再中序遍历右子树。
对图1.12的二叉树进行中序遍历,接见各个结点的
次序为:
HDIBEAFCG
2)后序遍历:
先后序遍历左子树,尔后再后序遍历右子树,最后再接见根结点。
对图1.12的二叉树进行后序遍历,接见各个结点的
次序为:
HIDEBFGCA。
下面树的先序、中序、后续遍历的结果依次为__abdcef_、bdaecf_、_dbefca
a
c
b
ef
d
4
公共基础知识
6、一棵二叉树以下列图,它的中序遍历的结果为(B)
A、abdgcefhB、dgbaechfC、gdbehfcaD、abcdefgh
a
bc
f
de
g
小结:
逻辑构造可分为线性表和非线性表。
h
线性表包括栈、队列,其储藏方式为次序储藏、链式储藏均可。
链式型有:
线性链表,带链的栈,带链的队列,循环链表等。
非线性表包括树(二叉树),其储藏方式为链式储藏。
1.7查找技术
只能使用次序查找的两种情况:
(1)线性表为无序表,无论是次序储藏还是链式储藏;
(2)表采用链式储藏构造,即即是有序线性表。
二分法查找只适用于次序储藏的有序表,关于长度为n的有序线性表,最坏情况只需比较log2n次,而次序查找需要
比较n次。
1.8排序技术
排序是指将一个无序序列整理成按值非递减次序排列的有序序列。
交换类排序法:
(1)冒泡排序法,需要比较的次数为n(n-1)/2;
(2)快速排序法。
插入类排序法:
(1)简单插入排序法,最坏情况需要n(n-1)/2次比较;
(2)希尔排序法,最坏情况需要O(n1.5)次比较。
选择类排序法:
(1)简单项选择择排序法,最坏情况需要n(n-1)/2次比较;
(2)堆排序法,最坏情况需要O(nlog2n)次比较。
对照以上几种(除希尔排序法外),堆排序法的时间复杂度最小。
第二章程序设计基础
2.1程序设计设计方法细风格
“清楚第一、效率第二”已成为现在主导的程序设计风格。
形成优秀的程序设计风格需注意:
(详见书P27)
1、源程序言档化;2、数听闻明的方法;3、语句的构造;4、输入和输出。
说明分序言性说明和功能性说明。
语句构造清楚第一、效率第二。
5
公共基础知识
2.2构造化程序设计
构造化程序设计方法的四条原则是:
1、自顶向下;2、渐渐求精;3、模块化;4、构造化编码限制使用goto语句。
(1)自顶向下。
程序设计时,应先考虑整体,后考虑细节;先考虑全局目标,后考虑局部目标。
不要一开始就过多追求众多的细节,先从最上层总目标开始设计,渐渐使问题详细化。
(2)渐渐求精。
对复杂问题,应设计一些子目标作过渡,渐渐细化。
(3)模块化。
一个复杂问题,必然是由若干稍简单的问题组成。
模块化是把程序要解决的总目标分解为分目标,再进一步分解为详细的小目标,把每个小目标称为一个模块。
(4)限制使用goto语句。
构造化程序的基本构造及特点:
(1)次序构造:
一种简单的程序设计,最基本、最常用的构造;
(2)选择构造:
又称分支构造,包括简单项选择择和多分支选择构造,可依照条件,判断应该
选择哪一条分支来执行相应的语句序列;
(3)循环构造:
又称重复构造,可依照给定条件,判断可否需要重复执行某一同样或近似的程序段。
构造化程序设计的特点:
只有一个入口和出口
2.3面向对象的程序设计
面向对象的程序设计的首次提出以60年月末挪威奥斯陆大学和挪威计算机中心研制的SIMULA语言为标志。
面向对象方法的优点:
(1)与人类习惯的思想方法一致;
(2)牢固性好;(3)可重用性好;(4)易于开发大型软件产品;(5)可保护性好。
对象是面向对象方法中最基本的见解,能够用来表示客观世界中的任何实体,对象是实体的抽象。
面向对象的程序设计方法中,对象是由数据的赞同的操作组成的封装体,是系统中用来描述客观事物的一个实体,是组成系
统的一个基本单位,由一组表示其静态特点的属性和它可执行的一组操作组成。
属性即对象所包括的信息,它在设计对象时确定,一般只能经过执行对象的操作来改变。
操作描述了对象执行的功能,是对象的动向属性,操作也称为方法或服务。
对象的基本特点:
(1)表记独一性。
指对象是可划分的,而且由对象的内在实质来划分,而不是经过描述来划分。
(2)分类性。
指能够将拥有同样属性的操作的对象抽象成类。
(3)多态性。
指同一个操作能够是不同样对象的行为。
(4)封装性。
从外面看只漂亮到对象的外面特点,即只需知道数据的取值范围和能够对该数据施加的操作,根本无需知道
数据的详细构造以及实现操作的算法。
对象的内部,即办理能力的推行和内部状态,对外是不能见的。
从外面不能够直接使用对象的办理能力,也不能够直接改正其内部状态,对象的内部状态只能由其自己改变。
*:
信息隐蔽是经过对象的封装性来实现的。
(5)模块独立性好。
对象是面向对象的软件的基本模块,它是由数据及能够对这些数据施加的操作所组成的一致体,而且
对象是以数据为中心的,操作围绕对其数据所需做的办理来设置,没有没关的操作。
从模块的独立性考虑,对象内部各种元素相互结合得很亲密,内聚性强。
类是指拥有共同属性、共同方法的对象的会集。
类是关于对象性质的描述。
类是对象的抽象,对象是其对应类的一个实例。
信息是一个实例与另一个实例之间传达的信息。
对象间的通信靠信息传达。
它央求对象执行某一办理或回答某一要求的信息,它一致了数据流和控制流。
信息的组成包括:
(1)接收信息的对象的名称;
(2)信息表记符,也称信息名;(3)零个或多个参数。
继承是使用已有的类定义作为基础成立新类的定义技术,广义指能够直接获取已有的性质和特点,而不用重复定义他们。
继承拥有传达性,一个类实质上继承了他上层的全部基类的特点。
继承分单继承和多重继承。
单继承指一个类只赞同有一个父类,即类等级为树形构造;多重继承指一个类赞同有多个父类。
多态性是指同样的信息被不同样的对象接受时可以致完满不同样的行动的现象
6
公共基础知识
第三章软件工程基础
3.1软件工程基本见解
计算机软件是包括程序、数据及相关文档的完满会集。
软件的特点包括:
(1)软件是一种逻辑实体,拥有抽象性;
(2)软件的生产与硬件不同样,它没有明显的制作过程;
(3)软件在运行、使用期间不存在磨损、老化问题;
(4)软件的开发、运行对计算机系统拥有依赖性,受计算机系统的限制,这以致了软件移植的问题;
(5)软件复杂性高,成本昂贵;
(6)软件开发涉及诸多的社会要素。
软件按功能分为应用软件、系统软件、支撑软件(或工具软件)。
软件危机主要表现在成本、质量、生产率等问题。
软件工程是应用于计算机软件的定义、开发和保护的一整套方法、工具、文档、实践标准和工序。
简单的说就是使软件走向工程化。
软件工程的中心思想是把软件产品看作是一个工程产品来办理。
软件工程包括3个要素:
方法、工具和过程。
软件工程过程是把软件转变成输出的一组相互相关的资源活动,包括4种基本活动:
(1)P(plan)——软件规格说明;
(2)D(do)——软件开发;
(3)C(check)——软件确认;(4)A(action)——软件演进。
软件生命周期:
软件产品从提出、实现、使用保护到停止使用退伍的过程。
软件生命周期分三个阶段:
软件定义、软件开发、运行保护,
主要活动阶段是:
(1)可行性研究与计划拟定;
(2)需求解析;
(3)软件设计(大纲设计和详细设计);(4)软件实现;(5)软件测试;
(6)运行和保护。
软件工程的目标:
在给定成本、进度的前提下,开发出拥有有效性、可靠性、可理解性、可保护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。
基本目标:
付出较低的开发成本;达到要求的软件功能;获取较好的软件性能;开发软件易于移植;需要较低的花销;能准时完成开发,及时交付使用。
软件工程的理论和技术性研究的内容主要包括:
软件开发技术和软件工程管理。
软件开发技术包括:
软件开发方法学、开发过程、开发工具和软件工程环境。
软件开发环境或软件工程环境是指全面支持软件开发全过程的软件工具的会集。
软件工程管理包括:
软件管理学、软件工程经济学、软件心理学等内容。
软件管理学包括人员组织、进度安排、质量保证、配置管理、项目计划等。
软件工程基根源则:
抽象、信息隐蔽、模块化、局部化、确定性、一致性、齐全性和可考据性。
3.2构造化解析方法
构造化方法的中心和基础是构造化程序设计理论。
软件定义阶段中,可行性研究与计划的拟定是确定待开发目标和总的要求,给出它的功能、性能、可靠性以及接口等方面的可能方案,拟定完成开发的推行计划。
需求解析,对待开发软件提出的需求解析并给出详细的定义。
需求解析阶段的工作:
需求获取,需求解析,编写需求规格说明书,需求评审。
需求解析方法有:
(1)构造化需求解析方法;
①面向数据构造的Jackson方法(ISD);
②面向数据流的构造化解析方法(SA);
③面向数据构造的构造化数据系统开发方法(DSSD);
(2)面向对象的解析的方法(OOA)。
从需求解析成立的模型的特点来分:
静态解析和动向解析。
构造化解析方法的实质:
着眼于数据流,自顶向下,逐层分解,成立系统的办理流程,以数据流图和数据字典为主要工具,
7
公共基础知识
成立系统的逻辑模型。
构造化解析的常用工具:
数据流图;数据字典;判断树;判断表。
(1)数据流图(DFD图):
描述数据办理过程的工具,是需求理解的逻辑模型的图形表示,它直接支持系统功能建模。
①加工(变换)——圆框,输入数据经加工变换产生的输出。
②数据流——箭头,沿箭头方向传达数据的通道,一般在旁边注明数据流名。
③储藏文件(数据源)——双横线,表示办理过程中存放各种数据的文件。
④源、潭——方框,表示系统和环境的接口,属系统之外的实体。
(2)数据字典:
对全部与系统相关的数据元素的一个有组织的列表,以及精确的、严格的定义,使得用户和系统解析员关于输入、输出、储藏成分和中间计算结果有共同的理解。
数据字典是构造化解析的中心。
(3)判断树:
从问题定义的文字描述中分清哪些是判断的条件,哪些是判断的结论,依照描述资料中的连接词找出判断条件之间的隶属关系、并列关系、选择关系,依照它们构造判断树。
(4)判断表:
与判断树相似,当数据流图中的加工要依赖于多个逻辑条件的取值,即完成该加工的一组动作是由于某一组条件取值的组合而惹起的,使用判断表描述比较合适。
软件需求规格说明书的特点:
①正确性;②无岐义性;③完满性;④可考据性;
⑤一致性;⑥可理解性;⑦可改正性;⑧可追踪性。
3.3构造化设计
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国计算机 二级 公共 基础知识 汇总
![提示](https://static.bingdoc.com/images/bang_tan.gif)