计算机的三级数据库复习提纲.doc

计算机基础知识 计算机系统组成 （1）计算机系统由 和 组成 （2）计算机发展的四个阶段： （3）“ ”工作原理由冯·诺依曼提出 （4）计算机指令：计算机所能执行的操作；包括 指令、 指令和 指令 （5）计算机的硬件由哪五部分组成： 和 合称中央处理器（CPU），中央处理器和存储器合称主机，输入设备和输出设备合称外部设备（I/O设备）； 中央处理器能直接访问的存储设备只有内存储器 （6）计算机软件分为 和 （7）计算机语言包括 、 和 （常用的有哪些）； 语言处理程序：将高级语言的 编译为机器语言表示的 ，包括 和 （8）计算机系统的技术指标： （9）计算机应用领域： 计算机中的信息显示 （1）进位计数制的基本三要素： （2）原码、反码、补码 计算机网络基础 计算机网络的基本特征： 网络协议是为 制定的规则 网络协议三要素： P19 X2.5,、帧中继、ISDN、ATM 网络分类，按网络所使用的传输技术分为两类： 按覆盖范围与规模分为三类： 点—点网络中，决定从通信子网的源结点到目的结点的路由的是 广域网通信子网主要使用 ，包括： Itnet组成： IP地址由 和 两部分组成，长度为 位 可分为5类，A类（网络地址长度 位，主机地址长度 位）； B类（网络地址长度 位，主机地址长度 位）； C类（网络地址长度 位，主机地址长度 位）;C类主机地址最多256位，适合小公司和普通研究机构 Itnet服务： 是Internet上的一个WWW服务器 Itnet基本接入方式： 信息安全基础 信息安全包括： 密码技术：加密密钥、解密密钥 是最关键和最有技术难点的问题 信息认证方式： 消息认证的检验内容： 病毒是具有自我复制能力的 网络安全的研究内容： 实施操作系统安全措施的具体方案： 数据结构与算法 基本概念 是数据的基本单位，即数据集合中的个体，也称结点、记录 是有独立含义的数据最小单位，一个数据元素由一个或多个数据项组成 数据结构的内容： 数据存储方式： 顺序存储结构特点 链式存储结构特点 线性表 顺序表中插入或删除一个结点平均移动的结点个数为 空串与空格串 串的基本运算： 多维数组、系数矩阵和广义表 稀疏矩阵定义 稀疏矩阵的存储方法： 广义表特点 树形结构 树的总度数= 结点总个数和总度数关系 树或树林转换成二叉树： 二叉树转换为树： 树林F有3棵树，拥有结点数依次为n1、n2、n3，则树林F对应的二叉树的 左子树结点数目为 ，右子树结点数目为 前序法（NLR）、后序法(LRN)、对称序法(LNR)周游二叉树 周游树和树林，深度优先（先跟次序、后跟次序）、广度优先 n个结点的二叉树llink-rlink存储中，必定有 个空指针 ltag、rtag字段是指向前驱、后继的线索； 表示结点T↑没有左子树 霍夫曼树外部结点（叶结点）数等于 霍夫曼算法，左 右 查找 顺序查找：逐个比较，平均比较次数 二分法查找特殊要求 分块查找：较快查找、动态变化 散列法（哈希法）：平均检索长度与 无关 碰撞处理方法， 二叉排序树：平均检索长度 M阶B树B+树要求： 排序 直接插入排序 二分法插入排序 Shell排序法（缩小增量法）： 比较次数和移动个数均为 直接选择排序： 堆排序： 起泡排序： 快速排序： 归并排序： 常用排序方法比较 方法 平均时间 最坏情况 辅助存储 起泡排序、简单选择排序、插入排序（shell除外） 快速排序 堆排序 归并排序 操作系统 操作系统概述 操作系统的作用： 操作系统的特征： 操作系统的功能： 操作系统的分类： 操作系统的结构： 操作系统的硬件环境 硬件环境主要包括： 指令，只能操作系统使用； 指令，用户和操作系统都可以使用 ，较高特权级别； ，较低特权级别，只能执行非特权指令 中断概念 ： 中断请求： 中断响应： 中断处理： 中断类型： 中断事件发生时，中断装置将对应的 送入程序状态字和指令计数器中，如此转换到对应的中断处理程序 I/O控制方式： 进程管理 进程是 的基本单位 进程状态：；N个进程至少 个至多 个就绪 进程组成： 进程