admin 管理员组

文章数量: 887021

文章目录

  • 软件设计师考试大纲
  • 上午题(选择题)
  • 一、计算机组成原理
    • 考点:CPU结构组成
    • 考点:原码、反码、补码定点整数范围
    • 考点:浮点数表示
    • 考点:RISC和CISC计算机的区别
    • 考点:奇校验与偶校验
    • 考点:寻址方式
    • 考点:RAM、ROM、FLASH(闪存)
    • 考点:CPI与MIPS
    • 考点:流水线吞吐率计算
    • 考点:指令周期、机器周期、时钟周期
  • 二、操作系统
    • 考点:中断方式
    • 考点:DMA
    • 考点:位示图
    • 考点:进程资源图
    • 考点:分页(物理地址计算)
    • 考点:信号量
    • 考点:多级索引结构
  • 三、计算机网络
    • 考点:TCP/IP五层模型中各个协议内容(高频)
    • 考点:HTTP一次请求的过程
    • 考点:A类、B类、C类网络
    • 考点:几种常见命令及功能
  • 四、网络信息安全
    • 考点:几种常见攻击方式
    • 考点:对称加密与非对称加密
    • 考点:计算机病毒的特性
  • 五、法律方面
    • 考点:保护期限
    • 考点:知识产权人确定
    • 考点:侵权判定
  • 六、软件工程
    • 考点:软件设计各个阶段
    • 考点:项目的活动图
    • 考点:进程前驱图
    • 考点:软件模型
    • 考点:模块的耦合类型
    • 考点:模块的内聚类型
    • 考点:白盒测试(路径覆盖与语句覆盖)
    • 考点:面向对象分析
    • 考点:类的设计原则
    • 考点:设计模式
    • 考点:ISO/IEC 9126软件质量模型
    • 考点:类的划分
    • 考点:UML类图
    • 考点:MTTF、MTTR、MTBF
    • 考点:V模型
    • 考点:嵌入式操作系统的特点
    • 考点:软件维护的特点
    • 考点:分布式数据库特点
  • 七、程序语言基础
    • 考点:词法、语法、语义分析
    • 考点:调用函数,采用传值方式和传引用方式区别
    • 考点:编译与解释
    • 考点:有限自动机
    • 考点:并行系统与串行系统可靠度计算
    • 考点:算数表达式
  • 八、数据结构
    • 考点:树
    • 考点:图的存储(邻接矩阵、邻接表)
    • 考点:广度优先与深度优先遍历
    • 考点:排序算法(复杂度)
    • 考点:算法设计策略
  • 九、数据库
    • 考点:确定候选码
    • 考点:部分依赖、完全依赖、传递依赖
    • 考点:关系代数表达式
    • 考点:1NF、2NF、3NF
    • 考点:共享锁与排他锁
    • 考点:外连接
    • 考点:数据流图
    • 考点:外模式、模式和内模式


软件设计师考试大纲

考试科目

  1. 计算机与软件工程知识,考试时间为150分钟,笔试,选择题;
  2. 软件设计,考试时间为150分钟,笔试,问答题。

考试范围
软件工程知识

  1. 计算机科学基础知识
    1.1数制及其转换
    ◇ 二进制、八进制、十进制和十六进制等常用数制及其相互转换
    1.2 计算机内数据的表示
    ◇ 数的表示(补码表示,整数和实数的表示,精度和溢出)
    ◇ 非数值表示(字符和汉字表示,声音表示、图像表示)
    1.3算术运算和逻辑运算
    ◇ 计算机中的二进制数运算方法
    ◇ 逻辑代数的基本运算
    1.4其他数学基础知识
    ◇ 常用数值计算
    ◇ 排列组合,概率论应用,应用统计(数据的统计分析)
    ◇编码基础
    ◇ 命题逻辑、谓词逻辑、形式逻辑的基础知识
    ◇ 运筹基本方法
    计算机系统知识
    2.1计算机硬件基础知识
    2.1.1计算机系统的组成、体系结构分类及特性
    ◇ CPU、存储器的组成、性能和基本工作原理
    ◇ 常用I/O设备、通信设备的性能以及基本工作原理
    ◇ I/O接口的功能、类型和特性
    ◇ CISC/RISC,流水线操作,多处理机,并行处理
    2.1.2存储系统
    ◇ 虚拟存储器基本工作原理,多级存储体系
    ◇ RAID类型和特性
    2.1.3可靠性与系统性能评测基础知识
    ◇ 诊断与容错
    ◇ 系统可靠性分析评价
    ◇ 计算机系统性能评测方法
    2.2计算机软件知识
    2.2.1数据结构与算法知识
    ◇ 数组
    ◇ 链表
    ◇ 队列、栈
    ◇ 树
    ◇ 图的定义、存储和基本操作
    ◇ 杂凑(Hash表)
    ◇ 常用的排序算法、查找算法、数值计算、字符串处理、数据压缩算法、递归算法、图的相关算法
    ◇ 算法描述和分析
    2.2.2 操作系统知识
    ◇操作系统的内核
    ◇ 处理机管理
    ◇ 存储管理
    ◇ 设备管理
    ◇ 文件管理
    ◇ 作业管理
    ◇ 网络操作系统和嵌入式操作系统基础知识
    ◇ 操作系统的配置
    2.2.3程序设计语言和语言处理程序知识
    ◇ 汇编、编译、解释系统的基础知识和基本工作原理
    ◇ 程序设计语言的基本成分(数据、运算、控制和传输),程序调用的实现机制
    ◇ 各类程序设计语言的主要特点和适用情况
    2.2.4 数据库知识
    ◇ 数据库模型(概念模式、外模式、内模式)
    ◇ 数据模型,ER图,规范化
    ◇ 数据操作
    ◇ 数据库语言
    ◇ 数据库管理系统的功能和特征
    ◇ 数据库的控制功能
    ◇ 数据仓库和分布式数据库基础知识
    2.3 计算机网络知识
    ◇网络体系结构
    ◇传输介质,传输技术,传输方法,传输控制
    ◇常用网络设备和各类通信设备的特点
    ◇Client-Server结构,Browser-Server结构
    ◇LAN(拓扑,存取控制,组网,网间互连)
    ◇Internet 和Intranet 基础知识以及应用
    ◇网络软件
    ◇网络管理,网络性能分析
    2.4 多媒体基础知识
    ◇ 多媒体系统基础知识
    ◇ 简单图形的绘制,图像文件的处理方法
    ◇ 音频和视频信息的应用
    ◇ 多媒体应用开发过程
    系统开发和运行
    3.1软件工程知识
    ◇ 软件生存周期与软件生存周期模型
    ◇ 软件开发方法
    ◇ 软件开发项目管理
    ◇ 软件开发工具与软件开发环境
    3.2 系统分析基础知识
    ◇ 系统分析的主要步骤
    ◇ 机构化分析方法
    3.3 系统设计基础知识
    ◇ 概要设计与详细设计的基本任务
    ◇ 系统设计的基本原理
    ◇ 系统模块结构设计
    ◇ 结构化设计方法
    ◇ 面向数据结构的设计方法
    ◇ 系统详细设计
    3.4 系统实施基础知识
    ◇ 系统实施的基本内容
    ◇ 程序设计方法
    ◇ 程序设计的基本模块
    ◇ 系统测试
    ◇ 系统转换
    3.5 系统运行和维护基础知识
    ◇ 系统可维护性的概念
    ◇ 系统维护的类型
    ◇ 系统评价的概念和类型
    3.6 软件质量管理基础知识
    ◇ 软件质量特性(ISO/IEC 9126软件质量模型)
    ◇ 软件质量保证
    ◇ 软件复杂性的概念及度量方法(McCabe度量法)
    ◇ 软件评审(设计质量评审、程序质量评审)
    ◇ 软件容错技术
    3.7 软件过程改进基础知识
    ◇ 软件能力成熟度模型CMM
    ◇ 统一过程(UP)与极限编程(XP)的基本概念
    面向对象
    ◇ 面向对象的基本概念
    ◇ 面向对象分析与设计知识
    ◇ 分析模式与设计模式知识
    ◇ 面向对象程序设计知识
    ◇ 面向对象数据库、分布式对象基础知识
    信息安全知识
    ◇ 信息系统安全基础知识
    ◇ 信息系统安全管理
    ◇ 保障完整性与可用性的措施
    ◇ 加密与解密机制基础知识
    ◇ 风险管理(风险分析、风险类型、抗风险措施和内部控制)
    ◇ 计算机安全相关的法律、法规基础知识
    标准化基础知识
    ◇ 标准化意识,标准化组织机构,标准的内容、分类、代号与编号规定,标准制订过程
    ◇ 国际标准、国家标准、行业标准、企业标准
    ◇ 代码标准、文件格式标准、安全标准、互联网相关标准、软件开发规范和文档标准、基于构件的软件标准
    6.2 信息化基础知识
    ◇ 全球信息化趋势、国家信息化战略、企业信息化战略和策略
    ◇ 互联网相关的法律、法规
    ◇ 个人信息保护规则
    ◇远程教育、电子商务、电子政务等基础知识
    ◇ 企业信息资源管理基础知识
    6.3知识产权基础知识
    ◇ 保护知识产权有关的法律、法规
    计算机专业英语
    ◇ 具有工程师所要求的英语阅读水平
    ◇ 理解本领域的英语术语

