复试准备背诵

数据库

代码说明

表格

代码	考察内容
sql	SQL 语句
alg	关系代数
er	ER 图
lock	死锁、串行化
closure	求闭包
mindep	最小依赖
key	求码
pattern	范式
optim	关系代数优化

---

1 关系模式【closure, key, pattern】

题目R (商店编号，商品编号，数量，部门编号，负责人)规定：(1) 每个商店的每种商品只在一个部门销售；(2) 每个商店的每个部门只有一个负责人；(3) 每个商店的每种商品只有一个库存数量。回答：(1) 基本函数依赖；(2) 候选码；(3) 最高范式及原因；(4) 分解为 3NF。

答案(1) 函数依赖：(商店编号，商品编号)→部门编号(商店编号，商品编号)→数量(商店编号，部门编号)→负责人(2) 候选码：(商店编号，商品编号)(3) 最高2NF，存在非主属性 “负责人” 对码的传递依赖。(4) 3NF 分解：R1 (商店编号，商品编号，数量，部门编号)R2 (商店编号，部门编号，负责人)

---

2 关系代数【alg】

题目学生 (学号，姓名，性别，专业，奖学金)课程 (课程号，名称，学分)学习 (学号，课程号，分数)

1. 检索 “国际贸易” 专业获奖学金学生信息：学号、姓名、课程名、分数
2. 检索成绩满分课程的课程号、名称、学分
3. 检索无奖学金且至少一门 > 95 分学生：学号、姓名、专业
4. 检索无 80 分以下成绩学生：学号、姓名、专业

答案

---

3 SQL 语句【sql】

题目学生 (学号，姓名，年龄，性别)社团 (编号，名称，负责人，办公地点)参加 (学号，编号，参加日期)

1. 定义社团表，主码 + 外键
2. 建立视图：社团负责人 (社团编号，名称，负责人学号，负责人姓名，负责人性别)
3. 查询参加 “科协” 学生：学号、姓名、性别
4. 统计每个社团参加人数
5. 赋插入 / 删除权限给李平并允许转授

答案

---

4 E-R 图【er】

题目实体：教员、学生、课程、教室联系：1 教员讲多课、1 课仅 1 教员；学生与课程多对多（带成绩）；1 课仅 1 教室、1 教室多课。画 ER 图。

答案实体：教员 (职工号，姓名，年龄，职称)、学生 (学号，姓名，年龄，性别)、课程 (课程号，课程名，课时数)、教室 (教室编号，地址，容量)联系：讲授 (教员→课程，1:n)选修 (学生↔课程，m:n，带成绩)上课 (课程→教室，n:1)

---

5 函数依赖集【mindep】

题目F={C→A, CG→D, CG→B, CE→A, ACD→B}，求最小依赖集。

答案最小依赖集：{C→A, CG→D, CD→B}

---

6 规范化【pattern】

题目表：部件号、部件名、现有数量、项目代号、项目内容、项目负责人、已提供数量规范化到 3NF，写函数依赖、主码、分解结果。

答案

---

7 关系代数【alg】

题目同第 2 题表结构

1. 英语专业学生课程信息：学号、姓名、课程名、分数
2. 数据库原理 > 90 分学生：学号、姓名、专业、分数
3. 不学 C135 学生：学号、姓名、专业
4. 无不及格学生：学号、姓名、专业

答案

1. Π 学号，姓名，课程名，分数 (σ 专业 =' 英语 '(学生∞学习∞课程))
2. Π 学号，姓名，专业，分数 (σ 分数> 90∧名称 =' 数据库原理 '(学生∞学习∞课程))
3. Π 学号，姓名，专业 (学生)−Π 学号，姓名，专业 (σ 课程号 ='C135'(学生∞学习))
4. Π 学号，姓名，专业 (学生)−Π 学号，姓名，专业 (σ 分数 < 60 (学生∞学习))

---

8 SQL 语句【sql】

题目职工 (职工号，姓名，性别，职务，家庭地址，部门编号)部门 (部门编号，部门名称，地址，电话)保健 (保健卡编号，职工号，检查日期，健康状况)

