计算机二级公共基础笔记

整理一下二级笔记。说真的借着二级的机会系统的刷一遍各种专业课还是挺爽的。希望自己不局限于背题吧，很多人都说二级没用，虽然确实是如此，但是借此机会学习何乐而不为呢。

然而由于时间有限，有所选择的省略，这份笔记并不完整，部分只是刚要方便检索。因此这份笔记不能单独拿出来看，更多是配合书籍与题目~

2021-07-25: 重新上传到网站，已经过了，不过感觉公共基础部分答的一般，主要是后面又有点偷懒了，这些内容以后希望能深入学习吧~下次做相关笔记就是考研408之类的东西了~加油！

计算机系统

该部分属于新加内容。

概述

1. 体系架构：
   • 冯·诺依曼架构(存储程序控制)
     • 计算机硬件由运算器、存储器、控制器、输入设备、输出设备组成。
     • 计算机内部使用二进制来表示指令和数据。
   • 非冯诺依曼架构：数据驱动、需求驱动、模式匹配驱动。
2. 计算机系统的组成图

硬件系统

基本硬件系统

• 中央处理器
• 存储器
• 输入设备
• 输出设备

存储器

高速缓存：解决CPU和主存之间速度匹配的问题。

数据的内部表示

1. 进制转换
   一个数X记作r进制的形式($a {n-1}a {n-2}….a {0}·a {-1}a {-2}….a {-m}$)，则其整数部分为n位，小数部分为m位，其值为： $$X = a_{n-1}r^{n-1} + a_{n-2}r^{n-2} + …… + a_{0}r^{0} + a_{-1}r^{-1}+a_{-2}r^{n-2}+a_{-m}r^{-m}$$ 或 $$(X)_{r} = \sum\limits_{i=-m}^{n-1} a_ir^i$$
2. 定点数的表示和运算
   1. 无符号数
   2. 符号位
   3. 补码

数据结构与算法

算法复杂度

1. 时间复杂度：执行算法所需要的计算工作量。

   可以用算法执行过程中所需基本运算的执行次数来度量算法的工作量。
   算法所执行的基本运算次数与问题的规模有关。
   与数据的存储结构也有关
   时间复杂度与所用的计算工具无关

2. 空间复杂度：执行算法所需要的内存空间。

   算法的时间复杂度与空间复杂度没有直接关系

3. 一个算法所占用的存储空间包括程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
   其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间相对于问题规模来说是常数，则称该算法是原地(in place)工作的。

4. 算法的有穷性，是指算法必须在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。

数据结构的基本概念

1. 数据的逻辑结构，是指反应数据元素之间关系的数据元素结合的表示。 即带有结构的数据元素的集合。
   • 数据元素的前后关见系是指逻辑关系。
   • $B = (D,R)$ ， 即 $B: \ D->R$ (R是D的后件，D是R的前件。)
   • 数据结构的图形表示、线性结构与非线性结构

用集合表示一个数据结构$B=(D,R)$其实就是这样子：

$$\begin{aligned} &D= \{d_{i}|1\leq i\leq7\} = \{d_{1},d_{2},d_{3},d_{4},d_{5},d_{6},d_{7}\}\\[2ex] &R= \{(d_{1},d_{3}),(d_{1},d_{7}),(d_{2},d_{4}),(d_{3},d_{6}),(d_{4},d_{5})\} \end{aligned}$$

他也可以用结构图表示：

其中，没有前件的节点成为根节点，没有后件的节点称为终端节点（叶子节点）。

啥是线性数据结构：
一个非空的数据结构如果满足以下两个条件：

• 有且只有一个根节点；
• 每一个节点最多有一个前件，也最多有一个后件。
  前图所示就是一个线性结构，非线性则正相反。
  所以此类题型只需对所给数据结构判断出根节点的数量与是否只有一个前后件。

例题

上个例题看看：

我们可以画图，也可以写出关系，每个括号前后分别代表着前者是后者的前件。
因此，
其中
A选项，2->5->4, 4->3->1 ，线性。
B选项，1->2->3->4->5，线性。
C选项，1->2->3->5, 4->3, 3有两个根节点，非线性。
如下图：

D选项，5->4->3>2->1，线性。

数据的存储结构是指数据的逻辑结构在计算机中的表示

• 一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。

线性表

顺序表在线性表中寻找最大项时，除了最大项本身以外，其余所有项都需要和相 邻的数据进行比较，需要比较的次数至少是 n-1。

存储结构(物理)

1. 栈(stack) 是限定在一端进行插入与删除的线性表，是有序的存储结构。
   因为栈只能在一端进出，所以先插入的元素要等后插入的元素出栈后才能被删除，即先进后出，或后进先出。

   可以形象记忆为子弹上膛，往后塞进去子弹，不断地向内走，最后进去的子弹是最先射出去的。

   允许插入与删除的一端为栈顶，指针记作top；不允许插入与删除的一端是栈底，指针记作bottom。栈底指针不变，栈中元素随栈顶指针的变化而动态变化。

   栈的顺序存储及运算:

   (1) 入栈，插入新元素。若top已指向最后位置，则栈满，出现overflow溢出。top未指向最终位置，则top+1，x插入top+1所在位置。

   (2) 退栈，取出栈顶元素赋给指定变量。若top=0，则栈空，无法读取。若栈非空，将栈顶元素赋给指定变量，栈顶指针退一。

   (3) 读栈顶，同退栈，但不会删除栈顶元素，top指针不会改变。

   存储空间Q(1:N)的栈若初始状况下top=N+1或bottom>top时，该栈是一个下压栈，bottom=N，top指针逐级递减，元素数量为N-top+1。