软件设计
外部设计
1.1 理解系统需求说明
1.2 准备进行系统开发
◇ 选择开发方法、准备开发环境、制订开发计划
1.3 设计系统功能
◇ 选择系统结构
◇ 设计各子系统的功能和接口
◇ 设计安全性策略、需求和实现方法
◇ 制订详细的工作流和数据流
1.4 设计数据模型
◇ 设计ER模型及其他数据模型
1.5 编写外部设计文档
◇ 系统配置图、各子系统关系图
◇ 系统流程图、系统功能说明书
◇ 输入输出规格说明、数据规格说明、用户手册框架
◇ 设计系统测试要求
1.6 外部设计的评审
内部设计
2.1 设计软件结构
◇ 按构件分解,确定构件功能、规格以及构件之间的接口
◇ 数据结构与算法设计
◇ 采用中间件和工具
2.2 设计输入输出
2.3 设计物理数据
2.4 构件的创建和重用
◇ 创建构件、重用构件
◇ 使用子程序库或类库
2.5 编写内部设计文档
◇ 构件划分图、构件间的接口、构件处理说明
◇屏幕界面设计文档、报表设计文档、文件设计文档、数据库设计文档
2.6 内部设计的评审
数据库
◇ 设计关系模式
◇ 数据库语言(SQL)
◇ 数据库访问
程序设计
4.1 模块划分
4.2 编写程序设计文档
4.3 程序设计评审
5.系统实施
5.1 配置计算机系统及环境
5.2 选择合适的程序设计语言
5.3 用C程序设计语言以及C++、Java中的任一种程序设计语言进行程序设计
5.4 系统测试
◇ 指导程序员进行模块测试,并进行验收
◇ 准备系统集成测试环境和测试工具
◇ 准备测试数据
◇ 写出测试报告
软件工程应用
6.1 软件开发周期模型
6.2 需求分析
6.3 软件设计
◇ 软件设计的基本原则
◇ 软件设计方法
◇ 程序设计(结构化程序设计、面向对象程序设计)
6.4 软件测试的原则与方法
6.5 软件质量(软件质量特性、软件质量控制)
6.6 软件过程评估基本方法、软件能力成熟度评估基本方法
6.7 软件开发环境和开发工具
6.8 面向对象技术
◇ 面向构件技术
◇ 统一建模语言(UML)
◇ 软件过程改进模型和方法
6.9 网络环境软件技术
我针对这份大纲,结合往年的真题整理出了一些高频的考点,可供大家参考!


软件设计师题目分为上午题和下午题,本章只整理上午题相关内容

上午题(选择题)

一、计算机组成原理

计算机结构

考点:CPU结构组成

(一)控制器
程序计数器PC:是用于存放下一条指令所在单元地址的地方,执行一条指令的时候,会将指令由内存取到(通过地址总线寻址)指令寄存器中,并且PC中的地址会自动加1

指令寄存器:临时放置从内存里面取得的程序指令的寄存器,用于存放当前从主存储器读出的正在执行的一条指令

地址寄存器:用来保存当前CPU所访问的内存单元的地址

指令译码器:从内存中取出的一条指令经数据总线送往指令寄存器中

(二)运算器
通用寄存器:一般是指处理器最常使用的整数通用寄存器,可用于保存整数数据、地址等
状态寄存器:状态寄存器用来存放两类信息:一类是体现当前指令执行结果的各种状态信息(条件码),如有无进位(CF位)、有无溢出(OV位)、结果正负(SF位)、结果是否为零(ZF位)、奇偶标志位(P位)等;另一类是存放控制信息(PSW:程序状态字寄存器),如允许中断(IF位)、跟踪标志(TF位)等。
累加寄存器AC:通用寄存器,为ALU提供一个工作区,用在暂存数据

CPU控制器:控制整个CPU工作,它负责一次访问程序指令,进行指令译码,并协调其他设备

CPU运算器:主要是用来进行数据运算加工的

Cache(高速缓存):是位于CPU和主存之间的一种存储器,速度高于主存,Cache保存的内容是CPU经常访问的数据,当CPU需要再次访问该部分数据时,就不用从主存中读取,节约了CPU的工作时间。Cache的内容是主存一部分内容的复本,当CPU访问主存时,访问的是主存的地址,因此需要采用一种“地址变换”的方式将主存地址“转换为”Cache地址,这种变换的方式是由计算机硬件自动完成的。

考点:原码、反码、补码定点整数范围

考点:浮点数表示

浮点数的表示:N = M*R^e
其中,M为尾数,e是指数,R是基数
它的组成部分:阶符、阶码、数符、尾数

阶码:常用补码或移码表示的定点整数(阶码的底一般为2)
尾数:常用原码或补码表示的定点小数

例题:若阶码以补码表示,尾数以原码表示,则100100000000001表示的浮点数是____。

按照题目给的位数,我们可以分别得出:
阶符(1):1表示该阶码是负数
阶码(0001):阶码是负数且以补码表示,所以阶码0001转换为原码为1111,是十进制的15
数符(0):表示尾数是正数
尾数(0000000001):尾数正的且以小数的表达形式是2^-10
因此该浮点数是2^-15 * 2^-10

考点:RISC和CISC计算机的区别

指令系统类型指令寻址方式实现方式其他
CISC(复杂指令集计算机)数量多,使用频率差别大,可变长格式支持多种微程序控制技术
RISC(精简指令集计算机)数量少,使用频率接近,定长格式,大部分为单周期指令,操作寄存器,只有Load/Store操作内存支持方式少增加了通用寄存器;硬布线逻辑控制为主,采用流水线优化编译,有效支持高级语言

考点:奇校验与偶校验