1. 女科长
2. 办公室科长姓名、地址
3. 财务科健康良好职工姓名、地址
4. 改 3016 健康状况为一般
5. 删除 3016 职工
6. 建健康差视图
7. 保健表加备注列 (20 字符)

答案

1. SELECT * FROM 职工 WHERE 性别 =' 女 ' AND 职务 =' 科长 ';
2. SELECT 姓名，家庭地址 FROM 职工，部门WHERE 职工。部门编号 = 部门。部门编号 AND 部门名称 =' 办公室 ' AND 职务 =' 科长 ';
3. SELECT 姓名，家庭地址 FROM 职工，部门，保健WHERE 职工。部门编号 = 部门。部门编号 AND 职工。职工号 = 保健。职工号AND 部门名称 =' 财务科 ' AND 健康状况 =' 良好 ';
4. UPDATE 保健 SET 健康状况 =' 一般 ' WHERE 职工号 ='3016';
5. DELETE FROM 职工 WHERE 职工号 ='3016';
6. CREATE VIEW VW ASSELECT * FROM 职工 WHERE 职工号 IN (SELECT 职工号 FROM 保健 WHERE 健康状况 =' 差 ');
7. ALTER TABLE 保健 ADD 备注 CHAR (20);

---

9 闭包【closure】

题目

1. F={AB→CE,A→C,GP→B,EP→A,CDE→P,HB→P,D→HG,ABC→PG}，求 D+
2. F={AC→PE,PG→A,B→CE,A→P,GA→B,GC→A,PAB→G,AE→GB,ABCP→H}，求 (BG)+

答案

1. D⁺ =DHG
2. (BG)⁺ =BGCEAPH

---

10 范式【pattern】

题目R (A,B,C,D,E)(1) F={AB→C,C→E,AB→D}(2) F={AB→C,CE→D,ABC→DE}判断最高范式。

答案(1)2NF，存在非主属性 E 对码 AB 传递依赖(2)3NF，无非主属性对码部分 / 传递依赖

---

11 关系代数 + SQL【alg,sql】

题目student(sno,sname,sex,birth,height,class,address)course(cno,cname,credit)elective(sno,cno,grade)

1. 至少选 C02、C06 的学号
2. 未选 C06 的姓名、班级
3. 学全部课程的姓名
4. 包含 S08 所学全部课程的学号

答案关系代数

1. πsno(σcno='C02'(elective))∩πsno(σcno='C06'(elective))
2. πsname,class(student)−πsname,class(σcno='C06'(student∞elective))
3. πsname(student∞(πsno,cno(elective)÷πcno(course)))
4. πsno,cno(elective)÷πcno(σsno='S08'(elective))

SQL

1. SELECT DISTINCT a.sno FROM elective a,elective bWHERE a.sno=b.sno AND a.cno='C02' AND b.cno='C06';
2. SELECT sname,class FROM studentWHERE NOT EXISTS(SELECT * FROM electiveWHERE sno=student.sno AND cno='C06');
3. SELECT sname FROM studentWHERE NOT EXISTS(SELECT * FROM courseWHERE NOT EXISTS(SELECT * FROM electiveWHERE sno=student.sno AND cno=course.cno));
4. SELECT DISTINCT sno FROM elective XWHERE NOT EXISTS(SELECT * FROM elective YWHERE Y.sno='S08' AND NOT EXISTS(SELECT * FROM elective ZWHERE Z.sno=X.sno AND Z.cno=Y.cno));

---

12 E-R 图【er】

题目实体：工厂、产品、工人联系：工厂 - 产品多对多（月产量）；工厂 - 工人一对多（雇用期、月薪）画 ER 并转关系模式，标主外码。

答案关系模式：工厂 (工厂名称，厂址，联系电话) PK：工厂名称产品 (产品号，产品名，规格，单价) PK：产品号工人 (工人编号，姓名，性别，职称，工厂名称，雇用期，月薪) PK：工人编号 FK：工厂名称生产 (工厂名称，产品号，月产量) PK：(工厂名称，产品号) FK：工厂名称，产品号

