2021年公共基础知识总结二级考试必看

第一章数据构造与算法算法1.1.1算法：是指解题方案精确而完整描述。规左理解决某类问题所需操作语句以及执行顺序使其能通过有限指令语句，在一疋期间内解决问题算法不等于程序，也不等计算机方法，程序编制不也许优于算法设汁。算法根本特性：是一组严谨地左义运算顺序规那么，每一种规那么都是有效，是明确，此顺序将在有限次数下终结。算法特性涉及：〔1) 可行性；〔2) 拟左性，算法中每一环节都必要有明拟泄义，不容许有模棱两可解释，不容许有多义性；〔3) 有穷性，算法必要能在有限时间内做完，即能在执行有限环节后终结，涉及合理执行时间含义：〔4) 拥有足够情报。算法根本要素：一是对数据对象运算和操作：二是算法控制构造普通，计算机可以以执行根本操作是以指令形式描述。一种汁算机系统能执行所有指令集合，称为汁算机系统指令系统。〔1)计算机系统中根本运算和操作涉及：算术运算 +-*/逻辑运算 notandor关系运算数据传播赋值输入与输出〔2）算法控制构造：顺序构造、选取构造、循环构造。算法根本设计方法：列举法〔列举所有解决方案）归纳法〔特殊T普通）递推 〔刁未知）递归〔逐级分解）减半递推“减半〃是指将问题规模减半，而问题性质不为，所谓“递推〃是指重复“减半〃过程回溯法找出一种解决问题线索，然后沿着这个线索逐渐屡次“探、试〃1.1.2算法复杂度算法时间复杂度和算法空间复杂度〔一种算法所要付岀代价）是衡理算法好坏。算法时间复杂度算法时间复杂度是指执行算法所需要计算工作量。〔既算法运算次数）含义：算法执行过程中所需要根本运算次数影响计算工作量重要因素：一、根本运算次数二、问题与规模算法空间复杂度是指执行这个算法所需要内存空间。一种算法所用内存空间涉及：1、算法程序所占空间2、 输入初始数据所占存储空间3、 算法执行过程中额外空间12数据构造根本根本概念数据：在汁算机科学中指所有能输入到计算机中并被计算机程序解决符号总称数据元素:数据根本单位，在il•算机程序中普通作为一种整体进行考虑和解决。数据构造：是互相之间存在一种或各种特左关系数据元素集合数据构造研究三个方面：〔1) 数据集合中各数据元素之间所固有逻辑关系，即数据逻借构造：〔2) 在对数据进行解决时，各数据元素在计算机中存储关系，即数拯存储构造：〔3) 对各种数据构造进行运算。线性结构7T歩卩 队列*•线性结构7T歩卩 队列*•卩 树形咨构〃非綫性a‘数据的逻辑结构.4-1数据的存储结构Pr顺序存储心j链式存储*飓据的运算：检索、挑序、插入、刪除、傷改卩数据构造是指互有关于联数据元素集合。即：普通来说，人们不会同步解决特性完全不同且互相之间没有任何关系各类数据元素，对于具备不同特性数据元素总是分别进行解决。7.数据逻辑构造包括：〔1)表达数据元素信息；(2＞表达各数据元素之间先后件关系。其中数据元素之间先后件关系是指它们逻辑关系，与它们在计算机中存储位置无关。2数据存储构造：P12一种数据构造中各数据元素在汁算机存储空间中位置关系与逻辑关系有也许不同数据存储构造指数据逻辑构造在计算机存储空间中存储形式-由于数据元素在汁算机存储空间中位置关系也许与逻借关系不同，因而，为了表达存储在计算机存储空间中各元素之间逻辑关系〔即先后件关系），在数据存储构造中，不但要存储并数据元素信息，还需要存储各数据元素之间先后件关系信息。逻辑构造与物理构造关系A.一种逻借构造可以用不同物理构造来实现B・.逻辑构造决左了算法设计C.物理构造决左了算法实现1.2.2数据构造图形表达：1.2.3线性构造与非线性构造如果一种非空数据构造满足以下两个条件有且只有一种根结点每一种结点最多有一种前件，也最多有一种后件那么称该数拯构造为线性构造，线性构造也称为线性表特别需要说明是，在一种线性构造中插入或删除任何一种结点后还应是线性构造。如果一种数据构造不是线性构造，那么称为非线性构造。数据存储构造有顺序、链接、索引等。对于同一种逻辑构造来说，采用不同存储构造，其数据解决效率是不同。线性构造条件：〔1) 有且只有一种根结点；〔2) 每一种结点最多有一种前件，也最多有一种后件。非线性构造：不满足线性构造条件数据构造。3线性表及其顺序存储构造线性表由一组数据元素构成，数据元素位置只取决于自己序号，元素之间相对位置是线性。在复杂线性表中，由假设干项数据元素构成数据元素称为记录，而由各种记录构成线性表又称为文献。1.3.1非空线性表构造特性：P16〔1) 且只有一种根结点al,它无前件；〔2) 有且只有一种终端结点an,它无后件：〔3) 除根结点与终端结点外，其她所有结点有且只有一种前件，也有且只有一种后件。结点个数n称为线性表长度，当n=0时，称为空表。3.2线性表顺序存储构造具备如下两个根本特点：〔1) 线性表中所有元素所占存储空间是持续；〔2) 线性表中各数据元素在存储空间中是按逻辑顺序依次存储。ai存储地址为：ADR〔ai)=ADR〔al)+〔i-1)k.,ADR〔al)为第一种元素地址，k代表每个元素占字节数。由此可以看出，在线性表顺序构造中，其先后件两个元素在存储空间中是紧邻，且前件元素一定存储在后件元素前而。在程序设计语言中，普通定义一种一维数组来表达线性表顺序存储空间。顺序表运算：插入、删除。〔详见17-18页)画图来理解1.4栈和队列1.4.1桟及其根本运算什么是栈栈是限泄在一端进行插入与删除线性表，容许插入与删除一端称为栈顶，不容许插入与删除另一端称为栈底。栈按照“先进后出〃〔FILO)或“后进先出〃〔LIFO)组织数据，栈具备记忆作用。用top表达栈顶位置，用bottom表达栈底。栈顺序存储与栈根本运算：〔1) 插入元素称为入栈运算；〔2) 删除元素称为退栈运算：〔3) 读栈顶元素是将栈顶元素赋给一种指泄变量，此时指针无变化。1.4.2队列及其根本运算什么是队列队列是指容许在一端〔队尾［进入插入，而在另一端〔队头［进行删除线性表。Rear指针指向队尾，from指针指向队头。队列是“先进先岀〃〔HFO)或“后进后岀〃〔LILO)线性表。循环队列运算涉及〔1) 入队运算：从队尾插入一种元素：〔2) 退队运算：从队头删除一种元素。循环队列：s=0表达队列空，s=l且front=rear表达队列满1.5线性链表p24对于大线性表或者变动频繁线性表不适当用顺序存储，应当用链式存储。在链式存储构造中每一种结点相应于一种存储单元，这种存储单元称为存储结点，简称结点。结点由两某些构成：〔1）用于存储数据元素值，称为数据域；〔2）用于存储指针，称为指针域，用于指向前一种或后一种结点。链式存储方式特点：☆在链式存储构造中，存储数拯构造存储空间可以不持续，☆各数据结点存储顺序与数拯元素之间逻辑关系可以不一致，而数据元素之间逻辑关系是由指针域来拟泄。☆链式存储方式即可用于表达线性构造，也可用于表达非线性构造。线性链表为了适应线性表存储构造，讣算机存储空间被划分为一种一种小块，每一种小块占假设干字节,普通称这些小块为存储结点。存储结点二数据域〔数据元素自身）+指针域〔数据元素之间先后逻辑关系）在线性链表中，用一种专门指针HEAD指向线性链表中第一种数据元素结点〔即存储线性表中第一种数据元素存储结点序号）称为头指针，头指针：在线性链表中，头指针〔HEAD）很核心，不得丧失。最后一种结点指针域：线性链表最一种结点指针域为空〔用NULL或0来表达）空表泄义：当HEAD=NULL〔或0）称为空表。单链表缺陷：只能找到后不能找到前件。双向链表为了克服单链表缺陷，把每个结点修改为由三某些组 左指针数据元素右指针一双向链表克服了单向链表只能找到后件不能找到前件缺陷。如果是两指针：左指针〔Llink）指向前件结点，右指针〔Rlink）指向后件结点。HfK注盘二诺栈中指针的方向带链栈 HfK注盘二诺栈中指针的方向带链栈 aiIA在实际应用中，带链栈可以用来收集讣算机存储空间中所有空闲存储结点。这种带链栈称为可运用栈当汁算机系统需要存储结点时，退栈。当计算机系统释放存储结点时，入栈3.循环链表单链表运算必要对于空表和对第一种结点解决必要单独考虑，为了克服这个缺陷，提出了循环链表概念。循环链表与单链表重要区别：第一，在循环链表中增长了表头结点，其数据域为任意或依照需要来设立，指针域为指向线性表第一种元素结点。第二，循环链表中最后一种结点指针不为空，而是指向表头结点。1.6树与二叉树p31树根本概念树是一种简朴非线性构造，所有元素之间具备明显层次特性。在树构造中，每一种结点只有一种前件，称为父结点，没有前件结点只有一种，称为树根结点，简称树根〃每一种结点可以有各种后件，称为该结点子结点。没有后件结点称为叶子结点。在树构造中，一种结点所拥有后件个数称为该结点度，所有结点中最大度称为树度。树最大层

