1 基础知识

计算机采用的是 存储程序控制 原理。

计算机功能部件--运算器 存储器 控制器 输入设备 输出设备

计算机指令类型--数据传送类、算术逻辑类、判定控制类

总线--数据总线 地址总线 控制总线

系统软件包括--程序设计语言处理程序 操作系统 数据库管理系统 通用服务程序

配置技术指标--运算速度MIPS 主频Hz 字长 存储容量 数据传输率bps

计算机应用领域--科学和工程计算 数据和信息处理 过程控制 计算机辅助系统 人工智能 网络应用 汉字代码体系--输入码 机内码 交换码（矢量 点阵)

网络分类

传输技术--广播式网络 点一点是网络

覆盖的地理范围--广域网 局域网（以太网） 城域网（FDDI）

广域网

X.25--速率较低 误码率高

帧中继--光纤 传输速率高 误码率高

ISDN--成本高 线路利用率低

ATM--满足多媒体网络

A类IP地址 空间长度7位 主机地址长度24位

B类IP地址 空间长度14位 主机地址长度16位

C类IP地址 空间长度21位 主机地址长度8位（192.0.0.0-223.255.255.255）

超文本标注语言HTML 超文本传输协议HTTP Internet服务提供者ISP

标准的URL组成--主机名 文件名与路径 协议类型

ISDN ADSL适用于小型公司 DDN 帧中继适用于大型企业

信息认证--数字签名技术 身份识别技术 信息的完整性校验技术

计算机病毒--传染性 破坏性 隐藏性 潜伏性 可激发性

操作系统的安全--隔离 分层 内控

网络安全主要涉及的内容--安全攻击 安全服务 安全机制

2 数据结构与算法

数据结构--数据的逻辑结构 存储结构 运算

算法的代价 if n>N T(n)<=C*f（n）

顺序表--插入一个结点和删除一个结点所需移动节点个数=n/2

栈stack LIFO stack push(S.x) pop(S) top(S.x) empty(S) makempty(S)