---

13 闭包【closure】

题目R (A,B,C,D,E)，F={AB→C,B→D,C→E,EC→B,AC→B,D→BE}判断 AC→BE 能否导出，用推理规则 + 闭包证明。

答案

1. 推理：AC→B，B→D ⇒ AC→D；D→BE ⇒ AC→BE
2. (AC)⁺=ABCDE，BE⊆(AC)⁺，可导出。

---

14 范式【pattern】

题目R (A,B,C,D,E)(1) F={AB→C,AB→E,CDE→AB}(2) F={CD→A,CD→B,AB→E}判断最高范式。

答案(1)BCNF，候选码 CDE，无部分 / 传递依赖(2)2NF，存在非主属性 E 对码 CD 传递依赖

---

15 关系代数 + SQL【alg,sql】

题目S(S#,SN,SD,SA),C(C#,CN,PC#),SC(S#,C#,G)

1. 95001 学生 > 60 分课程号；数据库概论 80/90 分学生学号姓名；选全部课程学生信息
2. 无人选课程；选课 > 3 门学生学号、门数、均分；删除数据结构课程及选课

答案关系代数

1. πC#(σS#='95001'∧G>=60(SC))
2. πS#,SN (σCN=' 数据库概论 '(C)∞σG=80∨G=90 (SC)∞S)
3. πS#,SN,SD(S∞(πS#,C#(SC)÷πC#(C)))

SQL

1. SELECT C# FROM SC WHERE S#='95001' AND G>=60;
2. SELECT S.S#,SN FROM S,SC,CWHERE C.C#=SC.C# AND SC.S#=S.S# AND CN=' 数据库概论 ' AND (G=80 OR G=90);
3. SELECT S#,SN,SD FROM SWHERE NOT EXISTS(SELECT * FROM C XWHERE NOT EXISTS(SELECT * FROM SC Y WHERE Y.C#=X.C# AND Y.S#=S.S#));
4. SELECT C#,CN FROM C WHERE C# NOT IN(SELECT DISTINCT C# FROM SC);
5. SELECT S#,COUNT(C#),AVG(G) FROM SC GROUP BY S# HAVING COUNT(C#)>3;
6. DELETE FROM SC WHERE C# IN (SELECT C# FROM C WHERE CN=' 数据结构 ');DELETE FROM C WHERE CN=' 数据结构 ';

---

16 E-R 图【er】

题目交通违章通知书：司机、机动车、警察、处罚通知、处罚方式（多值）设计 ER 并转关系，标主外码。

答案关系模式：司机 (驾照号，姓名，地址，邮编，电话) PK：驾照号机动车 (牌照号，型号，制造厂，生产日期) PK：牌照号警察 (警察编号，姓名) PK：警察编号通知书 (编号，日期，时间，地点，驾照号，牌照号，警察编号) PK：编号 FK：驾照号，牌照号，警察编号处罚 (编号，处罚方式) PK：(编号，处罚方式) FK：编号

---

17 事务【lock】

题目x=1000，甲取 300，乙取 200，并发调度问题，填空封锁步骤，说明可串行化标准。

答案(1) (a) 800；(b) Xlock x；(c) W (x)=700；(d) R (x)=700；(e) x←x-200；(f) Unlock x(2) 并发正确标准：结果与某一串行执行结果相同，即可串行化。

---

18 闭包【closure】

题目U={A,B,C,D,E}，F={B→A,D→A,A→E,AC→B}，求 (CD)⁺。

答案(CD)⁺ =CDAEB

---

19 SQL【sql】

题目职工 (职工号，姓名，年龄，月工资，部门号，电话，办公室)部门 (部门号，部门名，负责人代码，任职时间)建表、视图、插入判断、视图更新、查询功能。

答案

1. (a) PRIMARY KEY；(b) FOREIGN KEY (负责人代码) REFERENCES 职工 (职工号)(c) FOREIGN KEY (部门号) REFERENCES 部门 (部门号)(d) 月工资 >=500 AND 月工资 <=5000(e) COUNT (*),SUM (月工资),AVG (月工资)(f) GROUP BY 部门号
2. 1) 不可插入 (主键重复)；2) 可插入；3) 不可插入 (部门不存在)
3. 视图含聚集函数，不可更新；可查询
4. 查询每个部门工资最高的职工号

