软件设计师笔记

2023-09-09学习64 分钟270 次阅读
AI 摘要salmon-ai

本文详细解析了软件设计师备考笔记中的核心知识点,涵盖计算机组成原理、数据结构与算法、算法设计与分析,以及操作系统基础。内容包括原码、反码、补码、移码

前言

本文源于观看【B站UP主:学以致知Learning】的【2023软件设计师备考】软考中级 | 软件设计师考点理论精讲【零基础适用】视频所做的笔记记录,在此感谢该UP主。

第一章 计算机组成原理与体系结构基础知识

1、数据的表示

原码、反码、补码与移码

  • 原码:用数值部分表示真值的绝对值,符号位“0/1”对应”正负“,若机器字长n+1位,则数值部门(尾数)占n位;
  • 反码:若符号位为0,则反码与原码相同。若符号位为1,则数值位全部取反。若机器字长n+1位,反码整数的表示范围:−(2n−1)≤x≤2n−1-(2^n-1)\le x\le 2^n-1;
  • 补码:正数的补码=原码,负数的补码=反码末位+1(要考虑进位),若机器字长n+1位,补码整数的表示范围:−2n≤x≤2n−1-2^n\le x\le 2^n-1(比原码多表示一个−2n-2^n);
  • 移码:补码的基础上将符号位取反。注意:移码只能用于表示整数,若机器字长n+1位,移码整数的表示范围:−(2n−1)≤x≤2n−1-(2^n-1)\le x\le2^n-1(与补码相同)。

例子

x=+19Dx=+19D
[x]原=00010011[x]_\text{原}=00010011
[x]反=00010011[x]_\text{反}=00010011
[x]补=00010011[x]_\text{补}=00010011
[x]移=10010011[x]_\text{移}=10010011

x=−19Dx=-19D
[x]原=10010011[x]_\text{原}=10010011
[x]反=11101100[x]_\text{反}=11101100
[x]补=11101101[x]_\text{补}=11101101
[x]移=01101101[x]_\text{移}=01101101

浮点数

浮点数是小数点位置不固定的数,它能表示更大范围的数,浮点数的表示格式如下图所示。在浮点表示法中,阶码通常为带符号的纯整数,尾数为带符号的纯小数。
image.png
浮点数通常表示成

N=M⋅REN=M\cdot R^E

其中,M称为尾数,R称为基数,E称为阶码。
阶码,决定浮点数所能表示的数值范围;
阶尾数,决定浮点数所能表示的数值精度。

2、校验码

奇偶校验和循环冗余校验码(非重点)

    奇偶校验是一种简单有效的校验方法。其基本思想是:通过在编码中增加一位校验位来使编码中1的个数为奇数(奇校验)或者为偶数(偶校验),从而使码距变为 2。对于奇校验.它可以检测代码中奇数位出错的编码,但不能发现偶数位出错的情况,即当合法编码中奇数位发生了错误,也就是编码中的1变成0或0变成1,则该编码中1的个数的奇偶性就发生了变化,从而可以发现错误。

    常用的奇偶校验码有 3 种:水平奇偶校验码、垂直奇偶校验码和水平垂直奇偶校验码。

海明码

海明码的构成方法是:在数据位之间插入k个校验码,通过扩大码距来实现检错和纠错。

设数据位是n位,校验位是k位,则n和k必须满足一下关系

2k−1≥n+k2^k-1 \ge n+k

例子

已知数据信息为16位,最少应附加__位校验位,才能实现海明码纠错。
A、3  B、4  C、5  D、6

答:我们可以将A~D选项的值依次代入,当k=5k=5时,25−1=31>16+52^5-1=31>16+5,因此最少应附加5位校验位,才能实现海明码纠错。

3、计算机体系结构

概括

image.png
可形象成下边图例
image.png
小结
image.png

主存储器

image.png

CPU

运算器

image.png

控制器

  • 数据寄存器(Data Register,DR)又称数据缓冲寄存器,其主要功能是作为CPU和主存、外设之间信息传输的中转站。
  • 指令寄存器(Instruction Register,IR)用来保存当前正在执行的一条指令。
  • 程序计数器(Program Counter,PC)用来指出下一条指令在主存储器中的地址。
  • 地址寄存器(Address Register,AR)用来保存CPU当前所访问的主存单元的地址。
  • 指令译码器(Instruction Decoder,ID)对操作码进行分析。
    image.png

Flynn分类法

image.png

指令系统

指令

image.png

指令格式

image.png

寻址方式

image.png
image.png

CISC和RISC

image.png

指令的流水处理

image.png

流水线的计算

公式

流水线周期:执行时间最长的一段。
流水线公式:1条指令执行时间 +(指令条数)-1 * 流水线周期

吞吐率

流水线的吞吐率:是指在单位时间内流水线所完成的任务数量或输出的结果数量。
计算流水线吞吐率的最基本公式如下:

TP=指令条数流水线执行时间TP=\dfrac{\text{指令条数}}{\text{流水线执行时间}}

流水线开始工作后,须经过==一定时间==才能达到最大吞吐率,这就是==建立时间==。若m个子过程所用时间一样,均为Δto\Delta t_o,则建立时间To=m×ΔtoT_o=m \times \Delta t_o。

流水线的加速比

完成同样一批任务,不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比。计算流水线加速比的基本公式如下:

S=不使用流水线执行时间使用流水线执行时间S=\dfrac{\text{不使用流水线执行时间}}{\text{使用流水线执行时间}}

例子

若指令流水线把一条指令分为取指、分析和执行三部分,且三部分的时间分别是取指2ns,分析2ns ,执行1ns。
那么,流水线周期是多少?100条指令全部执行完毕需要的时间是多少?吞吐率?流水线的加速比?
image.png
答:流水线周期是2ns,
100条指令执行完毕需要的时间是:(2+2+1)+(100−1)×2=203(ns)(2+2+1)+(100-1)\times 2=203(ns),
吞吐率:TP=100203≈0.5TP=\dfrac{100}{203}\approx0.5,
不使用流水线的时间:5×100=5005\times100=500,则加速比为:S=500203≈2.46S=\dfrac{500}{203}\approx2.46

存储系统

层次结构

image.png
image.png

存储器的分类

  1. 按位置分类,可分为内存和外存。

    • 内存(主存,运行内存):用来存储当前运行所需要的程序和数据,速度快,容量小。
    • 外存(辅存):用来存储当前不参与运行的数据,容量大但速度慢。
  2. 按材料分类,可分为磁存储器、半导体存储器和光存储器。

    • 磁存储器:用磁性介质做成,如磁芯、磁泡、磁盘、磁带等。
    • 半导体存储器:根据所用元件可分为双极型和MOS型两类,根据是否需要刷新又可分为静态和动态两类。
    • 光存储器 :由光学、电学和机械部件等组成,如光盘存储器。
  3. 按工作方式,可分为读/写存储器和只读存储器。

    • 读/写存储器(RAM)它指既能读取数据也能存入数据的存储器。
    • 只读存储器(ROM)工作过程中仅能读取的存储器。
  4. 根据数据的写入方式,又可细分为ROM、PROM、EPROM和EEPROM等类型。
    ①固定只读存储器(ROM)。这种存储器是在厂家生产时就写好数据的。其内容只能读出,不能改变。一般用于存放系统BIOS和用于微程序控制。
    ②可编程的只读存储器(PROM)。其中的内容可以由用户一次性地写入,写入后不能再修改。
    ③可编程的只读存器(EPROM)。其中的内容既可以读出,也可以由用户写入,写入后还可以修改,紫外线照射擦除信息。
    ④电擦除可编程的只读存储器(EEPROM)。与EPROM相似,EEPROM中的内容既可以读出,也可以进行改写,电擦除的方法进行数据的改写。
    ⑤闪速存储器(Flash Memory)。简称闪存,闪存的特性介于EPROM和EEPROM之间类似于EEPROM,也可使用电信号进行信息的擦除操作。整块闪存可以在数秒内删除,速度远快于EPROM。

高速缓存Cache

image.png
要把主存种的地址映射为Cache存储器里面的地址,地址映像方法有三种

  1. 直接映像:就是主存的块与Cache中块的对应关系是固定的。这种方式的优点是地址变换很简单,缺点是灵活性差。
    image.png
  2. 全相联映像:允许主存的任一块可以调入Cache的任一块的空间。这种方式的优点是主存的块调入Cache的位置不受限制,十分灵活。其缺点是无法从主存块号中直接获得Cache的块号,变换比较复杂,速度比较慢。
    image.png
  3. 组相联映像:这种方式是前面两种方式的折中。具体方法是将Cache先分成组再分块。组相联映像就是组间采用直接映像方式,而组内的块采用全相联映像方式。
    image.png