队列queue FIFO queue enq(Q.x) deq(Q) front(Q.x) empty(Q）makempty(Q)

头变量Q。F 存放进行删除运算时应被删除的元素的下标

尾变量Q。R 存放待插入新元素的空位置的下标

定义

TYPE stack =RECORD

A;ARRAY[1..m]OFdatatype

t;0..m

VAR S;stack

栈的推入

PROCEDURE push(VAR s:stack;x:datatype)

BEGIN

IF s.t=m

THEN print(‘overflow')

ELSE BEGIN

s.t;=s.t + 1;

s.A[s.t];= x;

END

END

串最坏的情况下 比较次数n-m+1

二叉树 度-一个结点子树的个数 高度-叶结点的最大层数 层-父节点层数（0）加1.

完全二叉树；只有最下面两层度<2,最后一层节点都在左边。

树对应的二叉树 左结点是子女右结点是兄弟

线索二叉树；n个结点有n+1个空指针。

扩充二叉树（霍夫曼算法）的外部结点=二叉树结点+1

顺序查找优点；逻辑次序无要求，对存储结构无要求。

缺点；平均检索长度长。平均比较次数（n+1）/2.

二分法平均检索长度小，平均比较次数log2n。

缺点；需将线性表排序，存储方式插入删除不方便。

处理碰撞的方法 拉链法和开地址法

二叉排列树 左子树<根结点<右子树

最佳排序二叉树除了最下面一层各层都是满的。

B树--1，每个结点至多有m棵子树 2，根结点或为叶结点或至少有两棵子树 3 中间节点至少有m/2棵子树 4 k(i)<k(i+1) 5 叶结点出现在同一层

B+树--1 每个结点至多有m个子女 2 每个结点至少有m/2个子女 3 根结点至少有2个子女 4有l个子女的结点必须有l个关键码

直接插入排序平均比较i/2,总移动个数n*n/4.

二分法比较次数nlog2n,移动个数n*n。

shell排序法比较次数和移动个数为n（1.3）

直接排序比较次数为 n（n-1）/2

起泡排序法比较次数最大为n（n-1）/2 平均执行时间nlog2n

快速排序法 最坏执行时间n*n 平均执行时间nlog2n

散列表的平均检索长度不直接依赖于n

按后根次序周游树或树林等同于按对称次序周游树对应的二叉树

3 操作系统

操作系统的特征--并发性 共享性 随机性

操作系统的功能--进程管理 存储管理 文件管理 设备管理 用户接口

操作系统结构 整体结构 层次结构 客户机/服务器结构

操作系统的硬件环境--中央处理器 存储体系 I/O控制方式 时钟

管态(R0)-特权态 系统态 核心态 目态(R3)-普通态 用户态

多到程序设计--允许多个程序同时进入内存并运行--提高整个系统的效率

系统吞吐量--单位时间内系统所处理作业的道数

进程--运行 等待 就绪

死锁--每个进程要求的资源都已被另一进程占用，于是也就没有一个进程能继续运行

进程由程序、数据和进程控制块组成，进程控制块--调度信息 现场信息

线程--轻量级进程--调度和分配的基本单位

解决进程之间的信息通信的方案--共享内存 消息机制 管道通信（传输量大，速度较慢）

死锁的必要条件--互斥条件 不剥夺条件 部分分配 循环等待

文件目录是文件控制块的有序集合

存储共享的目的--节省内存空间 实现进程通信

4 数据库基础

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

数据库管理技术是指对数据的分类，组织，编码，存储，检索和维护的技术

数据库的三件大事--1968，IBM推出IMS 1969 CODASYL'发表DBTG报告 1970 E.F.Codd奠定关系数据库基础 数据库管理软件研究的目标是提高系统的性能和提高用户的生产率

数据模型由数据结构（基础） 数据操作 数据约束组成

数据模型分类 概念层模型（ER） 逻辑层模型 物理层模型

逻辑模型有层次模型IMS 网状模型DBTG 关系模型RDBME 面向对象模型ODBMS 对象关系模型（Oracle DB2）

模式--逻辑模式，概念模式 内模式--物理模式，存储模式 外模式--子模式，用户模式

外模式/模式映像-逻辑独立性 模式/内模式-物理独立性

5 关系数据库系统

关系数据模型由关系数据结构、关系操作集合、关系完整性约束组成

关系完整性--域完整性 实体完整性 参照完整性

插入操作--首先检查实体完整性 在检查参照完整性 最后检查域完整性

删除操作--只需考虑参照完整性

基本操作--并 差 笛卡尔积 投影 选择

6 SQL结构化查询语言

SQL --数据查询(SELECT) 数据定义(CREATE DROP ALTER) 数据操作(INSERT UPDATE DELETE) 数据控制（GRANT REVOKE）

SQL特点--综合统一 高度非过程化 面向集合的操作方式 灵活的使用方式 语言简洁

SQL语言 数据定义语言DDL 数据操作语言DML 数据控制语言DCL 嵌入式和动态SQL规则 SQL调用和会话规则

模式SCHEMA 索引INDEX 域DOMAIN

创建模式 CREATE SCHEMA S_SC_C AUTHORIZATION Jin

删除模式 DROP SCHEMA S_SC_S CASCADE

建表 CREATE TABLE S_SC_C.STUDENT

完整性约束 FOREIGN KEY (S#) REFERENCES STUDENT(S#)

修改表 ALTER TABLE STUDENT ADD telephone CHAR (12)

删除表 DROP TABLE STUDENT RESTRICT

cascade级联模式--以表中数据创建的视图索引全部消失

restrict 约束模式--只有先删除表内数据 否则拒绝删除表

数据简单查询 SELECT * FROM student

between SELECT sname,age FROM student WHERE age BETWEEN 20 AND 22

like SELECT * FROM student WHERE sname LIKE '_'

_ 表示任意单个字符 % 表示和任意长字符串

集合查询 并 union 交 intersect 差 except

7 关系数据库的规范化理论与数据库设计

数据依赖--函数依赖 多值依赖

合并规则 由X→Y,X→Z,有X→YZ

伪传递规则 X→Y,WY→Z 有XW→Z

分解规则 X→Y,Z属于Y 有X→Z

1NF元组每个分量必须是不可再分的数据项

2NF每个非主属性完全函数依赖于码

3NF每个非主属性不传递依赖于马

BCNF对于每个非平凡的函数依赖X→Y 都有X包含码

4NF对于每个非平凡的多值依赖X→→Y 都有X包含码

模式分解的等价标准--无损连接性 保持函数依赖

无损连接不一定保持函数依赖 保持函数依赖不一定无损连接

具有无损连接性 一定达到BCNF

保持函数依赖 可以3NF 比一定BCNF

数据库设计--结构特性设计 行为特性设计

概念模型设计 常用自底向上的设计策略

8 数据库系统实现技术

数据库管理系统功能--数据定义 数据操作 数据存储和管理 事务管理

数据库管理系统分为--存储管理器 查询处理器 事务管理器

支持对于所要求的数据进行快速定位的附加的数据结构称作索引--顺序索引 散列索引

顺序索引支持点查询和范围查询 散列索引支持点查询 不支持范围查询

为了将大小不同的记录组织在同一个磁盘块中，常常采用分槽的页结构

提高访问效率的方法--减少磁盘和内存之间传输的块数目

查询优化--选择逻辑查询计划 选择物理查询计划

查询执行的最基本的动作是关系代数运算的执行

事务是构成单一逻辑工作单元的操纵集合

数据库系统事务特征--原子性 一致性 隔离性 持久性

保持一致性是应用程序员责任

保持原子性 持久性是故障恢复机制责任

系统故障类型--事务故障（逻辑错误 系统错误） 系统故障 磁盘故障

并发执行可能出现的问题--丢失更新 对未提交更新的依赖 不一致的分析

并发控制最常用方法--封锁-共享锁（可读不可写） 排他锁（可读可写）

保证可串行性协议--两阶段封锁协议-增长阶段（可获得锁不可释放锁）减缩阶段（可以释放锁不可获得新锁）

9主流关系数据库管理系统

理论研究--20.70初期 实用阶段--20.70后期 成熟和发展20.80开始

成熟阶段--完整性 客户机/服务器环境 扩充OS功能 网络的互联

选用时考虑因素--1 模型类型和用户个数 2 速度 3 软硬件 性价比 4 开发使用者的经验 5 安全性 SQLserver20xx--客户端组件 服务器端组件 通信组件

客户端组件--企业管理器 查询分析器 数据传输服务 联机丛书 客户端网络使用工具

服务器组件-- SQL服务器服务 SQL服务器代理 分布师事务协调服务 服务器网络实用工具

SQLserver20xx使用T-SQL语言

SQLserver20xx约束包括--主键约束 外键约束 唯一性约束 条件约束 非空值约束

用windows20xx和IIS5用作Internet平台 使用ISAPI（函数调用集）AsP（服务器端脚本环境）Xml（扩展标记语言）

Oracle-对象关系数据库管理系统（ORDBMS）基本概念-- Oracle数据库 Oracle实例

Oracle数据库定义涉及模式对象和一个或多个表空间

Oracle数据库的物理存储按数据块 盘块和段组织

Oracle数据库实例由系统全局区 用户进程 Oracle进程

Oracle数据库允许用用户的编程语言 C Java

Developer/20xx应用开发工具集

Designer/20xx提供CASE工具帮助对复杂问题建模 分析和设计

Discoverer/20xx支持数据仓库

Oracle解决数据仓库的方案是OracleOLAP产品 Oracle针对Internet的产品是Oracle Webserver

Oracl的对象关系特性-使用可变长度数组 嵌套 抽象的数据类型创建表 对象视图构建虚对象 管理大对象 BLOB二进制数据大对象 CLOB字符数据型大对象 BFILE只读二进制数据文件 NCLOB固定宽度的CLOB 安全性--保密性 完整性 可用性 可控性

权限-Oracle分为数据库系统权限 数据库对象权限 SQLserver分为服务器权限 数据库权限

三级身份认证系统登录 数据库连接数据库对象访问

10 新一代数据库系统工具

数据库管理工具包（only for DBA）--加载工具 备份工具 文件重组工具 性能监控工具

for （数据库设计者，用户，DBA）--CASE（计算机辅助软件工程 ）应用开发环境 通讯接口

信息系统的三层结构--表现性 应用逻辑性 数据逻辑性 优点--易维护 可伸缩 高可靠性 低成本 浏览器/服务器模式--以Web服务器为中心 以应用服务器为中心 以数据库服务器为中心

服务器扩展程序主要使用CGI（公共网关接口） WebAPI两种编程接口编写

基于构件方式 客户机浏览器-Web服务器（应用服务器）-数据库服务器---企业内部系统开发

基于脚本方式 客户机浏览器-Web服务器-应用服务器-数据库服务器---电子商务系统开发