---

20 求码 + 范式【key,pattern】

题目项目信息、科研专家、项目研发人员三个关系，求候选码、判断范式、分解 3NF。

答案

1. 项目信息：课题编号；科研专家：人员编号 / 身份证号；研发人员：(课题编号，所在单位，职工号)
2. 科研专家：2NF，存在所在单位→单位地址传递依赖
3. 研发人员分解：研发人员 1 (所在单位，职工号，姓名，年龄，学历，职称)研发人员 2 (课题编号，所在单位，职工号，分工，排名，参加月数)

---

21 关系代数【alg】

题目同 15 题，写关系代数。

答案

1. πC#(σS#='95001'∧G>=60(SC))
2. πS#,SN (σCN=' 数据库概论 '(C)∞σG=80∨G=90 (SC)∞S)
3. πS#,SN,SD(S∞(πS#,C#(SC)÷πC#(C)))

---

22 事务【lock】

题目A=B=2，T1:A=B+1；T2:B=A+1，并发结果、正确性、封锁填空。

答案

1. 正确结果：A=3,B=4 或 A=4,B=3
2. 标准：可串行化；本例 A=3,B=3，不正确
3. (a) SLOCK B；(b) XLOCK A；(c) 写回 A=3；(d) X=A=3；(e) UNLOCK A

---

23 闭包【closure】

题目求 AE⁺，F 含 AE→C,E→D,C→B。

答案(AE)⁺ =ABCDE

---

24 SQL + 关系代数【sql,alg】

题目客户、产品、订单、订单明细，建表、查询、视图、包含查询。

答案

1. (a) PRIMARY KEY；(b) CHECK (性别 IN (' 男 ',' 女 '))；(c) FOREIGN KEY (客户号) REFERENCES 客户 (客户号)
2. 查询购买 02 号产品 > 10 件的客户号；π 客户号 (订单∞σ 产品号 ='02'∧数量> 10 (订单明细))
3. SUM (金额) 购买总额；GROUP BY 客户。客户号；ORDER BY 购买总额 DESC
4. 视图 + 包含查询用 NOT EXISTS 三层嵌套

---

25 范式【key,pattern】

题目旅游线路、订单、员工信息，判断 BCNF/3NF/4NF，分解。

答案

1. 线路信息：BCNF，无部分 / 传递依赖
2. 订单信息分解：订单 1 (订单号，线路编号，联系人身份证号，人数，订单价格，出发时间)订单 2 (联系人身份证号，联系人名称，联系方式)订单 3 (订单号，负责导游工号，负责城市)
3. 员工信息分解：员工 1 (员工工号，姓名，出生日期，员工类别)员工 2 (员工工号，手机号)员工 3 (员工工号，计薪月，被投诉次数，带团人数，月薪)

---

26 E-R 图【er】

题目车队、车辆、司机：车队聘司机 (1:n, 聘期)；车队拥车辆 (1:n)；司机用车辆 (m:n, 日期、公里数)ER 转关系，标主外码。

答案车队 (车队号，车队名) PK：车队号车辆 (牌照号，厂家，出厂日期，车队号) PK：牌照号 FK：车队号司机 (司机编号，姓名，电话，车队号，聘期) PK：司机编号 FK：车队号使用 (司机编号，牌照号，使用日期，公里数) PK：(司机编号，牌照号) FK：司机编号，牌照号

---

27 SQL + 关系代数 + 优化【sql,optim】

题目P (PNO,PNAME,COLOR,PRICE),S (SNO,SNAME,CITY),SP (PNO,SNO,QTY)查卖 TV 的商店名，转关系代数，画优化树。