选择替换算法的目标是使Cache获得最高的命中率。常用的替换算法有以下几种:

  1. 随机替换(RAND)算法:用随机数发生器产生一个要替换的块号,将该块替换出去。
  2. 先进先出(FIFO)算法:将最先进入的Cache信息块替换出去。
  3. 近期最少使用(LRU)算法:将近期最少使用的Cache中的信息块替换出去。这种算法较先进先出算法要好些,但此法也不能保证过去不常用的将来也不常用。
  4. 优化替换(OPT)算法:先执行一次程序,统计Cache的替换情况。有了这样的先验信息,在第二次执行该程序时便可以用最有效的方式来替换,达到最优目的。
性能分析
image.png
例子1

以下关于 Cache (高速缓冲存储器)的叙述中,不正确的是__。

A.Cache 的设置扩大了主存的容量
B.Cache 的内容是主存部分内容的拷贝
C.Cache 的命中率并不随其容量增大线性地提高
D.Cache 位于主存与 CPU 之间

答:选A,Cache本质是对主存的复制,并不是扩大。

例子2

以下关于 Cache 与主存间地址映射的叙述中,正确的是__。

A.操作系统负责管理 Cache 与主存之间的地址映射
B.程序员需要通过编程来处理 Cache 与主存之间的地址映射
C.应用软件对 Cache 与主存之间的地址映射进行调度
D.由硬件自动完成 Cache 与主存之间的地址映射

答:选D,Cache与主存之间的地址映射是由硬件自动完成的。

例子3

主存与 Cache 的地址映射方式中,____方式可以实现主存的任意一块装入 Cache 中任意位置,只有装满才需要替换。

A.全相联
B.直接映射
C.组相联
D.串并联

答:选A,全相联才可以主存的任意一块装入Cache中任意位置。
image.png

主存的编址

image.png
例子

image.png
答:(1)由K等于2102^{10},M等于2202^{20},G等于2302^{30},得:
C7FFFH+1=C8000HC7FFFH+1=C8000H
C8000H−AC000H=1C000HC8000H-AC000H=1C000H
1C000H=(00011100000000000000)21C000H=(00011100000000000000)_2
(00011100000000000000)2=(1110000)2⋅210=(26+25+24)⋅210=112K\begin{aligned}(00011100000000000000)_2 &=(1110000)_2\cdot2^{10}\\ &=(2^6+2^5+2^4)\cdot2^{10} \\ &=112K \end{aligned}
(2)112K×16b÷(28×16K)=4b112K\times16b\div(28\times16K)=4b

硬盘

image.png

总线系统

image.png
  1. 片内总线
        片内总线是芯片内部的总线。 它是CPU芯片内部寄存器与寄存器之间、寄存器与ALU之间的公共连接线。
  2. 系统总线
        系统总线是计算机系统内各功能部件(CPU、主存、I/O接口)之间相互连接的总线。按系统总线传输信息内容的不同,又可分为3类:数据总线、地址总线和控制总线。
  3. 通信总线

输入输出技术

CPU与外设之间的数据传送方式:

  1. 直接程序控制方式直接程序控制方式是指在完成数据的输入/输出中,整个输入/输出过程是在CPU执行程序的控制下完成的。这种方式还可以分为以下两种:
    • 无条件传送方式:无条件地与CPU交换数据。
    • 程序查询方式:先通过CPU查询外设状态,准备好之后再与CPU交换数据。
  2. 中断方式
  3. 直接存储器存取方式
    直接存储器存取(Direct Memory Access,DMA)方式是在存储器与I/O设备间直接传送数据,即在内存与I/O设备之间传送一个数据块的过程中,不需要CPU的任何干涉,是种完全由DMA硬件完成I/O操作的方式。

例子

image.png
答:选D,DMA方式,不需要CPU的任何干涉。

可靠性

计算机系统的可靠性是指从它开始运行(t=0)到某个时刻t这段时间内能正常运行的概率,用R(t)表示。

  • 串联部件的可靠度=各部件的可靠度的乘积。
  • 并联部件的可靠度=1-部件失效率的乘积。

例子

image.png
答:首先看左边三个并联的部件,三个部件失效率的乘积为(1−R)3(1-R)^3,所以该并联部件的可靠度为1−(1−R)31-(1-R)^3,同理可求出右边两个并联的部件的可靠度为1−(1−R)21-(1-R)^2,最后计算左右并联组件串联的可靠度,即R(t)=(1−(1−R)3)(1−(1−R)2)R(t)=(1-(1-R)^3)(1-(1-R)^2),故选B。

第二章 数据结构与算法基础

1、基本概念与三要素

数据

数据是信息的载体,是描述客观事务属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

数据元素、数据项

数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素由若干个数据项组成,数据项是构成数据数据元素不可分割的最小单位。

数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

三要素

image.png

逻辑结构

image.png
集合:各个元素同属一个集合,别无其他关系。
线性结构:数据元素之间是一对一的关系。除了第一个元素,所有元素都有唯前驱;除了最后一个元素,所有元素都有唯一后继。
树形结构:数据元素之间是 一对多的关系。
图结构:数据元素之间是多对多的关系。
image.png

物理结构

image.png

2、算法

程序 = 数据结构 + 算法

五个特性

有穷性:一个算法必须总在执行有穷步之后结束,且每一步都可在有穷时间内完成。
确定性:算法中每条指令必须有确切的含义,对于相同的输入只能得出相同的输出。
可行性:算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入:一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合。
输出:一个算法有一个或多个输出,这些输出是与输入有着某种特定关系的量。

算法效率的度量

image.png

时间复杂度

image.png

空间复杂度

image.png
image.png

3、线性表

image.png

定义

image.png

存储结构

image.png
image.png

插入删除操作

image.png

4、栈和队列

栈定义

image.png

队列定义

image.png
image.png

5、串、数组、矩阵和广义表

串

定义

image.png
image.png

基本操作

  1. 赋值操作StrAssign(s,):将串t的值赋给串s。
  2. 连接操作Concat(s,t):将串t接续在串s的尾部,形成一个新串。
  3. 求串长StrLength(s):返回串s的长度。
  4. 串比较StrCompare(s,t):比较两个串的大小。
  5. 求子串SubString(,tart,len):返回串s中从start开始的、长度为len的字符序列。

存储结构

  1. 串的顺序存储:定长存储结构。
  2. 串的链式存储:块链子串的定位操作通常称为串的模式匹配,它是各种串处理系统中最重要的运算之一。子串也称为模式串。

数组

image.png
答:由题意可知,i=2,j=3,m=4,n=4,则元素a[2][3]按行优先存储地址是:a+[i∗n+j]∗len=a+(2×4+3)×2=a+22a+[i*n+j]*len=a+(2\times4+3)\times2=a+22

矩阵

稀疏矩阵

image.png
例子

image.png
答:可以使用代入法,当A[0,0]时,对应M[1],将i=0,j=0依次代入上面四个选项,可以看到A与D满足A[0,0]=M[1],又A[1,0]对应M[2],所以将i=1,j=0代入A与D选项,计算可知A选项满足A[1,0]=M[2],故选A

广义表

image.png
答:1、长度为3,深度为2。
2、操作:head(head(tail(LS1)))。

6、树和二叉树

树的基本概念

image.png
  • 结点的度:结点子树的个数,比如结点1的度为2,结点3的度为1;
  • 树的度:树中最大的结点层,比如该树最大的度为2;
  • 叶子结点:没有子节点的结点,比如结点4、5、7、8;
  • 分支结点:度不为0的结点;
  • 内部结点:至少有一个孩子的结点,比如结点2、3、6;
  • 父结点:也叫双亲结点,相对于当前的结点而言,它的上层结点就叫做父结点;
  • 子结点:结点的子树的根称为该结点的子节点;
  • 兄弟结点:同一双亲的孩子结点;
  • 层次:树有几层,比如该树为4层。

二叉树

基本概念

image.png
image.png

遍历

image.png
  • 前序遍历:根左右,12457834
  • 中序遍历:左根右,42785136
  • 后序遍历:左右根,48752631
  • 层次遍历:12345678

反向构造二叉树

由前序序列为ABHFDECG;中序序列为HBEDFAGC构造二叉树。
image.png

树转二叉树

image.png

查找二叉树(二叉排序树)

image.png

哈夫曼树(最优二叉树)

