下载文档原格式
（2022年）浙江省杭州市全国计算机等级考试数据库技术真题(含答案) 学校:________ 班级:________ 姓名:________ 考号:________一、1.选择题(10题)1. 在并发控制的技术中，最常用的是封锁方法。
对于共享锁(S)和排他锁(X)来说，下面列出的关系中，哪一个是相容的?A.X／XB.S／SC.S／XD.X／S2. 在如下两个数据库的表中，若雇员信息表EMP的主键是雇员号，部门信息表DEPT的主键是部门号。
若执行所列出的操作，哪一项操作不能执行?A.从雇员信息表EMP中删除行('010','王宏达','01','1200')B.从雇员信息表EMP中插入行('102','赵敏','01','1500')C.将雇员信息表EMP中雇员号='010'的工资改为1600元D.将雇员信息表EMP中雇员号='001'的部门号改为'05'3. 下列哪一项的恢复需要DBA的干预?A.事务管理B.系统故障C.磁盘故障D.数据库镜像过程4. 在FoxBase中要建立一个与现有的某个数据库有完全相同结构和数据的新数据库，应该使用如下语句中的哪个语句?A.CREATEB.APPENDC.COPYD.INSERT5. 下列哪一个不是网络协议的要素?A.语法B.语义C.时态D.时序6. 在数据库管理系统中，下面哪一项不是数据库存取的功能模块?A.事务管理程序模块B.数据更新程序模块C.交互式程序查询模块D.查询处理程序模块7. 在一个单链表中，若要删除p节点的后续节点，则执行A.p↑.next:=p↑.next↑.next;B.p:=p↑.next; p↑.next:=p↑.next↑.next;C.free(p↑.next);D.p:=p↑.next↑.next;8. 构成文件的基本单位是字符，这一类文件称为______。
第一章计算机基础知识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系统设计阶段工作的是( )。
数据结构（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 的最大整数。
第一章计算机基础知识计算机的四特点：1．有信息处理的特性。
2．有程序控制的特性。
3．有灵活选择的特性。
4．有正确应用的特性。
计算机发展经历5个重要阶段：1 大型机阶段。
2 小型机阶段。
3 微型机阶段。
4 客户机/服务器阶段。
5 互联网阶段。
计算机现实分类：服务器，工作站，台式机，便携机，手持设备。
计算机传统分类：大型机，小型机，PC机，工作站，巨型机。
计算机指标：1．位数。
2．速度。
MIPS 是表示单字长定点指令的平均执行速度。
MFLOPS是考察单字长浮点指令的平均执行速度。
3．容量。
Byte用B表示。
1KB=1024B。
平均寻道时间是指磁头沿盘片移动到需要读写的磁道所要的平均时间。
平均等待时间是需要读写的扇区旋转到磁头下需要的平均时间。
数据传输率是指磁头找到所要读写的扇区后，每秒可以读出或写入的字节数。
4 带宽。
Bps用b 5 版本。
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 内建能源效率技术。
10 支持多重处理。
安腾芯片的技术特点：64位处理机。
奔腾系列为32。
INTER8080-8位。
INTER8088-16位。
复杂指令系统CISC。
最新资料，WORD格式，可编辑修改！目录第一部分备考指南............................................................第1章考试概述..........................................................第2章复习技巧.......................................................... 第二部分核心讲义............................................................第1章数据库应用系统开发方法............................................第2章需求分析..........................................................第3章数据库结构设计....................................................第4章数据库应用系统功能设计与实施......................................第5章UML与数据库应用系统 ..............................................第6章高级数据查询......................................................第7章数据库及数据库对象................................................第8章数据库后台编程技术................................................第9章安全管理..........................................................第10章数据库运行维护与优化.............................................第11章故障管理.........................................................第12章备份与恢复数据库.................................................第13章大规模数据库架构.................................................第14章数据仓库与数据挖掘............................................... 第三部分历年真题及详解......................................................全国计算机等级考试《三级数据库技术》真题精选（一）........................全国计算机等级考试《三级数据库技术》真题精选（二）........................ 第四部分模拟试题及详解......................................................全国计算机等级考试《三级数据库技术》模拟试题及详解（一）..................全国计算机等级考试《三级数据库技术》模拟试题及详解（二）..................第一部分备考指南第1章考试概述一、考试简介全国计算机等级考试（National Computer Rank Examination，简称NCRE），是经原国家教育委员会（现教育部）批准，由教育部考试中心主办，面向社会，用于考查应试人员计算机应用知识与技能的全国性计算机水平考试体系。
最新资料，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．基本要求（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数据库操作（数据类型、数据库的创建与删除、表的创建、修改与删除、视图的创建与删除、索引的创建与删除），数据查询（单表查询、多表连接查询、分组查询、按序查询、统计查询），数据更新（表和视图数据的插入、删除和修改）。
计算机三级数据库技术复习题及答计算机三级数据库技术复习题及答三级考试分为“网络技术”，“数据库技术”，“软件测试技术"，"信息安全技术"，"嵌入式系统开发技术"等五个类别，从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）数据结构的基本概念及有关术语：数据是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。
表示一个事物的一组数据称为一个数据元素，数据元素是数据的基本单位。
它可以是一个不可分割的原子项，也可以由多个数据项组成。
数据类型是指一个类型和定义在这个类型上的操作集合。
数据结构（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)。
查找成功的平均查找长度：10WPL ()n i i i w l -==⨯∑)(212)1(11)(11成功n O n n n n i n c p ASL n i i n i i =+=+⨯==⨯=∑∑==查找失败的平均查找长度：（P262）二分查找又叫折半查找，时间复杂度为O(log2n)。
折半查找算法分析8） 排序方法：直接插入排序总的关键码比较次数为n^2/4，总的记录移动个数也约为n^2/4；二分法插入排序关键码比较次数为O(nlog2n),记录移动个数为O(n^2)；shell排序法的关键)()1()(11不成功n O n n n c p ASL n i i n i i ==⨯=⨯=∑∑==码比较次数和记录移动个数均为n^1.3左右。
冒泡排序的最坏时间复杂度为O(n2),最好的时间复杂度为O(n)，算法的平均时间复杂度为O(n2)。
快速排序的最坏时间为O(n^2)，平均时间复杂度为(nlgn)。
插入排序：每趟将一个元素，按其关键字大小插入到它前面已排序的子序列中，使得插入后的子序列仍是排序的，依此重复，直到全部元素插入完毕。
直接插入排序数据序列已排序（最好情况）的时间复杂度为O（n）数据序列反序排列（最坏情况）的时间复杂度为O（n的平方）数据序列随机排列的时间复杂度为O（n的平方）折半插入排序希尔排序交换排序冒泡排序的基本思想是：比较相邻两个元素的关键字值，如果反序，则交换。
若按升序排序，每趟将被扫描的数据序列中的最大元素交换到最后位置，就像气泡从水里冒出来一样。
快速排序是一种分区交换排序算法。
快速排序的基本思想是;在数据序列中选择一个值作为比较的基准值，每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，见大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准值的最终位置。
同时，序列被划分成两个子序列，再用同样的方法分别对两个子序列进行排序，直到子序列的长度为1，则完成排序。