奇校验:确保整个被传输的数据中“1”的个数是奇数个,如果数据序列中“1”的个数为奇数则填0,否则填“1”;

偶校验:确保整个被传输的数据中“1”的个数是偶数个,如果数据序列中“1”的个数为偶数则填0,否则填“1”。

但是奇偶校验存在一个问题就是,只能检测错误但不能纠错。如果当多个数据位发生改变,那么奇(偶)校验位可能会出错,因为没有办法确定是哪一位出错,所以不能进行错误纠正。

考点:寻址方式

寻址方式是如何对指令中的地址字段进行解释,以获得操作数的方法或获得程序转移地址的方法。

寻址方式内容
立即寻址立即寻址的操作数就包含在指令中,取出指令时即可得到操作数,相较于直接寻址和寄存器寻址,立即寻址获取操作数的速度最快
直接寻址直接寻址的操作数存放在内存单元中,指令中直接给出操作数所在存储单元的地址
寄存器寻址寄存器寻址的操作数存放在寄存器中,指令中给出存放操作数的寄存器名,相较于直接寻址,在寄存器寻址方式中,指令在执行阶段不用访问主存,执行速度较快

所以访问速度:立即寻址最快,寄存器寻址次之,直接寻址最慢

考点:RAM、ROM、FLASH(闪存)

(一)RAM
RAM 随机存取存储器(英语:Random Access Memory,缩写:RAM),也叫主存,是与CPU直接交换数据的内部存储器。它可以随时读写(刷新时除外),而且速度很快,通常作为操作系统或其他正在运行中的程序的临时数据存储介质。RAM工作时可以随时从任何一个指定的地址写入(存入)或读出(取出)信息。它与ROM的最大区别是数据的易失性,即一旦断电所存储的数据将随之丢失。RAM在计算机和数字系统中用来暂时存储程序、数据和中间结果。

SRAM 是“static RAM(静态随机存储器)”的简称,之所以这样命名是因为当数据被存入其中后不会消失。

DRAM 动态随机存储器不同,DRAM 必须在一定的时间内不停的刷新才能保持其中存储的数据

(二)ROM
ROM 只读存储器(Read-Only Memory,ROM),以非破坏性读出方式工作,只能读出无法写入信息。信息一旦写入后就固定下来,即使切断电源,信息也不会丢失,所以又称为固定存储器。

(三)FLASH(闪存)
FLASH存储器又称闪存,它结合了ROM和RAM的长处,不仅具备电子可擦出可编程(EEPROM)的性能,还不会断电丢失数据同时可以快速读取数据 (NVRAM的优势),U盘和MP3里用的就是这种存储器。

考点:CPI与MIPS

  • CPI(指令时钟周期数)是指CPU每执行一条指令所需的始终周期数。
  • MIPS(每秒百万级指令执行数量)单字长定点指令平均执行速度 Million Instructions PerSecond的缩写,每秒处理的百万级的机器语言指令数。这是衡量CPU速度的一个指标。

计算
例题,某计算机系统的CPU主频为2.8GHz。某应用程序包括3类指令,各类指令的CPI(执行每条指令所需要的时钟周期数)及指令比例如下表所示。执行该应用程序时的平均CPI为( );运算速度用MIPS表示,约为( )。

解析
平均CPI=4 * 35%+3 * 45%+6 * 20%=3.95≈4
CPU主频为2.8G,即CPU每秒可以产生2.8G=2.8*10^9个时钟信号;而通过上面我们知道每条指令平均需要4个时钟信号(即CPI=4),因此,每百万条指令需要 4 * 10 ^ 6个时钟信号;所以MIPS=(2.8 * 10^9)/(4 * 10^6)=700MIPS

考点:流水线吞吐率计算

n条指令耗时:一整条指令所需时间 +(指令条数-1)* 时间最长的指令的一段
吞吐率 = 指令条数 / 一整条指令所需时间 +(指令条数-1)* 时间最长的指令的一段

考点:指令周期、机器周期、时钟周期

取出并执行一条指令所需要的时间称为指令周期

完成一项基本操作(例如取指令、存储器读、存储器写)所需要的时间称为机器周期

时钟脉冲的重复周期成为时钟周期

时钟周期也称为震荡周期,定义为时钟脉冲的倒数,是计算机中最基本,最小的时间单位。在一个时钟周期内,CPU仅完成一个最基本的动作。人们规定10纳秒为一个时钟周期,更小的时钟周期意味着更高的工作频率。计算机中执行指令的过程一般分为取指令,分析指令和执行指令的三个基本阶段。指令周期是执行一条指令所需要的时间,一般由若干个机器周期组成,是从取指令,分析指令到执行完所需的全部时间。指令不同,所需的机器周期数也不同,对于一些简单的单字节指令,在取指令周期中,指令取出到指令寄存器后,立即译码执行,不再需要其他的机器周期。对于一些比较复杂的指令,则需要两个或两个以上的机器周期。
总结:指令周期 > 机器周期 > 时钟周期

二、操作系统

考点:中断方式

在中断方式下,当I/O系统与外设交换数据的时候,CPU可以处理其他任务,不需要等待整个过程完成,也就是说外设与CPU之间可以并行工作。中断方式完成数据输入输出的过程为:

  1. I/O系统准备好以后,发出中断请求信号;
  2. CPU收到信号,保存正在执行程序的现场,转入执行I/O中断服务程序,中断服务程序完成后,返回被打断的程序继续执行。可见,一次中断处理过程需要经历保存现场、中断处理、恢复现场。

考点:DMA

概念:DMA方式也称为直接主存存取方式,其思想是:允许主存储器和I/O设备之间通过“DMA控制器”直接进行批量数据交换,除了在数据传输开始和结束时,整个过程无须CPU的干预

特点

  • DMA传送方式是让存储器与外设、或外设与外设之间直接交换数据,不需要经过CPU的介入
  • 一个DMA传送只需要执行一个DMA周期,相当于一个总线读写周期

考点:位示图

位示图是利用二进制的一位来表示磁盘中的一个盘块的使用情况。当其值为“0”时,表示对应的盘块空闲;为“1”时,表示已经分配。有的系统把"0"作为盘块已分配的标记,把“1”作为空闲标志。(它们的本质上是相同的,都是用一位的两种状态标志空闲和已分配两种情况。)磁盘上的所有盘块都有一个二进制位与之对应,这样,由所有盘块所对应的位构成一个集合,称为位示图。

先来看一个题目
某文件系统采用位示图记录磁盘的使用情况,若计算机系统的字长为64位,磁盘的容量为1024GB,物理块的大小为4MB,那么位示图的大小需要_____个字

解析:
给出了磁盘容量和物理块大小,我们就可以求得磁盘中一共有1024*1024/4个物理块。系统字长是64位,每一位对应文件存储器上的一个物理块。那么位示图就一个有1024 * 1024/4/64=4096个字

考点:进程资源图

如果一个图可完全简化,则不会产生死锁;如果一个图不可完全简化(即:图中还有“边”存在),则会产生死锁。这就是“死锁定理”。

案例原图:

如何简化呢?很简单
就是查看进程是否会被阻塞,如果非阻塞就消除与它相连的所有边,否则不消除

对P1进程:在原图中,P1进程需要请求一个R2资源,而R2原本有两个资源,分配给P2一个,还剩一个。所以可以满足P1的请求,P1不发生阻塞,可以消除与它相连的边,如下图所示