例如:1,2,4,8
image.png
左边树的带权路径长度(树的代价)为:2×2+4×3+8×3+1×1=412\times2+4\times3+8\times3+1\times1=41
右边树的带权路径长度(树的代价)为:4×2+1×3+2×3+8×1=254\times2+1\times3+2\times3+8\times1=25

例:假设有一组权值5、29、7、8、14、23、3、11请尝试构造哈夫曼树。
image.png

先排序:3、5、7、8、11、14、23、29
接着先找出最小的两个数,将其作为兄弟结点,如下:
7、8(3+5)、8、11、14、23、29
接着继续:
8、11、14、15(7+8(3+5))、23、29
14、15(7+8(3+5))、19(8+11)、23、29
19(8+11)、23、29(14+15(7+8(3+5)))、29
42(19(8+11)+23)、58(29(14+15(7+8(3+5)))+29)
100(42(19(8+11)+23)+58(29(14+15(7+8(3+5)))+29))

线索二叉树

image.png

平衡二叉树

定义:任意结点的左右子树深度相差不超过1,每结点的平衡度只能为-1、0或1。

**例:对数列{1,5,7,9,8,39,73,88}构造排序二叉树,可以构造出多颗形式不同的排序二叉树。
**image.png

7、图

有向图

image.png

无向图

image.png

完全图

在无向图中,若每对顶点之间都有一条边相连,则称该图为完全无向图。如下:
image.png
在有向图中,若每对顶点之间都有两条有向边相互连接,则称该图为完全有向图。如下:
image.png

度,入度与出度

  • 度:一个结点有几条连线,他的度就为多少;
  • 入度:指向该结点的箭头有几个,它的入度就为多少;
  • 出度:从该结点指出的箭头有几个,它的出度就为多少。

存储结构

邻接矩阵

用一个n阶方阵R来存放图中各节点的关联信息,其矩阵元素RijR_{ij}定义为:
image.png
image.png

邻接表

首先把每个顶点的邻接顶点用链表示出来,然后用一个一维数组来顺序存储上面每个链表的头指针。
image.png

图的遍历

image.png

拓扑排序

我们把用有向边表示活动之间开始的向后关系。这种有向图称为用顶点表示活动网络,简称AOV网络。
image.png

每次删除一个入度边个数为0的点,并刷新其他点的出度边个数。

上图的拓扑序列有: 02143567,01243567,02143657,01243657。

最小生成树

普利姆算法

image.png
image.png

克鲁斯卡尔算法

image.png
image.png

8、查找

基本概念

image.png
image.png

顺序查找

image.png

折半查找

image.png
image.png

分块查找

image.png

哈希表(散列表)

image.png
image.png
常见解决方法

  • 开放地址法
  • 链地址法
  • 再哈希法
  • 建立一个公共溢出区

9、排序

基本概念

  1. 排序:就是重新排列表中的元素,使表中的元素满足按关键字有序的过程。
    • 稳定与不稳定排序
    • 内部排序与外部排序(需要用到内存或者外部存储器)
  2. 排序方法分类
    插入类排序:希尔排序、直接插入排序
    交换类排序:冒泡排序、快速排序
    选择类排序:简单选择排序、堆排序
    归并排序:基数排序

直接插入排序

算法思想:每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中,直到全部记录插入完成。
image.png

希尔排序

算法思想:先将待排序表分割成若干形如 L[i,i + d,i + 2d,...,i + kd] 的“特殊”子表,对各个子表分别进行直接插入排序。缩小增量d,重复上述过程,直到d=1为止。
image.png

冒泡排序

算法思想:从后往前 (或从前往后)两两比较相邻元素的值,若为逆序(即A[i-1]>A[i]),则交换它们,直到序列比较完。称这样过程为“一趟”冒泡排序。
image.png

快速排序

image.png

简单选择排序

算法思想:每一趟在待排序元素中选取关键字最小的元素加入有序子序列。
image.png

堆排序

image.png
image.png
image.png

技巧:先按顺序,将数组中的元素排成一颗完全二叉树,找到当前子结点中最大或者最小的结点进行交换,反复操作,直到所有父节点比其子节点大或小时,结束。

归并排序

算法思想:把两个或多个已经有序的序列合并成一个。
image.png

基数排序

image.png

评价指标

image.png

第三章 算法设计与分析

1、分治法

image.png
image.png

递归

image.png
image.png

答:A、D

2、回溯法

image.png

3、贪心法

image.png

4、动态规划法

image.png
image.png
image.png

答:0-1背包问题,要么物品全装进背包,要么全部不装。
这里的话,可以先找到价值最高的两项,是6,分别对应着重量为2和4的物品,那这是背包容量剩余10-(2+4)=4,我们再一次查询剩余最大价值的,逐一排除,价值5对应的重量为6,背包没有足够容量,舍弃,价值为4的对应重量为5,也不够,只剩下3,对应重量为2,满足。
故最大装包价值为:3+6+6=15,算法的时间复杂度为:O(nW)。
因为该递归函数与物品个数n和物品的最大装包价值有关,故复杂度为O(nj),j是0-1背包问题的最大装包价值,其与背包容量W有关,故复杂度为O(nW)。

image.png

答:我们先计算每一个物品的单价,6/2=3,3/2=1.5,5/6=0.833,4/5=0.8,6/4=1.5。
找出其中单价最高的依次全部计入重量,2+2+4=8,还剩10-8=2的容量,接着讲5/6价值的物品来填充。
故最大装包价值为:6+3+6+5/6*2=16.67,算法的时间复杂度为:O(lgn)。
归并排序会将一个序列划分为lgn个小序列,每一步都是合并有序序列的过程,时间复杂度为O(n),故算法的时间复杂度为O(nlgn)。

第四章 操作系统基本原理

1、基本概念

概念(定义)

image.png

功能和目标

image.png

特征

image.png

发展与分类

image.png

2、进程管理

状态转换图

image.png
image.png

前驱图

image.png

进程同步机制

image.png
image.png

进程互斥机制

image.png
image.png
image.png

信号量机制

image.png
image.png

PV操作

image.png

PV操作实现前驱操作

image.png
image.png

答:(1)选C (2)选A (3)选A
p1->p3为S1,p2->p3为S2,p3->p4为S3,p3->p5为S4。
(1)故p1执行完,释放了信号量S1,p2执行完,释放了信号量S2,即V(S1)与V(S2)故(1)选C;
(2)p3执行之前,需要保证p1与p2完成操作,故锁定其资源,P(S1)和P(S2),p3执行后,需要释放资源,即V(S3)和V(S4),故选A;
(3)p4和p5执行之前,需要分别申请资源,故P(S3)和P(S5),故选A。

死锁

举例

image.png

产生的必要条件

image.png

处理策略

image.png
image.png

答:B。
先给三个进程每个分配4个R,然后再分配一个R给一个进程,等待他执行完释放后,下一个进程就有5个R,如此反复。故至少有4+4+4+1=13个R。

银行家算法

image.png
image.png
image.png

答:综上,选B

3、存储管理

内存的分配与回收

image.png
image.png

动态分区分配

首次适应算法

算法思想:每次都从低地址开始查找,找到第一个能满足大小的空闲分区。如何实现:空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
image.png

最佳适应算法

算法思想:由于动态分区分配是一种连续分配方式,为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间,可以尽可能多地留下大片的空闲区,即优先使用更小的空闲区。
如何实现:空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
image.png

最差适应算法

算法思想:为了解决最佳适应算法的问题,即留下太多难以利用的小碎片,可以在每次分配时优先使用最大的连续空闲区,这样分配后剩余的空闲区就不会太小,更方便使用。
如何实现:空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
image.png

邻近适应算法

算法思想:首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲.分区,而每次分配查找时,都要经过这些分区,因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索,就能解决上述问题。
如何实现:空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
image.png

分页存储管理

image.png
image.png

答:(1)D (2)B
1、4K=2122^{12},说明页内地址是12位,又逻辑地址是十六进制,一个十六进制对应4个二进制,所以A29为页内地址,5为页号,所以其物理地址应为十六进制6A29H。
2、首先查看状态位为1的,表示他们都在内存中,可以看到0、1、2、5在内存中,接着查看访问位为1的,最近有被访问过的有0、2、5,只有1没被访问,所以淘汰页号为1的页面。

分段存储管理

image.png

段页式存储管理

image.png

页面置换算法

image.png

最佳OPT

image.png

先进先出FIFO

image.png

最近最久未使用LRU

image.png

4、文件管理

image.png

文件目录

image.png
image.png

文件的结构

image.png