答案SQL：SELECT SNAME FROM P,S,SPWHERE P.PNO=SP.PNO AND S.SNO=SP.SNO AND PNAME='TV';关系代数：πSNAME (S∞SP∞σPNAME='TV'(P))优化：先选择、再连接、后投影。

---

28 范式【pattern】

题目R (X,Y,Z)(1) F={XY→Z}；(2) F={Y→Z,XZ→Y}；(3) F={Y→Z,Y→X,X→YZ}判断范式。

答案(1)BCNF；(2)3NF；(3)BCNF

---

29 E-R 图【er】

题目制药厂：客户、类别、销售单、业务员、产品、销售 (多对多)ER 转关系，标主外码。

答案类别 (客户类别名，最低供应扣率，资金回笼期限) PK：客户类别名客户 (客户编号，客户名，地址，电话，税金，账号，应收款，背景，客户类别名) PK：客户编号 FK：客户类别名业务员 (业务员编号，姓名，销售额，销售指标) PK：业务员编号销售单 (销售单编号，日期，到款日期，客户编号，业务员编号) PK：销售单编号 FK：客户编号，业务员编号产品 (产品编号，产品名，类别名，批发价，零售价，库存量) PK：产品编号销售 (销售单编号，产品编号，标记，数量，金额) PK：(销售单编号，产品编号) FK：销售单编号，产品编号

---

30 关系代数 + SQL【alg,sql】

题目同 27 题，查卖全部商品、不卖 P2、至少卖 P1/P2 的商店；建伦敦卖红色商品视图。

答案

1. 全部商品：用 NOT EXISTS 嵌套
2. 不卖 P2：WHERE NOT EXISTS (SELECT * FROM SP WHERE PNO='P2' AND SNO=S.SNO)
3. 至少 P1/P2：自连接 SP
4. 视图：CREATE VIEW RLS AS SELECT SNO,SNAME FROM S,SP,PWHERE S.SNO=SP.SNO AND SP.PNO=P.PNO AND CITY='London' AND COLOR='Red';

---

31 E-R 图【er】

题目车间、工人、产品、零件、仓库，画 ER 转关系。

答案车间 (车间号，主任姓名，地址，电话，厂名)仓库 (仓库号，主任姓名，电话，厂名)零件 (零件号，重量，价格，仓库号)产品 (产品号，价格，仓库号)工人 (职工号，姓名，年龄，性别，工种，车间号)制造 (车间号，零件号，数量 1)组成 (产品号，零件号，数量 2)

---

32 SQL + 关系代数【alg,sql】

题目S (SNO,SN,SEX,AGE),C (CNO,CN,PCNO),SC (SNO,CNO,G)查全选课、DB>90 分姓名、建 SDB 视图、英语课成绩提 10%。

答案

1. 全选课：NOT EXISTS 嵌套
2. SELECT SN FROM S,SC,CWHERE S.SNO=SC.SNO AND SC.CNO=C.CNO AND CN='DB' AND G>90;
3. CREATE VIEW SDB AS SELECT SNO,SN FROM S,SC,CWHERE S.SNO=SC.SNO AND SC.CNO=C.CNO AND CN='DB';
4. UPDATE SC SET G=G*1.1 WHERE CNO IN (SELECT CNO FROM C WHERE CN=' 英语 ');

---

33 E-R + 范式【er,pattern】

题目ER 转 3NF。

答案A(a1,a2),B(b1,b2),C(c1,c2,a1),R1(a1,b1)

---

34 范式【key,pattern】

题目R (队员编号，比赛场次，进球数，球队名，队长名)队员→球队，球队→队长，求 FD、主键、分解 2NF/3NF。

答案FD：(队员编号，比赛场次)→进球数；队员编号→球队名；球队名→队长名主键：(队员编号，比赛场次)2NF：R1 (队员编号，比赛场次，进球数)；R2 (队员编号，球队名，队长名)3NF：R1；R21 (队员编号，球队名)；R22 (球队名，队长名)

---

35 范式【key,pattern】

题目R (职工名，项目名，工资，部门号，部门经理)项目→部门，部门→经理，求 FD、主键、分解 2NF/3NF。

