1.E-R图
也称为实体联系图，提供了表示实体类型，属性和联系的方法，用来描述现实世界的概念模型。它有四个成分：
矩形框：用来表示实体，在框中记入实体名
菱形框：表示联系，在框中记入联系名
椭圆形框：用来表示实体或联系的属性，将属性名记入框中（对于主属性名则在其名称下划一下划线）
连线：实体与属性之间，实体和联系之间，联系与属性之间用直线相连，并在直线上标注联系的类型。
题目：在进行逻辑设计时，将E-R图中实体之间联系转换为关系数据库的关系
将E-R图转换为关系模式时，实体和联系都可以表示为关系
1.2 数据流程图
在数据流程图中用标有名字的箭头表示数据流
1.3程序流程图
用标有名字的箭头表示控制流
2.1.顺序表和链表的优缺点比较
顺序表-优点：
可以随机取存表中的任意结点
无需为表示结点间的逻辑关系额外增加存储空间
-缺点：
顺序表的插入和删除运算效率很低
顺序表的存储空间不便于扩充
顺序表不便于对存储空间动态分配
链表-优点：
在进行插入和删除运算时，只需要改变指针即可，不需要移动元素
链表的存储空间易于扩充并且方便空间的动态分配
-缺点：
需要额外的空间（指针域）来表示数据元素之间的逻辑关系，存储密度比顺序表低
2.2.关于链表其他知识
双向链表是线性结构，二叉树为非线性结构，二者结点中均有两个指针域。
循环链表是线性结构,是队列的一种顺序存储结构，队列的顺序存储结构一般采用循环队列的形式。
2.3 线性链表
一般来说，在线性表的链式存储结构中，各数据结点中的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。线性链表中数据的插入和删除都不需要移动表中的元素，只需要改变节点的指针域结点即可。
2.4 循环队列
循环队列有队头和队尾两个指针，但循环队列依旧是线性结构，在循环队列中需要两个队头和队尾指针来共同反映队列中元素的动态变化情况
2.5 线性表
栈是一种先进后出的线性表
队列是一种先进先出的线性表
对于长度为n的线性表，常用的排序算法最坏情况下的比较次数为：
冒泡排序————0（n2）
简单插入排序——- 0（n2）
简单选择排序——- 0（n2）
快速排序————0（n2）
堆排序————–0（nlog2n）
希尔排序————0（n1.5）
在长度为n的有序线性表中进行二分法查找，最坏情况下需要比较的次数为：
二分法查找———-0（log2n）
顺序查找————0（n）
2.6 栈
栈是先进后出的数据结构，所以栈顶元素最后入栈却最先删除，栈底元素最先入栈却最后被删除。
在整个过程中，栈底指针不变，入栈与出栈操作均由栈顶指针操作。
入栈运算即在栈顶位置插入一个新元素，退栈运算即取出栈顶元素赋予指定变量。
2.7 支持子程序调用的是栈
3.二叉树
完全二叉树：除最后一层外，每一层上的结点数均达到最大值
深度：在树的结构中，定义一棵树的根结点所在层次为1，其他结点所在的层次等于它的父结点所在的层次加1，树的最大层次称
树的深度。深度为6的满二叉树，结点个数为：2的6次方-1=63
度：二叉树（树）结点的度数指该结点所含子树的个数，二叉树（树）结点子树个数最多的那个结点的度为二叉树（树）的度
对任何一棵二叉树，度为0的结点（叶子结点）总是比度为2的结点多一。n0=n2+1
二叉树通常采用链式存储结构，也可以采用其他的存储结构。
4.有序
指特定元素按非递减排列。即从小到大排列，但允许相邻元素相等，有序表可以是顺序存储，也可以是链式存储，故（所谓有序表是指在顺序存储空间内连续存放的元素序列）错，有序表可以用链接存储方式在不连续的存储空间内。
5.二分法查找
能用二分法查找的线性表必须满足两个条件，用顺序存储结构存储，线性表是有序表。
6.1.软件的特点
软件是一种逻辑实体，具有抽象性
软件没有明显的制作过程
软件在使用过程中不在磨损，老化问题
对硬件和环境具有依赖性
软件复杂性高，成本昂贵
软件开发涉及诸多的社会因素
6.2软件分类
软件按功能可以分为，应用软件，系统软件，支撑软件。
操作系统，编译程序，汇编程序，网络软件，数据库管理程序都属于系统软件。比如学生成绩管理系统就是应用软件。
6.3.软件需求分析阶段任务：
需求获取，需求分析，编写需求规格说明书，和需求评审
在需求分析阶段可以使用的工具有数据流图（DFD图），数据字典（DD图），判定树与判定表
6.4.软件设计常用的工具：
图形工具，如程序流程图，N-S图（用方框图来代替传统的程序流程图），PAD图（问题分析图），HIPO图（层次结构图）
表格工具，如判定表
语言工具，PDL（伪码）
另外，在结构化设计方法中，常用的结构设计工具是结构图，结构化设计的思想包括自顶而下，逐步求精，模块化，限制使用GOTO语句。（不包括多态性！）
详细设计的任务是为软件结构图中而非总体结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。故（系统总体结构图支持软件系统的详细设计）错，PAD是软件详细设计的表示工具。
6.5.软件危机
软件需求的增长得不到满足
软件开发成本和进度无法控制
软件质量难以保证
软件不可维护或维护程度非常低
软件的成本不断提高
软件开发生产率的提高赶不上硬件的发展和应用需求的增长
6.6 软件测试的目的
软件测试的目的是发现程序中的错误。
6.7 软件的生命周期
软件产品从提出，实现，使用维护到停止使用退役的过程
7.1.计算机软件
由两部分组成，一是机器可执行的程序和数据，二是机器不可执行的，与软件开发，运行，维护，使用等有关的文档。
7.2计算机系统
由计算机硬件系统和软件系统两部分组成，硬件包括*处理器，存储器和外部设备等。软件有计算机的运行程序和相应的文档
7.3 计算机的系统总线
是计算机各部件间传递信息的公共通道，分为。数据总线，控制总线，地址总线
7.4 计算机操作系统
的五大功能：CPU管理，存储管理，文件管理，设备管理，作业管理
7.5.CPU
除了内部总线和必要的寄存器外，主要的两大部件分别是运算器和控制器。
通常说的计算机主机指，Cpu、和内存。
CPU可以直接存取内存储器上的数据
CPU的主要性能指标之一的主频是用来表示CPU内核工作的时钟频率
7.6 计算安全设置
停掉Guest账号，Guest账号即来宾账号，它可以访问计算机，但是受到控制。
7.7 计算机指令
由操作数和操作码两部分组成；
指令的地址码部分可能是操作数，也可能是操作数的内存单元地址
8.计算机网络的主要功能
数据通信，资源共享，多分布信息处理。
考点：在计算机网络中，所有计算机均连接到一条通信传输线路上，在线路两端连有防止信号反射的装置，这种连接结构被称为总线结构（以太网）
9.1.数据库语言
数据定义语言：负责数据的模式定义与数据的物理存取构建
数据操纵语言：负责数据的操纵，包括查询及增加，删除，修改等操作
数据控制语言：负责数据完整性，安全性的定义与检查以及并非控制，故障恢复等功能
9.2.数据库系统的三级模式
概念模式：是数据库系统中全局数据逻辑结构的描述，是全体用户公共数据视图
外模式：子模式或用户模式，它是用户的数据视图，给出了每个用户的局部数据描述
内模式：又称物理模式，它给出了数据库物理存储与物理存取方法
数据库设计中反映用户对数据要求的模式是，外模式。
9.3 数据库设计
数据库应用系统中的核心问题是数据库设计；
在需求分析阶段建立数据字典
在数据库设计过程中，将E-R图转换为关系数据模型的过程是逻辑设计阶段
9.4 数据库（DB），数据库系统（DBS），数据库管理系统（DBMS）
DBS包括DB和DBMS
9.5 数据管理
至今已经经历了3个阶段：人工管理阶段（无共享），文件系统阶段（共享性差）和数据库系统阶段（共享性大）。
10.1 数据的独立性
包括物理独立性和逻辑独立性，物理独立性指数据的物理结构的改变，不会影响数据库的逻辑结构，也不会引起应用程序的改变，逻辑独立性是指数据库的总体逻辑结构的改变，不会影响相应的应用程序的改变。
10.2 模块的独立性
耦合性和内聚性是度量模块独立性的两个标准
低耦合，高内聚，有利于提高模块的独立性
11.操作系统
在计算机系统软件中，最重要且最基本的就是操作系统（Operating system），它是最底层的软件，它控制所有计算机运行的程序并管理整个计算机的资源，是计算机裸机和应用程序及用户之间的桥梁，没有它，用户也就无法使用某种软件或程序。
考点：从用户观点看，操作系统是用户与计算机之间的接口
12.源程序
指未经编译的，按照一定的程序设计语言规范书写的，人类可读的文本文件，通常由高级语言编写，源程序可以是以书籍或者磁带或者其他载体的形式出现，但最为常用的格式是文本文件，这种典型格式的目的是为了编译出计算机可以执行的程序。
编译程序的最终目的是将源程序编译成目标程序。
13.环形拓扑结构
是使用中继器组成一个封闭的环，各节点直接连到环上，信息沿着环按一定方向从一个节点传送到另一个节点的拓扑结构。
14.DNS
是计算机域名系统或域名解析服务器，它是由解析器以及域名服务器组成的，域名服务器是保存有该网络中所有主机的域名和对应的IP地址，并将域名转换为IP地址功能的服务器，在Internet中完成从域名到IP地址或者从IP地址到域名转换服务的是DNS。
15.逻辑模型
也称数据模型，是面向数据库系统的模型，着重于在数据库系统一级的实现，成熟并大量使用的数据模型有层次模型，网状模型，关系模型和面向对象模型等。
16.堆排序
堆排序属于选择类的排序方法，最坏情况下时间复杂度为O（nlog2 n）
17.扇入扇出
在软件设计中，扇入和扇出的概念是指应用程序模块之间的层次调用情况。
按照结构化设计方法，一个应用程序是由多个功能相对独立的模块所组成。
扇入：是指直接调用该模块的上级模块的个数。扇入大表示模块的复用程序高。
扇出：是指该模块直接调用的下级模块的个数。扇出大表示模块的复杂度高，需要控制和协调过多的下级模块；但扇出过小（例如总是1）也不好。扇出过大一般是因为缺乏中间层次，应该适当增加中间层次的模块。扇出太小时可以把下级模块进一步分解成若干个子功能模块，或者合并到它的上级模块中去。
设计良好的软件结构，通常顶层扇出比较大，中间扇出小，底层模块则有大扇入。
18.存储单位
计算机存储信息的最小单位是位（bit，又称比特），存储器中所包含存储单位的数量称为存储容量，其计量基本单位是字节（byte，简称B），8个二进制位称为1个字节。
MIPS（Million Instruction Per Second）是计算机每秒执行的百万指令数，是衡量计算机速度的指标。
1024KB= 1MB
1024MB= 1GB
1024GB= 1TB
256MB=2（8）MB
1GB=1024MB=2（10）MB
19.ROM
即只读存储器，Read-Only-Memory，是一种只能读出事先所存数据的固态半导体存储器。其特性是一旦存储资料就无法再将之改变或者删除，通常用在不需经常变更资料的电子或计算机系统中，并且资料不会因为电源关闭而消失。
20.声音的计算公式
（采样频率Hz*量化位数bit *声道数 ）/8 单位为字节/秒
若要求每分钟产生的数据量，则应该再*60
21.1 千兆以太网
是一种高速局域网，其网络数据传输速率大约是 1000000位/秒
以太网的拓扑结构是总线型
21.2 网卡
网卡是构成网络所必须的基本设备，用于将计算机和通信电缆连接起来，以便使电缆在计算机中间进行高速数据传输，因此每台连到局域网的计算机都需要安装一块网卡。
22.磁道
磁盘上的磁道是一组记录密度不同的同心圆
23.关系
在一个关系中，候选关键字可以有多个，且在任何关系中至少有一个候选关键字，所以在满足实体完整约束的条件下，一个关系应该有一个或者多个候选关键字。
投影：
关系R（ABC）变成-关系S（AB）
自然连接：
下图中由R，S得到T的操作时 
差： 
24.黑盒测试
对软件已经实现的功能是否满足需求进行测试和验证，黑盒测试完全不考虑程序内部逻辑结构和内部特性，只根据程序的需求和外部功能规格说明，检查程序的功能是否符合它的功能说明。
25 缩写
CAD-Computer Aided Design-计算机辅助设计
CAM-Computer Aided Manufacturing-计算机辅助制造
CIMS-Computer Integrated Manufacturing Systems-计算机集成制造系统
CAI-Computer Aided Instruction-计算机辅助教学
ISDN-Integrated Services Digital Network-综合业务数字网（接入因特网的优点是上网通话两不误）
ADSL-非对称数字用户环路
ISP-互联网服务提供商
TCP-传输控制协议
26.1 电子计算机传统的分代方法
第一代到第四代分别为：
电子管计算机，晶体管计算机，中小规模集成电路计算机，大规模和超大规模集成电路计算机
26.2 第一台计算机
世界上公认的第一台电子计算机诞生的年代是 1946-ENIAC在美国宾夕法尼亚大学
世界上第一台冯·诺依曼式计算机是1949年研制的EDVAC，由于他对现代计算机技术的突出贡献，因此冯·诺依曼又被称为“现代计算机之父”。其中包括控制器，存储器，输入设备，输出设备，运算器。
27.Internat应用
新闻组，远程登陆，搜索引擎，（网络协议不属于应用）；
在Internat为人们提供的多种服务项目中，最常用的是在各Internet站点之间漫游，浏览文本，图形和声音各种信息，这项服务称为 www；
Internet环境中的防火墙建立在内部网络与外部网络的交叉点
28.机器语言
不同型号的计算机具有不同的计算机语言；
机器语言是由一串二进制数0，1组成；
用机器语言编写的程序执行率最高；
29.CD光盘
在光盘上标有“CD-RW”字样，“RW”标记表明该光盘是，可多次擦除型光盘，即可多次对其进行读/写，
其英文全称为CD-ReWritable