索引分配

image.png

例子

image.png

答:(1)C (2)D
1、我们从iaddr[0]iaddr[4]数,逻辑块号为04,由于iaddr[5]是一级间接地址索引,所以得从58继续数,则58位置的逻辑块号是5,则物理块号为58;又磁盘索引块大小为1KB字节,每个地址项为4字节,则1KB/4B=256,即每个磁盘索引块可以装256个地址,故物理块号136对应的逻辑块号为256+4=260,所以逻辑块号261对应的物理块号为187。
2、iaddr[7]是二级间接地址索引,故物理块号101存放的是二级地址索引表。

空闲存储空间的管理(位示图法)

image.png

例子

image.png

答:(1)D (2)B
1、物理块的编号从0开始的, 故(4195+1)/32=131.125,即在第132个字中描述。
2、由于题意中4195号物理块分配给某文件,故表示该块是被占用的,取值为1,排除A、C。
131*32=4192 -> 0~4191,第132字中:第0位置->4192,第1位置->4193,第2位置->4194,第3位置->4195,故该字的第3位置“1”。

5、设备管理

I/O控制方式

image.png
image.png

6、微内核操作系统

image.png

第五章 计算机网络基础

1、计算机网络的分类

image.png

2、七层网络体系结构

image.png

3、网络的标准

image.png

4、TCP/IP协议族

image.png

TCP与UDP的区别

image.png

例子

image.png

答:选B,UDP开销较小。

5、IP地址和IPv6简介

IP地址

image.png

IPv6

image.png

6、Internet服务

image.png

例子

image.png

答:选A。25端口用于邮件传送SMTP协议,110端口用于邮件接收POP3协议。

第六章 数据库系统基础知识

1、基本概念

  1. 数据库
            数据库 (Database,缩写为DB)是指长期存储在计算机内的、有组织的、可共享的数据集合。数据库中的数据按一定的数据模型组织、描述和存储,具有较小的冗余度、较高的数据独立性和易扩展性,并可为各种用户共享。像Mysql、Oracle、Sql Server等。
  2. 数据库管理系统
            数据库管理系统(DatabaseManagement System,DBMS) 是数据库系统的核心软件,要在操作系统的支持下工作,解决如何科学地组织和存储数据、如何高效地获取和维护数据的系统软件问题。其==主要功能包括数据定义功能、数据操纵功能、数据库的运行管理、数据组织、存储、管理和数据库的建立与维护==。像Navicate、SQLYog等。

DBMS的特征与分类

image.png

2、数据库三级模式二级映像

image.png
image.png

3、数据库的分析与设计过程

image.png

4、数据模型

基本概念

模型就是对现实世界特征的模拟和抽象。

数学模型是对现实世界数据特征的抽象。

数据模型是用来描述数据的一组概念和定义。

数据模型的三要素是数据结构、数据操作、数据的约束条件。

数据结构:==是所研究的对象类型的集合==,是对系统静态特性的描述。

数据操作:==是对数据库中各种对象的实例(值)允许执行的操作的集合==,包括操作及操作规则。数据操作是对系统动态特性的描述。

数据的约束条件:是==一组完整性规则的集合==。对于具体的应用数据必须遵循特定的语义约束条件,以保证数据的正确、有效、相容。

E-R模型

image.png
  • 实体:长方体框,一般用名词表示;
  • 联系:菱形框,一般用动词表示;
    • 1对1联系:比如,电影院中一个座位只能被一个人坐,而一个人只能坐一个座位,所以是一对一的关系;
    • 1对n联系:比如,一个员工只属于一个部门,而一个部门可以有多个员工;
    • m对n联系: 比如,一名学生可以选多门课程,一门课程可以被多名学生选择,所以学生与课程之间是多对多的关系。
  • 属性:椭圆框

关系模型

        关系数据库系统采用==关系模型作为数据的组织方式==,在关系模型中用表格结构表达实体集以及实体集之间的联系,其最大特色是==描述的一致性==。

        关系模型是由若干个==关系模式==组成的集合。一个关系模式相当于一个记录型,对应于程序设计语言中类型定义的概念。

        关系模型的优点是:概念单一,存储路径对用户是透明的,所以具有更好的数据独立性和安全保密性,简化了程序的开发和数据库的建立工作。
image.png

  • 一个实体型转换为一个关系模式;
  • 一个1:1联系可以转换为一个独立的关系模式,也可以与任意一端对应的关系模式合并;
  • 一个1:n联系可以转换为一个独立的关系模式,也可以与n端对应的关系模式合并;
  • 一个m:n联系可以转换为一个独立的关系模式;
  • 一个多元联系可以转换为一个独立的关系模式;
  • 具有相同码的关系模式可以合并;
  • 有些1:n的联系,将属性合并到n端后,该属性也作为主码的一部分。

例子

image.png

答:选C。一个实体型可转换为一个关系模式,故3个实体集可以转换为3个关系模式,ABC之间多对多的联系转换为一个关系模式,故最少可以转换3+1=4个关系模式。

5、关系代数

关系模式相关名称

image.png

关系的三种类型

image.png

例子

image.png

答:选B。
外模式:称为子模式或者用户模式,面向用户,是用户所看到的数据库视图,相关数据的逻辑表示;
模式:称为概念模式或者逻辑模式,对应概念级数据库;是对数据库中逻辑结构和特征的描述;
内模式:又称为存储模式,对应物理级数据库,全体数据库的内部表示或底层表示。

七种基本运算

image.png
  • 并
    image.png
  • 交
    image.png
  • 差(这里示例是S1减去S2中出现的重复元素)
    image.png
  • 笛卡尔积(将关系S1和关系S2的每行数据进行连接操作)
    image.png
  • 投影
    image.png
  • 选择
    image.png
  • 联接
    image.png
    image.png
    image.png

例子

image.png

答:(54)6 (55)B
1、自然连接要去除重复的属性列,故R.A、R.B、R.C、R.D、S.A(去除)、S.C(去除)、S.E、S.F
2、A与C使用了笛卡尔积与选择操作,并不会去除重复的属性列,故排除;
|R.A|R.B|R.C|R.D|S.A(去除)|S.C(去除)|S.E|S.F|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
由于A、C为同属性名,因此需要满足R.A=S.A^R.C=S.C,即1=5^3=6,而对于选择条件R.B>S.E,转换为数字序号,则为2>7,注意D选项的'7'为字符而不是数字。

查询优化的原则

image.png

例子

image.png

答:选D。
优化SQL语句,减少比较次数是提高查询效率的有效方法。
在这个题目中,如果连接的两个表越小,那么连接的时候多余的数据就更少。
D答案将可以对子表做的操作先做了,最后做连接,是效率最高的一种方法。
即先对R表和S表先选择过滤后,做笛卡尔积,最后选择过滤,再做投影去重,效率最高。

6、数据库完整性约束

image.png

7、关系型数据库SQL简介

    SQL是在关系数据库中最普遍使用的语言,它不仅包含数据查询功能还包括插入、删除、更新和数据定义功能。

    SQL具有综合统一、高度非过程化、面向集合的操作方式,两种使用方式,语言简洁且易学易用等特点。

    SOL支持关系数据库的三级模式结构:视图对应外模式、基本表对应模式、存储文件对应内模式。
image.png

8、关系数据库的规范

函数依赖

image.png

求候选码(键)

image.png

例子

image.png

答:选B。
本题关系模式R的函数依赖关系表达为:
image.png
首先找到入度为0的点,可以发现只有A入度为0,所以A必为候选关键字的一部分,AB->C,AC->B,故有2个候选关键字,所以有3个主属性。(主属性:包含在候选关键字中的诸位属性,这里是A、B、C)

规范化理论

概念

image.png

非规范化存在的问题

image.png

规范化理论(范式)

image.png
  1. 1NF(第一范式)
    若关系模式R的==每一个分量都是不可再分的数据项==,则关系模式R属于第一范式(1NF)
    image.png
    图中高级职称人数还可分为教授和副教授,不满足第一范式的要求。
  2. 2NF(第二范式)
    若关系模式==R∈1NF,且每一个非主属性完全依赖于主键==,则关系模式R∈2NF。
    换句话说,当1NF消除了非主属性对码的部分函数依赖,则称为2NF。
    学生选课SC关系模式:属性为==学号(Sno)、课程号(Cno)==、成绩(Grade)和学分(Gredit)
    image.png
    image.png
    学号和课程号可决定学分,学分对学号有部分函数依赖,故没有消除非主属性对码的部分函数依赖,不满足第二范式。
  3. 3NF(第三范式)
    image.png
    image.png
    这里学生关系中主属性只有单个,可以唯一决定一个学生,没有传递函数依赖,故满足第三范式要求。
  4. BCNF(巴克斯范式)
    image.png