答案FD：(职工名，项目名)→工资；项目名→部门号；部门号→部门经理主键：(职工名，项目名)2NF：R1 (职工名，项目名，工资)；R2 (项目名，部门号，部门经理)3NF：R1；R21 (项目名，部门号)；R22 (部门号，部门经理)

---

36 最小依赖集【mindep,key】

题目系、学生、班级、研究会，设计关系、最小依赖、传递依赖、候选码、外码。

答案关系：学生、班级、系、研究会、入会最小依赖、候选码、外码见原文，分解到 3NF。

---

37 查询树【optim】

题目查询信息系 (IS) 学生选修课程名，画语法树并优化。

答案原始：πCname (Student∞SC∞CourseσSdept='IS')优化：先 σSdept='IS'(Student)，再连接，最后 πCname。

数据结构

一、线性表

1. 逆转顺序表中的所有元素

c

运行

void Reverse(int A[], int n) { int i, t; for (i=0; i < n/2; i++) { t = A[i]; A[i] = A[n-i-1]; A[n-i-1] = t; } }

1. 删除线性链表中数据域为 item 的所有结点

c

运行

void PurgeItem(LinkList &list) { LinkList p, q = list; p = list->next; while (p != NULL) { if (p->data == item) { q->next = p->next; free(p); p = q->next; } else { q = p; p = p->next; } } if (list->data == item) { q = list; list = list->next; free(q); } }

1. 逆转线性链表

c

运行

void Reverse(LinkList &list) { LinkList p, q, r; p = list; q = NULL; while (p != NULL) { r = q; q = p; p = p->next; q->next = r; } list = q; }

1. 复制线性链表 (递归)

c

运行

LinkList Copy(LinkList lista) { LinkList listb; if (lista == NULL) return NULL; else { listb = (LinkList)malloc(sizeof(LNode)); listb->data = lista->data; listb->next = Copy(lista->next); return listb; } }

1. 将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表

c

运行

LinkList MergeList(LinkList lista, LinkList listb) { LinkList listc, p = lista, q = listb, r; if (lista->data <= listb->data) { listc = lista; r = lista; p = lista->next; } else { listc = listb; r = listb; q = listb->next; } while (p != NULL && q != NULL) { if (p->data <= q->data) { r->next = p; r = p; p = p->next; } else { r->next = q; r = q; q = q->next; } } r->next = (p != NULL) ? p : q; return listc; }

二、树

1. 二叉树的先序遍历 (非递归算法)

c

运行

#define MAX_STACK 50 void PreOrderTraverse(BTree T) { BTree STACK[MAX_STACK], p = T; int top = -1; while (p != NULL || top != -1) { while (p != NULL) { VISIT(p); STACK[++top] = p; p = p->lchild; } p = STACK[top--]; p = p->rchild; } }

1. 二叉树的中序遍历 (非递归算法)

c

运行

#define MAX_STACK 50 void InOrderTraverse(BTree T) { BTree STACK[MAX_STACK], p = T; int top = -1; while (p != NULL || top != -1) { while (p != NULL) { STACK[++top] = p; p = p->lchild; } p = STACK[top--]; VISIT(p); p = p->rchild; } }

1. 二叉树的后序遍历 (非递归算法)

c

运行

#define MAX_STACK 50 void PostOrderTraverse(BTree T) { BTree STACK1[MAX_STACK], p = T; int STACK2[MAX_STACK], flag, top = -1; while (p != NULL || top != -1) { while (p != NULL) { STACK1[++top] = p; STACK2[top] = 0; p = p->lchild; } p = STACK1[top]; flag = STACK2[top--]; if (flag == 0) { STACK1[++top] = p; STACK2[top] = 1; p = p->rchild; } else { VISIT(p); p = NULL; } } }

1. 二叉树的按层次遍历

c

运行