对P2进程:在上图中,此时P1进程已经完成,释放完所有资源。P2要想R1申请一个资源,而R1原本有三个资源,已分配给P2一个,还剩两个。所以也可以满足P2的请求,P2不发生阻塞,可以消除与它相连的边,如下图所示

经上所述,这个案例中进程不会发生死锁,那么上面情况会发生死锁呢,我们看下面这个图

按照之前的分析逻辑,我们会发现,就算P3进程执行完释放资源,P1进程申请依旧得不到满足,P2也是,它们都被阻塞,无法被唤醒,此时就发生了死锁(无法消除所有边)。

考点:分页(物理地址计算)

如果题目给出页面大小为4K,即2^12B。说明页内偏移量占0~11位,页号占了12 ~ 31位。

计算公式:
页号 = 逻辑地址 / 页面长度 (取整)
页内偏移量 = 逻辑地址 % 页面长度 (取余)
物理地址=b * L + W = 块号 × 页面大小 + 页内偏移量

考点:信号量

信号量(semaphore)的数据结构为一个值和一个指针。信号量的值与相应资源的使用情况有关。值大于0时表示当前可用资源的数量;值小于0时,其绝对值表示等待使用该资源的进程个数。指针指向等待该信号量的下一个进程。信号量的值仅能由PV操作来改变。

(1)同步信号量,值为资源可以使用的个数,信号量小于0,则线程进行等待,信号量大于0,表示可用资源个数。初始值0.
(2)互斥信号量只有两个值0或1,0表示资源正在被占用,线程等待。1表示,资源没有被使用,线程可以进入。初始值为1

考点:多级索引结构


【例题】某文件系统采用多级索引结构,若磁盘块的大小为 1K 字节,每个块号需占 3 字节,那么采用二级索引时的文件最大长度为116281K 字节。

116281K是怎么算出来的呢?
首先我们要知道这几个概念

  • 直接索引:索引指向物理块(地址直接对应物理盘块存索引的内容)
  • 一级间接地址索引:索引节点指向的物理块用来存放地址项。
  • 二级间接地址索引:索引节点指向的物理块,存放的是一级索引。

现在回到题目!
题目告诉我们磁盘块(物理盘块)的大小为1K字节,每个块号占3个字节,那么我们就可以求出一级索引一共存了1K/3≈341个磁盘块。因为是采用二级索引,每一个磁盘块还可以指向341个磁盘块,一共有341*341=116281个磁盘块存二级索引文件,每个磁盘块1K字节,所以该二级索引文件最大长度为116281k字节。

三、计算机网络

考点:TCP/IP五层模型中各个协议内容(高频)

应用层传输层网络层数据链路层物理层
FTP:文件传输协议。20为数据端口,21为控制端口UDP:无连接、不可靠的传输层协议ICMP:Internet控制报文协议。用于在IP主机、路由器之间传递控制消息L2TP:第二层隧道协议。
TFTP:简单文件传输协议TLS:传输层安全协议,用于在两个通信应用程序之间提供保密性和数据完整性OSPF:开放式最短路径优先PPP:点对点协议
SSH:安全远程登录协议TCP:面向连接的、可靠的传输层协议IP:网际互连协议PPPoE:以太网上的点对点协议,是将点对点协议(PPP)封装在以太网(Ethernet)框架中的一种网络隧道协议。提供用户身份验证、用户管理以及数据加密等功能
HTTP:超文本传输协议,用于从WWW服务器传输超文本到本地浏览器的传输协议,是浏览器默认的应用层协议ARP:地址解析协议。根据IP地址获取物理地址
SMTP:简单邮件传输协议,用于发送邮件,是电子邮件客户端向服务器发送邮件的协议 ,使用25端口RARP:反向地址转换协议。将物理地址转换为IP地址
POP3:有据协议。用于从目的邮件服务器上读取邮件,使用110端口IGMP:互联网组管理协议,用于IP主机向任一个直接相邻的路由器报告他们的组成员情况
MIME:多用途互联网邮件扩展类型。MIME消息能包含文本、图像、音频、视频等多媒体数据
Telnet:是Internet远程登录服务的标准协议和主要方式 ,使用23端口
DNS:域名系统。它作为将域名和IP地址相互映射的一个分布式数据库,能够使人更方便地访问互联网。
RIP:路由信息协议。是基于距离矢量算法的路由协议,利用跳数来作为计量标准
SNMP:简单网络管理协议
DHCP:动态主机配置协议
BGP:边界网关协议,构建在EGP的经验之上
IGP:内部网关协议
EGP:边界网关协议

考点:HTTP一次请求的过程

  1. 在浏览器中输入URL,并按下回车键
  2. 浏览器向DNS服务器发出域名解析请求并获得结果
  3. 根据目的的IP地址和端口号,与服务器建立TCP连接
  4. 浏览器向服务器发送数据请求
  5. 服务器将网页数据发送给浏览器
  6. 通信完成,断开TCP连接
  7. 浏览器解析收到的数据并显示

考点:A类、B类、C类网络

A类

B类

C类

考点:几种常见命令及功能

命令功能
netstat控制台命令,查看端口占用,是一个监控TCP/IP网络的工具,它可以显示路由表、实际网络连接以及每一个网络接口设备的状态信息
nslookup用于查询DNS记录,查看域名解析是否正常,在网络故障的时候用来诊断网络问题
ping可以检查网络是否连通
tracert跟踪路由,用于确定IP数据包访问目标锁采取的路径。Tracert命令使用IP生存时间(TTL)字段和ICMP错误消息来确定从一个主机到网络上其他主机的路由
traceroute可以利用ICMP协议跟踪并返回本机访问目标计算机时所经过的所有路由
ipconfig帮助用户查看网络状况,如延迟、IP、主机信息、物理地址信息等。
ipconfig/all查看详细IP的主机信息,DNS信息,物理地址信息,DHCP服务器信息等
ipconfig/renew更新所有适配器
ipconfig/release释放所有匹配的连接

四、网络信息安全

考点:几种常见攻击方式

方式内容
跨站脚本通过Web应用的安全漏洞,向网页中嵌入恶意脚本代码,以盗取用户信息为主
拒绝服务攻击(DoS)指攻击者向攻击对象发送大量请求,使得攻击对象不能继续提供服务
信息篡改当入侵者将网络上传送的信息数据在传送中途修改,然后再发向目的地。
口令猜测通过穷举方式搜索口令空间,逐一测试,得到口令,进而非法入侵系统。
SQL注入通过SQL漏洞,把恶意SQL命令插入到页面请求查询字符串中,来达到欺骗服务器执行恶意SQL命令的行为,目标是为了获得数据库权限,从而非法获取数据
ARP攻击当局域网内的计算机遭到ARP的攻击时,它就会持续地向局域网内所有的计算机及网络通信设备发送大量的ARP欺骗数据包,如果不及时处理,便会造成网络通道阻塞、网络设备的承载过重、网络的通讯质量不佳等情况

考点:对称加密与非对称加密

这里推荐一篇文章:搞懂加密、数字签名、证书
写的非常详细!!!
这里就列举一下常见的几种加密算法

对称加密非对称加密信息摘要
DES、3DES、AES、RC-5、IDEA、RC4RSA、Elgamal、ECC、背包算法、Rabin、D-HMD5、SHA

考点:计算机病毒的特性

计算机病毒具有隐蔽性传染性潜伏性触发性破坏性等特性

五、法律方面

考点:保护期限

考点:知识产权人确定


考点:侵权判定