例子
image.png

答:(55)C (56)
image.png
A3A5→A6,A5A6→A1 利用伪传递率:A3A5→A1,A1→A2利用传递率:A3A5→A2
A3A5→A1,A1A3→A4利用伪传递率:A3A5→A4
因此A3A5→{ A1,A2,A3,A4,A5,A6}
1、找到入度为0的点,A2、A4、A1、A6都有入度,只有A3、A5入度为0,又A3、A5能遍历到达所有属性,故A3A5是关系模式R的一个主键;
2、所有属性完全依赖于候选键A3A5,该关系模式满足2NF。A3A5→A1,A1→A6,存在非主属性A6通过非主属性A1传递依赖于候选键A3A5,因此该关系模式不满足3NF,R规范化程度最高达到2NF。

关系模式分解

image.png
image.png

9、数据可得控制功能

事务管理

image.png

并发控制

image.png
image.png
image.png

例子

image.png

答:(1)D (2)C
1、因为T2、T3对数据D2、D3加了写锁,故其他事务没法对其D2、D3加任何锁,故事务T1对数据D2、D3加排它锁和共享锁都失败;
2、由于事务T1给数据D1加了读锁,所以事务T2可以对数据D1加读锁(共享锁),而D3加的是写锁(排它锁),所以给D3加锁失败。

备份和恢复

image.png
image.png

10、数据仓库与数据挖掘基础

image.png
image.png

11、大数据基本概念

image.png

第七章 程序设计语言基础知识

1、基本概念

image.png
image.png
image.png

2、编译与解释

image.png
image.png
image.png
image.png

3、文法

image.png

语法推导树

image.png

例子

image.png

答:可以从题意得知:
S->aAS、S->a、A->SbA、A->SS、A->ba
image.png

4、有限自动机

image.png
image.png

5、正规式

有限自动机的另外一种表达形式
image.png

例子1

image.png

答:(1)D (2)C
1、推导过程:image.png
2、A选项只要包含a、b的文法都可以,范围太广,排除;
B选项只能包含a开头的文法,而b选项是b开头的,所以不符合;
C选项即可包含ab也可以包含ba的文法,即*=1取ab,*=2取ab,*=3取ab,得到ababab,或者*=1取ba,*=2取ba,*=3取ba,得到bababa,或者*=1取ab,*=2取ba,*=3取ab,得到abbaab,所以选C;D选项*1=abba,*2=abba,故不符合。

例子2

image.png

答:选C。
A(1)=A、A(0)=B、B(0)=B、B(1)=C、C(0)=B、C(1)=A。
A(0)->A(0)后,就没有00的,故排除A;
A(1)后没有连续可输入1的,故排除B;
A(0)->B(1)->C(0)->B(1),即0101,满足C选项;
A(1)->A(0)->B(1)->C(0),终态是B,由于题意要求C是终态,故不满足。

6、表达式

image.png

例子

image.png

答:选D。
image.png
进行后续遍历,得:ab-c5+*

7、传值与引用(传址)

image.png

例子

image.png

答:选D。
形参x为值传递,形参x的改变不会影响第一个实参x,而形参a为引用传递,形参a的改变会影响实参x,x=2*10-1=19,a=10+19=29,故第二个实参x的值为29。

8、各种程序语言特点

image.png

第八章 软件工程基础知识

1、软件工程概述

image.png

能力成熟度模型(CMMI)

image.png
image.png
image.png
image.png

统一过程模型

image.png
image.png

2、软件开发模型

image.png

瀑布模型

image.png

演化模型

image.png

增量模型

image.png

螺旋模型

image.png

模型图示

image.png
  • 图1:原型模型
  • 图2:增量模型
  • 图3:螺旋模型

V模型(瀑布模型的变体)

image.png

喷泉模型

image.png

基于构件的开发模型

image.png

3、软件开发方法

结构化方法

image.png

Jackson方法

image.png

原型化方法

image.png

面向对象方法

image.png

敏捷开发方法

image.png

极限编程XP

image.png

4、需求分析

分类

image.png
image.png

获取方法

image.png

5、系统设计

采用了结构化方法的结构化设计

image.png

内聚和耦合

image.png
image.png

6、系统测试

原则和目的

  • 尽早、不断的进行测试。
  • 程序员避免测试自己设计的程序。
  • 既要选择有效、合理的数据,也要选择无效、不合理的数据。
  • 修改后应进行回归测试。
  • 尚未发现的错误数量与该程序已发现错误数成正比。

测试方法

静态测试

image.png

动态测试

image.png
image.png

测试阶段

image.png

7、软件开发项目管理

Gantt图

image.png

PERT图

image.png

例子

image.png

答:(1)D (2)C
1、Gantt不能清晰的描述各任务之间的依赖关系;
2、推导过程如下:
image.png

风险管理

风险是指“==损失或伤害的可能性==”。

风险管理包含:

  1. 风险识别
  2. 风险预测
  3. 风险评估
  4. 风险控制

8、软件质量

特性

image.png
image.png
image.png
image.png
image.png

9、软件度量

McCabe度量法

image.png
image.png

上图中,弧的个数为11,节点数为8,故环的个数为V(G)=11-8+2=5。
也可以通过数环,2->3->7,2->3->4->7,7->10,7->9->12,共4个,再加1,即5个环。

第九章 结构化开发方法(数据流图)

1、系统设计原理

  1. 抽象
            抽象是一种设计技术,重点说明一个实体的本质方面,而忽略或者掩盖不是很重要或非本质的方面。
  2. 模块化
            模块化是指将一个待开发的软件分解成若干个小的、简单的部分------模块,每个模块可独立地开发、测试,最后组装成完整的程序。模块化的目的是使程序的结构清晰,容易阅读、理解、测试和修改。
  3. 信息隐蔽
            信息隐蔽是开发整体程序结构时使用的法则,即将每个程序的成分隐蔽或封装在一个单一的设计模块中,定义每一个模块时尽可能少地显露其内部的处理。信息隐蔽原则对提高软件的可修改性、可测试性和可移植性都有重要的作用。
  4. 模块独立
            模块独立是指每个模块完成一个相对独立的特定子功能,并且与其他模块之间的联系简单。
            衡量模块独立程度的标准有两个:耦合和内聚。耦合是指模块之间联系的紧密程度。耦合度越高,则模块的独立性越差。
        内聚是指模块内部各元素之间联系的紧密程度。内聚度越低,则模块的独立性越差。因此,模块独立就是希望每个模块都是高内聚、低耦合的。
    image.png
    image.png

例子

image.png

答:选A。模块A和B都访问同一个公共数据环境。

2、系统总体结构设计

系统结构设计应遵循以下原则:

  • 分解----协调原则
  • 自顶向下原则
  • 信息隐蔽、抽象的原则
  • 一致性原则
  • 明确性原则
  • 模块之间的耦合度尽可能小,模块的内聚度尽可能高
  • 模块的扇入系数和扇出系数要合理
  • 模块的规模适当

子系统划分要遵循以下原则:

  • 子系统要具有相对独立性
  • 子系统之间数据的依赖性尽量小
  • 子系统划分的结果应使数据冗余较小
  • 子系统的设置应考虑今后管理发展的需要
  • 子系统的划分应便于系统分阶段实现
  • 子系统的划分应考虑到各类资源的充分利用

        ==模块是组成系统的基本单位==,它的特点是==可以组合、分解和更换==。系统中任何一个处理功能都可以看成是一个模块。根据模块功能具体化程度的不同,可以分为逻辑模块和物理模块。

一个模块要具备以下4个要素:

  • 输入和输出:模块的输入来源和输出去向都是同一个调用者,即一个模块从调用者那里取得输入,进行加工后再把输出返回给调用者
  • 处理功能:指模块把输入转换成输出所做的工作
  • 内部数据:指仅供该模块本身引用的数据
  • 程序代码:指用来实现模块功能的程序

3、数据字典

image.png
image.png

4、数据流图

基本概念

image.png

基本成分

image.png

数据流图示例图

image.png

数据流图的分层

image.png

对图和加工进行编号

image.png
image.png

应注意的问题

image.png
image.png
image.png
image.png

第十章 UML建模⭐️⭐️