#define MAX_QUEUE 50 void LayeredOrderTraverse(BTree T) { BTree QUEUE[MAX_QUEUE], p; int front, rear; if (T != NULL) { QUEUE[0] = T; front = -1; rear = 0; while (front < rear) { p = QUEUE[++front]; VISIT(p); if (p->lchild != NULL) QUEUE[++rear] = p->lchild; if (p->rchild != NULL) QUEUE[++rear] = p->rchild; } } }

1. 建立二叉树 (从键盘输入数据，先序遍历递归算法)

c

运行

BTree CreateBT() { char ch; BTree T; scanf("%c", &ch); if (ch == ' ') return NULL; else { T = (BTree)malloc(sizeof(BTNode)); T->data = ch; T->lchild = CreateBT(); T->rchild = CreateBT(); return T; } }

1. 建立二叉树 (从数组获取数据)

c

运行

BTree CreateBT(int A[], int i, int n) { BTree p; if (i > n) return NULL; else { p = (BTree)malloc(sizeof(BTNode)); p->data = A[i]; p->lchild = CreateBT(A, 2*i, n); p->rchild = CreateBT(A, 2*i+1, n); return p; } }

1. 求二叉树的深度 (递归算法)

c

运行

int Depth(BTree T) { int ldepth, rdepth; if (T == NULL) return 0; else { ldepth = Depth(T->lchild); rdepth = Depth(T->rchild); if (ldepth > rdepth) return ldepth+1; else return rdepth+1; } }

1. 求二叉树的深度 (非递归算法)

c

运行

#define MAX_STACK 50 int Depth(BTree T) { BTree STACK1[MAX_STACK], p = T; int STACK2[MAX_STACK]; int curdepth, maxdepth = 0, top = -1; if (T != NULL) { curdepth = 1; while (p != NULL || top != -1) { while (p != NULL) { STACK1[++top] = p; STACK2[top] = curdepth; p = p->lchild; curdepth++; } p = STACK1[top]; curdepth = STACK2[top--]; if (p->lchild == NULL && p->rchild == NULL) if (curdepth > maxdepth) maxdepth = curdepth; p = p->rchild; curdepth++; } } return maxdepth; }

1. 求结点所在层次

c

运行

#define MAX_STACK 50 int LayerNode(BTree T, int item) { BTree STACK1[MAX_STACK], p = T; int STACK2[MAX_STACK], flag, top = -1; while (p != NULL || top != -1) { while (p != NULL) { STACK1[++top] = p; STACK2[top] = 0; p = p->lchild; } p = STACK1[top]; flag = STACK2[top--]; if (flag == 0) { STACK1[++top] = p; STACK2[top] = 1; p = p->rchild; } else { if (p->data == item) return top+2; p = NULL; } } }

1. 交换二叉树中所有结点的左右子树的位置

c

运行

#define MAX_QUEUE 50 void ExchangeBT(BTree T) { BTree QUEUE[MAX_QUEUE], temp, p = T; int front, rear; if (T != NULL) { QUEUE[0] = T; front = -1; rear = 0; while (front < rear) { p = QUEUE[++front]; temp = p->lchild; p->lchild = p->rchild; p->rchild = temp; if (p->lchild != NULL) QUEUE[++rear] = p->lchild; if (p->rchild != NULL) QUEUE[++rear] = p->rchild; } } }

1. 删除二叉树中以某个结点为根结点的子树

c

运行

#define MAX_STACK 50 BTree DeleteSubtree(BTree &T, int item) { BTree STACK[MAX_STACK], q, p = T; int top = -1; if (T->data == item) { DestroyBT(T); T = NULL; return NULL; } else { while (p != NULL || top != -1) { while (p != NULL) { if (p->data == item) { if (q->lchild == p) q->lchild = NULL; else q->rchild = NULL; DestroyBT(p); return T; } STACK[++top]= p; q = p; p = p->lchild; } q = STACK[top--]; p = q->rchild; } } }

三、查找

1. 顺序查找的递归算法

c

运行

int RecurSeqSearch(int A[], int n, int key, int i) { if (i >= n) return -1; if (A[i] == key) return i; else return RecurSeqSearch(A, n, key, i+1); }

1. 折半查找

c

运行

