计算机二级公共基础知识点考点整理

Skyforever2025-03-112025-03-17

以下内容在c语言中占了40分，所以考c语言二级必看，如果是考wps二级之类的话就不用看

这个资料分为了两部分：

计算题部分穿插在c语言选择题中30分
记忆题部分只占了10分，所以几乎不用看记忆部分

一、计算题部分讲解

1.进制转换

十进制数转换为二进制

方法：将十进制数除以2，取余数，倒序排列。

2.原码反码补码偏移码的计算

原始规则：

正数：原码=反码=补码
负数的反码：符号位为1，原码数值位取反
负数的补码：反码+1
偏移码=补码符号位取反

选择题中的绕口令：

反码的反码 = 原码
补码的补码＝原码
补码之和 = 和的补码
引入补码之后，带符号数的加减运算都可以用加法实现
整数在计算机中的存储和运算，通常采用补码

3.线性结构的判断

线性表特点：表中的每一个数据元素：

除了第一个外，有且只有一个前件，
除了最后一个外，有且只有一个后件。

简单说，就是用一条线能吧所有元素串在一起

例题：

设元素集合为D={1, 2, 3, 4, 5, 6}，B=(D,R)为线性结构所对应的R是

A.R={(6,1),(5,6),(1,3),(2,4),(3,2)}
B.R={(4,5),(6,1),(5,6),(1,3),(2,4),(3,2)}
C.R={(6,1),(5,6),(1,3),(2,4),(3,2)}
D.R={(6,1),(5,6),(2,3),(2,4),(3,2)}

此题选A，A选项5-6-1-3-2-4能连成一根线，首尾不连接

4.栈和队列元素的增删计算

栈的特点
- 栈顶/栈底
- 先进后出、后进先出（迟到早退）
- 具有记忆功能
  - 子程序调用
  - 函数调用
  - 递归调用
队列
- 队头/队尾
- 先进先出、后进后出
- 队列的应用
  - 操作系统中的工作调度，
  - 若工作的优先权相同，则采用先到先操作的原则。

5.栈中元素个数的计算

需要分栈的升降序

当初始状态top值小于1

栈底序号为1，序号越往上走越大
当初始状态top值大于存储空间最大序号n

栈底序号n为最大序号，序号越往上走越小

栈底的最小值会超出栈的范围（0或者n+1),这个栈底位置不存数据！只存栈的状态）

6.循环队列元素个数的计算

Rear指向队列最后一个元素的位置
Front指向队列第一个元素的位置

指针情形

指针情形	队列中元素个数
Rear=front	0或容量为满
Rear>front	Rear-front
Rear<front	Rear-front+总容量

顺序查找

长度为n的线性表，找到某个特定元素，最坏需要比较n次，最坏需要比较n-1次
长度为n的线性表，找到最大（最小）值，最坏需要比较n次最坏需要比较n-1次

7.树中元素个数的计算

树的特点

父节点
- 在树结构中，每一个结点只有一个前件，称为父结点。
根节点
- 没有前件的结点只有一个，称为树的根结点，简称树的根。
子节点
- 每一个结点可以有多个后件，称为该结点的子结点。
叶子节点
- 没有后件的结点称为叶子结点。
节点的度
- 一个结点所拥有的后件的个数称为该结点的度。
树的度
- 所有结点中最大子节点个数称为树的度。
树的深度
- 树的最大层次称为树的深度。

树的节点个数计算

父节点树相加
度数与对应的节点数乘积之和 +1

例题：

度为3的一棵树共有30个结点，其中度为3、1的结点个数分别为3、4，则该树中的叶子结点数为（）。

A. 14
B. 15
C. 16
D. 不可能有这样的树

对应解法：

根据树的基本性质：
树的叶子结点数（ $L$ ）可以通过如下公式计算：

$L = N - \sum (\text{度数} \times \text{该度数的结点数})$

其中，

$N = 30$ （总节点数）
度为3的结点数为3，则它们贡献的子节点数为 $3 \times 3 = 9$
度为1的结点数为4，则它们贡献的子节点数为 $4 \times 1 = 4$
假设度为2的结点数为 $x$ ，则它们贡献的子节点数为 $2x$

根据上面给的计算方法：

$30 - 1 = 9 + 4 + 2x + L$

$29 = 13 + 2x + L$

$L = 16 - 2x$

由于树的度数最高为3，度为2的结点数量 $x$ 可能为0（即所有非叶子节点度为3或1），因此：

$L = 16 - 2 \times 0 = 16$