1、概述

        统一建模语言(UML)是面向对象软件的==标准化建模语言==。UML由3个要素组成:==UML的基本构造块==、==支配这些构造块如何放置在一起的规则==和==运用于整个语言的一些公共机制==。

        UML的词汇表包含3种构造块:==事物、关系和图==。

        事物是对模型中最具代表性的成分的抽象,关系把事物结合在一起,图聚集了相关的事物。

image.png
image.png
image.png

2、类图⭐️

        类图(Class Diagram)展现了一组对象、接口、协作及其之间的关系。在面向对象系统的建模中所建立的最常见的图就是类图。

        类图==给出了系统的静态设计视图==,包含主动类的类图给出了系统的静态进程视图。作为模型管理视图还可以含有包或子系统,二者都用于把模型元素聚集成更大的组块。

        类图用于对系统的静态视图建模。这种视图主要支持系统的功能需求,即系统要提供给最终用户的服务。

        当图对系统的静态设计建模时,通常以下述3种方式之一使用类图:对系统的词汇建模;对简单的协作建模;对逻辑数据库模式建模。

考察方式

image.png

3、用例图⭐️

image.png

4、顺序图

image.png
image.png

5、活动图

        活动图(Activity Diagram)是一种特殊的状态图,它展现了在系统内从一个活动到另—个活动的流程。

        活动图==专注于系统的动态视图==,它对于系统的功能建模特别重要,并强调对象间的控制流程。
image.png

6、状态图

        状态图(State Diagram)展现了一个状态机,它由状态、转换、事件和活动组成。==状态图关注系统的动态视图==,对于接口、类和协作的行为建模尤为重要,==强调对象行为的事件顺序==。

        状态图通常包含简单状态和组合状态、转换(事件和动作)。

        状态图关注系统的动态视图,它对接口、类和协作的行为建模尤为重要,它强调对象行为的事件顺序。

image.png

7、通信图

        通信图(Communication Diagram)强调收发消息的对象的结构组织。通信图==强调参加交互的对象的组织==。

        产生一张通信图,如图所示,首先要将参加交互的对象作为图的顶点,然后把连接这些对象的链表示为图的弧,最后用对象发送和接收的消息来修饰这些链。这就提供了在协作对象的结构组织的语境中观察控制流的一个清晰的可视化轨迹。
image.png

8、构件图

构件图(Component Diagram)展现了==一组构件之间的组织和依赖==。构件图==专注于系统的静态实现视图==。如图所示,它与类图相关,通常把构件映射为一个或多个类、接口或协作。
image.png

第十一章 面向对象技术

1、基础概念

==面向对象=对象+分类+继承+通过消息的通信==

1、对象
        在面向对象的系统中,对象是基本的运行实体,它既包括数据(属性),也包括作用于数据的操作(行为),所以一个对象把属性和行为封装为一个整体。从程序设计者角度看,对象是一个程序模块,从用户角度看,对象为他们提供了所希望的行为。在对象内的操作通常叫作方法。 ==一个对象通常可由对象名、属性和操作3部分组成==。

2、消息
        对象之间进行通信的一种构造叫作消息。当一个消息发送给某个对象时,包含要求接收对象去执行某些活动的信息,接收到消息的对象经过解释,然后予以响应,这种通信机制叫作消息传递。发送消息的对象不需要知道接收消息的对象如何对请求予以响应。

3、类
        一个类定义了一组大体上相似的对象,一个类所包含的方法和数据描述一组对象的共同行为和属性。类是在对象之上的抽象,对象是类的具体化,是类的实例。

4、继承
        ==继承是父类和子类之间共享数据和方法的机制==。这是类之间的一种关系,在定义和实现一个类的时候,可以在一个已经存在的类的基础上来进行,把这个已经存在的类所定义的内容作为自己的内容,并加入若干新的内容。
        ==一个父类可以有多个子类,这些子类都是父类的特例==,父类描述了这些子类的公共属性和操作。一个子类可以继承它的父类中的属性和操作,这些属性和操作在子类中不必定义。子类中还可以定义自己的属性和操作。

5、多态
        ==不同的对象收到同一消息可以产生完全不同的结果,这一现象叫作多态==。在使用多态的时候,用户可以发送一个通用的消息,而实现的细节则由接收对象自行决定,这样,把具有通用功能的消息存放在高层次,而把不同的实现这一功能的行为放在较低层次,在这些低层次上生成的对象能够给通用消息以不同的响应。

例子

image.png

答:选A。
比如Student stu=new Xiaoming(); Xiaoming实现了Student中的特殊能力方法,Student只需要调用调用特殊能力的方法,就能使用小明的实现方法,故其无需知道。

2、设计原则

==单一职责原则==:设计目的单一的类。
==开放一封闭原则==:对扩展开放,对修改封闭。
李氏(Liskov)==替换原则==:子类可以替换父类。
==依赖倒置原则==:要依赖于抽象,而不是具体实现:针对接口编程,不要针对实现编程。
==接口隔离原则==:使用多个专门的接口比使用单一的总接口要好。
==组合重用原则==:要尽量使用组合,而不是继承关系达到重用的目的。
==迪米特(Demeter)原则==:一个对象应当对其他对象有尽可能少的了解。

3、设计模式的概念与分类

设计模式:==主要关注软件系统的设计,与具体的实现语言无关==

设计模式一般有以下4个要素:

(1)==模式名称==。用一两个词来描述模式的问题、解决方案和效果。设计模式允许在较高的抽象层次上进行设计。
(2)==问题==。描述了应该在何时使用模式。它解释了设计问题和问题存在的前因后果,可能描述了特定的设计问题,如怎样用对象表示算法等;也可能描述了导致不灵活设计的类或对象结构。
(3)==解决方案==。描述了设计的组成成分、它们之问的相互关系及各自的职责和协作方式。模式就像一个模板,提供设计问题的抽象描述和怎样用一个具有一般意义
的元素组合(类或对象组合)来解决这个问题。
(4)==效果==。描述了模式应用的效果及使用模式应权衡的问题。

image.png

常考的设计模式

工厂方法模式、抽象工厂模式、构建器模式、适配器模式、装饰器模式、外观模式、命令模式、中介者模式、观察者模式。

4、创建型模式

        创建型模式 ==抽象了实例化过程==。它们帮助一个系统独立于如何创建、组合和表示它的那些对象。一个类创建型模式使用继承改变被实例化的类,而一个对象创建型模式将实例化委托给另一个对象。

        创建型模式中有两个不断出现的主旋律。第一,它们都将关于该系统使用哪些具体的类的信息封装起来。第二,它们隐藏了这些类的实例是如何被创建和放在一起的整个系统关于这些对象所知道的是由抽象类所定义的接口。

        因此,创建型模式在为什么被创建,谁创建它,它是怎样被创建的,以及何时创建这些方面给予了很大的灵活性。它们允许用结构和功能差别很大的 “产品”对象配置一个系统。配置可以是静态的(即在编译时指定),也可以是动态的(在运行时指定)。

image.png

5、结构型模式

        结构性模式涉及 ==如何组合类和对象以获得更大的结构==。结构性模式采用继承机制来组合接口或实现。

        结构性对象模式不是对接口和实现进行组合,而是描述了如何对一些对象进行组合,从而实现新功能的一些方法。
image.png

6、行为型模式

        行为模式涉及 ==算法和对象间职责的分配==。行为模式不仅描述对象或类的模式,还描述它们之间的通信模式。这些模式刻画了在运行时难以跟踪的复杂的控制流。它们将用户的注意力从控制流转移到对象间的联系方式上来。

        行为类模式使用继承机制在类问分派行为,主要有 Template Method(模板方法)和Interpreter(解释器)两种模式。

        行为对象模式使用对象复合而不是继承。一些行为对象模式描述了一组对等的对象怎样相互协作以完成其中任一个对象都无法单独完成的任务。其他的行为对象模式常将行为封装在一个对象中并将请求指派给它。
image.png
image.png

7、Java程序设计

优点

(1)跨平台。
(2)代码可移动(与html相结合)。
(3)完全面向对象。
(4)编出来的程序不易出错(没有指针,内存垃圾自动回收,不会产生內存泄露)。此外,还有简单、安全、多线程等优点。

Java与C++的区别

(1)完全面向对象:无全局变量、无结构和联合、自动回收内存垃圾。
(2)没有指针。
(3)没有多继承。
(4)解释执行。

基本语法

image.png

类

        一个类是 ==一些属性和方法的封装体==,类的定义用关键字 ==class== 声明,用关键字public、 protected、 private指定类的成员的存取控制属性:

  • ==private(私有)成员==,只有类内部的方法才能访问;
  • ==protected(保护)成员==,可被派生类和同一文件夹下的类访问;
  • ==public(公有)成员==,可以从类的外部访问。

        默认是public。这体现了面向对象的以下指导思想:尽量将类内部的细
