二级公共基础知识

NationalComputerRankExamination二级公共基础知识全国计算机等级考试备考核心指南Contents目录二级公共基础知识01计算机系统基础02基本数据结构与算法03程序设计基础04软件工程基础05数据库设计基础CHAPTER01计算机系统基础从硬件架构到操作系统的核心概念梳理CHAPTER04计算机系统概述现代计算机基于冯·诺依曼"存储程序"体系，核心思想是程序与数据以二进制形式存储并按序自动执行。冯·诺依曼体系核心程序和数据以二进制形式存储在存储器中，计算机按程序顺序自动执行指令，这一设计思想奠定了现代计算机的基本架构。存储程序硬件系统五大部件运算器负责算术和逻辑运算、控制器指挥协调各部件工作、存储器存放数据和程序、输入设备接收外部信息、输出设备呈现处理结果。5大部件软件系统分层结构系统软件（如操作系统、编译器）管理硬件资源并提供运行环境，应用软件（如办公软件、浏览器）面向用户解决具体问题。双层架构冯·诺依曼体系结构五大部件关系示意图COMPUTERFUNDAMENTALSCPU的功能与组成CPU是计算机的核心处理单元，由运算器和控制器组成。运算器执行算术和逻辑运算，控制器负责取指、译码和执行指令的协调控制。CPU的性能由主频、字长和缓存容量三大指标决定。IntelCPU芯片实拍主频GHz字长64位缓存L1–L301运算器组成算术逻辑单元ALU执行加减乘除和逻辑运算，累加寄存器暂存运算结果，数据缓冲寄存器暂存输入数据，状态条件寄存器记录运算状态标志02控制器组成程序计数器PC存放放下条指令地址，指令寄存器IR存放当前指令，指令译码器分析操作码，时序产生器产生节拍脉冲信号协调各部件03CPU性能指标主频决定运算速度（单位GHz），字长决定一次处理的数据位数（如64位），缓存容量影响数据访问速度（L1/L2/L3三级缓存）Chapter02·ComputerFundamentals存储器分层体系存储器采用分层体系结构（寄存器→Cache→主存→辅存），基于局部性原理实现速度与容量的平衡。越靠近CPU的存储器速度越快、容量越小、价格越高，各层协同工作构成完整的存储系统。高速存储层寄存器位于CPU内部，速度最快（与CPU同频），容量极小（几十到几百字节），存放当前正在处理的数据和指令高速缓存Cache位于CPU与主存之间，分为L1/L2/L3三级，容量从几十KB到几十MB，命中率通常可达90%以上命中率90%+主存储器主存直接与CPU交换数据，分为RAM（随机存取存储器，断电丢失）和ROM（只读存储器，断电不丢失）内存容量和访问速度直接影响系统性能，当前主流配置为8GB–32GB，访问速度以纳秒（ns）为单位衡量8–32GB辅助存储器辅存包括机械硬盘HDD、固态硬盘SSD、U盘和光盘，容量大（GB到TB级）但速度慢，断电后数据不丢失SSD采用闪存芯片存储，读写速度是HDD的5–10倍，已成为主流配置；HDD容量大价格低，适合大容量数据存储5–10×HDDChapter02·OperatingSystem操作系统基础操作系统是管理计算机硬件与软件资源的核心系统软件，承担处理器管理、存储管理、文件管理、设备管理和用户接口五大功能。01处理器管理：通过进程调度算法（先来先服务、时间片轮转、优先级调度）合理分配CPU时间，实现多道程序并发执行02存储管理：负责内存分配与回收、地址映射和内存保护，常用技术包括分页、分段和虚拟内存管理03文件管理：组织和管理磁盘文件，提供创建、删除、读写和目录管理功能，实现按名存取04进程与程序：程序是静态指令集合，进程是动态执行过程；一个程序可对应多个进程，进程具有动态性、并发性和独立性Linux命令行终端工作场景CHAPTER02基本数据结构与算法从算法复杂度到二叉树遍历的核心考点全面解析AlgorithmBasics算法的基本概念算法是求解特定问题的有穷规则序列，具备五个基本特性，性能通过时间与空间复杂度两个维度评价。01算法五大特性—有穷性（有限步骤内终止）、确定性（每条指令无歧义）、可行性（每条指令可执行）、输入（0个或多个）、输出（1个或多个）02时间复杂度—用大O符号表示执行时间随规模n增长的变化趋势，常见复杂度从低到高依次为O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(2ⁿ)03空间复杂度—额外存储空间随规模n增长的变化趋势，原地工作的算法空间复杂度为O(1)程序员编写算法代码的工作场景FUNDAMENTALS数据结构的基本概念数据结构是存在特定关系的数据元素集合，包含逻辑结构、存储结构和数据运算三个方面。逻辑结构分为线性结构（一对一关系）和非线性结构（一对多或多对多关系），存储结构主要有顺序、链式、索引和散列四种方式。逻辑结构分类线性结构数据元素之间存在一对一的前后关系，如线性表、栈、队列，每个元素最多有一个前驱和一个后继非线性结构数据元素之间存在一对多（树）或多对多（图）的关系，一个元素可以有多个前驱或多个后继存储结构分类顺序存储用连续的存储单元依次存放数据元素，逻辑相邻的元素物理位置也相邻，支持随机访问链式存储用指针将分散的存储单元链接起来，逻辑相邻的元素物理位置不一定相邻，支持动态插入和删除Chapter02·数据结构基础线性表及其顺序存储结构线性表是n个数据元素的有限序列，元素间存在一对一的前驱后继关系。顺序存储用连续存储单元依次存放元素，支持随机访问（O(1)），但插入和删除操作需要移动大量元素，平均时间复杂度为O(n)。01线性表定义：由n（n≥0）个数据元素组成的有限序列（a₁,a₂,...,aₙ），n=0时称为空表；元素间存在严格的前驱后继关系。(a₁,a₂,…,aₙ)02顺序存储特点：用一组地址连续的存储单元依次存放元素，逻辑相邻则物理相邻，可通过下标直接访问任意元素（随机访问）。O(1)随机访问03插入运算：在第i个位置插入新元素时，需将第i至第n个元素依次后移一位，平均移动n/2个元素，时间复杂度O(n)。平均移动n/204删除运算：删除第i个元素时，需将第i+1至第n个元素依次前移一位，平均移动(n-1)/2个元素，时间复杂度O(n)。平均移动(n-1)/2DataStructures栈和队列栈和队列是两种特殊的线性表：栈限制在栈顶进行插入和删除，遵循后进先出（LIFO）原则；队列限制在队尾插入、队头删除，遵循先进先出（FIFO）原则。栈（LIFO结构）核心特性仅允许在栈顶进行插入（push）和删除（pop），最后入栈的元素最先被删除，即后进先出典型应用函数调用的栈帧管理、表达式求值、括号匹配、递归非递归化转换等场景依赖栈的LIFO特性异常处理上溢（栈满继续入栈）和下溢（栈空继续退栈）是栈操作需处理的异常情况队列（FIFO结构）核心特性仅允许在队尾插入（入队）、在队头删除（退队），最先进入的元素最先被删除，即先进先出循环队列为解决顺序队列的"假溢出"问题，将队列首尾相连，用front和rear指针及取模运算实现典型应用操作系统的作业调度、缓冲区管理、广度优先搜索（BFS）算法等场景依赖队列的FIFO特性DataStructure线性链表线性链表用指针将分散的存储单元链接起来，每个节点由数据域和指针域组成。链表插入删除只需修改指针（O(1)），但查找需从头遍历（O(n)）。单链表每个节点包含数据域和指向下一个节点的指针域，只能从头节点单向遍历，末尾指针为NULL单向遍历双向链表包含数据域、前驱指针和后继指针，可双向遍历，适合前后方向频繁查找双向遍历循环链表末节点指针指向头节点形成环，从任一节点出发都能遍历整个链表环形结构链表vs顺序表链表插入删除O(1)但查找O(n)；顺序表查找O(1)但插入删除O(n)O(1)vsO(n)DataStructure树与二叉树树是具有层次结构的非线性数据结构，二叉树是每个节点最多有两棵子树的特殊树。二叉树的三种遍历方式（前序、中序、后序）是核心考点，考试中常要求根据遍历序列还原二叉树或写出遍历结果。树的基本概念TREEFUNDAMENTALS由n（n≥0）个节点组成的有限集合，n=0为空树；有且仅有一个根节点，其余节点互不相交地分为若干子树节点的度（子树个数）、树的度（节点度的最大值）、叶子节点（度为0）、深度（根到最深层的层数）n≥0·根唯一二叉树遍历BINARYTREETRAVERSAL前序遍历（根左右）—先访问根节点，再前序遍历左子树，最后前序遍历右子树中序遍历（左根右）—先中序遍历左子树，再访问根节点，最后中序遍历右子树后序遍历（左右根）—先后序遍历左子树，再后序遍历右子树，最后访问根节点前序·中序·后序SEARCHALGORITHMS查找技术顺序查找逐个比较，时间复杂度O(n)；二分法要求数据有序，每次缩小一半范围，时间复杂度O(logn)，效率更高。LINEARSEARCH顺序查找从表的一端开始逐个比较，找到则返回位置，查完未找到则失败。适用于无序表或链表结构，实现简单但效率较低。ASL=(n+1)/2·O(n)PRECONDITION二分法查找前提数据必须按关键字有序排列，且采用顺序存储结构；每次将中间元素与目标值比较，缩小一半范围。不满足条件则无法使用。有序+顺序存储ALGORITHM二分法查找过程设low和high为上下界，mid=(low+high)/2，比较a[mid]与目标值调整边界直至命中。循环或递归实现均可。mid=(low+high)/2PERFORMANCE二分法查找性能最多比较次数为⌊log₂n⌋+1，可用判定树分析，树的深度即为最大比较次数。查找效率显著优于顺序查找。O(logn)CHAPTER03程序设计基础从结构化编程到面向对象设计的编程范式演进ProgrammingStyle程序设计方法和风格良好的程序设计风格要求源程序文档化、数据说明规范化、语句结构简单清晰、输入输出格式友好。程序设计应遵循'自顶向下、逐步求精'的思路，先设计算法再编写代码。源程序文档化添加序言性注释（说明程序功能、作者、日期）和功能性注释（解释关键代码段的作用），提高程序可读性和可维护性可读性数据说明规范化按常量→简单变量→数组→复杂数据结构的统一顺序组织数据声明，同类变量按字母序排列，便于查找和维护字母序语句结构原则避免过度嵌套（一般不超过3层）、避免复杂条件表达式、每条语句独占一行、适当使用空行分隔逻辑段落3层嵌套输入输出规范输入时提供清晰的提示信息，输出时格式整齐美观，对输入数据进行合法性检查，防止非法数据导致程序崩溃合法性PROGRAMMINGPARADIGM结构化程序设计结构化程序设计采用"自顶向下、逐步求精、模块化"的方法，仅使用顺序、选择和循环三种基本控制结构，确保程序清晰且易于维护。CONTROLSTRUCTURES三种基本控制结构01·顺序结构按语句书写顺序从上到下依次执行，每条语句执行一次且仅执行一次，是最基本的程序执行方式。02·选择结构根据条件判断结果选择不同的执行路径，包括单分支if、双分支if-else和多分支switch-case。03·循环结构在满足条件的情况下重复执行某段代码，包括当型循环while（先判断后执行）和直到型do-while。DESIGNPRINCIPLES设计原则01·自顶向下从整体到局部，先设计主程序框架，再逐步细化各个子模块的实现细节。02·逐步求精将复杂问题分解为若干简单的子问题，每个子问题再进一步分解，直到可以直接用代码实现。03·模块化设计将程序划分为若干功能独立的模块，每个模块完成特定的子功能，模块间通过接口进行通信。OOP·CORECONCEPTS面向对象的程序设计面向对象程序设计将现实世界抽象为对象（数据+方法），通过类来描述对象的共性。封装性隐藏内部细节、继承性实现代码复用、多态性支持灵活扩展，三大特征共同构成OOP的核心优势。封装性将对象的属性和方法封装为整体，外部通过公开接口访问，隐藏内部实现细节，提高安全性和可维护性。通过访问修饰符控制可见性，有效防止外部随意修改对象状态。Encapsulation继承性子类自动继承父类属性和方法，可添加新成员或重写父类方法，实现代码复用和层次化设计。建立"is-a"关系，形成类的层次结构，减少重复代码编写。Inheritance多态性同一操作作用于不同对象产生不同行为，如"绘制"对圆形和矩形执行不同逻辑，提高灵活性。支持运行时绑定，使程序具有良好的扩展性和可维护性。Polymorphism类与对象类是对具有相同属性和方法的对象的抽象模板，对象是类的具体实例，一个类可创建多个对象。类定义了对象的行为和状态，是面向对象编程的基本构造单元。Class&ObjectCHAPTER04软件工程基础从需求分析到软件测试的工程化方法全解析CHAPTER02·SOFTWAREENGINEERING软件工程基本概念软件工程是用工程化方法开发和维护软件的学科，目标是生产高质量、低成本、易维护的软件。软件生命周期分为定义期（需求分析）、开发期（设计、编码、测试）和维护期三个阶段。PHASE01软件定义期问题定义：明确要解决的问题是什么，确定项目的目标和范围，产出问题定义报告可行性研究：从技术、经济和操作三个方面评估项目是否可行，产出可行性研究报告需求分析：详细确定系统必须做什么，产出软件需求规格说明书（SRS），是整个开发过程的基础PHASE02软件开发期概要设计：确定系统的总体结构和模块划分，设计模块间的接口关系，产出概要设计说明书详细设计：设计每个模块的内部算法和数据结构，产出详细设计说明书编码与测试：将设计转化为程序代码，并通过单元测试、集成测试和系统测试验证软件质量SoftwareEngineering·SA结构化分析方法结构化分析（SA）是面向数据流的需求分析方法，采用'自顶向下、逐层分解'策略。数据流图（DFD）和数据字典（DD）是核心工具。数据流图四元素外部实体（方框，数据来源/去向）、加工（圆角矩形，数据处理）、数据流（箭头，流动方向）、存储文件（开口矩形，数据暂存）DFD·四元素数据字典对数据流图中所有数据流、数据项、数据存储和加工进行精确定义，确保开发人员对数据有一致理解DD·精确定义逐层分解策略顶层DFD描述系统整体功能（只有一个加工），逐层细化到每个加工的内部逻辑，直到底层加工足够简单可直接实现层级关系：顶层→中层→底层自顶向下判定表与判定树用于描述复杂加工逻辑，当加工涉及多个条件和多个动作的组合时，用判定表比文字描述更清晰条件组合→动作选择条件组合SOFTWAREDESIGN结构化设计方法结构化设计（SD）将分析结果转化为软件方案，追求"高内聚、低耦合"的模块独立性。内聚衡量模块内部关联度（越高越好），耦合衡量模块间依赖度（越低越好）。详细设计用流程图、N-S图等工具描述算法。模块独立性内聚由低到高偶然→逻辑→时间→过程→通信→顺序→功能内聚耦合由低到高无直接→数据→标记→控制→外部→公共→内容耦合功能内聚最理想·数据耦合最理想详细设计工具程序流程图用图形符号表示算法步骤和控制流程，直观易懂但容易画出非结构化流程N-S图（盒图）用嵌套矩形框表示结构化控制结构，强制结构化设计但复杂算法时嵌套层次过多流程图直观·盒图强制结构化SoftwareTesting软件测试软件测试旨在发现程序中的错误，分为白盒测试与黑盒测试两大类。测试策略按单元→集成→确认→系统逐步扩大范围。白盒测试逻辑覆盖语句覆盖（每条语句至少执行一次）→判定覆盖（每个判定真假各一次）→条件覆盖（每个条件真假各一次），覆盖强度递增。覆盖递增白盒测试基本路径测试根据程序控制流图计算圈复杂度，确定独立路径数，为每条独立路径设计测试用例。圈复杂度黑盒测试等价类划分将输入数据划分为有效等价类和无效等价类，从每个等价类中选取代表性数据作为测试用例。有效/无效黑盒测试边界值分析针对输入数据的边界值设计测试用例，因为错误往往发生在输入范围的边界附近。边界检测Chapter05数据库设计基础从数据模型到关系代数的数据库核心知识梳理DatabaseSystem数据库系统基本概念数据库系统（DBS）由数据库（DB）、数据库管理系统（DBMS）、应用程序、DBA和用户五部分组成。DBMS是核心软件，提供数据定义、操纵、控制和维护功能。数据库系统实现了数据结构化、高共享、低冗余和高独立性。01数据库（DB）长期存储在计算机内的、有组织的、可共享的数据集合，数据按一定的数据模型组织、描述和存储。数据集合02数据库管理系统（DBMS）位于用户与操作系统之间的数据管理软件，提供DDL、DML和DCL三种语言。核心软件03数据独立性物理独立性（存储结构改变不影响应用）和逻辑独立性（逻辑结构改变不影响应用），由三级模式两级映射实现。两级映射04三级模式结构外模式（用户视图）、概念模式（全局逻辑结构）和内模式（物理存储结构），两级映射保证数据独立性。三级两层DatabaseFundamentals数据模型数据模型分为层次模型（树形结构，一对多）、网状模型（图形结构，多对多）和关系模型（二维表格）三种。关系模型因结构简单、数学基础扎实成为主流，用关系（表）、元组（行）、属性（列）描述数据。层次模型用树形结构表示实体间联系，有且仅有一个根节点，节点间是一对多关系。典型代表为IBM的IMS系统。IMS网状模型用图形结构表示实体间联系，允许多个父节点，可表示多对多关系。典型代表为CODASYL标准。CODASYL关系模型用二维表格表示实体及联系，结构简单直观，有严格数学理论基础。关系即表、元组即行、属性即列，主键唯一标识元组。MySQLRelationalAlgebra关系代数关系代数是操作关系的形式化语言，基本运算包括并、差、交、笛卡尔积、选择、投影和连接。选择操作取满足条件的行，投影操作取指定的列，连接操作基于公共属性组合两个关系的元组。集合运算01并（∪）：R∪S包含属于R或属于S的所有元组（去重），要求R和S具有相同的属性结构02差（-）：R-S包含属于R但不属于S的元组；交（∩）：R∩S包含同时属于R和S的元组03笛卡尔积（×）：R×S将R的每个元组与S的每个元组组合，结果关系的元组数为R和S元组数之积专门关系运算01选择（σ）：从关系中选取满足给定条件的元组，是水平方向的操作（