所以，正确答案是：
C. 16

8.二叉树的计算

基本性质

性质1 ：在二叉树的第 $k$ 层上，最多有 $2^{(k-1)} \ (k \geq 1)$ 个结点。
性质2 ：深度为 $m$ 的二叉树最多有 $2^m - 1$ 个结点。
性质3 ：在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。
性质4 ：具有 $n$ 个结点的二叉树，其深度至少为 $\lfloor \log_2 n \rfloor + 1$ ，其中 $\lfloor \log_2 n \rfloor$ 表示取 $\log_2 n$ 的整数部分。

特殊二叉树

满二叉树：每一层上的所有结点都有两个子结点。
完全二叉树：
- 除了最后一层，每一层都达到最大节点数，最后一层只缺少右侧节点。
- 完全二叉树总结点个数，是奇数，度为1的结点个数为0个；是偶数，度为1的结点个数为1个。

二叉树遍历结构

A下面有两个子节点，左到右为B-C

按照三种不同的排序排出来为（根在哪里就是什么序）：

前序	中序	后序
根-左-右	左-根-右	左-右-根
ABC	BAC	BCA

9.扇入数，扇出数，宽度

扇入数：指一个节点的输入边的数量，即有多少个其他节点指入该节点，注意是只看本节点的入数。
扇出数：指一个节点的输出边的数量，即该节点往下指出多少个其他节点，注意是只看本节点的出数。
结构图宽度：指的是宽度最大一层的宽度

10.传统集合运算

计算机二级考这部分的选择题，一般可以根据图的特点判断，下面后面括号里的就是特点

并（Union）

将两个集合中的所有元素合并成一个新集合，并去除重复元素（特点是行数增加）

交（Intersection）

返回同时属于两个集合的共同元素，即两个集合的交集（特点是行数减少）。

差（Difference）

返回属于第一个集合但不属于第二个集合的元素，即集合的差集。

下面的情况考的不多

笛卡儿积：两个集合的笛卡儿积是指将每个元素与另一个集合的每个元素两两组合，形成所有可能的有序对（特点是行数和列数都增加）。
商运算：两个集合做除法（特点是行数和列数都减少）。

11.数据库关系运算

除开上面的运算，还有下面的这几种运算

基本关系运算

选择：从关系中筛选满足特定条件的元组（行），一般用σ表示。
投影：从关系中选择特定的属性（列），一般用π表示。

连接运算

自然连接：基于同名属性匹配并合并两个关系的数据。
等值连接：通过相等条件进行连接。
一般情况下，商运算得到的结果**一定和除数完全相关**

12.三大范式

直接看本网站数据库复习的部分

二、记忆题部分速记

01 计算机系统概述

概述
- 计算机产生与发展
  - 冯诺依曼
    - 存储程序控制
    - 二进制
    - 计算机五大组成部分
      - 运算器
      - 控制器
      - 存储器
      - 输入设备
      - 输出设备
  - 计算机硬件发展阶段
    - 电子管
    - 晶体管
    - 小规模集成电路
    - 大规模、超大规模集成电路
- 计算机系统
  - 硬件系统
    - 主机
      - CPU（中央处理器）
        
        由运算器和控制器构成
        
        性能指标：字长和主频
      - 内存（主存储器）
        
        ROM
        
        断电后数据不会消失
        
        信息由生产厂家先写入
        
        RAM
        
        断电后数据会消失
        
        SRAM：静态随机存储器
        
        DRAM：动态随机存储器
    - 外设
      - 外存储器
      - 输入设备
      - 输出设备
  - 软件系统
    - 系统软件
      - 操作系统
      - 语言处理系统
      - 数据库系统
    - 应用软件
      - 文字处理软件
      - 图像处理软件
      - 辅助设计软件
      - Internet 工具软件

02 存储器考点

存储器
- ★寄存器
  - 分布在CPU内部的高速存储器
  - 保存正在执行的指令，保存中间数据、操作数
  - CPU不经过总线能直接访问的是寄存器
- ★CACHE 高速缓冲存储器
  - 解决CPU和内存速度不匹配
- 内存储器
  - ROM和RAM
- 外存储器
  - 硬盘
  - 光盘
  - U盘
- 读取速度排序
  - 寄存器 > 缓存 > 内存 > 外存
- 程序局限性
  - 时间局部性
    - 如果一个存储项被访问，则该项在近期可能很快被再次访问
  - 空间局部性
    - 如果一个存储项被访问，则该项及其邻近的项也可能很快被访问