节隐藏起来,对类的属性的操作应该通过类的方法来进行
。

继承

        Java中用关键字 ==extends== 表示类间的继承关系。

        父类的公有属性和方法成为子类的属性和方法,子类如果有和父类同名、同参数类型的方法,那么子类对象在调用该方法时,调用的是子类的方法,亦即方法的重置。如果想要调用父类的同名方法,需要用 ==super== 关键字(属性同理)。

        子类的对象可以作为祖先类的对象使用,即所谓类的向上转换,反之则不行。具体表现在:可以用子类对象来对祖先类对象赋值,可以用子类对象作为实参去调用以父类对象为形参的函数。

重载

        同一个类中的两个或两个以上方法,名字相同,而参数个数不同或参数类型不同,叫作重载。注意:方法名字和参数都一样,而仅仅返回值类型不同,这不是重载。

静态属性和静态方法

        静态属性和静态方法的声明用关键字 ==static== 实现。一个类的静态属性只有一个,由所有该类的对象共享。不需要创建对象也能访问类的静态属性和方法,访问方式为"类名.静态属性或静态方法〞。静态方法与对象无关,因此不能在静态方法中访问非静态属性和调用非静态方法。

this、super和final

        this代表当前对象,super代表当前对象的父类。

        this的主要用途有:(1)==一个构造函数调用另一个构造函数,对构造函数的调用必须是第一条语句==。(2)==将对象自身作为参数来调用一个函数==。

        super的用途:==在子类中调用父类的同名方法,或在子类的构造函数中调用父类的构造函数,此时也必须是第一条语句==。

        用final关键字定义的常量,在其初始化或第一次赋值后,其值不能被改变。常量必须先有值,然后才能使用。对于常量的第一次赋值只能在构造函数中进行。

        final对象的值不能被改变,指的是该对象不能再指向其他对象,而不是指不能改变当前对象内部的属性值。

        函数参数声明为final后,函数中的值不能改变。

        final方法是不能被重置的方法。

        final类不能被继承,其所有方法都是final的,但属性可以不是final的。

抽象类和接口

1)抽象类

抽象类通过关键字abstract 实现,抽象类的目的是定义一个框架,规定某些类必须具有的一些共性。包含抽象方法的类一定是抽象类,所谓抽象方法是指没有函数体的方法。抽象类的直接派生类必须实现其抽象方法,==抽象类只能用于继承,不能创建对象==。

2)接口

接口用关键字interface 声明,==只能用于继承==。注意:此时关键字为implements(实现)。接口用于替代多继承的概念,==能实现多继承的部分特点,又避免了多继承的混乱==,还能起到规定程序框架的作用。注意:接口也可以用于多态。直接继承了接口的类,必须实现接口中的抽象方法,间接的则可以实现,也可以不实现。

3)抽象类与接口的异同

接口和抽象类都不能创建对象。
抽象类 ==不能参与多继承==,抽象类可以有非静态的成员变量,可以有非抽象方法。
接口 ==可以参与多继承==,所有属性都是静态常量,所有方法都是public抽象方法。

第十二章 信息安全与多媒体基础知识

1、网络安全基本概念

        计算机网络安全是指计算机、网络系统的硬件、软件以及系统中的数据受到保护,不因偶然的或恶意的原因而遭到破坏、更改、泄露,确保系统能连续和可靠地运行,使网络服务不中断。广义地说,凡是涉及网络上信息的保密性、完整性、可用性、真实性和可控性的相关技术和理论,都是网络安全所要研究的领域。

        网络安全涉及的主要内容包括运行系统的安全、信息系统的安全、信息传播的安全和信息内容的安全。==信息系统对安全的基本需求有保密性、完整性、可用性、可控性和可核查性==。

信息系统安全属性

  1. 保密性:确保信息不暴露给未授权的实体或进程。
  2. 完整性:只有得到允许的人才能修改数据,并且能够判别出数据是否已被篡改。
  3. 可用性:得到授权的实体在需要时可访问数据,即攻击者不能占用所有的资源而阻碍授权者的工作。
  4. 可控性:可以控制授权范围内的信息流向及行为方式。
  5. 可审查性:对出现的信息安全问题提供调查的依据和手段。

2、网络安全威胁

(1)物理威胁:指计算机硬件和存储介质受到的偷窃、废物搜寻及线路劫取活动的威胁。

(2)网络攻击:计算机网络的使用对数据造成了新的安全威胁,攻击者可通过网络利用电子窃听、入侵拨号入网、冒名顶替等方式进行入侵攻击、偷窃和篡改。

(3)身份鉴别:由于身份鉴别通常是用设置口令的手段实现的,入侵者可通过口令圈套、密码破译等方式扰乱身份鉴别。

(4)编程威胁:指通过病毒进行攻击的一种方法。

(5)系统漏洞:也称代码漏洞,是操作系统设计者有意设置的,目的是为了使用户在失去对系统的访问权时仍有机会进入系统。入侵者可使用扫描器发现系统漏洞,从而进行攻击。

image.png
image.png

3、网络攻击

        黑客(Hacker)常用的攻击手段主要有口令入侵、放置特洛伊木马、DoS攻击、端口扫描、网络监听、欺骗攻击、电子邮件攻击等。

1、口令入侵
        是指黑客使用某些合法用户的账号和口令登录到目的主机,然后再实施攻击活动。使用这种方法的前提是必须先得到该主机上的某个合法用户的账号,然后再进行合法用户的口令的破译。

2、放置特洛伊木马
        在计算机领域里,有一类特殊的程序,黑客可以通过它来远程控制别人的计算机,这类程序称为特洛伊木马程序。特洛伊木马程序一般分为服务器端(Server)/和客户端(Client)。

3、DoS攻击
        DoS即拒绝服务,其攻击目的是使计算机或网络无法提供正常的服务。最常见的DoS攻击有计算机网络带宽攻击和连通性攻击。

4、端口扫描
        端口扫描就是利用Socket编程与目标主机的某些端口建立TCP连接、进行传输协议的验证等,从而获知目标主机的扫描端口是否处于激活状态、主机提供了哪些服务、提供的服务中是否含有某些缺陷等。常用的扫描方式有TCP connect()扫描、TCP SYN扫描、TCPFIN扫描、IP 段扫描和FTP返回攻击等。

5、网络监听
        网络监听是主机的一种工作模式,在这种模式下,主机可以接收到本网段在同一条物理通道上传输的所有信息,而不管这些信息的发送方和接收方是谁。
        Sniffer是一款著名的监听工具,可以监听到网上传输的所有信息。Sniffer可以是硬件也可以是软件,主要用来接收在网络上传输的信息。

6、欺骗攻击
        欺骗攻击是指攻击者创造一个易于误解的上下文环境,以诱使受攻击者进入并且做出缺乏安全考虑的决策。常见的欺骗攻击有Web欺骗、ARP欺骗、IP欺骗。

7、电子邮件攻击
        电子邮件攻击主要表现为向目标信箱发送电子邮件炸弹。所谓的邮件炸弹实质上就是发送地址不详且容量庞大的垃圾邮件。由于邮件信箱容量是有限的,当庞大的垃圾邮件到达信箱时,就会把信箱挤爆。

4、防火墙技术

防火墙可分为以下几类

1、==包过滤型防火墙==。包过滤型防火墙工作在网络层,对数据包的源及目的IP具有识别和控制作用,对于传输层,它只能识别数据包是TCP还是UDP及所用的端口信息。

2、==应用代理网关防火墙==。应用代理网关防火墙彻底隔断内网与外网的直接通信,内网用户对外网的访问变成防火墙对外网的访问,然后再由防火墙将结果转发给内网用户。

3、==状态检测技术防火墙==。状态检测技术防火墙结合了代理防火墙的安全性和包过滤防火墙的高速度等优点,在不损失安全性的基础上将代理防火墙的性能提高了10倍。

典型防火墙的体系结构

        一个防火墙系统通常是由==过滤路由器和代理服务器组成。典型防火墙的体系结构包括包过滤路由器、双宿主主机、被屏蔽主机、被屏蔽子网等。
image.png

5、加密与数字签名

        数据加密的基本思想是通过 ==变换信息的表示形式来伪装需要保护的敏感信息,使非授权者不能了解被加密的内容==。需要隐藏的信息称为==明文==,产生的结果称为==密文==,加密时使用的变换规则称为密码算法。

        信息安全的核心是密码技术。根据密码算法所使用的加密密钥和解密密钥是否相同,可将密码体制分为==对称密钥密码体制==、==非对称密钥密码体制==。