往年一些考题涉及到的内容:
著作权法

  • 著作权法规定,作品完成之时就开始受到保护
  • 著作权归属由委托人和受委托人通过合同约定。合同中未作明确约定的,著作权属于受托人
  • 软件属于本职工作中明确的开发目标,单位享有著作权
  • 甲公司购买了一款工具软件,甲公司向客户提供工具软件的复制品,该行为属于侵犯了著作权
  • 我国保护计算机软件著作权的两个基本法律文件是《中华人民共和国著作权法》和《计算机软件保护条例》

商标权

  • 商标权可以每10年无限续期

专利权

  • 当有两人以上申请人分别就相同内容的就相同的计算机软件发明创造,向专利部门提出专利申请,先申请的获得该项专利的申请权
  • 利用本单位的物质技术条件所完成的发明创造,单位与发明人或者设计人订有合同对申请专利的权利的归属作出约定的,从其约定

署名权

  • 作者的署名权、修改权、保护作品完整权的保护期不受限制

六、软件工程

考点:软件设计各个阶段

阶段内容
需求分析确定软件要完成的功能及非功能性要求
概念设计将需求转换为软件的模块划分,确定模块功能与接口、调用关系等
详细设计将模块进行细化,得到详细的数据结构及算法
编码根据详细设计进行代码的编写,得到可运行的软件,并进行单元测试

考点:项目的活动图

一般会考察两个地方

  • 项目完成的最少时间,即关键路径
  • 活动xx最多可以晚xx天不会影响项目进度,即松弛时间

关键路径就是项目从开始到结束的最长路径
松弛时间 = 关键路径 - 通过整个活动经过xx最长路径

例题
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天),则完成该项目的最少时间为( )天。活动BD最多可以晚开始( )天而不会影响整个项目的进度。

解析:第一空就是求得关键路径,在图中找出最长路径,即ABDGIKL,累加得22。第二空求松弛路径,因为活动BD在关键路径上,所以松弛时间:22-22=0

考点:进程前驱图

只需要记住一个秘诀!

一个箭头两端,都有一对对应的PV操作。带有指向的是P操作,另一头是V操作。
举个例子

至于具体是哪个信号量S,还需要根据题目给定的已知条件来判断。

考点:软件模型

模型特点适用场景
瀑布模型其过程是从上一项活动接收该项活动的工作对象作为输入,利用这一输入实施该项活动应完成的内容给出该项活动的工作成果,并作为输出传给下一项活动。需求明确,或者需求很少变化,风险低
快速原型模型原型模型能快速迅速地开发出一个让用户看得见的系统框架,可以用来支持用户界面设计。它所能完成的功能往往是最终产品能完成功能的一个子集。用途是获知用户的真正需求,一旦需求确定了,原型将被抛弃适用于用户需求不清、需求经常变化的情况
增量模型增量模型在各个阶段并不交付一个可运行的完整产品,而是交付满足客户需求的一个子集的可运行产品。整个产品被分解成若干个构件,开发人员逐个构件地交付产品,这样做的好处是软件开发可以较好地适应变化,客户可以不断地看到锁开发的软件,从而降低开发风险希望系统能快速投入使用,系统功能可以在使用过程中不断改善
螺旋模型是瀑布模型与原型模型的结合,它将风险分析加入到了瀑布模型中,将开发过程划分为几个螺旋周期,每个螺旋周期大致和瀑布模型相符适用于大规模、复杂且具有高风险的项目
喷泉模型是一种以用户需求为动力,以对象为驱动的模型,其特征是复用性好、开发过程无间隙、节省时间适合于面向对象的开发方法
敏捷方法敏捷方法是逐渐流行起来的一款新型软件开发方法,以应对快速变化的需求。在敏捷开发中,软件项目的构建被分成多个子项目,各个子项目的成果都经过测试,具备集成可运行的特征。换言之,就是把一个大项目分为多个相互联系,但也可以独立运行的小项目,并分别完成,在此过程中软件一直处于可使用转台可以应对后期需求变化
统一过程模型UP统一过程(RUP/UP,Rational Unified Process)是一种以用例驱动、以体系结构为核心、迭代及增量的软件过程模型,由UML方法和工具支持,广泛应用于各类面向对象项目。需求明确且很少变更的项目,如二次开发或升级型项目。”

考点:模块的耦合类型

耦合关系内容
内容耦合内容耦合是最紧的耦合程度,一个模块直接访问另一模块的内容,或者通过非正常入口转入模块另一个模块内部,则称这两个模块为内容耦合。这种耦合是危险的。
公共耦合指模块通过公共数据环境中的全局数据结构、共享的通信区、内存的公共区等产生的耦合
外部耦合一组模块都访问同一全局简单变量,而且不通过参数表传递该全局变量的信息,则称之为外部耦合。外部耦合和公共耦合很像,区别就是一个是简单变量,一个是复杂数据结构
控制耦合模块之间传递的不是数据信息,而是控制信息例如标志、开关量等,一个模块控制了另一个模块的功能。
标记耦合调用模块和被调用模块之间传递数据结构而不是简单数据,同时也称作特征耦合。
数据耦合调用模块和被调用模块之间只传递简单的数据项参数。相当于高级语言中的值传递
非直接耦合两个模块之间没有直接关系,它们之间的联系完全是通过主模块的控制和调用来实现的。耦合度最弱,模块独立性最强。

详情见这

考点:模块的内聚类型

内聚关系内容
功能内聚如果一个模块内所有处理元素完成一个,而且仅完成一个功能,则称为功能内聚。 功能内聚是最高程度的内聚。但在软件结构中,并不是每个模块都能设计成一个功能内聚模块。
顺序内聚如果一个模块内处理元素和同一个功能密切相关,而且这些处理元素必须顺序执行,则称为顺序内聚。
通信内聚模块内的所有处理元素都在同一数据结构上操作, 各处理使用相同的输入数据或参数相同的输出数据
过程内聚如果一个模块内的处理元素是相关的,而且必须以特定的次序执行,称为过程内聚。 过程内聚与顺序内聚的区别是: 顺序内聚中是数据流从一个处理单元流到另一个处理单元,而过程内聚是控制流从一个动作流向另一个动作。
时间内聚如果一个模块包含的任务必须在同一段时间内执行,称为时间内聚。也称为瞬时内聚。
逻辑内聚如果模块完成的任务在逻辑上属于相同或相似的一类,称为逻辑内聚。
偶然内聚如果一个模块由完成若干毫无关系的功能处理元素偶然组合在一起的,就叫偶然内聚。

考点:白盒测试(路径覆盖与语句覆盖)

路径覆盖语句覆盖
选取合适的用例,将图中所有可能执行路径都走一遍选择足够的测试用例,使得程序中每个语句至少都能被执行一次

对于下面图例:

  • 如果要实现语句覆盖,那么只用设计一用例能通过路径ABCDEFG即可,因为这条路径满足每个语句至少都能被执行一次。
  • 如果要实现路径覆盖,仅仅ABCDEFG是不够的,要使所有路径都被覆盖到,那么每个条件语句的Y/N情况都要分别考虑,比如ADG、ABCDG、ABCDEFG,这样才能将图中所有可能执行路径都走一遍

采用McCabe度量法计算程序的环路复杂度 = 闭环数量 + 1

考点:面向对象分析

面向对象分析包含5个活动:认定(识别)对象、组织对象、描述对象间的相互作用、确定对象的操作、定义对象的内部信息

考点:类的设计原则