03 机器指令

机器指令
- 定义
  - 计算机可直接识别和执行的命令
- 组成
  - 操作码：执行什么操作
  - 操作数：操作的对象（数据或者地址）
- 操作数地址
  - 有效地址（真实地址）
  - 形式地址（需按寻址方式转换成有效地址）
- ★寻址方式
  - 目标：确定本条指令的数据地址与下一条将要执行的指令地址
  - 指令寻址
    - 顺序寻址
    - 跳跃寻址
  - ★数据寻址
    - 立即寻址：地址码直接给出操作数
    - 直接寻址：地址码给出的是操作数的地址
    - 间接寻址：地址码部分给出的是操作数的地址
    - 隐含寻址：操作数的地址隐含在固定的地址或寄存器中
- 指令系统
  - 计算机的所有指令的集合称指令系统
  - 不同的计算机指令系统各有不同（指令条数、操作码、地址码）
- 指令周期
  - 计算机完成一条指令所花费的时间

04 总线

总线
- 作用
  - CPU可以通过总线访问计算机内存和各种输入输出设备
  - ★ 易考：CPU不经过总线能直接访问的是寄存器
- 分类
  - 片内总线
    - CPU芯片内部连接各元件的总线
  - ★ 系统总线
    - 地址总线（单向）
      - 地址总线的位数决定CPU直接寻址的内存范围
    - 数据总线（双向）
    - 控制总线（双向）
  - 通信总线
    - 串行数据总线
    - 并行数据总线
- 性能指标
  - 总线宽度（数据总线根数）
  - 总线带宽（数据传输率）
  - 时钟同步/异步
    - 同步总线：通过使用统一的时钟信号来协调设备间的数据传输
    - 异步总线：不依赖统一的时钟信号进行数据传输

05 操作系统

操作系统主要特征

共享性
异步性
虚拟性
并发性

主要功能

进程管理
- 进程：程序在内存中运行的基本单位
- 进程管理的任务：
  1. 进程的创建
  2. 进程的终止
  3. 进程的调度
  4. 进程的同步和通信
- 进程控制块（PCB）：存储进程控制信息
- 进程的状态：
  - 就绪：等待CPU分配
  - 运行：正在执行
  - 阻塞：等待某些事件完成
存储管理
- 地址重定位方式
  - 静态重定位
  - 动态重定位
- 存储管理技术
  - 连续分区存储管理
    - 固定分区存储管理
    - 可变分区存储管理
  - 分页存储管理
  - 分段存储管理
  - 段页式存储管理
- 虚拟存储器
  - 通过存储管理提高CPU的效率
  - 采用请求分页、请求分段方式进行存储
文件管理
- 负责存取和管理文件系统
- 组织文件的存储结构
设备管理
- I/O控制：操作系统用于管理输入输出设备的技术
- 方式
  - 程序查询：CPU查询设备状态
  - 中断驱动：CPU执行其他任务，设备准备好时发出中断
  - DMA（直接存储访问）：数据由I/O设备直接存取内存
  - 通道方式：独立的处理单元管理I/O操作

06 I/O 控制方式

概述

I/O 控制方式是计算机系统中用于管理和控制输入输出操作的一组技术。

方式

程序查询
- 程序主动查询 I/O 设备是否准备好
程序中断
- 当出现异常或特殊情况时，CPU 停止当前程序的运行，转而执行对这些情况进行处理的程序（中断服务处理程序）
DMA（直接内存存取）
- I/O 设备不经过 CPU 的情况下直接与内存交换数据
通道方式
- 通过独立的通道处理器来控制 I/O 操作，使得 CPU 可以更高效地处理其他任务
- 增加计算机系统的并行程度

07 算法

定义

算法是解决问题的方法和步骤。
程序可以作为算法的一种描述方法，但算法 ≠ 程序。

四个特点

确定性：每条指令有明确含义
可行性：在经过有限次运算后得到结果
有穷性：有穷时间内可以执行完
- 补充：算法是有穷的，程序可以是无穷的
输入输出：
- 0 个或多个输入
- 1 个或多个输出

算法的控制结构

顺序结构
选择结构（分支结构）
循环结构（重复）

衡量算法的优劣标准

时间复杂度：需要运算的次数（工作量）
空间复杂度：
- 程序代码所占空间
- 输入数据所占空间
- 程序运行所需的额外空间
- 补充：
  - 原地工作：执行算法时不需要额外辅助空间
  - 额外辅助空间固定，不随输入数据规模增长
注：时间复杂度与空间复杂度没有直接关系