1、对称密钥密码体制

        对称密钥密码体制中,发送和接收数据的双方必须使用相同的或对称的密钥对明文进行加密和解密运算。常用的对称加密算法有DES、IDEA、TDEA、AES、RC2、RC4、RC5等。

常见对称密钥加密算法:

==DES==:替换+移位、56位密钥、64位数据块、速度快、密钥易产生
==3DES(三重DES)==:两个56位的密钥K1、K2

  • 加密:K1加密->K2解密->K1加密
  • 解密:K1解密->K2加密->K1解密

==AES==:高级加密标准Rijndael加密法,是美国联邦政府采用的一种区块加密标准。
==RC-5==:RSA数据安全公司的很多产品都使用了RC-5。
==IDEA算法==:128位密钥、64位数据块、比DES的加密性好,对计算机功能要求相对低。

2、非对称密钥密码体制

        非对称密钥密码体制也叫公开密钥密码体制。该体制中,每个用户都有一对密钥:公开密钥(简称公钥)和私有密钥(简称私钥)。公钥对外公开,私钥由个人秘密保存。用其中一把密钥来加密,另一把密钥来解密。由于私钥带有个人特征,因此可以解决数据的签名验证问题。

常见非对称密钥加密算法:

==RSA==:512位(或1024位)密钥、计算量极大、难破解。
==Elgamal==:其基础是Diffie-Hellman密钥交换算法。
==ECC==:椭圆曲线算法。
其它非对称算法包括:==背包算法、Rabin、D-H==。

3、数字签名

==数字签名是用于确认发送者身份和消息完整性的一个加密的消息摘要。==

数字签名应满足以下3点:
1、接收者能够核实发送者。
2、发送者事后不能抵赖对报文的签名。
3、接收者不能伪造对报文的签名。

        数字签名可以利用对称密码体制(如DES)、公钥密码体制或公证体制来实现。最常用的实现方法建立在公钥密码体制和单向散列函数算法(如MD5、SHA)的组合基础上。

6、各个网络层次的安全保障

image.png

7、音频相关概念

image.png

8、图像相关概念

image.png

9、多媒体的种类

==感觉媒体==:指人们接触信息的感觉形式。如:视觉、听觉、触觉、嗅觉和味觉等。

==表示媒体==:指信息的表示形式。如:文字、图形、图像、动画、音频和视频等。

==显示媒体(表现媒体)==:表现和获取信息的物理设备。如:输入显示媒体键盘、鼠标和麦克风等;输出显示媒体显示器、打印机和音箱等。

==存储媒体==:存储数据的物理设备,如磁盘、光盘和内存等。

==传输媒体==:传输数据的物理载体,如电缆、光缆和交换设备等。

10、多媒体的计算问题

image.png

例子

image.png

答:1、D 2、C 3、D
1、一张图片大小:1600×1200×24÷8=5760000B1600\times1200\times24\div8=5760000B,128MB=227B128MB=2^{27}B,故最多可以存储227/5760000≈232^{27}/5760000\approx23张图片。
2、44.1×16×2=1411.2kb/s44.1\times16\times2=1411.2kb/s
3、每秒的数据量为30×64=192MB30\times64=192MB,故显示10秒的视频信息其原始数据量为192×10=1920MB192\times10=1920MB。

第十三章 法律法规与标准知识

1、知识产权

知识产权又称为智慧财产权,是指人们通过自己的智力活动创造的成果和经营管理活动中的经验、知识而依法所享有的权利。传统的知识产权可分为“工业产权“和
”著作权”。

知识产权包括以下内容

  1. 关于文学、艺术和科学作品的权利。
  2. 关于表演艺术家的表演以及唱片和广播节目的权利。
  3. 关于人类一切活动领域的发明的权利。
  4. 关于科学发现的权利。
  5. 关于工业品外观设计的权利。
  6. 关于商标、服务标记以及商业名称和标志的权利。
  7. 关于制止不正当竞争的权利。
  8. 在工业、科学、文学艺术领域内由于智力创造活动而产生的一切其他权利。

从所涉及的法律法规角度

  1. 著作权法
  2. 讦算机软件保护条例
  3. 商标法
  4. 专利法

从试题考点分布的角度

  1. 保护期限
  2. 知识产权人确定
  3. 侵权判断

2、保护期限

image.png

3、知识产权人确定

image.png
image.png

4、侵权判定

中国公民、法人或者其他组织的作品,不论是否发表,都享有著作权。

开发软件所用的思想、处理过程、操作方法或者数学概念不受保护。

著作权法不适用于下列情形:

  1. 法律、法规,国家机关的决议、决定、命令和其他具有立法、行政、司法性质的文件,及其官方正式译文。
  2. 时事新闻。
  3. 历法、通用数表、通用表格和公式。
image.png

5、标准的分类与标准的编号

分类

image.png

编号

image.png

第十四章 专业英语词汇知识

1、试题分析

        计算机专业英语一般是以完形填空的形式出现在71~75题中。具体而言,完形填空主要考查对语篇中句法、词语和短语的把握能力,具有较强的测试性。每一个空处都要通过上下文进行综合考虑,仅仅依靠一个单句往往无法确定正确选项。语篇的内容往往是对软件设计中相关知识的描述,需要对于这些内容有一定的了解。

完形填空中的短语和固定用法

        英语中有相当数量的动词短语、介词短语和固定搭配,其来源广泛,搭配方式丰富多变。因此需要 ==从动词入手==,==熟悉固定搭配==,==尤其是动词短语==,==从介词入手==,==了解介词本身的意义==,==进而了解同一个介词与不同动词、名词搭配产生的不同或相关的意义==,理解固定搭配的外延,增强对语义提示的审查力。

完形填空中的句法

        计算机英语的完形填空句法==强调时态、语态、倒装、复合,同时要求主语、谓语和宾语结构在数、格等方面的一致性==。此外,连接手段包括关系代词、关系副词、连接词等,要求与整个语篇的行文相一致,起到或承接或转折或加强的作用,有着非常突出的个性特征。

        时态在描述某项事物的发展历史时,一般采用==过去时态==。对目前尚还使用中的技术,采取==完成时态或现在时==。对未来技术的展望,大都采用将来时。句中几个受同一时间状态限制的动词时态在==表达形式上要保持一致==。这里包括并列的谓语动词以及主句和从句中谓语动词在表达形式上的一致。

        计算机英语的语篇在描述技术类知识时,语态一般力求客观,采用描述性和被动语态较多。这里要注意只有及物动词及相当于及物动词的词组才有被动语态的表达形式。在并列结构中,同样的语义往往需要高态表达形式。

2、答题要领

(1)==通过首句或出现的核心词汇来推断全文的信息==。短文的首句往往是主题句,或出现了核心词汇,能为理解文章的大意和主要内容提供必要线索。一般首句还提供背景资料,因此要特别注意首句,抓住整个段落的纲要。

(2)==把握文章发展的基本线索==。文章总是按照一定思路发展起来的,不同的逻辑关系主要依靠使用逻辑连接词来表达,文章如果没有内在的逻辑关系,就会出现语义不清、逻辑.混乱的问题。所以,通过表示逻辑关系的词汇把握文章发展的基本线索是至关重要的。

(3)==借助语法知识和专业背景知识确定正确的词汇选项==。计算机专业英语词汇的考查在试题中占一定比例,词汇选项的设计和文章难度的制定与语法都息息相关。务必借助语法知识和专业背景知识来确定正确的词汇选项,同时注意填入的词汇和文中句子的结构要相一致。

3、答题步骤

(1)==通读全文==。完形填空考查在全面理解内容的基础上运用语言的能力,由于试题篇幅较短,完全有时间利用通读对全文内容有一个基本的了解。要快速阅读段落,把握基本观点,通读时以浏览为主,可以忽略细节。

(2)==复读答题==。在通读的基础上,最好能立即复读,并结合选项,从语法结构、语义、词义、固定搭配等方面结合专业知识来考虑选项。选定之后,还需要回读。答题过程中,切记把握全文的整体意义,保持思路的连贯性,从而做出正确选择。

(3)==重读检查==。在确定所有选项以后,一定要重读全文,检查并核实每个选项在整篇文章中没有造成语义、结构、逻辑等方面的差错,确保短文是一个内容连贯、层次清晰、中心思想突出的整体。

4、专业词汇

image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png

觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句