设计原则内容
开闭原则指类对于功能扩展应该是开放的,对于修改应该是封闭的
里氏替换原则即一个模块中如果使用了一个基类,那么这个基类应该可以被其子类替换,同时不会改变程序的正确性。总结就是子类必须能够替换他们的父类
单一职责原则指类的功能应该是尽量单一的。要修改一个类的时候,应该只因为一个原因
接口隔离原则接口要尽量独立,不要把很多接口包在一个模块中,否则,当用户只需要某个接口时,就需要把很多不相关的接口导入进来,也就是“强迫”了用户依赖于人家不需要的接口
依赖反转原则这个原则有两层含义,一是高级别模块不应该依赖于低级别模块,但都应该依赖于抽象;二是抽象不应该依赖于具体,但具体应该依赖于抽象
迪米特原则迪米特法则又叫最少知识原则。如果两个软件实体无须直接通信,那么就不应当发生直接的相互调用,可以通过第三方转发该调用。其目的是降低类之间的耦合度,提高模块的相对独立性。
共同封闭指因某一个同样的原因而需要修改的所有类,都应该封闭进同一个包中
共同重用指一个包中的所有类应该是共同重用的,即如果重用了包中的一个类,那么就要重用包中的所有类

考点:设计模式

23中设计模式图解

创建者模式结构型模式行为型模式
单例模式代理模式模板方法模式
工厂方法模式适配器模式策略模式
抽象工厂模式装饰者模式命令模式
原型模式桥接模式职责链模式
建造者模式外观模式状态模式
组合模式观察者模式
享元模式迭代器模式
访问者模式
备忘录模式
解释器模式
中介者模式

考点:ISO/IEC 9126软件质量模型

功能性可靠性易用性效率维护性可移植性
适合性
准确性
互操作性
依从性
安全性
容错性
易恢复性
成熟性
易学性
易理解性
易操作性
时间特性
资源利用特性
易分析性
易改变性
稳定性
易测试性
适应性
易安装性
共存性
易替换性

内容详情

考点:类的划分

类可以分为三种:实体类、接口类(边界类)、控制类

类型内容
实体类实体类的对象表示现实世界中真实的实体,如人、物等
接口类(边界类)接口类的对象为用户提供一种与系统合作交互的方式,分为人和系统两大类,其中人的接口可以是显示屏、窗口、对话框等。系统接口涉及到把数据发送到其他系统,或者从其他系统接收数据
控制类控制类的对象用来控制活动流,充当协调者

考点:UML类图

九种常见的UML类图总结:UML类图

类与类之间关系的表达方式
(一)关联关系
关联关系是对象之间的一种引用关系,用于表示一类对象与另一类对象之间的联系,如老师和学生、师傅和徒弟、丈夫和妻子等。关联关系是类与类之间最常用的一种关系,分为一般关联关系、聚合关系和组合关系。我们先介绍一般关联。

关联又可以分为单向关联,双向关联,自关联。

1,单向关联

在UML类图中单向关联用一个带箭头的实线表示。上图表示每个顾客都有一个地址,这通过让Customer类持有一个类型为Address的成员变量类实现。

2,双向关联

从上图中我们很容易看出,所谓的双向关联就是双方各自持有对方类型的成员变量。

在UML类图中,双向关联用一个不带箭头的直线表示。上图中在Customer类中维护一个List,表示一个顾客可以购买多个商品;在Product类中维护一个Customer类型的成员变量表示这个产品被哪个顾客所购买。

3,自关联


自关联在UML类图中用一个带有箭头且指向自身的线表示。上图的意思就是Node类包含类型为Node的成员变量,也就是“自己包含自己”。

(二)聚合关系
聚合关系是关联关系的一种,是强关联关系,是整体和部分之间的关系。

聚合关系也是通过成员对象来实现的,其中成员对象是整体对象的一部分,但是成员对象可以脱离整体对象而独立存在。例如,学校与老师的关系,学校包含老师,但如果学校停办了,老师依然存在。

在 UML 类图中,聚合关系可以用带空心菱形的实线来表示,菱形指向整体。下图所示是大学和教师的关系图:

(三)组合关系
组合表示类之间的整体与部分的关系,但它是一种更强烈的聚合关系。

在组合关系中,整体对象可以控制部分对象的生命周期,一旦整体对象不存在,部分对象也将不存在,部分对象不能脱离整体对象而存在。例如,头和嘴的关系,没有了头,嘴也就不存在了。

在 UML 类图中,组合关系用带实心菱形的实线来表示,菱形指向整体。下图所示是头和嘴的关系图:

(四)依赖关系
依赖关系是一种使用关系,它是对象之间耦合度最弱的一种关联方式,是临时性的关联。在代码中,某个类的方法通过局部变量、方法的参数或者对静态方法的调用来访问另一个类(被依赖类)中的某些方法来完成一些职责。

在 UML 类图中,依赖关系使用带箭头的虚线来表示,箭头从使用类指向被依赖的类。下图所示是司机和汽车的关系图,司机驾驶汽车:

(五)继承关系
继承关系是对象之间耦合度最大的一种关系,表示一般与特殊的关系,是父类与子类之间的关系,是一种继承关系。

在 UML 类图中,泛化关系用带空心三角箭头的实线来表示,箭头从子类指向父类。在代码实现时,使用面向对象的继承机制来实现泛化关系。例如,Student 类和 Teacher 类都是 Person 类的子类,其类图如下图所示:

(六)实现关系
实现关系是接口与实现类之间的关系。在这种关系中,类实现了接口,类中的操作实现了接口中所声明的所有的抽象操作。

在 UML 类图中,实现关系使用带空心三角箭头的虚线来表示,箭头从实现类指向接口。例如,汽车和船实现了交通工具,其类图如下图所示。

考点:MTTF、MTTR、MTBF

  1. MTBF——全称是Mean Time Between Failure,即平均失效间隔。就是从新的产品在规定的工作环境条件下开始工作到出现第一个故障的时间的平均值。MTBF越长表示可靠性越高正确工作能力越强 。
  2. MTTR——全称是Mean Time To Repair,即平均恢复时间。就是从出现故障到恢复中间的这段时间。MTTR越短表示易恢复性越好。
  3. MTTF——全称是Mean Time To Failure,即平均无故障时间。系统平均能够正常运行多长时间,才发生一次故障。系统的可靠性越高,平均无故障时间越长。(MTTF=MTBF+MTTR)

可靠性:MTTF /(1+MTTF)
可用性:MTBF /(1+MTBF)
可维护性:1 /(1+MTTR)

考点:V模型

RAD(Rapid Application Development,快速应用开发)模型是软件开发过程中的一个重要模型,由于其模型构图形似字母V,所以又称软件测试的V模型。


在V模型中,有以下对应关系

  • 需求分析 —— 验收测试
  • 概要设计 —— 系统测试
  • 详细设计 —— 集成测试
  • 软件编码 —— 单元测试

但不管哪一阶段的测试,其测试的目标都来自需求分析!

考点:嵌入式操作系统的特点

微型化:从性能和成本角度考虑,希望占用的资源和系统代码量少。
可定制:从减少成本和缩短研发周期考虑,要求嵌入式操作系统能运行在不同的微处理器平台上,能针对硬件变化进行结构与功能上的配置,以满足不同应用的需求。
实时性:嵌入式操作系统主要应用于过程控制、数据采集、传输通信、多媒体信息及关键要害领填需要迅速响应的场合,所以对实时性要求较高。
可靠性:系统构件、模块和体系结构必须达到应有的可靠性,对关键要害应用还要提供容错和防故障措施。
易移植性:为了提高系统的易移植性,通常采用硬件抽象层和板级支持包的底层设计技术。