08数据结构

逻辑结构

定义

数据元素在逻辑上的前后件关系。
数据的逻辑结构与所使用的计算机无关。

存储结构

定义

数据元素在计算机上的存储关系。
算法的执行效率与数据的存储结构有关。

关系

线性表可以采用顺序存储，也可以采用链式存储
非线性表可以采用顺序存储，也可以采用链式存储

数据结构的表达

数据元素的集合：d
数据的前后件关系：r
示例：
- 数据集合 D = {1,2,3,4}
- 前后件关系 R = {(1,2), (2,3), (3,4)}

09 栈与队列

栈

栈：只允许在一端（栈顶）插入或删除的线性表。

结构

栈顶/栈底
特点：先进后出，后进先出

应用

子程序调用
具有记忆功能
- 函数调用
- 递归调用

存储方式

顺序存储
链式存储

栈中元素个数（计算题）

TOP 小于等于 0
TOP 大于最大容量值

队列

队列：只允许在一端进行插入，在另一端删除的线性表。

结构

在队尾添加记录
在队头删除记录
特点：先进先出，后进后出

循环队列元素个数（计算题）

rear = front → 0 或满
rear > front → rear - front
rear < front → rear - front + 总容量

队列的应用

操作系统中的工作调度
- 若工作的优先权相同，则采用先到先得的原则。

10 查找与排序技术

查找技术

顺序查找

适用于长度为 n 的线性表，查找特定元素。
最坏情况：需要查找 n 次。
平均比较次数： (n+1)/2 次。
可用于查找最大（最小）值，最坏情况需要比较 n-1 次。

二分法查找（对分查找）

只适用于顺序存储的有序表。
最坏情况：查找特定元素时需要 log₂(n) 次比较。

排序技术

交换类排序

冒泡排序
快速排序（适用于顺序存储的线性表）

插入类排序

简单插入排序
希尔排序（每次数据元素的移动可以消除多个逆序）

选择类排序

简单选择排序
堆排序（时间复杂度最小）

重点-排序方法及时间复杂度

类别	排序方法	时间复杂度
交换类	冒泡排序	N(N-1)/2
	快速排序	N(N-1)/2
插入类	简单插入排序	N(N-1)/2
	希尔排序	O(n^1.5)
选择类	简单选择排序	N(N-1)/2
	堆排序	O(nlog₂n)（最小）

11 软件工程基础

软件的组成

软件是包括程序、数据及相关文档的完整集合。

功能分类

系统软件

操作系统
数据库管理系统
编译程序
汇编程序

应用软件

支撑软件

软件工程

源于软件危机

软件危机可归结为成本、质量、生产率等问题。

三要素

方法
工具
过程

软件生命周期

软件定义阶段

问题定义
可行性研究
需求分析

软件开发阶段

概要（总体）设计
详细设计
软件实现
软件测试

软件运行维护阶段

软件生命周期中花费最多的阶段是软件运行维护阶段。

12 需求分析（做什么）

主要任务

确定软件系统的功能（做什么）

2种方法

结构化分析方法
面向对象的分析方法

4个步骤

需求获取
需求分析
- 需求分析的最终结果
- 软件设计和交付的依据
编写软件需求规格说明书
需求评审

4种工具

数据字典 DD
- 数据字典的作用是对数据流图中出现的被命名的图形元素的确切解释。
- 数据字典是结构化分析方法的核心。
- 作用：支持软件系统功能建模。
数据流图 DFD
- 梳理或存贮：数据处理
- 箭头：数据流
- 双线：表示数据存储，又称为文件。
- 矩形：源、池
判定树
判定表

13 软件设计（怎么做）

总体设计（概要设计）

主要任务：确定软件系统的整体结构、模块划分、接口和数据流等
模块的两个定性指标
- 耦合性：不同模块之间相互链接的紧密程度
- 内聚性：单个模块内部各元素间彼此结合的紧密程度
- 目标：高内聚、低耦合
系统总体结构图
- 风入数、风出数、宽度、深度
- 示例图
总体设计完成后，需要编写概要设计文档

详细设计

主要任务：确定每个模块的算法和使用的数据结构，并用特定表达工具表示细节
程序流程图
图形工具
- N-S（方盒图）
- PAD（问题分析图）
- HIPO（层次图 + 输入/处理/输出图）
表格工具
- 判定表
语言工具
- PDL（伪码）

14 软件测试（找错误）

软件测试的目的

发现错误

测试方法