2. 队列(queue) 是在一端进行插入，另一端进行删除的线性表。因此最先插入的元素可以先被删除，即先进先出或后进后出。

   插入端为队尾，指针记作尾指针(rear)。删除端为队头，指针记作头指针(front)

   实际应用中，队列的顺序存储结构一般采用循环队列，即当存储空间的最后一个位置被使用后，只要第一个位置空闲就可以将元素添加到第一个位置，将第一个位置作为队尾。

   循环队列的动态变化需要头尾指针共同反映。

   存储空间Q(1:N)下循环队列初始状态为front=rear=N

   经历一系列出对入队运算后:

   若front=rear=X，则此时元素数量为0或N

   若rear>front，元素数量为rear-front

   若front>rear，元素数量为rear-front + N

   后两条就简单为：尾减头（rear-front），若为负加（存储空间的）上限。

   相关服务：到先服务的作业调度、操作系统中的作业调度。

3. 线性链表

常见题型中的图形

1. 强连通图
   强连通图（Strongly Connected Graph）是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。
   有n个顶点的强连通图最多有n（n-1）条边，最少有n条边。

程序设计基础

软件工程基础

软件危机与软件工程

软件危机

1. 需求增长得不到满足
2. 开发成本与进度无法控制，成本不断提高。
3. 质量难以保证
4. 维护程度低或不可维护
5. 生产率的提高与硬件发展和需求增长不匹配

工程概念

1. 定义：应用计算机科学理论和技术以及工程管理的原则和方法，按照预算和进度，实现满足用户需求的软件产品的定义、开发、发布和维护的工程或进行研究的学科。
2. 将系统化、规范的、可度量的方法应用于软件开发、运行和维护的过程，即工程化应用于软件中。
3. 软件工程的三要素：方法、工具和过程。 方法是完成工程项目的技术手段，工具支持软件的开发、管理文件生成。过程支持软件开发各个环节的控制、管理。

过程与生命周期

软件过程

软件过程是软件开发为自己规定的工作步骤，是综合软件工程方法和工具以达到合理及时开发的目的。

Ⅰ P(plan) ——软件规格说明。 规定软件的功能及其运行时的限制。

Ⅱ D(do) ——软件开发或软件设计与实现。 生产满足规格说明的软件

Ⅲ C(check) —— 软件确认。 确认软件能够满足客户提出的要求。

Ⅳ A (action) —— 软件严谨。 为满足各户的变更要求，必须在使用过程中演进。

软件生命周期

software life cycle

1. 定义阶段：

   • 可行性研究、初步项目计划
   • 需求分析 “做什么”
     软件需求规格说明书：是需求分析阶段的最后成果，是软件开发的重要文档之一。软件需求规格说明书有以下几个方面的作用。①便于用户、开发人员进行理解和交流;②反映出用户问题的结构，可以作为软件开发工作的基础和依据;③作为确认测试和验收的依据。

2. 开发阶段：

   • 总体设计
   • 详细设计
   • 编码
   • 测试
3. 维护阶段：
   • 使用
   • 维护
   • 退役

结构化分析方法

1. 数据流图（DFD）
2. 数据字典（DD）

结构化设计方法

基本概念

1. 抽象
2. 逐步求精和模块化
3. 信息隐蔽和局部化
4. 模块独立性

   模块独立性是模块化、抽象、信息隐蔽和局部化概念的直接结果。
   模块独立性由耦合性和内聚性来度量，高内聚，低耦合。

详细设计

1. 程序流程图
2. N-S图
3. PAD图
4. PDL

软件测试

静态测试

代码检查、静态结构分析、代码质量度量。

动态测试

黑盒测试：等价划分法、边界值分析法、错误推测法。

白盒测试：

• 逻辑覆盖
  • 语句覆盖
  • 基本路径测试
  • 判定覆盖
  • 判断-条件覆盖
• 基本路径测试

数据库设计基础

数据库系统的发展

	人工管理	文件系统	数据库系统
应用背景	科学计算	科学计算、管理	大规模管理
硬件背景	无直接存取设备	磁盘、磁鼓	大容量磁盘
软件背景	无操作系统	有文件系统	数据库管理系统
管理者	人	文件系统	数据库管理系统
面向对象	某个应用程序	某个应用系统	现实世界
数据共享程度	无共享，冗余度大	共享性差，冗余度大	共享性大，冗余度小
数据独立性	不独立，完全依赖于程序	独立性差	具有高度的物理独立性和一定的逻辑独立性
数据结构化	无结构	记录内有结构，整体无结构	整体结构化，用数据模型描述

基本特点

1. 集成性
2. 高共享性与低冗余性
3. 独立性（物理与逻辑）
   • 数据独立性是数据与程序间的互不依赖性，即数据库中数据独立于应用程序而不依赖于应用程序。也就是说，数据的逻辑结构、存储结构与存取方式的改变不会影响应用程序。
4. 统一控制与管理

内部结构体系

1. 概念模式。 全局数据逻辑结构的描述，不涉及硬件环境与平台，与软件环境无关。
2. 外模式。 子模式、用户模式。 是用户的数据视图，即用户缩减的数据模式。
3. 内模式。 物理模式。物理存储结构与物理存取方法。

数据库语言

数据定义语言（DDL）：该语言负责数据的模式定义与数据的物理存取构建。

数据操纵语言（DML）：该语言负责数据的操纵，包括查询及增、删、改等操作。

数据控制语言（DCL）：该语言负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能。

SQL，结构化查询语言（Structured Query Language）是一种数据库查询和程序设计语言，用于存取数据以及查询、更新和管理关系数据库系统。集以上三者于一体。

数据模型

（略）