int BinSearch(int A[], int n, int key) { int low=0, high=n-1, mid; while (low <= high) { mid = (low+high)/2; if (key == A[mid]) return mid; if (key > A[mid]) low = mid + 1; else high = mid – 1; } return -1; }

1. 折半查找的递归算法

c

运行

int RecurBinSearch(int A[], int low, int high, int key) { int mid; if (low > high) return -1; else { mid = (low+high)/2; if (key == A[mid]) return mid; if (key > A[mid]) return RecurBinSearch(A, mid+1, high, key); else return RecurBinSearch(A, low, mid-1, key); } }

1. 在按值递增排列且长度为 n 的线性表中折半查找并插入一元素

c

运行

void BinInsert(int A[], int &n, int key) { int j, low=0, high=n-1, mid; while (low <= high) { mid = (low+high)/2; if (key > A[mid]) low = mid + 1; else high = mid – 1; } for (j=n; j > low; j--) A[j] = A[j-1]; A[low] = key; n++; }

1. 在按值递增排列且长度为 n 的线性表中折半查找值不小于 key 的最小元素

c

运行

int BinSearch(int A[], int n, int key) { int low=0, high=n-1, mid; while (low <= high) { mid = (low+high)/2; if (key == A[mid]) return mid; if (key > A[mid]) low = mid + 1; else high = mid – 1; } if (low <= n-1) return low; else return -1; }

四、排序

1. 插入排序

c

运行

void InsertSort(int A[], int n) { int i, j, temp; for (i=1; i <= n-1; i++) { if (A[i] < A[i-1]) { j = i-1; temp = A[i]; while (j >= 0 && temp < A[j]) { A[j+1] = A[j]; j--; } A[j+1] = temp; } } }

1. 折半插入排序

c

运行

void BinInsertSort(int A[], int n) { int i, j, low, high, mid, temp; for (i=1; i <= n-1; i++) { temp = A[i]; low = 0; high = i – 1; while (low <= high) { mid = (low+high)/2; if (temp > A[mid]) low = mid + 1; else high = mid – 1; } for (j=i; j > low; j--) A[j] = A[j-1]; A[low] = temp; } }

1. 冒泡排序

c

运行

void BubbleSort(int A[], int n) { int i, j, temp, flag = 1; for (i=n-1; i >= 1 && flag == 1; i--) { flag = 0; for (j=0; j < i; j++) { if (A[j] > A[j+1]) { temp = A[j]; A[j] = A[j+1]; A[j+1] = temp; flag = 1; } } } }

1. 选择排序

c

运行

void SelectSort(int A[], int n) { int i, j, min, temp; for (i=0; i < n; i++) { min = i; for (j=i+1; j < n; j++) if (A[min] > A[j]) min = j; if (min != i) { temp = A[min]; A[min] = A[i]; A[i] = temp; } } }

1. 快速排序

c

运行

void QuickSort(int A[], int n) { QSort(A, 0, n-1); } void QSort(int A[], int low, int high) { int pivotloc; if (low < high) { pivotloc = Partition(A, low, high); QSort(A, low, pivotloc-1); QSort(A, pivotloc+1, high); } } int Partition(int A[], int low, int high) { int pivot; pivot = A[low]; while (low < high) { while (low < high && A[high] >= pivot) high--; A[low] = A[high]; while (low < high && A[low] <= pivot) low++; A[high] = A[low]; } A[low] = pivot; return low; }

1. 堆排序

c

运行

void HeapSort(int A[], int n) { int i, temp; for (i = n/2; i >= 1; i--) HeapAdjust(A,i,n); for (i = n-1; i >= 1; i--) { temp = A[1]; A[1] = A[i+1]; A[i+1] = temp; HeapAdjust(A,1,i); } } void HeapAdjust(int A[], int low, int high) { int i, temp; temp = A[low]; for (i=2*low; i <= high; i=i*2) { if (i < high && A[i] < A[i+1]) i++; if (temp >= A[i]) break; else { A[low] = A[i]; low = i; } } A[low] = temp; }

over