按是否被运行
- 静态测试（不运行）
- 动态测试（运行）
是否考虑软件内部逻辑结构
- 白盒测试
  - 逻辑覆盖测试
  - 基本路径测试
  - 等价类别划分
- 黑盒测试
  - 边界值分析法
  - 错误推测法

软件测试的四个步骤

单元测试
- 依据：编码和详细设计说明书
- 测试内容：模块的接口、局部数据结构和出错处理能力
集成测试
系统测试
确认测试

测试用例

测试数据
预期结果
测试环境
操作步骤

其他测试原则

软件测试严格执行测试计划，排除测试的随意性
软件调试的目的是改正软件错误

15 数据库系统

基本术语

数据库系统（DBS） 包括数据库（DB）和数据库管理系统（DBMS）
DBMS是DBS的核心

数据管理三大发展阶段

人工管理阶段
文件系统阶段
数据库系统阶段

数据库系统特点

集成性高
高共享低冗余
数据独立性高
数据的统一管理与控制

数据库语言

数据定义语言
- 对概念模式内容进行说明
数据操纵语言
- 负责数据的增删改查等操作
数据控制语言
- 支持安全性定义和检查

数据库系统三级模式

内模式（物理模式）
- 反映物理存储形式，只有一个
外模式（用户模式）
- 反映用户的需求，可有多个
概念模式（逻辑模式）
- 反映全局逻辑要求，只有一个

三级模式的作用

物理独立性
逻辑独立性
保持数据库的独立性

16 数据库与数据模型

关系型数据库

记录（元组）：二维表中的每一行信息
字段（属性）：二维表中的每一列信息
关系（二维表）：一张二维表就是一个关系

约束：

候选码：能唯一标识一行记录的字段（例如学号字段）
主码：从多个候选码中选出一个，以它作为唯一关键字
外码（外部关键字）：如果表A的某字段是表B的主码，则A这个字段就是外码
全码：极个别情况下，表的所有字段组合成主码

数据模型

基本概念

实体：实体是具有特定属性的对象或事物
属性：事物的特征
联系：事物之间的关系
- 一对一
- 一对多
- 多对多

三大要素

数据结构
数据操作
数据约束
- 参照完整性
- 实体完整性
- 自定义完整性（相当于设置数据库约束规则）
- 面向宏观世界和用户

数据模型分类

概念数据模型
- ER模型
  - 矩形：实体
  - 椭圆：属性
  - 菱形：联系
逻辑数据模型
- 按照数据之间的联系方式划分
  - 层次模型
  - 网状模型
  - 关系模型
物理数据模型
- 面向计算机物理存储

数据库设计

四个阶段

需求分析阶段 - 形成软件需求说明书
概念设计阶段 - ER模型
逻辑设计阶段 - ER模型 → 关系模型
物理设计阶段

规范化

第一范式（1NF）：关系中的每个属性都不可分
第二范式（2NF）：在1NF的基础上，消除非主属性对主码的部分依赖
第三范式（3NF）：在2NF的基础上，消除非主属性对主码的传递依赖

一 、计算题部分讲解

1.进制转换

2.原码反码补码偏移码的计算

原始规则：

选择题中的绕口令：

3.线性结构的判断

4.栈和队列元素的增删计算

5.栈中元素个数的计算

6.循环队列元素个数的计算

指针情形

顺序查找

7.树中元素个数的计算

树的特点

树的节点个数计算

例题：

对应解法：

8.二叉树的计算

基本性质

特殊二叉树

二叉树遍历结构

9.扇入数，扇出数，宽度

10.传统集合运算

并（Union）

交（Intersection）

差（Difference）

11.数据库关系运算

基本关系运算

连接运算

12.三大范式

二、记忆题部分速记

01 计算机系统概述

02 存储器考点

03 机器指令

04 总线

05 操作系统

操作系统主要特征

分类

主要功能

06 I/O 控制方式

概述

方式

07 算法

定义

四个特点

算法的控制结构

衡量算法的优劣标准

08数据结构

逻辑结构

定义

分类

存储结构

定义

分类

关系

数据结构的表达

09 栈与队列

栈

结构

应用

存储方式

栈中元素个数（计算题）

队列

结构

循环队列元素个数（计算题）

队列的应用

10 查找与排序技术

查找技术

顺序查找

二分法查找（对分查找）

排序技术

交换类排序

插入类排序

选择类排序

重点-排序方法及时间复杂度

11 软件工程基础

软件的组成

功能分类

系统软件

应用软件

支撑软件

一、计算题部分讲解