考点:软件维护的特点

更正性:由于系统测试不可能揭露系统存在的所有错误,因此在系统投入运行后频繁的实际应用过程中,就有可能暴露出系统内隐藏的错误。
适应性维护:适应性维护是为了使系统适应环境的变化而进行的维护工作。
完善性维护:在系统的使用过程中,用户往往要求扩充原有系统的功能,增加一些在软件需求规范书中没有规定的功能与性能特征,以及对处理效率和编写程序的改进。
预防性维护:系统维护工作不应总是被动地等待用户提出要求后才进行,应进行主动的预防性维护。即选择那些还有较长使用寿命,目前尚能正常运行,但可能将要发生变化或调整的系统进行维护,目的是通过预防性维护为未来的修改与调整奠定更好的基础。

考点:分布式数据库特点

1)逻辑透明性(局部映像透明性):它是最低层次的透明性,该透明性提供数据到局部数据库的映像,即用户不必关心局部 DBMS 支持哪种数据模型、使用哪种数据操纵语言,数据模型和操纵语言的转换是由系统完成的。因此,局部映像透明性对异构型和同构异质的分布式数据库系统是非常重要的。

2)位置透明性:用户不必知道所操作的数据放在何处,即数据分配到哪个或哪些站点存储对用户是透明的。因此,数据分片模式的改变,如把数据从一个站点转移到另一个站点将不会影响应用程序,因而应用程序不必改写。

3)分片透明性:用户不必关心数据是如何分片,他们对数据的操作在全局关系上进行,即关心如何分片对用户是透明的,因此,当分片改变时应用程序可以不变。

4)复制透明性:用户不用关心数据库在网络中的各个节点的复制情况,被复制的数据的更新都由系统自动完成。

七、程序语言基础

考点:词法、语法、语义分析

阶段任务
词法分析在输入源程序时对构成源程序的字符串进行扫描和分解,识别出一个个单词,删除无用的信息,并报告分析出来的错误。词法如关键字(保留字)、标识符、常数、运算符、分隔符 等。
语法分析在词法分析的基础上,根据语言的语法规则将单词符号序列分解成各类语法单位。通过语法分析确定整个输入串是否构成一个语法上正确的程序,然后构造成一颗语法树。语法如“表达式”、“赋值”、“循环”,按语法规则分析检查每条语句是否有正确的逻辑结构。
语义分析检查源程序是否存在语义错误,并收集类型信息供后面的代码生成阶段使用。主要有这三个方面:类型检查和自动类型转换、常量表达式的计算、运算符重载和函数重载
目标代码生成目标代码生成是编译的最后一个阶段。目标代码生成器把语法分析后或优化后的中间代码变换成目标代码。

详情见百度百科:编译原理

考点:调用函数,采用传值方式和传引用方式区别

实现函数调用时,形参具有独立的存储空间。

  • 在传值方式下,将实参的值拷贝给形参
  • 在传引用方式下,将实参的地址传给形参,也可简单理解为被调用函数中形参名实际成了实参的一个别名

如图所示:

在这张图中,调用函数f(1,x)执行时(第一个参数传值,第二个传引用)
1、形参x的初始值为1,a的值为2(形参a指向main函数中的变量x)
2、经过“x=2*a+1”,形参x的值变为了5,经过“a=x+3”,a的值变为8,而a实质上是main函数中x的别名,所以返回后x的值为8

考点:编译与解释

在编译过程中:词法分析;语法分析;语义分析;目标代码生成是必须的,而代码优化和中间代码生成是可以不需要的。

编译和与解释的区别在于:编译直接生成与源程序等价的目标程序,在机器上执行而编译器不需要参与执行,因此程序执行速度快;解释则生成中间代码或其等价形式,程序执行时需要解释器的参与,并且由解释器控制程序的执行,因此执行速度慢。

考点:有限自动机


有限自动机上都会有一个初态终态,每一个状态都都与其他状态有连线,连线上面的数字表示从一个状态输入n可以到达另一个状态。当此表初态走到终态,那一连串的数字代表的是能识别的输入

看如下例题:

经过一一带入可知,只有依次输入0101可以从初态A到达终态C。

确定的有限自动机DFA与不确定的有限自动机NFA的区别:
确定的有限自动机在任何一个状态,基于输入的字符都能完成一个确定的状态转换;不确定的有限自动机是指该状态机在任何一个状态,基于输入的字符都不能完成一个确定的状态转换,这里分两种情况:①对于一个输入,它有两个或更多状态可以转换;②存在E的情况,即没有任何字符输入的情况下,NFA可以从一个状态迁移到另一个状态。

考点:并行系统与串行系统可靠度计算

  • 串行系统的可靠度:R=R1×R2×…Rn
  • 并联系统的可靠度:R=1-(1-R1)×(1-R2)×…×(1-Rn)

考点:算数表达式

表达式有三种:前缀表达式、中缀表达式、后缀表达式。实际上分为前、中、后这里和树的变遍历方式——前中后序遍历是类似的。

前序遍历:按照 根 -> 左孩子 -> 右孩子 顺序遍历
中序遍历:按照 左孩子 -> 根 -> 右孩子 顺序遍历
后序遍历:按照 左孩子 -> 右孩子 -> 根 顺序遍历

那么现在再看表达式就简单了。
比如:算数表达式 a*(b+c/d)-e的后缀式
第一步:先对表达式 a*(b+c/d)-e(中缀)构造一颗树

第二步:用后序遍历的方式来遍历这颗树
结果为:a b c d / + * e -

八、数据结构

考点:树

1、二叉排序树、完全二叉树、线索二叉树和最优二叉树的概念
可以参考一下我以前写过的这篇文章:二叉排序树、完全二叉树、线索二叉树、最优二叉树

2、先序遍历、中序遍历、后序遍历
其实这个非常简单,只需要记住遍历的顺序就行:

先序遍历:根 -> 左 -> 右 根节点先遍历,再到左孩子,最后右孩子
中序遍历:左 -> 中 -> 右 左孩子先遍历,再到根结点,最后右孩子
后序遍历:左 -> 右 -> 根 左孩子先遍历,再到右孩子,最后根结点

实际上你会发现,先中后的意思,就是根是在什么时刻遍历,是最先,还是中时刻,还是最后呢,

考点:图的存储(邻接矩阵、邻接表)

1、邻接矩阵

邻接矩阵的大小取决于图的节点数,例如图中有5个结点,那么邻接矩阵的大小就是5×5

那么邻接矩阵的数据是怎么由图转换过来的呢?
很简单,先给邻接矩阵编号,比如说(1,1)表示的就是第一行第一列的数据,为0,说明结点1和结点1之间没有连线。同理,(1,2)为1,说明结点1和结点2有一条连线,以此类推。

2、邻接表

邻接表会记录所有节点,每个节点能到达哪个节点,用链表的形式记录下来。如上图,与V1相邻的节点有V2,距离为6;V4,距离为1;V6,距离为50。在邻接表中就是以V1——26——41这样连接。

邻接表先用一个数组记录每个节点,在用链表记录每个节点能到的顶点的情况。

考点:广度优先与深度优先遍历

深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次(二叉树的深度优先遍历比较特殊,可以细分为先序遍历,中序遍历,后序遍历)。

广度优先遍历:又叫层次遍历从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问节点,访问完一层就继续访问下一层,直到没有节点可以访问为止。

分别深度优先和广度优先来得到图例这颗树的遍历次序


深度优先:一路走到底,路不通就换另一条路。
遍历顺序:ABDEFGC