次称为树深度—叉树特点：〔1〕非空—叉树只有一种根结点；〔2〕每一种结点最多有两棵子树，且分别称为该结点左子树与右子树。二叉树根本性质：〔1〕在二叉树第k层上，最多有2k-l〔k21〕个结点：〔2〕 深度为m二叉树最多有2m-1个结点：〔3〕度为0结点〔即叶子结点〕总是比度为2结点多一种：〔4〕 具备n个结点二叉树，其深度至少为［Iog2n］+Ljt中［I°g2n］表达取log2n整数某些：〔5〕具备n个结点完全二叉树深度为［Iog2n］+I;〔6〕设完全二叉树共有n个结点。如果从根结点开始，按层序〔每一层从左到右〕用自然数］,2,....n给结点进彳亍编号〔k=l,2—.n〕，有如下结论：假设k=l,那么该结点为根结点，它没有父结点；假设k>l,那么该结点父结点编号为INT〔k/2〕；假设2k£n,那么编号为k结点左子结点编号为2k:否那么该结点无左子结点〔也无右子结点）；假设2k+lWn,那么编号为k结点右子结点编号为2k+l;否那么该结点无右子结点。满二叉树是指除最后一层外，每一层上所有结点有两个子结点，那么k层上有2k-l个结点深度为m满二叉树有2m-1个结点。完全二叉树是指除最后一层外，每一层上结点数均到达最大值，在最后一层上只缺少右边假设干结点。二叉树存储构造采用链式存储构造，对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树遍历：〔1〕 前序遍历〔DLR〕,一方而访问根结点，然后遍历左子树，最后適历右子树:〔2〕 中序適历〔LDR〕,一方而遍历左子树，然后访问根结点，最后適历右子树:3〕后序遍历〔LRD3〕后序遍历〔LRD〕—方而遍历左子树,然后访问遍历右子树，最后访问根结点。1.7查找技术顺序查找使用状况：线性表为无序表：表采用链式存储构造。二分法查找只合用于顺序存储有序表，对于长度为n有序线性表，最坏状况只需比拟log2n次。1.8排序技术排序是指将一种无序序列整顿成按值非递减顺序排列有序序列。互换类排序法：(1)冒泡排序法，需要比拟次数为n(n-l)/2; (2)迅速排序法。插入类排序法：(1)简朴插入排序法，最坏状况需要n(n-l)/2次比拟；(2)希尔排序法，最坏状况需要0(nl.5)次比拟。选取类排序法：(1)简朴选取排序法，最坏状况需要n(n-l)/2次比拟：(2)堆排序法，最坏状况需要O(nlog2n)次比拟。当前位置：公共根本知识总结之第二章程序设计根本第二章程序设计根本2.1程序设il・设计方法和风格如何形成良好程序设讣风格1、源程序文档化；〔〔3〕 C一一软件确认：〔〔3〕 可重用性好：2、数据说明方法:3、 语句构造；4、 输入和输出。注释分前言性注释和功能性注释，语句构造淸晰第一、效率第二。2构造化程序设计构造化程序设汁方法四条原那么是：1.自顶向下；2.逐渐求精：3•模块化：4.限制使用goto语句。构造化程序根本构造和特点：〔1〕 顺序构造：一种简朴程序设计，最根本、最惯用构造：〔2〕 选取构造：又称分支构造，涉及简朴选取和多分支选取构造，可依照条件，判断应当选取哪一条分支来执行相应语句序列；〔3〕 重复构造：又称循环构造，可依照给左条件，判断与否需要重复执行某一相似程序段。2.3而向对象程序设计而向对象程序设计：以60年代末挪威奥斯陆大学和挪威讣算机中心研制SIMULA语言为标，占0而向对象方法长处：〔1〕 与人类习惯思维方法一致：〔2〕 稳左性好；〔4〕易于开发大型软件产品:〔5〕可维护性好。对象是而向对象方法中最根本概念，可以用来表达客观世界中任何实体，对象是实体抽象。而向对象程序设计方法中对象是系统中用来描述客观事物一种实体，是构成系统一种根本单位，由一组表达其静态特性属性和它可执行一组操作构成。属性即对象所包括信息，操作描述了对象执行功能，操作也称为方法或效劳。对象根本特点：〔1〕 标记惟一性：〔2〕分类性：〔3〕多态性；〔4〕封装性：〔5〕 模块独立性好。类是指具备共同属性、共同方法对象集合。因此类是对象抽象，对象是相应类一种实例。消息构成涉及〔1〕接受消息对象名称；〔2〕消息标记符，也称消息名；〔3〕零个或各种参数。继承是指可以直接获得已有性质和特性，而不必重复圮义她们。继承分单继承和多重继承。单继承指一种类只容许有一种父类，多重继承指一种类容许有各种父类。多态性是指同样消息被不同对象接受时可导致完全不同行动现象。当前位置：公共根本知识总结之第三章软件工程根本第三章软件工程根本1软件工程根本概念计算机软件是涉及程序、数搦及有关文档完整集合。软件特点涉及：〔1〕 软件是一种逻辑实体；〔2〕 软件生产与硬件不同，它没有明显制作过程：〔3〕 软件在运营、有效期间不存在磨损、老化问题：〔4〕 软件开发、运营对讣算机系统具备依赖性，受计算机系统限制，这导致了软件移植问题：〔5〕 软件复杂性髙，本钱昂贵：〔6〕 软件开发涉及诸多社会因素。软件按功能分为应用软件、系统软件、支撑软件〔或工具软件〕。软件危机重要体当前本钱、质量、生产率等问题。软件工程是应用于计算机软件立义、开发和维护一整套方法、工具、文档、实践原那么和工序。软件工程涉及3个要素：方法、工具和过程。软件工程过程是把软件转化为输出一组彼此有关资源和活动，包括4种根本活动：〔1〕P 软件规格说明；〔2〕 D——软件开发；〔4〕 A 软件演进。软件周期：软件产品从提岀、实现、使用维护到停止使用退役过程。软件生命周期三个阶段:软件左义、软件开发、运营维护，重要活动阶段是：〔1〕 可行性研究与筹划制立：〔2〕 需求分析；〔3〕 软件设计：〔4〕软件实现;〔5〕 软件测试；〔6〕 运营和维护。软件工程目的和与原那么：目的：在给泄本钱、进度前提下，开发出具备有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足顾客需求产品。根本目的：付岀较低开发本钱；到达规左软件功能；获得较好软件性能；开发软件易于移植：需要较低费用：能准时完毕开发，及时交付使用。根本原那么：抽象、信息隐蔽、模块化、局部化、拟定性、一致性、完备性和可验证性。软件工程理论和技术性研究内容重要涉及：软件开发技术和软件工程管理。软件开发技术涉及：软件开发方法学、开发过程、开发工具和软件工程环境。软件工程管理涉及：软件管理学、软件工程经济学、软件心理学等内容。软件管理学涉及人员组织、进度安排、质量保证、配备管理、工程筹划等。软件工程原那么涉及抽象、信息隐蔽、模块化、局部化、拟龙性、一致性、完备性和可验证性。2构造化分析方法构造化方法核心和根本是构造化程序设计理论。需求分析方法有〔1〕构造化需求分析方法；〔2〕而向对象分析方法。从需求分析建立模型特性来分：静态分析和动态分析。构造化分析方法实质：着眼于数据流，自顶向下，逐级分解，建立系统解决流程，以数据流图和数据字典为重要工具,建立系统逻借模型。构造化分析惯用工具〔1〕数据流图；〔2〕数据字典；〔3〕鉴宦树：〔4〕鉴左表。数据流图：描述数据解决过程工具，是需求理解逻借模型图形表达，它直接支持系统功能建模。数据字典：对所有与系统有关数据元素一种有组织列表，以及精准、严格宦义，使得顾客和系统分析员对于输入、输岀、存储成分和中间计算成果有共同理解。鉴泄树：从问题立义文字描述中分淸哪些是鉴泄条件，哪些是鉴左结论，依照描述材料中连接词找岀鉴泄条件之间附属关系、并列关系、选取关系，依照它们构造鉴左树。鉴泄表：与鉴立树相似，当数拯流图中加工要依赖于各种逻借条件取值，即完毕该加工一组动作是由于某一组条件取值组合而引起，使用鉴圧表描述比拟适当。数据字典是构造化分析核心。软件需求规格说明书特点：〔1〕 对的性：〔2〕 无岐义性；〔3〕 完整性：〔4〕 可验证性；〔5〕 一致性：〔6〕 可理解性;〔7〕 可追踪性。3.3构造化设计方法软件设计根本目的是用比拟抽象概括方式拟左目的系统如何完毕预龙任务，软件设计是拟赵系统物理模型。软件设计是开发阶段最重要环节，是将需求精确地转化为完整软件产品或系统唯一途径。从技术观点来看，软件设计涉及软件构造设计、数据设计、接口设汁、过程设计。构造设计：泄义软件系统各重要部件之间关系。数据设计：将分析时创立模型转化为数据构造左义。接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。过程设计：把系统构造部件转换成软件过程描述。从工程管理角度来看：槪要设计和详细设计。软件设计普通过程：软件设计是一种迭代过程：先进行高层次构造设计：后进行低层次过程设计：穿插进行数据设计和接口设计。衡量软件模块独立性使用耦合性和内聚性两个怎性度量原那么。在程序构造中各模块内聚性越强，那么耦合性越弱。先进软件应高内聚，低耦合。软件槪要设汁根本任务是：〔1〕设计软件系统构造；〔2〕数据构造及数据库设计；〔3〕编写概要设计文档；〔4〕槪要设计文档评审。模块用一种矩形表达，箭头表达模块间调用关系。在构造图中还可以用带注释箭头表达模块调用过程中来回传递信息。还可用带实心圆箭头表达传递是控制信息，空心圆箭心表达传递是数据。构造图根本形式：根本形式、顺序形式、重复形式、选取形式。构造图有四种模块类型：传入模块、传出模块、变换模块和协调模块。典型数据流类型有两种：变换型和事务型。变换型系统构造图由输入、中心变换、输出三某些构成。事务型数据流特点是：接受一项事务，依照事务解决特点和性质，选取分派一种恰当解决单元，然后给岀成果。详细设计：是为软件构造图中每一种模块拟定实现算法和局部数据构造，用某种选定表达工具表达算法和数据构造细节。常用过程设il•工具备：图形工具〔程序流程图〕、表格工具〔鉴左表〕、语言工具〔PDL〕。3.4软件测试软件测试定义：使用人工或自动手段来运营或测左某个系统过程，其目在于检查它与否满足规定需求或是弄淸预期成果与实际成果之间差异。软件测试目：发现错误而执行程序过程。软件测试方法：静态测试和动态测试。静态测试涉及代码检查、静态构造分析、代码质虽度量。不实际运营软件，重要通过人工进行。动态测试：是根本计算机测试，重要涉及白盒测试方法和黑盒测试方法。白盒测试：在程序内部进行，重要用于完毕软件内部操作验证。重要方法有逻辑覆盖、根本基途径测试。黑盒测试：重要诊断功能不对或漏掉、界而错误、数拯构造或外部数据库访问错误、性能错误、初始化和终结条件错，用于软件确认。重要方法有等价类划分法、边界值分析法、错误推测法、因果图等。软件测试过程普通按4个环节进行：单元测试、集成测试、验收测试〔确认测试〕和系统测试。5程序调试程序调试任务是诊断和改正程序中错误，重要在开发阶段进行。程序调试根本环节：〔1〕错误宦位；〔2〕 修改设汁和代码，以排除错误：〔3〕进行回归测试，防止引进新错误。软件调试可分表静态调试和动态调试。静态调试重要是指通过人思维来分析源程序代码和排错，是重要设讣手段，而动态调试是辅助静态调试。重要调试方法有：〔1〕强行排错法；〔2〕回溯法：〔3〕因素排除法。当前位置：公共根本知识总结之第四章数据库应用第四章数据库应用1数据库系统根本概念数据：事实上就是描述事物符号记录。数据特点：有一立构造，有型与值之分，如整型、实型、字符型等。而数据值给岀了符合泄型值，如整型值15。数据库：是数据集合，具备统一构造形式并存储于统一存储介质内，是各种应用数据集成，并可被各个应用程序共享。数据库存储数据是按数据所提供数据模式存储，具备集成与共享特点。数据库管理系统：一种系统软件，负责数据库中数据组织、数据操纵、数据维护、控制及保护和数据效劳等，是数据库核心。数据库管理系统功能：〔1〕 数据模式左义：即为数据库构建其数据框架：〔2〕数据存取物理构建：为数据•模式物理存取与构建提供有效存取方法与手段：〔3〕数据操纵：为顾客使用数据库数据提供以便，如査询、插入、修改、删除等以及简朴算术运算及记录；〔4〕数据完整性、安生性疋义与检查：〔5〕 数据库并发控制与故障恢复；〔6〕数据效劳：如拷贝、转存、重组、性能监测、分析等。为完毕以上六个功能，数据库管理系统提供如下数摇语言：〔1〕数据定义语•言：负责数据模式左义与数据物理存取构建：〔2〕数据操纵语言：负责数据操纵，如查询与增、删、改等：〔3〕数据控制语言：负责数据完整性、平安性立义与检査以及并发控制、故障恢复等。数据语言按其使用方式具备两种构造形式：交互式命令〔又称自含型或自主型语言〕宿主型语言〔普通可嵌入某些宿主语言中〕。数据库管理员：对数据库进行规划、设计、维护、监视等专业管理人员。数据库系统：由数据库〔数据）、数据库管理系统〔软件）、数据库管理员〔人员）、硬件平台〔硬件〕、软件平台〔软件〕五个某些构成运营实体。数据库应用系统：由数据库系统、应用软件及应用界而三者构成。文献系统阶段：提供了简朴数据共享与数据管理能力，但是它无法提供完整、统一、管理和数据共享能力。层次数据库与网状数据库系统阶段：为统一与共享数据提供了有力支撑。关系数据库系统阶段数据库系统根本特点：数据集成性、数据高共享性与低冗余性、数据独立性〔物理独立性与逻辑独立性〕、数据统一管理与控制。数据库系统三级模式：〔1〕 概念模式：数据库系统中全局数据逻辑构造描述，全体顾客公共数据视图：〔2〕 外模式：也称子模式与顾客模式。是顾客数据视图，也就是顾客所见到数据模式；〔3〕 内模式：又称物理模式，它给岀了数据库物理存储构造与物理存取方法。数据库系统两级映射：〔1〕 概念模式到内模式映射：〔2〕外模式到概念模式映射。数据模型数据模型概念：是数据特性抽象，从抽象层次上描述了系统静态特性、动态行为和约朿条件，为数据库系统信息表与操作提供一种抽象框架。描述了数据构造、数据操作及数据约朿。E-R模型根本概念〔1〕 实体：现实世界中事物：〔2〕 属性：事物特性：〔3〕 联系：现实世界中事物间关系。实体集关系有一对一、一对多、多对多联系。E-R模型三个根本概念之间联接关系：实体是概念世界中根本单位，属性有属性域，每个实体可取属性域内值。一种实体所有属性值叫元组。E-R模型图示法：〔1〕实体集表达法：〔2〕属性表法；〔3〕联系表达法。层次模型根本构造是树形构造，具备如下特点：〔1〕 每棵树有