数据与数据处理经历了三个发展阶段：
一、人工管理阶段。程序与数据是一个整体，
一个程序中的数据无法被其他程序使用，因此
程序与程序之间存在大量的重复数据。特点:程序之间不能共享数据；程序复杂；数据量小
且无法长期保存；人工重复输入数据数据不保
存。
二、文件管理阶段20世纪50年代后期至60年代后期,计算机外存储器有了磁鼓和磁盘等直接存取设备；软件有了操作系统和文件系统；程序通过数据文件访问数据。特点:易于长期保存数据；程序代码有所简化；数据冗余（重复）度较大；程序对数据依赖性较强；缺乏对数据的统一管理，数据的完整性和一致性无法保证
三、数据库管理阶段数据库是在数据库管理系
统的集中控制之下，按一定的组织方式存储起
来的、相互关联的数据集合。特点：数据真正实现了结构化；数据的共享性高，冗余度低，易扩充；数据独立性高；数据由DBMS
统一管理和控制
数据库系统的组成：计算机硬件、计算机软件、数据库、数据库系统的有关人员
数据库模型：
1层次模型：用树形结构表示实体及其间的关系。特点：a有一个结点没有父结点，这个结点即是根结点；b其他结点有且仅有一个父结点。
2.网状模型：用以实体型为结点的有向图来表示实体及其间的关系。特点：a可以有一个以上的结点无父结点；b至少有一个结点有多于一个的父结点层次与网状模型优缺点:
优点:能直观、形象地描述实体及其联系，易于被人们所理解和掌握。
缺点:数据结构较复杂，存储数据需要更多的链接指针；在检索数据时，需要考虑数据的存储路径；在插入或删除数据时，涉及到调整链接指针。
3.关系模型：用二维表格表示实体间的关系，每个二维表称为一个关系，没有重复行和重复列。每一行称为元组，每一列称为属性。
关系模型的优点：A建立在严格的数学概念的基础上B 概念单一。数据结构简单、清晰，用户易懂易用C实体和各类联系都用关系来表示。D对数据的检索结果也是关系。
E关系模型的存取路径对用户透明F具有更高的数据独立性，更好的安全保密性G简化了程序员的工作和数据库开发建立的工作
关系模型的缺点：A存取路径对用户透明导致查询效率往往不如非关系数据模型
B为提高性能，必须对用户的查询请求进行优化，增加了开发数据库管理系统的难度
数据库的三级模式结构
数据库领域公认的标准结构是三级模式结构，它包括外模式、模式和内模式。
a模式:模式又称概念模式或逻辑模式，对应于概念级。它是由数据库设计者综合所有用户的数据，按照统一的观点构造的全局逻辑结构，是对数据库中全部数据的逻辑结构和特征的总体描述，是所有用户的公共数据视图(全局视图)。b外模式:外模式又称子模式，对应于用户级。它是某个或某几个用户所看到的数据库的数据视图，是与某一应用有关的数据的逻辑表示。C:内模式：内模式又称存储模式，对应于物理级，它是数据库中全体数据的内部表示或底层描述，它描述了数据在存储介质上的存储方式及物理结构，对应着实际存储在外存储介质上的数据库。
数据库的基本特征：1）有坚实的理论基础2）数据库结构简单、易理解3）对用户提供了较全面的操作支持4）得到了众多开发商的支持
数据库系统的优点：数据共享，减少数据冗余，具有较高的数据独立性，增强了数据安全性和完整性保护
第一范式：当关系模型R的所有属性都不能分解为更基本的数据单位时，称R满足第一范式1NF。例如，如果关于员工的关系中有一个工资属性，而工资又由更基本的两个数据项基本工资和岗位工资组成，则这个员工的关系模式就不满足1NF。第二范式：若关系模式R满足第一范式，且R的所有非主属性都完全依赖于R的每一个候选关键属性，称R满足第二范式2NF
第三范式：设R是满足第一范式条件的关系模式，X是R的任意属性集，若X非传递依赖于（即直接依赖）R的任意一个候选关键字，称R满足第三范式3NF。
关系模型的完整性约束
1、实体完整性。所谓实体完整性，就是一个关系模型中的所有元组都是惟一的，没有两个完全相同的元组，也就是一个二维表中没有两个完全相同行，也称为行完整性。（主键）
2、域完整性。域完整性就是对表中列数据的规范，也称列完整性，用于限制列的数据类型、格式以及取值范围。
3、参照完整性。当一个数据表中有外部关键字(即该列是另外一个表的关键字)时，外部关键字列的
所有值，都必须出现在其所对应的表中，这就是参照完整性的含义。
4、用户定义完整性
数据库设计过程
数据库设计过程一般包括：(1)需求分析(2)概念设计(3)逻辑设计(4)物理设计(5)实施与维护
SQL Server 2000的常用管理工具：SQL Sever服务管理器、SQL Sever企业管理器、SQL查询分析器
数据文件：是存放数据和数据库对象的文件。一个数据库可以有一个或多个数据文件，每个数据文件只属于一个数据库。分主数据文件.mdf（用来存储数据库的启动信息和部分或全部数据。）和次数据文件.ndf
事务日志文件：用来记录数据库更新信息的文件(例如使用INSERT、UPDATE、DELETE等语句对数据进行更改的操作)的文件。这些更新信息(日志)可用来恢复数据库。事务日志文件最小为512 KB，扩展名为LDF。每个数据库可以有一个或多个事务日志文件。
常规标识符符合标识符的格式规则，不需要使用分隔标识符进行分隔
1、第一个字符必须是字母、下划线(_)、at 符号（@）和数字标记（#）以某些符号开始的标识符名称具有的特殊用途；以@ 符号开始的标识符表示局部变量或参数；以@@ 双符号开始的标识符表示全局变量；以数字标记#符号开始的标识符表示临时表或过程；以数字标记##双符号开始的标识符表示全局临时对象
2、第一个字符后，标识符可以是字母、数字、美元符号($)、下划线(_)、at 符号(@)和数字标记(#)。/
3、标识符不能是Transact-SQL的保留字。不允许嵌入空格或其他特殊字符。否则需用分割标识符处理：被引用的标识符用双引号(“”)分隔开；括在括号中的标识符用方括号([ ])分隔
4、常规标识符和分隔标识符包含的字符数必须在1～128。
约束：约束定义了关于列中允许值的规则，SQL Server通过限制列中数据、行中数据和表之间数据来保证数据的完整性。
(1) 非空值约束(Not Null) (2) 默认约束(Default) (3) 惟一性约束(Unique ）
(4) 主键约束(Primary Key，也称主关键字约束) (5) 外键约束(Foreign Key，也称为外部关键字约束) 索引是对数据库表中一个或多个字段的值进行排序而创建的一种分散存储结构。3种类型的索引，惟一性索引：在表中建立惟一性索引时，组成该索引的字段或字段组合在表中具有惟一值，也就是说，对于表中的任何两行记录来说，索引键的值都是各不相同；主键索引：表中通常有一个字段或一些字段组的合，其值用来惟一标识表中的每一行记录，该字段或字段组合称为表的主键；聚集索引：在聚集索引中，表中各记录的物理顺序与键值的逻辑(索引)顺序相同。只有在表中建立了一个聚集索引后，数据才会按照索引键值指定的顺序存储到表中。在一个表中只能建立一个聚集索引。优点：查询速度快，因为一旦具有第一个索引值的纪录被找到，具有连续索引值的记录也一定物理的紧跟其后。缺点：对表进行修改的速度较慢，这是为了保持表中的记录的物理顺序与索引的顺序一致，而把记录插入到数据页的相应位置，必须在数据页中进行数据重排，降低了执行速度。
建立索引的目的有以下几点：
(1)加速数据检索(2)加速连接、ORDER BY和GROUP BY等操作(3)查询优化器依赖于索引起作用(4)强制实行的惟一性
视图是一个虚拟表，并不表示任何物理数据，而只是用来查看数据的窗口而已。
视图的作用：视图通常用来集中、简化和自定义每个用户对数据库的不同认识。视图可用作安全机制，方法是允许用户通过视图访问数据，而不授予用户直接访问视图基础表的权限。(1)简化操作；
(2)定制数据；(3)导出数据；(4)安全性
存储过程是SQL Server服务器上一组预编译的Transact-SQL语句，用于完成某项任务，它可以接受参数、返回状态值和参数值，并且可以嵌套调用类型包括：系统存储过程；用户定义存储过程；临时存储过程；扩展存储过程。
功能特点：(1)接收输入参数并以输出参数的形式为调用过程或批处理返回多个值。
(2)包含执行数据库操作的编程语句，包括调用其他过程。
(3)为调用过程或批处理返回一个状态值，以表示成功或失败(及失败原因)。
优点：1)模块化编程。(2)快速执行。(3)减少网络通信量。(4)提供安全机制。(5)保证操作一致性。
事务(Transaction)是SQL Server中的一个逻辑工作单元，该单元将被作为一个整体进行处理。4个属性ACID：原子性；一致性；隔离性；持久性SQL Server以3种事务模式管理事务。
(1) 自动提交事务模式：每条单独的语句都是一个事务。在此模式下，每条Transact-SQL语句在成功执行完成后，都被自动提交，如果遇到错误，则自动回滚该语句。该模式为系统默认的事务管理模式。
(2) 显式事务模式：该模式允许用户定义事务的启动和结束。事务以BEGIN TRANSACTION语句显式开始，以COMMIT或ROLLBACK语句显式结束。
(3) 隐性事务模式：在当前事务完成提交或回滚后，新事务自动启动。隐性事务不需要使用BEGIN TRANSACTION语句标识事务的开始，但需要以COMMIT或ROLLBACK语句来提交或回滚事务。锁(Lock)作为一种安全机制，用于控制多个用户的并发操作，以防止用户读取正在由其他用户更改的数据或者多个用户同时修改同一数据，从而确保事务完整性和数据库一致性。类型：共享锁；排它锁；更新锁
两种安全机制：身份验证和访问许可
两种身份验证模式：
(1)Windows身份验证模式。该模式使用Windows 操作系统的安全机制验证用户身份，只要用户能够通过Windows用户账号验证，即可连接到SQL Server而不再进行身份验证。这种模式只适用于能够提供有效身份验证的Windows操作系统。(2)混合身份验证模式。在该模式下，Windows身份验证和SQL server验证两种模式都可用。对于可信任连接用户(由Windows验证)，系统直接采用Windows的身份验证机制，否则SQL Server将通过账号的存在性和密码的匹配性自行进行验证，即采用SQL Server身份验证模式。
SQL Server中有两种角色类型：固定角色和用户定义数据库角色。
1. 固定角色。固定角色分为：
固定服务器角色：独立于各个数据库，具有固定的权限。
固定数据库角色：是指角色所具有的管理、访问数据库权限已被SQL Server定义，并且SQL Server 管理者不能对其所具有的权限进行任何修改。
2用户定义数据库角色的优点是：SQL Server数据库角色可以包含Windows用户组或用户；同一数据库的用户可以具有多个不同的用户定义角色，这种角色的组合是自由的，而不仅仅是public与其他一种角色的结合；角色可以进行嵌套，从而在数据库中实现不同级别的安全性。
备份是对SQL Server数据库或事务日志进行的复制，数据库备份记录了在进行备份操作时数据库中所有数据的状态，如果数据库因意外而损坏，这些备份文件将在数据库恢复时被用来恢复数据库。备份内容，数据库需备份的内容可分为:
Ａ系统数据库主要包括master、msdb和model数据库，它们记录了重要的系统信息，是确保系统正常运行的重要依据，必须完全备份。
Ｂ用户数据库是存储用户数据的存储空间集，通常用户数据库中的数据依其重要性可分为关键数据和非关键数据。对于关键数据则是用户的重要数据，不易甚至不能重新创建，必须进行完全备份。Ｃ事务日志记录了用户对数据的各种操作，平时系统会自动管理和维护所有的数据库事务日志。相对于数据库备份，事务日志备份所需要的时间较少，但恢复需要的时间比较长。
1.编写SQL语句建立一个宾馆数据库bg，参数如下：（*）
a.数据文件逻辑名为bg，物理文件为d:\bg.mdf；初始大小为2000KB，递增方式为10%，最大9000KB
b.日志文件逻辑名为bglog；物理文件为d:\bg.ldf；初始大小1M，递增方式为5%，大小不限制
create database bg
on
( name=bg,filename='d:\bg.mdf',size=2000kb, filegrowth=10%, maxsize=9000kb)
log on
( name=bglog, filename='d:\bg.ldf',size=1,filegrowth=5%)
1．在bg数据库中有客房信息表和订房信息表，具体表结构如下：
1) 在企业管理器中创建表rooms（客房信息表）不需要输入列的中文说明
2) 使用T-SQL语句创建表bookin（订房信息表）不需要输入列的中文说明（*）
create table bookin
(bookno varchar(50) primary key,guestid varchar(50) not null,
roomno varchar(50) check(roomno like '[0-9][0-9][0-9][0-9]'),
staydate datetime, returndate datetime, check(returndate>staydate),
discount numeric default(0.8), amount numeric)
3.编写SQL创建规则ruletype，限制其值只能是‘标准房’或者‘单人房’（*）
create rule ruletype as @value in ('标准房','单人房')
4.编写SQL将规则ruletype绑定到rooms表的roomtype列（*） exec sp_bindrule ruletype,'rooms.roomtype'
5.编写SQL创建默认对象defmemo，其值为‘未预定’create default defmemo as '未预定'
6.编写SQL将默认对象defmemo绑定到rooms表的roommemo
exec sp_bindefault defmemo,'rooms.roommemo'
7.用T-SQL语句在rooms表中插入下列客房信息(*)
insert rooms values('1003','标准房','10层朝南',100,'否',null)
8.查询所有客户的身份证号、客房编号、入住日期、结算日期 (使用三种不同的列别名方式显示列别名)。
select guestid as 身份证号,roomno 客房编号,入住日期=staydate,returndate 结算日期 from bookin
9.查询被预定的标准房的客房编号, 按客房编号的升序排序。9题以下各题不需要使用列别名
select roomno from rooms where roomtype='标准房'and putup='是' order by roomno
10.查询身份证号为“310222************”的客户入住酒店的日期、结算日期以及客房编号。(*)
select roomno,staydate,returndate from bookin where guestid='310222************'
11.创建存储过程proc_room，查询rooms表中单价大于200或者小于80的客房信息。(*)
create procedure proc_room as select * from rooms where roomprice>200 or roomprice <80
12.使用T-SQL语句创建视图roomview,显示订房编号，身份证号，入住日期，金额，客房位置，客房单价。
create view roomview as
select bookin.bookno,bookin.guestid,bookin.staydate,bookin.amount,rooms.roomposition,
rooms.roomprice from bookin,rooms where bookin.roomno=rooms.roomno
13.将pubs数据库中的titles表导入到数据库bg中,以下各题在导入的titles表上进行
14.查询titles表中不同的书籍type。(*)select distinct type from titles
15.查询title_id倒数第二个数字是7的所有记录并按照价格的逆序排序。(*)
select * from titles where title_id like '%7_' order by price desc
16.查询advance是空值的书籍的编号、类型、价格。(*)select title_id,type,price from titles where advance is null
数据库原理简答题总结第一章数据库概论 1.人工管理阶段数据管理的特点： （1）数据不保存在机器中 （2）无专用的软件对数据进行管理 （3）只有程序的概念，没有文件的概念 （4）数据面向程序 2.文件系统阶段数据管理的特点： （1）数据可长期保存在外存的磁盘上 （2）数据的逻辑结构和物理结构有了区别 （3）文件组织已呈多样化。有索引、链接和散列文件 （4）数据不再属于某个特定的程序，可重复使用。 3.文件系统显露出三个缺陷： （1）数据冗余性 （2）数据不一致性 （3）数据联系弱 4.数据库阶段的管理方式具有以下特点： （1）采用复杂的数据模型表示数据结构 （2）有较高的数据独立性 （3）数据库系统为用户提供方便的用户接口 （4）系统提供四方面的数据控制功能 （5）对数据的操作既可以以记录为单位，又可以以数据项为单位 5.数据描述三个领域之间的关系： 从事物的特性到计算机中的数据表示，经历了三个领域：现实世界、信息世界、机器世界。 （1）现实世界：存在于人们头脑之外的客观世界，称为现实世界。 （2）信息世界：是现实世界在人们头脑中的反映。 （3）机器世界：信息世界的信息在机器世界中以数据形式存储。 信息世界中数据描述的术语有：实体、实体集、属性、实体标识符 机器世界中数据描述的术语有：字段、记录、文件、关键码 它们的对应关系是： 在数据库中每个概念都有类型和值之区分，类型是概念的内涵，值是概念的外延 6.数据描述的两种形式： 数据描述有物理描述和逻辑描述两种形式。 物理数据描述指数据在存储设备上的存储方式，物理数据是实际存放在存储设备上的数据。 逻辑数据描述指程序员或用户用以操作的数据形式，是抽象的概念化数据。 数据管理软件的功能之一，就是要把逻辑数据转换成物理数据，以及把物理数据转换成逻辑数据。 7.物理存储介质层次：
1.文件的建立与打开： office图表新建新工作簿确定 打开 2.文件的保存与加密保存： office图表保存 xls 准备加密文档输入密码确定再次输入并确定 3.强制换行：alt+enter 4.删除与清除：删除整个单元格，清除格式、内容、批注 5.填充序列： 等差等比： 在单元格中输入起始值开始填充序列选择等差等比、行列输入步长值、终止值 文字序列： 在单元格输入文字序列 office按钮 excel选项常用编辑自定义序列选中刚才输入的文字序列导入确定6.复制移动： 移动覆盖左键拖拽 复制移动覆盖 ctrl+左键拖拽 移动插入 shift+左键拖拽 复制移动插入 ctrl+shift+左键拖拽 7.插入行列：选中要插入数量的行或列右键插入 8.为行、列、单元格命名： 先选中要命名的区域在左上角的名称框内输入名字 直观，快速选定 如何删除名称：公式名称管理器选中删除 9.批注：单击单元格审阅新建批注 10.科学计数法： >=12位用科计表示 123456789012=1.234567E+11 1.A3=R3C1 R为行C为列 C1 C2 C3 R1 R2 R3A3 2.数组运算Ctrl+Shift+Enter 3.将某一函数，作为另一函数的参数调用。最多可以嵌套七层 COUNT(参数1,参数2,…）功能：求一系列数据中数值型数据的个数。 COUNTA(参数1,参数2,…）功能：求“非空”单元格的个数。 COUNTBLANK(参数1,参数2,…）功能：求“空”单元格的个数。 COUNTIF功能：求符合条件的单元格数 4.四舍五入函数ROUND(number, num_digits) =ROUND(1234.567,2)=1234.57 =ROUND(1234.567,1)=1234.6 =ROUND(1234.567,0)=1235 =ROUND(1234.567,-1)=1230 =ROUND(1234.567,-2)=1200 负的往左，正的往右
一、单选题（共 10 道试题，共 50 分。）V 1. SQL Server中，保存着每个数据库对象的信息的系统表是（）。 A. sysdatabases B. Syscolumns C. Sysobjects D. Syslogs 满分：5 分 2. 在存在下列关键字的SQL语句中，不可能出现Where子句的是（）。 A. Update B. Delete C. Insert D. Alter 满分：5 分 3. 在查询语句的Where子句中，如果出现了“age Between 30 and 40”,这个表达式等同于（）。 A. age>=30 and age<=40 B. age>=30 or age<=40 C. age>30 and age<40 D. age>30 or age<40 满分：5 分 4. 如果要在一管理职工工资的表中限制工资的输入围，应使用（）约束。 A. PDRIMARY KEY B. FOREIGN KEY C. unique D. check 满分：5 分 5. 记录数据库事务操作信息的文件是（）。 A. 数据文件 B. 索引文件 C. 辅助数据文件 D. 日志文件 满分：5 分 6. 要查询XSH数据库CP表中产品名含有“冰箱”的产品情况，可用（）命令。 A. SELECT * FROM CP WHERE 产品名称LIKE ‘冰箱’ B. SELECT * FROM XSH WHERE 产品名称LIKE ‘冰箱’ C. SELECT * FROM CP WHERE 产品名称LIKE ‘%冰箱%’ D. SELECT * FROM CP WHERE 产品名称=‘冰箱’ 满分：5 分 7. 储蓄所有多个储户，储户能够在多个储蓄所存取款，储蓄所与储户之间是（）。 A. 一对一的联系 B. 一对多的联系 C. 多对一的联系 D. 多对多的联系 满分：5 分
一.根据下列员工信息表和部门信息表完成以下SQL查询 (表1 emp_xiangyoulu 员工信息表) (表2 dept_xiangyoulu) 1.查询所有员工信息 Select * from emp_xianyoulu; 2.查看所有部门信息 Select * from dept_xiangyoulu; 3:查看公司工资排名的第2-5名(分页查询rownum ) select * from( select rownum rn,ename,sal from emp_xiangyoulu order by sal desc) where rn between 2 and 5;--->错! 伪列rownum和排序order by 同时出现时,先生成伪列号,再按条件排序--->导致rn对应的序号在排序之前就定了,查出的结果和预期不符;; SELECT ROWNUM rn,e.* FROM ( SELECT * FROM emp_xiangyoulu ORDER BY sal desc) e WHERE rn BETWEEN 2 AND 5;--->错! "RN": 标识符无效,伪列号不能直接当成一般属性直接用; select rownum,e.* from( select * from emp_xiangyoulu order by sal desc)e where rownum between 2 and 5;--->错! 不报错,但查询结果为0条,原因同上; select * from( select rownum,e.* from( select * from emp_xiangyoulu order by sal desc)e)
数据库知识要点归纳 第1章数据库基础知识 1.数据库（DB）是一个按数据结构来存储和管理数据的计算机软件系统。 数据库是长期储存在计算机内的、有组织的、可共享的数据集合。 数据库管理数据两个特征：1.数据整体性 2.数据库中的数据具有数据共享性 2.数据库管理系统（DBMS）是专门用于管理数据库的计算机系统软件 3.数据库应用系统是在数据库管理系统（DBMS）支持下建立的计算机应用系统，简写为DBAS。数据库应用系统是由数据库系统、应用程序系统、用户组成的。 例如，以数据库为基础的财务管理系统、人事管理系统、图书管理系统,成绩查询系统等等。 4.数据库系统DBS是一个实际可运行的存储、维护和应用系统提供数据的软件系统，是存储介质、处理对象和管理系统的集合体。它通常由软件、数据库和数据管理员组成。 5.数据库中数据独立性数据和程序之间的依赖程度低，独立程度大的特性称为数据独立性高。1、数据的物理独立性数据的物理独立性是指应用程序对数据存储结构的依赖程度。2、数据的逻辑独立性数据的逻辑独立性是指应用程序对数据全局逻辑结构的依赖程度。 6.数据库的三级模式是模式、外模式、内模式。1.模式（Schema）一个数据库只有一个模式 2.外模式（External Schema）一个数据库有多个外模式。3.内模式（Internal Schema）一个数据库只有一个内模式。 7.数据库系统的二级映象技术 第2章数据模型与概念模型 1.实体联系的类型：一对一联系（1:1）一对多联系（1:n）多对多联系（m:n） 2.E-R图描述现实世界的概念模型，提供了表示实体集、属性和联系的方法。 长方形表示实体集椭圆形表示实体集的属性菱形表示实体集间的联系 3.数据模型的三要素数据结构、数据操作、数据约束条件 数据结构分为：层状结构、网状结构和关系结构 常见的数据模型：层次模型、网状模型和关系模型。 层次模型用树形结构来表示各类实体以及实体间的联系
试题六 一、单项选择题 （本大题共10小题，每小题2分，共20分) 在每小题列出的四个备选项中只有一个是符合题目要 求的，错选、多选或未选均无分。 1. DB 、DBMS 和DBS 三者之间的关系是（ ）。 A ．D B 包括DBMS 和DBS B ．DBS 包括DB 和DBMS C ．DBMS 包括DB 和DBS D ．不能相互包括 2. 对数据库物理存储方式的描述称为（ ） A ．外模式 B ．内模式 C ．概念模式 D ．逻辑模式 3. 在数据库三级模式间引入二级映象的主要作用是（ ） 得 分 (考 生 答 题 不 得 超 过 此 线)
A．提高数据与程序的独立性B．提高数据与程序的安全性 C．保持数据与程序的一致性D．提高数据与程序的可移植性 4. 视图是一个“虚表”，视图的构造基于（） A．基本表B．视图 C．基本表或视图D．数据字典 5．关系代数中的π运算符对应SELECT语句中的以下哪个子句？（）A．SELECT B．FROM C．WHERE D．GROUP BY 6．公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以有多名职员，从职员到部门的联系类型是（） A．多对多 B．一对一 C．多对一 D．一对多 7．如何构造出一个合适的数据逻辑结构是（）主要解决的问题。
A．关系系统查询优化B．数据字典 C．关系数据库规范化理论D．关系数据库查询 8. 将E-R模型转换成关系模型，属于数据库的（）。 A. 需求分析 B. 概念设计 C. 逻辑设计 D. 物理设计 9．事务日志的用途是（） A. 事务处理 B. 完整性约束 C. 数据恢复 D. 安全性控制 10．如果事务T已在数据R上加了X锁，则其他事务在数据R上（） A. 只可加X锁 B. 只可加S锁 C. 可加S锁或X锁 D. 不能加任何锁
.栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________
第一章数据库概论 1.人工管理阶段,文件系统阶段,数据库阶段,高级数据库阶段(对象数据库技术,分布式数据库系统,开放数据库互连技术,xml数据库技术,现代信息集成技术) 2.数据描述:概念设计中:实体,实体集,属性,实体标识符; 逻辑设计中:字段,记录,文件,关键码; 物理设计中:位,字节,字,块,桶,卷; 3.概念模型,逻辑模型(层次,网状,关系,对象),外部模型,内部模型; 4.三层模式(外模式,逻辑模式,内模式),两级映像(外模式/逻辑模式映像，逻辑模式/内模式映像) 5.数据库系统：数据库，硬件，软件，数据库管理员 第二章关系模型和关系运算理论 1.超键：能唯一标识元组的属性或属性集。 候选键：不含有多余属性的超键 主键：用户选作元祖标识的候选键。 外键：是其他模式的主键。 实体完整性规则，参照完整性规则，用户定义的完整性规则 关系模式的三层体系结构：关系模式，子模式，存储模式 2.关系代数的5个基本操作：并，差，笛卡尔积，投影，选择； 关系代数的4个组合操作：交，连接，自然连接，除法。 关系代数的7个扩充操作：改名，广义投影，赋值，外连接，外部并，半连接，聚集操作3.关系代数表达式的启发式优化算法： 尽可能早的执行选择操作； 尽可能早的执行投影操作； 避免直接做笛卡尔积 第三章关系数据库语言SQL 1.SQL的组成：数据定义语言，数据操纵语言，嵌入式，数据控制语言 2.数据定义：数据类型ok，数据库，数据表，索引的创建等ok。 3.数据查询，数据更新ok。 4，视图，嵌入式，动态SQL语句，存储过程。 第四章关系数据库的规范化设计 1.定义1：函数依赖：设有关系模式R（U），U为属性集，x、y为U的子集，函数依赖（FD）是形为X→Y的一个命题，只要r是R的当前关系，对r中任意两个元组t和s,都有t[X]=s[X]蕴涵t[Y]=s[Y],那么称FDX→Y在关系模式R(U)中成立。 定义2：如果X→Y和Y→X同时成立，则可记为X←→Y。 定义3：设F是在关系模式R上成立的函数依赖的集合，X→Y 是一个函数依赖。如果对于R 的每个满足F的关系r也满足X→Y ，那么称F逻辑蕴涵X→Y，记为F ? X→Y。 定义4：设F是函数依赖集，被F逻辑蕴涵的函数依赖全体构成的集合，称为函数依赖集F 的闭包（closure），记为F+。即F+ =｛X→Y | 记为F ? X→Y ｝
java知识点总结 应同学要求，特意写了一个知识点总结，因比较匆忙，可能归纳不是很准确，重点是面向对象的部分。 java有三个版本：JAVA SE 标准版\JAVA ME移动版\JAVA EE企业版 java常用命令：java, javac, appletview java程序文件名：.java, .class java的两类程序：applet, application; 特点，区别，这两类程序如何运行 java的主方法，主类，共有类；其特征 java的数据类型，注意与C++的不同，如字符型，引用型，初值 java与C++的不同之处，期中已总结 java标记符的命名规则 1）标识符有大小写字母、下划线、数字和$符号组成。 2）开头可以是大小写字母，下划线，和$符号（不能用数字开头） 3）标识符长度没有限制 4）标识符不能使关键字和保留字 面向对象的四大特征 抽象、封装、继承、多态 封装，类、对象，类与对象的关系，创建对象，对象实例变量 构造函数，默认构造函数，派生类的构造函数，构造函数的作用，初始化的顺序，构造方法的重载 构造函数：创建对象的同时将调用这个对象的构造函数完成对象的初始化工作。把若干个赋初值语句组合成一个方法在创建对象时一次性同时执行，这个方法就是构造函数。是与类同名的方法，创建对象的语句用new算符开辟了新建对象的内存空间之后，将调用构造函数初始化这个新建对象。 构造函数是类的特殊方法： 构造函数的方法名与类名相同。 构造函数没有返回类型。 构造函数的主要作用是完成对类对象的初始化工作。 构造函数一般不能由编程人员显式地直接调用。 在创建一个类的新对象的同时，系统会自动调用该类的构造函数为新对象初始化。 类的修饰符：public类VS 默认; abstract类; final类; 1）类的访问控制符只有一个：public，即公共的。公共类表明它可以被所有其他类访问和引用。 若一个类没有访问控制符，说明它有默认访问控制特性，规定该类智能被同一个包中的类访问引用（包访问控制）。 2）abstract类：用abstract修饰符修饰的类被称为抽象类，抽象类是没有具体对象的概念类，抽象类是它所有子类的公共属性集合，用抽象类可以充分利用这些公共属性来提高开发和维护效率。 3）final类：被final修饰符修饰限定的，说明这个类不能再有子类。所以abstract与final 不能同时修饰一个类。 域和方法的定义 1)域：定义一个类时，需要定义一组称之为“域”或“属性”的变量，保存类或对象的数据。
2019 数据库期末复习内容 1.选择题 （ 1）（数据库）是存储在计算机内结构化的数据的集合 （ 2）下述关于数据系统正确的描述是（数据库系统减少了数据冗余）。 （ 3）数据库（ DB）、与数据库系统（ DBS）和数据库管理系统（DBMS）之间的关系是（DBS 包含 DB 和 DBMS ）。（ 4）数据库管理系统的工作不包括（为定义的确据库提供操作系统）。 （ 5）用于对现实世界进行描述的工具是（数据模型）。 （ 6）在数据库的三级模式结构中，描述数据库中全局逻辑结构和特征的是（模式）。 （ 7） E-R图用来建立数据库的（概念模型）。 （ 8）下列模型中不能直接描述实体间多对多的联系的是（关系模型）。 （ 9）数据模型的三个要素是（数据结构、数据操作、完整性约束） （ 10）数据库的设计人员和用户之间沟通信息的桥梁是（实体联系图）。 （11）数据的独立性分为（逻辑独立性和物理独立性）。 （12）数据库通常是根据（数据模型）来分类的。 （ 13）关系数据库系统能实现专门的关系运算，包括（选择、投影、连接、除）。 （14）在关系模型中，下述关于关键字的说法正确的是（可以由一个或多个其值能唯一标识该关系模式中任何元组 的属性组成）。 （ 15）被称为关系的两个不变性，由关系数据库系统自动支持的是（实体完整性和参照完整性）。 （ 16）在关系中不能出现相同元组的约束是通过（主码）来实现。 （ 17）下列数据模型中，数据独立性最高的是（关系模型）. （18）规范化理论是关系数据库进行逻辑设计的理论依据。根据这个理论，关系数据库中的关系必须满足：每一属 性都是（不可分解的）。 （19）关系数据库规范化是为解决关系数据库中（插入异常、删除异常和数据冗余）问题而引入的。 （ 20）在关系数据库中，任何二元关系模式的最高范式必定是（BCNF） （ 21）若属性X 函数依赖于属性Y 时，则属性X 与属性 Y 之间的关系是（多对一）。 （ 22）设有关系模式：部门（部门代码，部门名称，部门成员，部门经理）由于其中（部门成员）属性存在， 使该关系不属于第一范式。 （ 23）若关系模式R 中的属性都是主属性，则R 最高属于（3NF）。 （ 24）若要彻底消除插入异常和删除异常，关系模式最低要属于（BCNF）。 （ 25）关系模式分解的无损连接和保持函数依赖两个特性之间的联系是（没有必然联系）。 （ 26）关系模式中数据依赖的存在，可能会导致成立蕴涵后者数据插入异常，这是指（该插入的数据未被插入）。（ 27）设要对关系模式R（学号，姓名，课程代码，课程名，课程成绩）进行分解，将其规范化到3NF，下列（ B）是正确的规范化结果。（学号，姓名）R2（课程代码，课程名）R3 （学号，课程代码，课程成绩） （ 28）有如下关系R（是 BCNF）。 （ 29）对用户访问数据库的权限加以限定是为了保护数据库的（安全性）。 （ 30）下面（可移植性）不是数据库系统必须提供的数据控制功能。 （ 31）数据库系统中，对存取权限定义为（授权）。 （ 32）在数据库的安全性控制中，为了保证用户只能存取他有权存取的数据，在授权的定义中，数据对象的（范围越小），授权子系统就越灵活。 （ 33）数据库安全性遭到破坏的情况属于（非法用户读取数据库中的数据）。 （ 34）数据库的（完整性）是指数据的正确性和相容性。 （ 35）数据完整性保护中的约束条件是指（值的约束和结构的约束）。 （ 36）实体完整性和参照完整性属于（静态关系约束）。 （ 37）数据类型、取值范围、空值约束属于（静态列级约束）。
姓名：日期： 1、事务是什么？ 2、oracle中truncate和delete命令有何区别？ 3、Oracle中char和varchar2数据类型有什么区别？有数据”test”分别存放到char(10)和varchar2(1 0)类型的字段中，其存储长度及类型有何区别？ 4、参见如下表结构 出版社: 出版社代码char(2), 出版社名称varchar2(32) 图书: 图书编号char(8),
图书名称varchar2(128), 出版社代码char(2), 作者代号char(4), 图书简介varchar2(128) 作者: 作者代号char(4), 作者名称varchar2(10), 性别char(1), 年龄number(3), 文学方向varchar2(64) 获奖名单: 获奖日期date, 获奖人员char(4) 编写SQL语句，找出“作者”库中没有出现在“获奖名单”库中所有作者信息的SQL语句（提示：使用not in、not exists以及外关联三种方法，并说明哪种方法最优。
5、Oracle数据库表存在伪列rowid，请利用rowid编写一个SQL语句，从以下记录中找到唯一记录，并将其flag列更新为Y No name sex flag 1 张三 1 N 1 张三 1 N 1 张三 1 N 6、Oracle中，需要在查询语句中把空值（NULL）输出为0，如何处理？ 7、见第四题“获奖名单”表，写出SQL语句，查询出在上一个月获奖的人员。
8、见第四题“图书”表，在表上对图书名称、出版社代码、作者代号创建了组合索引，请问在执行如下语句时会不会利用到索引。 Select * from 图书where 图书名称=?xxxx? Select * from 图书where 图书名称=?xxxx?and 出版社代码=?bb? Select * from 图书where 图书名称=?xxxx?and 作者代号=?ddd? Select * from 图书where 出版社代码=?yyy? 9、编写一个简单的Oracle存储过程，输出参数必须有一个是结果集。 专家对本试卷的分析： 第一，这张笔试卷从题目的考点上来看，属于基础知识类的； 第二，从难度上分析属于中等； 第三，从题目的设置上来看，该公司的主要用意是考察笔试者的工作经验和项目经验，尽管是基础知识，但是只要没做过开发工作，想回答上来并不容易；
数据库原理综合习题答案 1.1名词解释 (1) DB：即数据库（Database),是统一管理的相关数据的集合。DB能为各种用户共享，具有最小冗余度，数据间联系密切，而又有较高的数据独立性。 (2) DBMS：即数据库管理系统（Database Management System)，是位于用户与操作系统之间的一层数据管理软件，为用户或应用程序提供访问DB的方法，包括DB的建立、查询、更新及各种数据控制。DBMS总是基于某种数据模型，可以分为层次型、网状型、关系型、面向对象型DBMS。 (3) DBS：即数据库系统（Database System),是实现有组织地、动态地存储大量关联数据，方便多用户访问的计算机软件、硬件和数据资源组成的系统，即采用了数据库技术的计算机系统。 (4) 1：1联系：如果实体集E1中的每个实体最多只能和实体集E2中的一个实体有联系，反之亦然，那么实体集E1对E2的联系称为“一对一联系”，记为“1：1”。 (5) 1：N联系：如果实体集E1中每个实体与实体集E2中任意个（零个或多个）实体有联系，而E2中每个实体至多和E1中的一个实体有联系，那么E1对E2的联系是“一对多联系”，记为“1：N”。 (6) M：N联系：如果实体集E1中每个实体与实体集E2中任意个（零个或多个）实体有联系，反之亦然，那么E1对E2的联系是“多对多联系”，记为“M：N”。 (7) 数据模型：模型是对现实世界的抽象。在数据库技术中，表示实体类型及实体类型间联系的模型称为“数据模型”。它可分为两种类型：概念数据模型和结构数据模型。 (6) 概念数据模型：是独门于计算机系统的模型，完全不涉及信息在系统中的表示，只是用来描述某个特定组织所关心的信息结构。 (9) 结构数据模型：是直接面向数据库的逻辑结构，是现实世界的第二层抽象。这类模型涉及到计算机系统和数据库管理系统，所以称为“结构数据模型”。结构数据模型应包含：数据结构、数据操作、数据完整性约束三部分。它主要有：层次、网状、关系三种模型。 (10) 层次模型：用树型结构表示实体类型及实体间联系的数据模型。 (11) 网状模型：用有向图结构表示实体类型及实体间联系的数据模型。 (12) 关系模型：是目前最流行的数据库模型。其主要特征是用二维表格结构表达实体集，用外鍵表示实体间联系。关系模型是由若干个关系模式组成的集合。 (13) 概念模式：是数据库中全部数据的整体逻辑结构的描述。它由若干个概念记录类型组成。概念模式不仅要描述概念记录类型，还要描述记录间的联系、操作、数据的完整性、安全性等要求。 (14) 外模式：是用户与数据库系统的接口，是用户用到的那部分数据的描述。 (15) 内模式：是数据库在物理存储方面的描述，定义所有的内部记录类型、索引和文件的组成方式，以及数据控制方面的细节。 (16) 模式/内模式映象：这个映象存在于概念级和内部级之间，用于定义概念模式和内模式间的对应性，即概念记录和内部记录间的对应性。此映象一般在内模式中描述。 (17) 外模式/模式映象：这人映象存在于外部级和概念级之间，用于定义外模式和概念模式间的对应性，即外部记录和内部记录间的对应性。此映象都是在外模式中描述。 (18) 数据独立性：在数据库技术中，数据独立性是指应用程序和数据之间相互独立，不受影响。数据独立性分成物理数据独立性和逻辑数据独立性两级。 (19) 物理数据独立性：如果数据库的内模式要进行修改，即数据库的存储设备和存储方法有所变化，那么模式/内模式映象也要进行相应的修改，使概念模式尽可能保持不变。也就是对模式的修改尽量不影响概念模式。
高一期末知识点总结 第一篇：宇宙与地球 专题1 地球在宇宙中的位置 A 1、天体的概念 2、最基本的天体共同的特征 3、主要天体的特征（恒星、星云、行星、卫星、彗星、流星体） 4、天体系统的层次 5、太阳系的中心天体 6、河外星云的成员 7、宇宙年 8、太阳系八大行星按距离太阳远近的名称 9、八大行星的共同特点 10、距离地球最近的恒星 11、太阳辐射的形式 12、太阳结构（外层、内层） 13、太阳大气的主要特征 14、各层主要的太阳活动的标志 15、太阳活动的主要标志 16、太阳活动的周期 17、太阳对地球的影响
18、八大行星的分类 19、地球成为有生命存有的天体的条件 专题2 地球的伙伴——月球B 20、月球的环境特点 21、月球的地形特点 22、月球公转周期、自转周期、方向 23、地球的天然卫星 24、熟悉月相的名称、各月相的出现的农历时间 25、月相循环一个周期的时间、名称 26、日食、月食出现的原因 27、日食、月食时，月球、地球、太阳的三者位置 28、日食、月食出现时的月相情况 29、潮、汐的概念 30、潮、汐出现的原因（不必展开阐述） 31、理解潮汐随月球而不是太阳的出没而出现潮起潮落的现象的原因 32、连续两次涨潮的时间间隔 33、大潮、小潮出现的月相农历时间 34、潮汐与人类的关系 专题3 人类对太空的探索A 35、太空探索的意义、太空探索的历程 专题4 地球的运动C
36、地球自转的方向、周期、一个周期所需的时间、速度 37、地轴北端的指向 38、恒星日与太阳日的区别（时间、参照物、成因） 39、南、北两极上空所观察到的地球自转的方向 40、什么是地方时、区时、北京时间 41、时区划分的方法 42、国际日期变更线两侧日期的变化 43、地球表面作水平运动的物体发生偏向的的规律（南、北半球、赤道的区别） 44、地球公转的方向、周期、速度 45、黄赤交角的度数 46、太阳直射点在赤道、北回归线、南回归线上的日期、节气 47、正午太阳高度角在纬度和季节上变化的规律 48、晨昏线的区分 49、昼夜长短在纬度和季节上变化的规律极昼、极夜现象 50、天文角度、传统上、气候上四季的划分 第二篇岩石与地貌 专题5 板块运动B 1、用于解释地壳运动的三大学说的名称 2、六大板块的名称 3、板块构造学说的主要观点
一单词解释(2分/个) 34分 Data 数据Database 数据库RDBMS 关系数据库管理系统GRANT 授权 REVOKE 取消权限DENY 拒绝权限DECLARE 定义变量PROCEDURE存储过程 事务Transaction 触发器TRIGGER 继续continue 唯一unqiue 主键primary key 标识列identity 外键foreign key 检查check 约束constraint 二编写SQL语句(5分/题) 50分（包含笔试题问题和解答答案） 1) 创建一张学生表，包含以下信息，学号，姓名，年龄，性别，家庭住址，联系电话Create table stu (学号int , 姓名varchar(8), 年龄int, 性别varchar(4), 家庭地址varchar(50), 联系电话int ); 2) 修改学生表的结构，添加一列信息，学历 Alter table stu add 学历varchar(6); 3) 修改学生表的结构，删除一列信息，家庭住址 Alter table stu drop column 家庭地址 4) 向学生表添加如下信息： 学号姓名年龄性别联系电话学历 1A22男123456小学 2B21男119中学 3C23男110高中 4D18女114大学 Insert into stu values(1,’A’,22,’男’,123456,’小学’) Insert into stu values(2,’B’,21,’男’,119,’中学’) Insert into stu va lues(3,’C’,23,’男’,110,’高中’) Insert into stu values(4,’D’,18,’女’,114,’大学’) 5) 修改学生表的数据，将电话号码以11开头的学员的学历改为“大专” Update stu set 学历=’大专’ where 联系电话like ‘11%’ 6) 删除学生表的数据，姓名以C开头，性别为‘男’的记录删除 Delect from stu where 性别=’男’ and 姓名like ‘c%’ 7) 查询学生表的数据，将所有年龄小于22岁的，学历为“大专”的，学生的姓名和学号示出来
《数据库原理》知识点总结标准化文件发布号：（9312-EUATWW-MWUB-WUNN-INNUL-DQQTY-
目录未找到目录项。 一数据库基础知识（第1、2章） 一、有关概念 1．数据 2．数据库（DB） 3．数据库管理系统（DBMS） Access 桌面DBMS VFP SQL Server Oracle 客户机/服务器型DBMS MySQL DB2 4．数据库系统（DBS） 数据库（DB） 数据库管理系统（DBMS） 开发工具 应用系统 二、数据管理技术的发展 1．数据管理的三个阶段 概念模型 一、模型的三个世界 1．现实世界
2．信息世界：即根据需求分析画概念模型（即E-R图），E-R图与DBMS 无关。 3．机器世界：将E-R图转换为某一种数据模型，数据模型与DBMS相关。 注意：信息世界又称概念模型，机器世界又称数据模型 二、实体及属性 1．实体：客观存在并可相互区别的事物。 2．属性： 3．关键词（码、key）：能唯一标识每个实体又不含多余属性的属性组合。 一个表的码可以有多个，但主码只能有一个。 例：借书表（学号，姓名，书号，书名，作者，定价，借期，还期） 规定：学生一次可以借多本书，同一种书只能借一本，但可以多次续借。 4．实体型：即二维表的结构 例 student(no，name，sex，age，dept) 5．实体集：即整个二维表 三、实体间的联系： 1．两实体集间实体之间的联系 1：1联系 1：n联系 m：n联系 2．同一实体集内实体之间的联系 1：1联系 1：n联系 m：n联系 四、概念模型（常用E-R图表示） 属性： 联系： 说明：① E-R图作为用户与开发人员的中间语言。 ② E-R图可以等价转换为层次、网状、关系模型。 举例： 学校有若干个系，每个系有若干班级和教研室，每个教研室有若干教员，其中有的教授 和副教授每人各带若干研究生。每个班有若干学生，每个学生选修若干课程，每门课程有若干学生选修。用E-R图画出概念模型。
第一章概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据（结点集合K）以及这些数据之间的一组二元关系（关系集合R）来表示：(K, R) 结点集K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据 关系集R是定义在集合K上的一组关系，其中每个关系r（r∈R）都是K×K上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char）、指针类型（pointer）b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型 4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多） 5.四种基本存储映射方法：顺序、链接、索引、散列 6.算法的特性：通用性、有效性、确定性、有穷性 7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a．大Ο分析法：上限，表明最坏情况 b．Ω分析法：下限，表明最好情况 c．Θ分析法：当上限和下限相同时，表明平均情况 第二章线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度 b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L（设每个元素需占用L个存储单元） c. 线性表的优缺点： 优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样 缺点：空间难以扩充 d.检索：ASL=【Ο（1）】 e.插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head和tail指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n）】 e.不足：next仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head和tail指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相比其比例较大时，应该慎重选择 第三章栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项><项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ?<常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp为中缀表达式，PostfixExp为后缀表 达式 初始化操作数栈OP，运算符栈OPND； OPND.push('#'); 读取InfixExp表达式的一项 操作数：直接输出到PostfixExp中； 操作符： 当‘（’：入OPND; 当‘）’：OPND此时若空，则出错；OPND若 非空，栈中元素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若为‘（’，弹出即 可 当‘四则运算符’：循环（当栈非空且栈顶不是 ‘（’&& 当前运算符优先级>栈顶运算符优先 级），反复弹出栈顶运算符并输入到 PostfixExp中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是 递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作 在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear；队满： (rear+1)%n==front 第五章二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶 结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶 结点的层数 d.如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作满二 叉树 e.如果一颗二叉树最多只有最下面的两层结点 度数可以小于2；最下面一层的结点都集中在 该层最左边的位置上，则称此二叉树为完全二 叉树 f.当二叉树里出现空的子树时，就增加新的、特 殊的结点——空树叶组成扩充二叉树，扩充二 叉树是满二叉树 外部路径长度E：从扩充的二叉树的根到每个 外部结点（新增的空树叶）的路径长度之和 内部路径长度I：扩充的二叉树中从根到每个内 部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i层（根为第0层，i≥0）最多有 2^i个结点 b. 深度为k的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的 结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其 分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子 树(指针)数目等于其结点数加1 f. 有n个结点（n>0）的完全二叉树的高度为 ?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n个结点的完全二叉树，结点按层 次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点 编号是(i-1)/2 2) 当2i+1
相关主题
文本预览