广度优先:对于每个结点每次先访问完它的邻结点,再往下走
遍历顺序:ABCDEFG

考点:排序算法(复杂度)


各种排序算法的时间复杂度和空间复杂度

考点:算法设计策略

算法设计特点
分治分治算法求出的子问题是互相独立的
贪心总是做出在当前来说是最好的选择,而并不从整体上加以考虑,它所做的每步选择只是当前步骤的局部最优选择,但从整体来说不一定是最优的选择。
动态规划具有最优子结构性质和重叠子问题性质
回溯回溯法是一种选优搜索法,按选有条件向前搜索,以达到目标。但当搜索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择。类似于深度优先算法

九、数据库

考点:确定候选码

概念:通过一个(或一组)属性(即候选码)可以唯一地标识一个元组

怎么确定候选码呢?
比如在一个关系R(U,F),其中U={A,B,C,D,E,H},F={A->B,B->DH,A->H,C->E}
将依赖关系转换为有向图形式

我们会发现,只有(A,C)这个组合作为候选码(有向图起点)时,才能遍历整个有向图。而只靠A或只靠C作为候选键是无法遍历得到所有结点的。

考点:部分依赖、完全依赖、传递依赖

(一)部分函数依赖

设X,Y是关系R的两个属性集合,存在X→Y,若X’是X的真子集,存在X’→Y,则称Y部分函数依赖于X。

例如:通过AB能得出C,通过A也能得出C,通过B也能得出C,那么说C部分依赖于AB。

(二)完全函数依赖
设X,Y是关系R的两个属性集合,X’是X的真子集,存在X→Y,但对每一个X’都有X’!→Y,则称Y完全函数依赖于X。

例如:通过AB能得出C,但是AB单独得不出C,那么说C完全依赖于AB.

(三)传递函数依赖

设X,Y,Z是关系R中互不相同的属性集合,存在X→Y(Y !→X),Y→Z,则称Z传递函数依赖于X。

例如:通过A得到B,通过B得到C,但是C得不到B,B得不到A,那么成C传递依赖于A

考点:关系代数表达式

首先准备S1和S2两张表

1、并
符号为“∪”,它运算的结果是将两张表合并起来,并去除重复的内容。

2、交

符号为“∩”,它运算的结果是将两张表公共部门提取出来

3、差
符号为“-”,它意思就是“我有的你没有”,什么意思呢?比如说S1-S2,表示的就是在S1表中有的内容在S2表中没有的内容。如下图所示

这两行结果均只在S1中出现,在S2中没有

4、笛卡尔积
笛卡尔积符号为“×”,它的运算是将两个集合中任意取出两个元素构成的组合的集合。有点像数学中(a+b)×(c+d)=ac+ad+bc+bd。也就是所有元素都要两两组合一次。

5、投影
投影的符号是“π”,关系R上的投影是从R中选择出若干属性列组成新的关系,如下图所示,“πSno,Sname(S1)”,意思是得到在S1上投影出来的Sno和Sname两列数据,其他不需要投影的数据就不需要。类似于sql语句中的select Sno,Sname from S1;

“πSno,Sname(S1)” 还可以表示为 “π1,2(S1)”
6、选择
选择的符号是“σ”,代表着在关系R上选择出满足条件的元组。例如“σSno=No0003(S1)”意思是在S1表中选择满足Sno=No0003条件的记录。类似于sql语句中的select * from S1 where Sno =No0003

“σSno=No0003(S1)” 还可以表示为 “σ1=No0003(S1)”

7、连接

连接的符号是“⋈”,意思是将多表进行连接,它与笛卡尔积的区别是,它会把需要连接的表都有的字段只保留一个。一般来说⋈下面会接上连接条件。

考点:1NF、2NF、3NF

(一)第一范式1NF

符合1NF的关系中的每个属性都不可再分。

(二)第二范式2NF

消除了1NF非主属性对主属性的部分函数依赖。

(三)第三范式3NF

消除了非主属性对码的传递函数依赖。

考点:共享锁与排他锁

共享锁:又称读锁或S锁。若事务T对数据加上共享锁,其他事务也只能对该数据加共享锁。

排他锁:又称写锁或X锁。若事务T对数据加上排他锁,其他事务不能再对该数据加任何锁,直至事务T释放加在数据上的锁。

考点:外连接

左外连接:左表不加限制,保留左表的数据,匹配右表,右表没有匹配到的行中的列显示为null。
右外连接:右表不加限制,保留右表的数据。匹配左表,左表没有匹配到的行中列显示为null。
完全外连接:左右表都不加限制。即右外连接的结果为:左右表匹配的数据+左表没有匹配到的数据+右表没有匹配到的数据。

考点:数据流图

数据流图是结构化开发的一种工具,它描述了系统的输入数据流如何经过一系列的加工,逐步变换成系统的输出数据流,属于一种功能模型。数据流图的基本成分及图形表示法如下图所示。


这几个角色的概念:

  • 数据流:由一组固定成分的数据组成,表示数据的流向,每一个数据流都有一个定义明确的名字。
  • 加工:加工描述了输入数据流到输入数据流之间的变换,即输入数据流经过什么处理后编程输出数据流,每个加工都有一个名字和编号;
  • 数据存储:数据存储用来存储数据,每个数据存储都有一个定义明确的名字标识;
  • 外部实体:指存在于软件系统之外的人员或组织,它指出系统所需数据的发源地和系统所产生的数据的归属地,每个外部实体都有一个定义明确的名字标识。

考点:外模式、模式和内模式

一、模式(Schema)

定义:也称逻辑模式,是数据库中全体数据的逻辑结构和特征的描述,是所有用户的公共数据视图。

理解: ① 一个数据库只有一个模式; ② 是数据库数据在逻辑级上的视图; ③ 数据库模式以某一种数据模型为基础; ④ 定义模式时不仅要定义数据的逻辑结构(如数据记录由哪些数据项构成,数据项的名字、类型、取值范围等),而且要定义与数据有关的安全性、完整性要求,定义这些数据之间的联系。

二、外模式(External Schema)

定义:也称子模式(Subschema)或用户模式,是数据库用户(包括应用程序员和最终用户)能够看见和使用的局部数据的逻辑结构和特征的描述,是数据库用户的数据视图,是与某一应用有关的数据的逻辑表示。

理解: ① 一个数据库可以有多个外模式; ② 外模式就是用户视图; ③ 外模式是保证数据安全性的一个有力措施。

三、内模式(Internal Schema)

定义:也称存储模式(Storage Schema),它是数据物理结构和存储方式的描述,是数据在数据库内部的表示方式(例如,记录的存储方式是顺序存储、按照B树结构存储还是按hash方法存储;索引按照什么方式组织;数据是否压缩存储,是否加密;数据的存储记录结构有何规定)。

理解: ① 一个数据库只有一个内模式; ② 一个表可能由多个文件组成,如:数据文件、索引文件。 它是数据库管理系统(DBMS)对数据库中数据进行有效组织和管理的方法 其目的有: ① 为了减少数据冗余,实现数据共享; ② 为了提高存取效率,改善性能。

例题:数据库系统中的视图、存储文件和基本表分别对应数据库系统结构的外模式、内模式和模式

原文链接


由于时间关系,上午题资料整理只有这么多了,有待完善。文章内容大部分是笔记整理,若有侵权部分,请联系删除。

部分参考内容:
王勇,软件设计师课程;黑马,设计模式;王道,操作系统;湖科大,计算机网络;

本文标签: 复习资料 提纲 设计师 上午 软件