下载文档原格式
第一章计算机基础知识1．有信息处理的特性。
2．有程序控制的特性。
3．有灵活选择的特性。
4．有正确应用的特性。
1 大型机阶段。
2 小型机阶段。
3 微型机阶段。
4 客户机/服务器阶段。
5 互联网阶段。
服务器，工作站，台式机，便携机，手持设备。
大型机，小型机，PC机，工作站，巨型机。
1．位数。
2．速度。
MIPS是表示单字长定点指令的平均执行速度。
MFLOPS是考察单字长浮点指令的平均执行速度。
3．容量。
Byte用B表示。
1KB=1024B。
平均寻道时间是指磁头沿盘片移动到需要读写的磁道所要的平均时间。
平均等待时间是需要读写的扇区旋转到磁头下需要的平均时间。
数据传输率是指磁头找到所要读写的扇区后，每秒可以读出或写入的字节数。
4 带宽。
Bps用b5 版本。
6 可靠性。
平均无故障时间MTBF和平均故障修复时间MTTR 来表示。
1 科学计算。
2 事务处理。
3 过程控制。
4 辅助工程。
5 人工智能。
6 网络应用。
1 芯片。
2 板卡。
3 设备。
4 网络。
1。
超标量技术。
通过内置多条流水线来同时执行多个处理，其实质是用空间换取时间。
2．超流水线技术。
通过细化流水，提高主频，使得机器在一个周期内完成一个甚至多个操作，其实质是用时间换取空间。
经典奔腾采用每条流水线分为四级流水：指令预取，译码，执行和写回结果。
3．分支预测。
4．双CACHE哈佛结构：指令与数据分开。
5 固化常用指令。
6 增强的64位数据总线。
7 采用PCI标准的局部总线。
8 错误检测既功能用于校验技术。
9 内建能源效率技术。
64位处理机。
奔腾系列为32 。
INTER8080-8位。
INTER8088-16位。
复杂指令系统CISC。
精简指令技术RISC。
1 实现与主机总线的通讯连接，解释并执行主机的控制命令。
2 实现数据链路层的功能。
3 实现物理层的功能。
软件就是指令序列：以代码形式储存储存器中。
数据库软件是桌面应用软件。
程序是由指令序列组成的，告诉计算机如何完成一个任务。
xx年计算机等级三级《数据库技术》考试题库1.设有关系模式R(A, B, C, D), 其函数依赖集为F={A一>D, B一>D, C一>D}。
如果将R分解为R1(A, B, C)和R2(C, D), 那么该分解是( )。
A)同时保持函数依赖和无损连接的分解B)保持函数依赖但不保持无损连接的分解C)保持无损连接但不保持函数依赖的分解D)既不保持函数依赖也不保持无损连接的分解2.下面关于模式分解的说法, 错误的选项是( )。
A)分解并不总能提高查询效率B)分解通常使得涉及属性少的查询执行效率更高C)分解通常使得简单的更新事务执行效率更高D)分解总是能降低存储空间的要求, 因为它能消除冗余数据3.设有关系表: 职工(职工号, 姓名, 领导职工号), 其中职工号是主码, 领导职工号是外码。
当前表中没有任何数据。
现在依次向该表中插入如下数据(1)(e1, Tom, e2)(2)(e3, Jerry, null)(3)(null, F00, null)(4)(e2, Fake, e2)(5)(el, Ghost, e3)(6)(e4, Wh0, el)那么最终该表中有( )行数据。
A)2B)3C)4D)54.数据库物理设计阶段是根据数据库逻辑设计的结果设计适宜的数据库物理结构。
以下关于数据库物理设计的说法, 错误的选项是( )。
A)物理设计着眼于数据库底层的物理存储与存取, 与和硬件环境及数据库管理系统密切相关B)物理设计时需要合理安排不同的存储介质, 索引文件一般存储在高速磁盘中, 日志文件可以考虑存储在磁带中C)物理设计过程中需要考虑设置合理的数据库管理系统参数和操作系统相关参数D)物理设计过程中需要考虑RAID级别、操作系统的文件管理机制、数据库管理系统支持的索引类型5.三层浏览器/效劳器架构是现在比拟流行的应用系统架构。
以下关于此架构的说法, 错误的选项是( )。
A)表示层使用Web浏览器实现, 位于客户端, 一般无需安装其他程序B)数据层位于数据库效劳器, 由DBMS完成数据存储和数据存取等数据管理功能C)此架构将人机交互、应用业务逻辑和数据管理三类功能别离, 提高了可维护性D)与二层的客户/效劳器架构相比, 此架构在交互性、运行速度方面优势明显6.设有以下关于数据库分析、设计与实现的工作:Ⅰ.用概念数据模型表示数据对象的特征及其相互间的关联关系Ⅱ.进行数据库的备份与恢复等日常维护Ⅲ.在ER图的根底上确定数据库关系模式Ⅳ.调整数据库逻辑模式, 确定文件组织与存取方式, 评估物理模式V.考虑分析DBAS运行过程中备份数据库策略, 如备份时问点和备份周期Ⅵ.事务和应用程序的编码及测试上述工作中, 属于DBAS系统设计阶段工作的是( )。
XX年全国计算机等级考试《三级数据库技术》专用教材【考纲分析＋考点精讲＋真题演练】最新资料，WORD格式，可编辑修改！目录第1章数据库应用系统开发方法................................................考纲分析..................................................................考点精讲..................................................................1.1 数据库应用系统概述...............................................考点1 数据库系统和数据库应用系统的区别 ..........................考点2 数据库应用系统设计与开发的定义 ............................1.2 数据库应用系统生命周期...........................................考点1 软件工程与软件开发方法 ....................................考点2 DBAS生命周期模型..........................................1.3 规划与分析.......................................................考点1 概述 ....................................................考点2 系统规划与定义 ............................................考点3 可行性分析 ................................................考点4 项目规划 ..................................................1.4 需求分析.........................................................考点1 系统需求 ..................................................考点2 数据需求分析 ..............................................考点3 功能需求分析 ..............................................考点4 性能需求分析 ..............................................考点5 其他需求分析 ..............................................1.5 系统设计.........................................................考点1 概念设计 ..................................................考点2 逻辑设计 ..................................................考点3 物理设计 ..................................................1.6 实现与部署.......................................................考点1 定义 ....................................................考点2 内容 ....................................................1.7 运行管理与维护...................................................考点1 内容 ....................................................考点2 重要性 .................................................... 第2章需求分析..............................................................考纲分析..................................................................考点精讲..................................................................2.1 需求分析.........................................................考点1 需求分析的概念与意义 ......................................考点2 需求获取的方法 ............................................考点3 需求分析过程 ..............................................2.2 需求分析方法.....................................................考点1 需求分析方法概述 ..........................................考点2 DFD需求建模方法...........................................考点3 其他需求建模方法 ..........................................考点4 DFD与IDEFO比较........................................... 第3章数据库结构设计........................................................考纲分析..................................................................考点精讲..................................................................3.1 数据库概念设计...................................................考点1 概念设计的任务 ............................................考点2 概念设计的依据及过程 ......................................考点3 数据建模方法 ..............................................考点4 概念设计实例 ..............................................3.2 数据库逻辑设计...................................................考点1 任务 ....................................................考点2 目标 ....................................................3.3 数据库物理设计...................................................考点1 物理设计的目的 ............................................考点2 数据库的物理结构 ..........................................考点3 索引 ....................................................考点4 数据库物理设计 ............................................考点5 其他物理设计环节 .......................................... 第4章数据库应用系统功能设计与实施..........................................考纲分析..................................................................考点精讲..................................................................4.1 软件体系结构.....................................................考点1 定义 ....................................................考点2 功能 ....................................................考点3 分类 ....................................................4.2 软件设计过程.....................................................考点1 软件设计的目的 ............................................考点2 软件设计的原则 ............................................考点3 软件设计的分类 ............................................4.3 DBAS总体设计 ....................................................考点1 DBAS总体设计主要内容......................................考点2 DBAS体系结构设计..........................................考点3 DBAS软件总体设计..........................................考点4 软硬件选型与配置设计 ......................................考点5 业务规则初步设计 ..........................................4.4 DBAS功能概要设计 ................................................考点1 概述 ....................................................考点2 实现方法 ..................................................考点3 表示层概要设计 ............................................考点4 业务逻辑层概要设计 ........................................考点5 数据访问层概要设计 ........................................4.5 DBAS功能详细设计 ................................................考点1 表示层详细设计 ............................................考点2 业务逻辑层详细设计 ........................................4.6 应用系统安全架构设计.............................................考点1 数据安全设计 ..............................................考点2 环境安全设计 ..............................................考点3 制度安全设计 ..............................................4.7 DBAS实施.........................................................考点1 DBAS实施阶段的主要工作....................................考点2 创建数据库 ................................................考点3 数据装载 ..................................................考点4 编写与调试应用程序 ........................................考点5 数据库系统试运行 .......................................... 第5章UML与数据库应用系统 ..................................................考纲分析..................................................................考点精讲..................................................................5.1 DBAS建模.........................................................考点1 方法 ....................................................考点2 UML .......................................................5.2 DBAS业务流程与需求表达 ..........................................考点1 业务流程与活动图 ..........................................考点2 系统需求与用例图 ..........................................5.3 DBAS系统内部结构的表达 ..........................................考点1 DBAS系统内部结构分类......................................考点2 系统结构与类图 ............................................考点3 系统结构与顺序图 ..........................................考点4 系统结构与通信图 ..........................................5.4 DBAS系统微观设计的表达 ..........................................考点1 微观设计的表达方法 ........................................考点2 对象图 ....................................................考点3 状态机图 ..................................................考点4 时间图 ....................................................5.5 DBAS系统宏观设计的表达 ..........................................考点1 宏观设计的对象 ............................................考点2 包图 ....................................................考点3 交互概述图 ................................................考点4 复合结构图 ................................................5.6 DBAS系统实现与部署的表达 ........................................考点1 表达方法 ..................................................考点2 组件图 ....................................................考点3 系统实现与部署图 .......................................... 第6章高级数据查询..........................................................考纲分析..................................................................考点精讲..................................................................6.1 一般数据查询功能扩展.............................................考点1 使用TOP限制结果集 ........................................考点2 使用CASE函数 .............................................考点3 将查询结果保存到新表中 ....................................6.2 查询结果的并、交、差运算.........................................考点1 并运算 ....................................................考点2 交运算 ....................................................考点3 差运算 ....................................................6.3 相关子查询.......................................................考点1 概述 ....................................................考点2 语法格式 ..................................................考点3 用途 ....................................................6.4 其他形式的子查询.................................................考点1 替代表达式的子查询 ........................................考点2 派生表 ....................................................6.5 其他一些查询功能.................................................考点1 开窗函数 ..................................................考点2 公用表表达式 .............................................. 第7章数据库及数据库对象....................................................考纲分析..................................................................考点精讲..................................................................7.1 创建及维护数据库.................................................考点1 SQL Server数据库概述......................................考点2 SQL Server数据库的组成....................................考点3 数据库文件组 ..............................................考点4 数据库文件的属性 ..........................................考点5 用T-SQL语句创建数据库 ....................................考点6 修改数据库 ................................................考点7 分离和附加数据库 ..........................................7.2 架构...........................................................考点1 定义 ....................................................考点2 架构对象的定义和种类 ......................................考点3 命名规则 ..................................................考点4 定义架构的T-SQL语句 ......................................考点5 删除架构的T-SQL语句 ......................................7.3 分区表...........................................................考点1 基本概念 ..................................................考点2 创建分区表 ................................................7.4 索引.............................................................考点1 创建索引 ..................................................考点2 删除索引 ..................................................7.5 索引视图.........................................................考点1 基本概念 ..................................................考点2 适合建立索引视图的场合 ....................................考点3 定义索引视图 .............................................. 第8章数据库后台编程技术....................................................考纲分析..................................................................考点精讲..................................................................8.1 存储过程.........................................................考点1 基本概念 ..................................................考点2 创建、执行和删除存储过程 ..................................8.2 用户定义函数.....................................................考点1 概述 ....................................................考点2 创建和调用标量函数 ........................................考点3 创建和调用内联表值函数 ....................................考点4 创建和调用多语句表值函数 ..................................考点5 删除用户自定义函数 ........................................8.3 触发器...........................................................考点1 基本概念 ..................................................考点2 创建触发器 ................................................考点3 删除触发器 ................................................8.4 游标...........................................................考点1 游标的组成 ................................................考点2 使用游标 .................................................. 第9章安全管理..............................................................考纲分析..................................................................考点精讲..................................................................9.1 安全控制.........................................................考点1 概述 ......................................................考点2 数据库安全控制的目标 ......................................考点3 数据库安全的威胁 ..........................................考点4 安全控制模型的内容 ........................................考点5 授权和认证 ................................................9.2 存取控制.........................................................考点1 自主存取控制（自主安全模式） ..............................考点2 强制存取控制 ..............................................9.3 审计跟踪.........................................................9.4 统计数据库的安全性...............................................考点1 统计数据库的定义 ..........................................考点2 安全性问题 ................................................考点3 解决方案 ..................................................考点4 目标 ....................................................9.5 SQL Server的安全控制 ............................................考点1 身份验证模式 ..............................................考点2 登录账户 ..................................................考点3 数据库用户 ................................................考点4 权限管理 ..................................................考点5 角色 ....................................................9.6 Oracle的安全管理 ................................................考点1 Oracle的安全控制机制......................................考点2 Oracle的特点..............................................考点3 用户与资源管理 ............................................考点4 权限管理 ..................................................考点5 审计功能 .................................................. 第10章数据库运行维护与优化.................................................考纲分析..................................................................考点精讲..................................................................10.1 数据库运行维护基本工作..........................................考点1 概述 ....................................................考点2 工作内容 ..................................................10.2 运行状态监控与分析..............................................考点1 定义 ....................................................考点2 监控分析机制的分类 ........................................10.3 数据库存储空间管理..............................................考点1 数据库的存储结构分类 ......................................考点2 管理内容 ..................................................考点3 数据库管理预测内容 ........................................10.4 数据库性能优化..................................................考点1 数据库运行环境与参数调整 ..................................考点2 模式调整与优化 ............................................考点3 存储优化 ..................................................考点4 查询优化 ..................................................考点5 SQL Server性能工具........................................ 第11章故障管理.............................................................考纲分析..................................................................考点精讲..................................................................11.1 故障管理概述....................................................考点1 故障类型及其解决方法 ......................................考点2 数据库恢复技术概述 ........................................11.2 数据转储（数据备份）............................................考点1 概述 ....................................................考点2 静态转储和动态转储 ........................................考点3 数据转储机制 ..............................................考点4 多种转储方法结合使用 ......................................11.3 日志文件........................................................考点1 日志文件的概念 ............................................考点2 日志文件的格式与内容 ......................................考点3 登记日志文件的原则 ........................................考点4 检查点 ....................................................11.4 硬件容错方案....................................................考点1 磁盘保护技术 ..............................................考点2 服务器容错技术 ............................................考点3 数据库镜像与数据库容灾 .................................... 第12章备份与恢复数据库.....................................................考纲分析..................................................................考点精讲..................................................................12.1 备份与恢复的概念................................................考点1 备份数据库 ................................................考点2 恢复数据库 ................................................12.2 SQL Server的备份与恢复机制 .....................................考点1 恢复模式 ..................................................考点2 备份内容及时间 ............................................考点3 SQL Server的备份机制......................................考点4 SQL Server的恢复机制......................................12.3 Oracle的备份与恢复机制 .........................................考点1 Oracle数据库逻辑备份与恢复................................考点2 0racle数据库物理备份与恢复................................ 第13章大规模数据库架构.....................................................考纲分析..................................................................考点精讲..................................................................13.1 分布式数据库....................................................考点1 分布式数据库系统 ..........................................考点2 分布式数据库目标 ..........................................考点3 分布式数据库的数据分布策略 ................................考点4 分布式数据库系统的体系结构 ................................考点5 分布式数据库的相关技术 ....................................13.2 并行数据库......................................................考点1 并行数据库系统结构 ........................................考点2 数据划分与并行算法 ........................................13.3 云计算数据库架构................................................考点1 云计算概述 ................................................考点2 Google的云数据库体系结构..................................13.4 XML数据库 ......................................................考点1 XML数据库概述.............................................考点2 SQL Server 2008与XML ..................................... 第14章数据仓库与数据挖掘...................................................考纲分析..................................................................考点精讲..................................................................14.1 决策支持系统的发展..............................................14.2 数据仓库技术概述................................................考点1 数据仓库的概念 ............................................考点2 数据仓库的特性 ............................................考点3 数据仓库的体系结构与环境 ..................................考点4 数据仓库的数据组织 ........................................考点5 元数据 ....................................................考点6 操作型数据存储 ............................................14.3 设计与建造数据仓库..............................................考点1 数据仓库设计的需求与方法 ..................................考点2 数据仓库的数据模型 ........................................考点3 数据仓库设计步骤 ..........................................14.4 数据仓库的运行与维护............................................考点1 数据仓库数据的更新维护 ....................................考点2 数据仓库监控与元数据管理 ..................................14.5 联机分析处理与多维数据模型......................................考点1 OLAP ......................................................考点2 多维分析的基本概念 ........................................考点3 多维分析的基本操作 ........................................考点4 OLAP的实现方式............................................14.6 数据挖掘技术....................................................考点1 数据挖掘步骤 ..............................................考点2 关联规则挖掘 ..............................................考点3 分类挖掘 ..................................................考点4 聚类挖掘 ..................................................考点5 时间序列分析 ..............................................第1章数据库应用系统开发方法考纲分析1．数据库应用系统的概念2．数据库应用系统生命周期。
数据结构（1）栈：限定仅在表尾进行插入或者删除操作的线性表。
即S=（a1，a2，…，an），表尾an 是栈顶，表头a1 是栈底。
n=0 是空栈。
（2）基本运算：入栈和出栈。
如果进栈顺序为a1，a2，…，an，则出栈顺序为an，an-1，…，a1。
因此栈是后进先出LIFO 或者先进后出FILO 的线性表。
（1）队列：限定只能在表的一端进行插入，表的另一端进行删除的线性表。
即Q=（a1，a2，…，an），插入端an 是队尾（rear），删除端a1 是队头（front）。
n=0 是空队列。
（2）基本运算：进队和出队。
如果进队顺序为a1，a2，…，an，则出队顺序仍为a1，a2，…，an。
因此队列是先进先出FIFO 或者后进后出LILO 的线性表。
（3）存储结构：顺序队列和链队列两种存储结构。
顺序队列可能导致假满现象，通常使用循环队列；链队列可能发生溢出。
树：其中结点的度：结点拥有的子树数；叶子（终端结点）：度为0 的结点；非终端结点（分支结点）：度不为0 的结点；树的度：树内结点的度的最大值；孩子：结点的子树的根；双亲：孩子的直接上级结点。
兄弟：同一个双亲的孩子；深度（高度）：树中结点的最大层次。
二叉树：结点数为0 或者每个结点最多有两棵互不相交的有左右子树之分的树。
（6）满二叉树：深度为k 且有2k -1 个结点的二叉树。
（7）完全二叉树：深度为k 的n 个结点的二叉树当且仅当每个结点都与深度为k 的满二叉树中编号从1 至n 的结点一一对应时（8）二叉树的性质：已知二叉树的深度h 可求出该二叉树拥有的最多结点数，已知结点数n 可求出对应树或二叉树的最大和最小高度。
1）二叉树的第i 层最多有2i-1 个结点（i≥1）。
2）深度为k 的二叉树最多有2k -1 个结点（k≥1）。
3）二叉树的叶结点数为n0，度为2 的结点数为n2，则n0= n2＋1。
4）n 个结点的完全二叉树的深度为为不大于n 2 log 的最大整数。
最新资料，WORD格式，可编辑修改！目录第一部分备考指南............................................................第1章考试概述..........................................................第2章复习技巧.......................................................... 第二部分核心讲义............................................................第1章数据库应用系统开发方法............................................第2章需求分析..........................................................第3章数据库结构设计....................................................第4章数据库应用系统功能设计与实施......................................第5章UML与数据库应用系统 ..............................................第6章高级数据查询......................................................第7章数据库及数据库对象................................................第8章数据库后台编程技术................................................第9章安全管理..........................................................第10章数据库运行维护与优化.............................................第11章故障管理.........................................................第12章备份与恢复数据库.................................................第13章大规模数据库架构.................................................第14章数据仓库与数据挖掘............................................... 第三部分历年真题及详解......................................................全国计算机等级考试《三级数据库技术》真题精选（一）........................全国计算机等级考试《三级数据库技术》真题精选（二）........................ 第四部分模拟试题及详解......................................................全国计算机等级考试《三级数据库技术》模拟试题及详解（一）..................全国计算机等级考试《三级数据库技术》模拟试题及详解（二）..................第一部分备考指南第1章考试概述一、考试简介全国计算机等级考试（National Computer Rank Examination，简称NCRE），是经原国家教育委员会（现教育部）批准，由教育部考试中心主办，面向社会，用于考查应试人员计算机应用知识与技能的全国性计算机水平考试体系。
计算机等级考试三级数据库技术复习资料1、计算机的硬件基本上由哪五大部分组成？答：运算器、控制器、存储器、输入设备、输出设备。
2、运算器都可对数据进行哪两种运算？答：算术运算和逻辑运算。
3、CAD、CAM、CAT、CAI都代表什么？答：计算机辅助设计（CAD）计算机辅助制造（CAM）计算机辅助测试（CAT）计算机辅助教学（CAI）4、数据处理是指对数据的（收集）、（存储）、（加工）、（分析）、（传送）的全过程。
5、程序性语言分为（机器语言）、（汇编语言）、（高级语言）三类。
6、能举出哪些是高级语言、哪些是低级语言？低级语言：汇编语言高级语言：baic.cobol.c.fo某bae等7、操作系统可分为（批处理操作系统）、（分时操作系统）、（实时操作系统）三种操作系统。
8、解释型程序和编译型程序有什么不同？哪种程序产生目标程序？编译程序产生目标程序9、DBMS是什么的？答：DBMS是数据库管理系统。
10、计算机系统由（硬件）系统、（软件）系统两部份组成。
11、软件系统分为（系统）软件、（应用）软件两部分。
12、操作系统的特征：（并发性）、（共享性）、（随机性）。
13、没有任何软件支持的计算机称为（裸机）。
14、操作系统的五大功能（进程管理）、（存储管理）、（文件管理）、（设备管理）、（作业管理）。
15、操作系统发展的过程：（手工操作阶段）、（早期批处理阶段）、（执行系统阶段）、（多道程序系统阶段）、（分时系统）、（实时系统）、（通用操作系统）。
16、Spooling系统是（批处理）系统。
17、批处理系统有两大特点（多道）、（成批）。
18、批处理系统追求的目标是什么？答：提高系统资源利用率和大作业的吞吐量以作业流量的自动化。
19、分时系统的特点（多路性）、（交互性）、（独立性）、（及时性）。
20、分时系统的主要目标？答：用户响应的及时性。
21、实时系统分为哪两类？并能举出这两类的例子。
飞机飞行、弹道发射、预定飞机票、查询航班都是什么系统？答：实时系统分为实时控制系统和实时信息处理系统。
浙江省数据库技术三级考试大纲1．基本要求（1）掌握数据结构的基础知识和简单应用。
（2）掌握数据库的基本概念。
（3）熟练掌握E-R模型、关系模型、关系代数运算及关系模式的规范化。
（4）掌握结构化查询语言SQL常用语句。
（5）了解数据库管理系统SQL SERVER的常用操作。
（6）能进行简单的数据库应用系统设计。
2．考试范围（1）数据结构基础1）数据结构的基本概念及有关术语：数据、数据元素、数据类型、数据的逻辑结构、数据的存储结构、算法和算法分析、算法的时间及空间复杂性。
2）基本数据结构及其操作：线性表的定义、逻辑结构、存储结构（顺序存储、链式存储），插入、删除操作。
3）数组的定义、数组逻辑结构与存储结构的关系。
4）栈的定义、逻辑结构、存储结构，进栈、出栈操作。
5）队列的定义、逻辑结构、存储结构，循环队列，进队、出队操作。
6）二叉树的定义、性质、存储结构，二叉树的遍历，二叉排序树，哈夫曼树。
7）检索方法：顺序查找、二分查找。
8）排序方法：选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序。
（2）数据库系统1）数据库的基本概念：信息、数据和数据处理、数据库系统的组成与结构。
2）数据库系统三级模式结构的概念和原理及其数据独立性。
3）数据库系统的数据模型：层次、网状、关系和面向对象模型的含义、特点和区别。
4）关系、关系模式、关系数据库模式、关系数据库的定义（关系、元组、属性、域、关键字、数据项）；主属性和非主属性。
5）关系运算：选择、投影、集合并运算、集合差运算、笛卡儿积、连接。
6）关系数据库基本概念：函数依赖的定义和相应的概念；完全函数依赖、部分函数依赖和传递函数依赖定义。
7）规范化理论：第一范式、第二范式、第三范式和BCNF范式的定义、关系模式规范化的方法和关系模式分解的方法及分解准则。
8）关系数据库规范化：1NF，2NF，3NF，BCNF。
9）结构查询语言SQL数据库操作（数据类型、数据库的创建与删除、表的创建、修改与删除、视图的创建与删除、索引的创建与删除），数据查询（单表查询、多表连接查询、分组查询、按序查询、统计查询），数据更新（表和视图数据的插入、删除和修改）。
【关键字】考试计算机等级考试——三级数据库复习资料第1章基础知识【考点一】计算机的发展自从1946年2月现代电子计算机的鼻祖ENIAC(electronic numerical integrator and computer)在美国宾夕法尼亚大学问世以后，短短50年里，计算机技术经历了巨大的变革。
学术界经常使用器件(硬件)划分计算机的发展史，如第一代电子管计算机(1947～1957)，第二代晶体管计算机(1958～1964)，第三代集成电路计算机(1964～1972)，第四代大规模集成电路计算机(1972～)，目前提出了所谓的第五代(或新一代)计算机。
从1946年到50年代后期(1946～1957)为电子管计算机时期。
计算机的元器件主要由电子管(vacuum tube)组成。
其特点是体积庞大、功耗高、运算速度较低。
如ENIAC占地170m2，重达30吨，功耗为140kW，有18000多个电子管，每秒钟能进行5000次加法计算。
这一阶段，计算机主要用于军事、国防等尖端技术领域。
除了ENIAC以外，1945年左右，冯·诺依曼等人在研制EDV AC(electronic discrete variable computer)时，提出了保存程序(stored-program)概念，奠定了以后计算机发展的基石。
IBM公司1954年12月推出的IBM650是第一代计算机的代表。
从20世纪50年代后期到60年代中期(1958～1964)为晶体管计算机时期。
自从1947年晶体管(transistor)在贝尔实验室诞生后，引发了一场影响深远的电子革命。
体积小、功耗低、价格便宜的晶体管取代了电子管，不仅提高了计算机的性能，也使计算机在科研、商业等领域内得到广泛地应用。
第二代计算机不仅采用了晶体管器件，而且保存器改用速度更快的磁芯保存器；与此同时高级编程语言和系统软件的出现，也大大提高了计算机的性能和拓宽了其应用领域。
计算机三级数据库技术复习题及答计算机三级数据库技术复习题及答三级考试分为“网络技术”，“数据库技术”，“软件测试技术"，"信息安全技术"，"嵌入式系统开发技术"等五个类别，从2013年下半年开始实施2013版考试大纲，并首次实现全部科目无纸化考试。
那么计算机三级数据库技术考试会怎么考？以下仅供参考！【复习题一】1). 结构化程序设计的三种基本逻辑结构是( )。
A.选择结构、循环结构和嵌套结构B.顺序结构、选择结构和循环结构C.选择结构、循环结构和模块结构D.顺序结构、递归结构和循环结构正确答案：B2). E-R图提供了表示实体型、属性和联系的方法，其中菱形表示( )。
A.实体型B.属性C.联系D.属性和联系正确答案：C3). 下列叙述中不属于三层B/S结构数据库应用系统特点和操作特征的是( )A.客户端使用浏览器，浏览器与Web应用服务器之间的通信使用超文本传输协议(HTTP)B.数据库服务器接受应用服务器提出的数据操作请求，对数据库进行相应的操作，并将操作结果返回给应用服务器C.这种结构使客户端和服务器能在不同的系统间通信，但对客户机配置要求较高，且应用软件维护代价也较大D.这种结构不受时空限制，使用者可以在全球任何地方，任何时间请求数据库应用系统提供的各种数据服务正确答案：C答案解析：B/S结构的数据库应用系统的特点是用户界面完全通过WWW浏览器实现，一部分事务逻辑在前端实现，主要的事务逻辑在服务器实现，所以其对客户机配置要求不高，即使对服务器要求较高，也不需要安装客户端软件。
4). 可以伴随着表的打开而自动打开的索引是( )。
A.GOTOPB.GOBOTFOMC.GO6D.SKIP正确答案：C5). 通过连编可以生成多种类型的文件，但是却不能生成( )A.PRG文件B.APP文件C.DLL文件D.EXE正确答案：A6). 在信息系统的需求分析中，广为使用的DFD建模方法属于( )A.结构化分析方法B.数据分析方法C.数据抽象方法D.业务归纳方法正确答案：A答案解析：DFD图采用自顶向下逐步细化的结构化分析方法。
数据库技术三级考试知识点总结一、数据库基础。
1. 数据库系统概述。
- 数据库（DB）、数据库管理系统（DBMS）和数据库系统（DBS）的概念。
数据库是长期存储在计算机内、有组织、可共享的数据集合；DBMS是位于用户与操作系统之间的一层数据管理软件，用于科学地组织和存储数据、高效地获取和维护数据；数据库系统是由数据库、数据库管理系统、应用程序、数据库管理员（DBA）等组成的人机系统。
- 数据库系统的特点，如数据结构化（整体结构化，数据不再针对某一应用，而是面向全组织）、数据的共享性高、冗余度低且易扩充、数据独立性高（包括物理独立性和逻辑独立性）等。
2. 数据模型。
- 概念模型：用于信息世界的建模，是现实世界到机器世界的一个中间层次。
常用的概念模型是实体 - 联系模型（E - R模型），其中包括实体（客观存在并可相互区别的事物）、属性（实体所具有的某一特性）和联系（实体之间的联系有一对一、一对多和多对多等类型）。
- 数据模型的组成要素：数据结构（描述数据库的组成对象以及对象之间的联系）、数据操作（对数据库中各种对象的实例允许执行的操作的集合，包括操作及有关的操作规则）和数据的完整性约束条件（一组完整性规则，用以限定符合数据模型的数据库状态以及状态的变化，以保证数据的正确、有效和相容）。
- 常见的逻辑数据模型：- 层次模型：用树形结构表示实体及其之间的联系，有且只有一个根结点，根结点以外的其他结点有且只有一个父结点。
- 网状模型：用网状结构表示实体及其之间的联系，允许一个以上的结点无双亲，一个结点可以有多于一个的双亲。
- 关系模型：以二维表的形式组织数据，关系模型中的数据结构是关系（二维表），关系操作包括查询（选择、投影、连接等）和更新（插入、删除、修改）操作，关系的完整性约束包括实体完整性（主关键字不能取空值）、参照完整性（外键要么取空值，要么取对应主键的值）和用户定义的完整性。
3. 数据库系统结构。
数据结构1.基本概念数据是信息的载体，是计算机程序加工的“原料”。
数据不仅包括整数、实数、字符串，还包括图像和声音等。
数据元素是数据的基本单位，数据元素也称元素、结点、顶点、记录。
一个数据元素可以由若干个数据项（也可以成为字段、域、属性）组成。
数据项是具有独立含义的最小标识单位。
数据结构指的是数据之间的相互关系，即数据的组织形式。
数据结构一般包括数据的逻辑结构、数据的存储结构和数据的运算，这三方面是一个整体，孤立地去理解一个方面，而不注意它们之间的的联系是不可取的。
数据的存储结构可以用顺序、链接、索引和散列存储方法得到。
数据类型是指一个值的集合以及在这些值上定义的一组操作的总称。
按“值”是否可分解，可将数据类型划分为两类：原子类型和结构类型。
时间代价就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的时间，也以某种单位由f(1)增至f(n)，则称该算法的时间代价为f(n)。
空间代价就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的空间，也以某种单位由g(1)增至g(n)，则称该算法的空间代价为g(n)。
2.线性表线性表是由n(n>=0)个数据元素（结点）a1,a2,…an组成的有限序列。
带头结点的单循环链表中，判断空链表的条件是head==head->next.仅设尾指针的单循环链表中，判断空链表的条件为rear==rear->next.双向链表既可以用来表示线性结构，也可以用来表示非线性结构，其每个结点包括三个域：一个数据域和两个指针域，一个指向它的前趋，另一个指向它的后继。
在双向链表中，若d 是指向表中任一结点的指针，则有llink(rlink(d))=rlink(llink(d))=d.队列在两个方向都有限制，插入只能在表的一端进行（只入不出），而删除只能在表的另一端进行（只出不进），允许插入的一端称队尾（rear），允许删除的一端称队头（front），队列的操作原则是先进先出。
全国计算机等级考试三级笔试样卷数据库技术（考试时间120分钟，满分100分）一、选择题（每小题1分，共60分）下列各题A）、B）、C）、D）四个选项中，只有一个选项是正确的。
请将正确选项涂写在答题卡相应位置上，答在试卷上不得分。
（1）下列哪一项指标在实现控制系统时不需要满足？A）可靠性 B）实时性 C）交互性 D）抗干扰性（2）下列哪一类程序不属于服务性程序？A）编译程序 B）编辑程序 C）纠错程序 D）连接程序（3）下列关于网络协议的叙述中，哪一项是不正确的？A）语法规定了用户控制信息的命令格式B）语义规定了用户控制信息的意义以及完成控制的动作与响应C）时序是对事件实现顺序的说明D）网络协议是为网络数据交换而制定的（4）下列哪一个不是TCP/IP参考模型中的应用层协议？A）电子邮件协议SMPT B）网络文件系统NFSC）简单网络管理协议SNMP D）文件传输协议FTP（5）下列关于信息认证的叙述中，哪一项是不正确的？A）验证体制中存在一个完成仲裁、颁发证书等功能的可信中心B）数字签名的签名者事后不能否认自己的签名C）消息认证要检验的内容包括消息的序号和时间性D）对密码系统的主动攻击是通过分析和识别截获的密文完成的（6）下列哪一项不是网络防病毒软件允许用户设置的扫描方式？A）实时扫描 B）警告扫描 C）预置扫描 D）人工扫描（7）下列哪些是数据结构研究的内容？Ⅰ．数据的采集Ⅱ．数据的逻辑组织Ⅲ．数据的存储实现Ⅳ．数据的传输Ⅴ．数据的检索A）Ⅱ和Ⅳ B）Ⅰ、Ⅱ和ⅢC）Ⅱ、Ⅲ和Ⅴ D）Ⅰ、Ⅲ和Ⅴ（8）下列关于数据元素的叙述中，哪一项是不正确的？A）数据元素是数据的基本单位，即数据集合中的个体B）数据元素是有独立含义的数据最小单位C）数据元素又称作结点D）数据元素又称作记录（9）下列关于数据的存储结构的叙述中，哪一项是正确的？A）数据的存储结构是数据间关系的抽象描述B）数据的存储结构是逻辑结构在计算机存储器中的实现C）数据的存储结构分为线性结构和非线性结构D）数据的存储结构对数据运算的具体实现没有影响（10）栈S最多能容纳4个元素。
2005年秋浙江省高等学校计算机等级考试试卷（三级，网络技术）说明:（1）考生应将一至四题的答案涂写在答题卡上，将第五、六题答案写在答卷纸上，否则作无效处理；（2）除了第六题目A、B选择其中之一，其他所有题目均为必答题；（3）请将你的准考证号的后四位填写在答卷的右下角指定位置内；（4）考试时间为120分钟。
一、计算机网络基础（本题21分）1、调制解调技术主要用于下列 A 种通信方式中。
（1）A．模拟信号传输数字数据B．模拟信号传输模拟数据C．数字信号传输数字数据D．数字信号传输模拟数据解释:数字数据经过编码后得到数字信号,将数字数据信号变成模拟信号的过程称为调制,接收端将模拟数据信号还原成数字数据信号的过程称为解调.选项A的过程是在模拟信号中传输数字数据,需要把数字数据转换成模拟信号,是调制过程,接收端还要将模拟信号转换回数字信号,是解调过程.选项D的过程是将模拟数据转换为数字信号,只需要解调过程.2、在下列多路复用技术中， B 具有动态分配时隙的功能。
（2）A．同步时分多路复用B．统计时分多路复用C．频分多路复用D．波分多路复用3、下面属于数据通信中差错控制技术的是D。
（3）A．分组技术B．曼彻斯特码C．异步传输D．海明码解释:接收方通过对差错编码(奇偶校验码或CRC码)的检查，可以判定一帧在传输过程中是否发生了差错。
一旦发现差错，一般可以采用反馈重发的方法来纠正。
这就要求接受方收完一帧后，向发送方反柜一个接收是否正确的信息，使发送方据此做出是否需要重新发送的决定。
发送方仅当收到接收方以正确接收的反馈信号后才能认为该帧已经正确发送完毕，否则需要重发直至正确为止。
最常用的差错控制方法有奇偶校验法、循环冗余校验法和海明码等。
这些方法用于识别数据是否发生传输错误，并且可以启动校正措施，或者舍弃传输发生错误的数据，要求重新传输有错误的数据块。
4、按覆盖的地理范围进行分类，计算机网络可以分为3类，即 D 。
数据结构基础1）数据结构的基本概念及有关术语：数据是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。
表示一个事物的一组数据称为一个数据元素，数据元素是数据的基本单位。
它可以是一个不可分割的原子项，也可以由多个数据项组成。
数据类型是指一个类型和定义在这个类型上的操作集合。
数据结构（data structure）指数据元素之间存在的关系数据的逻辑结构是指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系来表示，常被称为数据结构。
根据数据元素之间逻辑关系的不同数学特性，数据结构可分为三种：线性结构、树结构和图，其中树结构和图又称为非线性结构。
P2数据元素及其关系在计算机中的存储表示或实现称为数据的存储结构，也称为物理结构。
数据的逻辑结构从逻辑关系角度观察数据，与数据的存储无关，是独立与计算机的。
而数据的存储结构是逻辑结构在计算机内存中的实现，是依赖于计算机的。
数据存储结构的基本形式有两种：顺序存储结构和链式存储结构。
数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构四种算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。
算法分析主要包含时间代价和空间代价两个方面。
时间代价就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的时间，也以某种单位由f(1)增至f(n)，则称该算法的时间代价为f(n)。
空间代价就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的空间，也以某种单位由g(1)增至g(n)，则称该算法的空间代价为g(n)。
算法的时间及空间复杂性度量算法的时间效率算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率。
T(n)=O(f(n))度量算法的空间效率空间复杂度指算法在执行时为解决问题所需要的额外内存空间，不包括输入数据所占用的存储空间。
浙江省计算机三级数据库技术三级考试⼤纲与历年试题浙江省数据库技术三级考试⼤纲1．基本要求（1）掌握数据结构的基础知识和简单应⽤。
（2）掌握数据库的基本概念。
（3）熟练掌握E-R模型、关系模型、关系代数运算及关系模式的规范化。
（4）掌握结构化查询语⾔SQL常⽤语句。
（5）了解数据库管理系统SQL SERVER的常⽤操作。
（6）能进⾏简单的数据库应⽤系统设计。
2．考试范围（1）数据结构基础1）数据结构的基本概念及有关术语：数据、数据元素、数据类型、数据的逻辑结构、数据的存储结构、算法和算法分析、算法的时间及空间复杂性。
2）基本数据结构及其操作：线性表的定义、逻辑结构、存储结构（顺序存储、链式存储），插⼊、删除操作。
3）数组的定义、数组逻辑结构与存储结构的关系。
4）栈的定义、逻辑结构、存储结构，进栈、出栈操作。
5）队列的定义、逻辑结构、存储结构，循环队列，进队、出队操作。
6）⼆叉树的定义、性质、存储结构，⼆叉树的遍历，⼆叉排序树，哈夫曼树。
7）检索⽅法：顺序查找、⼆分查找。
8）排序⽅法：选择排序、冒泡排序、插⼊排序、归并排序、快速排序、堆排序。
（2）数据库系统1）数据库的基本概念：信息、数据和数据处理、数据库系统的组成与结构。
2）数据库系统三级模式结构的概念和原理及其数据独⽴性。
3）数据库系统的数据模型：层次、⽹状、关系和⾯向对象模型的含义、特点和区别。
4）关系、关系模式、关系数据库模式、关系数据库的定义（关系、元组、属性、域、关键字、数据项）；主属性和⾮主属性。
5）关系运算：选择、投影、集合并运算、集合差运算、笛卡⼉积、连接。
6）关系数据库基本概念：函数依赖的定义和相应的概念；完全函数依赖、部分函数依赖和传递函数依赖定义。
7）规范化理论：第⼀范式、第⼆范式、第三范式和BCNF范式的定义、关系模式规范化的⽅法和关系模式分解的⽅法及分解准则。
8）关系数据库规范化：1NF，2NF，3NF，BCNF。
9）结构查询语⾔SQL数据库操作（数据类型、数据库的创建与删除、表的创建、修改与删除、视图的创建与删除、索引的创建与删除），数据查询（单表查询、多表连接查询、分组查询、按序查询、统计查询），数据更新（表和视图数据的插⼊、删除和修改）。
选择题计算机中，负责解释和执行程序指令的部件是：A. 运算器B. 控制器C. 存储器D. 输入/输出设备在关系数据库中，用来描述“表”的结构的语言是：A. SQLB. DDLC. DMLD. TCL下列哪个不是计算机网络的主要功能？A. 数据通信B. 资源共享C. 分布式处理D. 提高单个计算机性能互联网上的每个网站都有一个唯一的地址，称为：A. URLB. IP地址C. 域名D. MAC地址下列哪个不是常见的计算机网络拓扑结构？A. 星型B. 环形C. 树型D. 直线型在Windows操作系统中，用于临时存储信息的内存区域是：A. ROMB. RAMC. 缓存D. 寄存器填空题计算机的五大基本部件包括输入设备、输出设备、_____、存储器和_____。
在计算机编程中，_____是一种用于存储和管理数据的结构。
计算机网络中的_____协议规定了数据如何在网络中传输和路由。
在关系型数据库中，数据的完整性通常通过_____、参照完整性和应用完整性来维护。
计算机的_____是指计算机执行程序的速度，通常用每秒执行的指令数来衡量。
_____是一种将多台计算机连接起来，实现资源共享和信息传递的技术。
简答题简述计算机系统的基本组成。
描述关系数据库中主键和外键的作用。
简述计算机网络中路由器的主要功能。
解释计算机中“进程”和“线程”的概念，并说明它们之间的区别。
写出三种常见的计算机网络攻击方式，并简要描述其特点。
数据结构基础1）数据结构的基本概念及有关术语：数据是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。
表示一个事物的一组数据称为一个数据元素，数据元素是数据的基本单位。
它可以是一个不可分割的原子项，也可以由多个数据项组成。
数据类型是指一个类型和定义在这个类型上的操作集合。
数据结构（data structure）指数据元素之间存在的关系数据的逻辑结构是指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系来表示，常被称为数据结构。
根据数据元素之间逻辑关系的不同数学特性，数据结构可分为三种：线性结构、树结构和图，其中树结构和图又称为非线性结构。
P2数据元素及其关系在计算机中的存储表示或实现称为数据的存储结构，也称为物理结构。
数据的逻辑结构从逻辑关系角度观察数据，与数据的存储无关，是独立与计算机的。
而数据的存储结构是逻辑结构在计算机内存中的实现，是依赖于计算机的。
数据存储结构的基本形式有两种：顺序存储结构和链式存储结构。
数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构四种算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。
算法分析主要包含时间代价和空间代价两个方面。
时间代价就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的时间，也以某种单位由f(1)增至f(n)，则称该算法的时间代价为f(n)。
空间代价就是当问题的规模以某种单位由1增至n时，解决该问题的算法实现运行时所消耗的空间，也以某种单位由g(1)增至g(n)，则称该算法的空间代价为g(n)。
算法的时间及空间复杂性度量算法的时间效率算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率。
T(n)=O(f(n))度量算法的空间效率空间复杂度指算法在执行时为解决问题所需要的额外内存空间，不包括输入数据所占用的存储空间。
S(n)=O(f(n))2）基本数据结构及其操作：线性表是由n(n>=0)个类型相同的数据元素a0,a1,…,a(n-1)组成的有限序列。
P36 线性表的逻辑结构：其中，元素ai的数据类型可以是整数、浮点数、字符或类；n是线性表的元素个数，称为线性长度。
若n=0,则为空表；若n>0,ai(0<i<n-1)有且仅有一个前驱元素a(i-1),没有后继元素a(i+1),a0没有前驱元素，a(n-1)没有后继元素线性表的存储结构（顺序存储、链式存储）线性表的顺序存储结构使用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存放次序与它们在线性表中的逻辑次序相同，即元素ai与其前驱a(i-1)及后继a(i+1)的存储位置相邻。
顺序存储的线性表也称为顺序表。
线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。
插入、删除操作单链表的插入操作：①空表插入/头插入if(head==null)head=new Node<T>(x,null); //空表插入else{Node<T>q= new Node<T>(x,null); //头插入q.next=head;head=q;}②中间插入/尾插入Node<T>q= new Node<T>(x,null);q.next=p.next;p.next=q;单链表的删除操作：③头删除head = head.next;④中间/尾删除if (p.next!=null)p.next = p.next.next;双链表的插入操作：q = new DLinkNode(x);q.prev = p.prev;q.next = p;p.prev.next = q;p.prev = q;双链表的删除操作：p.prev.next = p.next;if (p.next!=null)(p.next).prev = p.prev;3）数组是一种数据结构，数据元素具有相同的数据类型。
数组逻辑结构与存储结构的关系：数组采用的是顺序存储结构，即使用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存放次序与它们在线性表中的逻辑次序相同，即元素ai与其前驱a(i-1)及后继a(i+1)的存储位置相邻。
所以数组的存储结构表现其存储结构。
4）栈是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。
允许操作的一段称为栈顶，不允许操作的一端称为栈底。
栈中插入元素的操作称为入栈，删除元素的操作称为出栈。
没有元素的栈称为空栈。
栈的插入和删除只允许在栈顶进行，每次入栈即成为当前栈顶元素，每次出栈元素总是最后一个入栈元素，因此栈也称为后进先出表。
逻辑结构存储结构采用顺序存储结构的栈称为顺序栈，采用链式存储结构的栈称为链式栈。
进栈、出栈操作：链式栈使用单链表即可，不需要使用循环链表或双链表，并且头结点的作用不明显。
采用不带头结点的单链表实现栈。
单链表的第一个结点为站定结点，设top指向栈顶结点，入栈操作是在当前栈顶结点之前插入新结点；出栈操作是删除栈顶结点并返回栈顶元素值，再使top指向新的栈顶结点。
5）队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。
允许入队的一端称为队尾，允许出队的一端称为队头。
向队列中插入元素的过程成为入队，删除元素的过程成为出队。
没有元素的队列称为空队列。
由于插入和删除操作分别在队尾和队头进行，最先入队的元素总是最先出队，因此队列也称为先进先出表。
逻辑结构存储结构采用顺序存储结构的栈称为顺序队列，采用链式存储结构的栈称为链式队列。
循环队列：如果循环使用顺序队列的连续存储单元，则将顺序队列设计成在逻辑上首尾相接的循环结构，称为顺序循环队列。
进队、出队操作：以不带头结点的单链表实现链式队列。
设指针front和rear分别指向队头和队尾结点，入队操作将结点链在队尾结点之后，并使front指向新的队尾结点；出队操作，当队列不空时，取得队头结点值，删除该节点，并使front指向后续结点。
6）二叉树是n（n>=0）个结点组成的有限集合，n=0时称为空二叉树；n>0的二叉树由一个根结点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。
二叉树也是递归定义的。
二叉树的性质性质1：若根结点的层次为1，则二叉树第i层最多有2i-1（i≥1）个结点。
性质2：在高度为k的二叉树中，最多有2k-1个结点（k≥0）。
性质3：设一棵二叉树的叶子结点数为n0，2度结点数为n2，则n0=n2+1。
性质4：一棵具有n个结点的完全二叉树，其高度。
性质5：一棵具有n个结点的完全二叉树，对序号为i（0≤i ＜n）的结点，有：①若i=0，则i为根结点，无父母结点；若i>0，则i的父母结点序号为。
②若2i+1＜n，则i的左孩子结点序号为2i+1；否则i无左孩子。
③若2i+2＜n，则i的右孩子结点序号为2i+2；否则i无右孩子。
二叉树的存储结构1.二叉树的顺序存储结构顺序存储结构仅适用于完全二叉树跟满二叉树。
2.二叉树的链式存储结构二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点，并且每个结点仅被访问一次。
虽然二叉树是非线性结构，但遍历二叉树访问结点的次序是线性的，而且访问的规则和次序不止一种。
二叉树的遍历规则有孩子优先和兄弟优先。
孩子优先：先根次序：访问根结点，遍历左子树，遍历右子树。
中根次序：遍历左子树，访问根结点，遍历右子树。
后根次序：遍历左子树，遍历右子树，访问根结点二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树。
哈夫曼树定义为带权外路径长度最短的二叉树路径长度：从根结点到所有结点的路径长度之和(a)、(b)、（c ）、(d)的路径长度为1x2+2x2+3x2=12外路径长度：从根结点到所有叶子结点的路径长度之和(a)、(b)、（c ）、(d)的外路径长度为2+3x2+1=9从根到X 结点的带权路径长度是X 结点的权值与从根到X 结点路径长度的乘积。
所有叶子结点的带权路径长度之和称为二叉树的带权外路径长度。
二叉树的带权外路径长度7） 检索方法：（P259）顺序查找算法描述为：从线性表的一端开始，依次将每个元素的关键字与给定值进行比较，若有相等者，则查找成功；否则比较继续，直到比较完所有元素，仍未有相等者，则查找不成功，给出结果信息。
平均查找长度为（n+1）/2,查找一个元素的平均比较次数为n ，查找失败需比较n+1次，时间复杂度为O(n)。
查找成功的平均查找长度：1WPL ()n i i i w l -==⨯∑)(212)1(11)(11成功n O n n n ni nc p ASL ni i ni i =+=+⨯==⨯=∑∑==查找失败的平均查找长度：（P262）二分查找又叫折半查找，时间复杂度为O(log2n)。
折半查找算法分析8） 排序方法：直接插入排序总的关键码比较次数为n^2/4，总的记录移动个数也约为n^2/4；二分法插入排序关键码比较次数为O(nlog2n),记录移动个数为O(n^2)；shell排序法的关键码)()1()(11不成功n O n n nc p ASL ni i ni i ==⨯=⨯=∑∑==比较次数和记录移动个数均为n^1.3左右。
冒泡排序的最坏时间复杂度为O(n2),最好的时间复杂度为O(n)，算法的平均时间复杂度为O(n2)。
快速排序的最坏时间为O(n^2)，平均时间复杂度为(nlgn)。
插入排序：每趟将一个元素，按其关键字大小插入到它前面已排序的子序列中，使得插入后的子序列仍是排序的，依此重复，直到全部元素插入完毕。
直接插入排序数据序列已排序（最好情况）的时间复杂度为O（n）数据序列反序排列（最坏情况）的时间复杂度为O（n的平方）数据序列随机排列的时间复杂度为O（n的平方）折半插入排序希尔排序交换排序冒泡排序的基本思想是：比较相邻两个元素的关键字值，如果反序，则交换。
若按升序排序，每趟将被扫描的数据序列中的最大元素交换到最后位置，就像气泡从水里冒出来一样。
快速排序是一种分区交换排序算法。
快速排序的基本思想是;在数据序列中选择一个值作为比较的基准值，每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，见大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准值的最终位置。
同时，序列被划分成两个子序列，再用同样的方法分别对两个子序列进行排序，直到子序列的长度为1，则完成排序。
