数据库代码说明表格代码考察内容sqlSQL 语句alg关系代数erER 图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】题目学生 (学号姓名性别专业奖学金)课程 (课程号名称学分)学习 (学号课程号分数)检索 “国际贸易” 专业获奖学金学生信息学号、姓名、课程名、分数检索成绩满分课程的课程号、名称、学分检索无奖学金且至少一门 95 分学生学号、姓名、专业检索无 80 分以下成绩学生学号、姓名、专业答案3 SQL 语句【sql】题目学生 (学号姓名年龄性别)社团 (编号名称负责人办公地点)参加 (学号编号参加日期)定义社团表主码 外键建立视图社团负责人 (社团编号名称负责人学号负责人姓名负责人性别)查询参加 “科协” 学生学号、姓名、性别统计每个社团参加人数赋插入 / 删除权限给李平并允许转授答案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 题表结构英语专业学生课程信息学号、姓名、课程名、分数数据库原理 90 分学生学号、姓名、专业、分数不学 C135 学生学号、姓名、专业无不及格学生学号、姓名、专业答案Π 学号姓名课程名分数 (σ 专业 英语 (学生∞学习∞课程))Π 学号姓名专业分数 (σ 分数 90∧名称 数据库原理 (学生∞学习∞课程))Π 学号姓名专业 (学生)−Π 学号姓名专业 (σ 课程号 C135(学生∞学习))Π 学号姓名专业 (学生)−Π 学号姓名专业 (σ 分数 60 (学生∞学习))8 SQL 语句【sql】题目职工 (职工号姓名性别职务家庭地址部门编号)部门 (部门编号部门名称地址电话)保健 (保健卡编号职工号检查日期健康状况)女科长办公室科长姓名、地址财务科健康良好职工姓名、地址改 3016 健康状况为一般删除 3016 职工建健康差视图保健表加备注列 (20 字符)答案SELECT * FROM 职工 WHERE 性别 女 AND 职务 科长 ;SELECT 姓名家庭地址 FROM 职工部门WHERE 职工。部门编号 部门。部门编号 AND 部门名称 办公室 AND 职务 科长 ;SELECT 姓名家庭地址 FROM 职工部门保健WHERE 职工。部门编号 部门。部门编号 AND 职工。职工号 保健。职工号AND 部门名称 财务科 AND 健康状况 良好 ;UPDATE 保健 SET 健康状况 一般 WHERE 职工号 3016;DELETE FROM 职工 WHERE 职工号 3016;CREATE VIEW VW ASSELECT * FROM 职工 WHERE 职工号 IN (SELECT 职工号 FROM 保健 WHERE 健康状况 差 );ALTER TABLE 保健 ADD 备注 CHAR (20);9 闭包【closure】题目F{AB→CE,A→C,GP→B,EP→A,CDE→P,HB→P,D→HG,ABC→PG}求 DF{AC→PE,PG→A,B→CE,A→P,GA→B,GC→A,PAB→G,AE→GB,ABCP→H}求 (BG)答案D⁺ DHG(BG)⁺ BGCEAPH10 范式【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)至少选 C02、C06 的学号未选 C06 的姓名、班级学全部课程的姓名包含 S08 所学全部课程的学号答案关系代数πsno(σcnoC02(elective))∩πsno(σcnoC06(elective))πsname,class(student)−πsname,class(σcnoC06(student∞elective))πsname(student∞(πsno,cno(elective)÷πcno(course)))πsno,cno(elective)÷πcno(σsnoS08(elective))SQLSELECT DISTINCT a.sno FROM elective a,elective bWHERE a.snob.sno AND a.cnoC02 AND b.cnoC06;SELECT sname,class FROM studentWHERE NOT EXISTS(SELECT * FROM electiveWHERE snostudent.sno AND cnoC06);SELECT sname FROM studentWHERE NOT EXISTS(SELECT * FROM courseWHERE NOT EXISTS(SELECT * FROM electiveWHERE snostudent.sno AND cnocourse.cno));SELECT DISTINCT sno FROM elective XWHERE NOT EXISTS(SELECT * FROM elective YWHERE Y.snoS08 AND NOT EXISTS(SELECT * FROM elective ZWHERE Z.snoX.sno AND Z.cnoY.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 能否导出用推理规则 闭包证明。答案推理AC→BB→D ⇒ AC→DD→BE ⇒ AC→BE(AC)⁺ABCDEBE⊆(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)95001 学生 60 分课程号数据库概论 80/90 分学生学号姓名选全部课程学生信息无人选课程选课 3 门学生学号、门数、均分删除数据结构课程及选课答案关系代数πC#(σS#95001∧G60(SC))πS#,SN (σCN 数据库概论 (C)∞σG80∨G90 (SC)∞S)πS#,SN,SD(S∞(πS#,C#(SC)÷πC#(C)))SQLSELECT C# FROM SC WHERE S#95001 AND G60;SELECT S.S#,SN FROM S,SC,CWHERE C.C#SC.C# AND SC.S#S.S# AND CN 数据库概论 AND (G80 OR G90);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#));SELECT C#,CN FROM C WHERE C# NOT IN(SELECT DISTINCT C# FROM SC);SELECT S#,COUNT(C#),AVG(G) FROM SC GROUP BY S# HAVING COUNT(C#)3;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】题目x1000甲取 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)⁺ CDAEB19 SQL【sql】题目职工 (职工号姓名年龄月工资部门号电话办公室)部门 (部门号部门名负责人代码任职时间)建表、视图、插入判断、视图更新、查询功能。答案(a) PRIMARY KEY(b) FOREIGN KEY (负责人代码) REFERENCES 职工 (职工号)(c) FOREIGN KEY (部门号) REFERENCES 部门 (部门号)(d) 月工资 500 AND 月工资 5000(e) COUNT (*),SUM (月工资),AVG (月工资)(f) GROUP BY 部门号1) 不可插入 (主键重复)2) 可插入3) 不可插入 (部门不存在)视图含聚集函数不可更新可查询查询每个部门工资最高的职工号20 求码 范式【key,pattern】题目项目信息、科研专家、项目研发人员三个关系求候选码、判断范式、分解 3NF。答案项目信息课题编号科研专家人员编号 / 身份证号研发人员(课题编号所在单位职工号)科研专家2NF存在所在单位→单位地址传递依赖研发人员分解研发人员 1 (所在单位职工号姓名年龄学历职称)研发人员 2 (课题编号所在单位职工号分工排名参加月数)21 关系代数【alg】题目同 15 题写关系代数。答案πC#(σS#95001∧G60(SC))πS#,SN (σCN 数据库概论 (C)∞σG80∨G90 (SC)∞S)πS#,SN,SD(S∞(πS#,C#(SC)÷πC#(C)))22 事务【lock】题目AB2T1:AB1T2:BA1并发结果、正确性、封锁填空。答案正确结果A3,B4 或 A4,B3标准可串行化本例 A3,B3不正确(a) SLOCK B(b) XLOCK A(c) 写回 A3(d) XA3(e) UNLOCK A23 闭包【closure】题目求 AE⁺F 含 AE→C,E→D,C→B。答案(AE)⁺ ABCDE24 SQL 关系代数【sql,alg】题目客户、产品、订单、订单明细建表、查询、视图、包含查询。答案(a) PRIMARY KEY(b) CHECK (性别 IN ( 男 , 女 ))(c) FOREIGN KEY (客户号) REFERENCES 客户 (客户号)查询购买 02 号产品 10 件的客户号π 客户号 (订单∞σ 产品号 02∧数量 10 (订单明细))SUM (金额) 购买总额GROUP BY 客户。客户号ORDER BY 购买总额 DESC视图 包含查询用 NOT EXISTS 三层嵌套25 范式【key,pattern】题目旅游线路、订单、员工信息判断 BCNF/3NF/4NF分解。答案线路信息BCNF无部分 / 传递依赖订单信息分解订单 1 (订单号线路编号联系人身份证号人数订单价格出发时间)订单 2 (联系人身份证号联系人名称联系方式)订单 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 的商店名转关系代数画优化树。答案SQLSELECT SNAME FROM P,S,SPWHERE P.PNOSP.PNO AND S.SNOSP.SNO AND PNAMETV;关系代数πSNAME (S∞SP∞σPNAMETV(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)BCNF29 E-R 图【er】题目制药厂客户、类别、销售单、业务员、产品、销售 (多对多)ER 转关系标主外码。答案类别 (客户类别名最低供应扣率资金回笼期限) PK客户类别名客户 (客户编号客户名地址电话税金账号应收款背景客户类别名) PK客户编号 FK客户类别名业务员 (业务员编号姓名销售额销售指标) PK业务员编号销售单 (销售单编号日期到款日期客户编号业务员编号) PK销售单编号 FK客户编号业务员编号产品 (产品编号产品名类别名批发价零售价库存量) PK产品编号销售 (销售单编号产品编号标记数量金额) PK(销售单编号产品编号) FK销售单编号产品编号30 关系代数 SQL【alg,sql】题目同 27 题查卖全部商品、不卖 P2、至少卖 P1/P2 的商店建伦敦卖红色商品视图。答案全部商品用 NOT EXISTS 嵌套不卖 P2WHERE NOT EXISTS (SELECT * FROM SP WHERE PNOP2 AND SNOS.SNO)至少 P1/P2自连接 SP视图CREATE VIEW RLS AS SELECT SNO,SNAME FROM S,SP,PWHERE S.SNOSP.SNO AND SP.PNOP.PNO AND CITYLondon AND COLORRed;31 E-R 图【er】题目车间、工人、产品、零件、仓库画 ER 转关系。答案车间 (车间号主任姓名地址电话厂名)仓库 (仓库号主任姓名电话厂名)零件 (零件号重量价格仓库号)产品 (产品号价格仓库号)工人 (职工号姓名年龄性别工种车间号)制造 (车间号零件号数量 1)组成 (产品号零件号数量 2)32 SQL 关系代数【alg,sql】题目S (SNO,SN,SEX,AGE),C (CNO,CN,PCNO),SC (SNO,CNO,G)查全选课、DB90 分姓名、建 SDB 视图、英语课成绩提 10%。答案全选课NOT EXISTS 嵌套SELECT SN FROM S,SC,CWHERE S.SNOSC.SNO AND SC.CNOC.CNO AND CNDB AND G90;CREATE VIEW SDB AS SELECT SNO,SN FROM S,SC,CWHERE S.SNOSC.SNO AND SC.CNOC.CNO AND CNDB;UPDATE SC SET GG*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(队员编号比赛场次)→进球数队员编号→球队名球队名→队长名主键(队员编号比赛场次)2NFR1 (队员编号比赛场次进球数)R2 (队员编号球队名队长名)3NFR1R21 (队员编号球队名)R22 (球队名队长名)35 范式【key,pattern】题目R (职工名项目名工资部门号部门经理)项目→部门部门→经理求 FD、主键、分解 2NF/3NF。答案FD(职工名项目名)→工资项目名→部门号部门号→部门经理主键(职工名项目名)2NFR1 (职工名项目名工资)R2 (项目名部门号部门经理)3NFR1R21 (项目名部门号)R22 (部门号部门经理)36 最小依赖集【mindep,key】题目系、学生、班级、研究会设计关系、最小依赖、传递依赖、候选码、外码。答案关系学生、班级、系、研究会、入会最小依赖、候选码、外码见原文分解到 3NF。37 查询树【optim】题目查询信息系 (IS) 学生选修课程名画语法树并优化。答案原始πCname (Student∞SC∞CourseσSdeptIS)优化先 σSdeptIS(Student)再连接最后 πCname。数据结构一、线性表逆转顺序表中的所有元素c运行void Reverse(int A[], int n) { int i, t; for (i0; i n/2; i) { t A[i]; A[i] A[n-i-1]; A[n-i-1] t; } }删除线性链表中数据域为 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); } }逆转线性链表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; }复制线性链表 (递归)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; } }将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表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; }二、树二叉树的先序遍历 (非递归算法)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; } }二叉树的中序遍历 (非递归算法)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; } }二叉树的后序遍历 (非递归算法)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; } } }二叉树的按层次遍历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; } } }建立二叉树 (从键盘输入数据先序遍历递归算法)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; } }建立二叉树 (从数组获取数据)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*i1, n); return p; } }求二叉树的深度 (递归算法)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 ldepth1; else return rdepth1; } }求二叉树的深度 (非递归算法)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; }求结点所在层次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 top2; p NULL; } } }交换二叉树中所有结点的左右子树的位置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; } } }删除二叉树中以某个结点为根结点的子树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; } } }三、查找顺序查找的递归算法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, i1); }折半查找c运行int BinSearch(int A[], int n, int key) { int low0, highn-1, mid; while (low high) { mid (lowhigh)/2; if (key A[mid]) return mid; if (key A[mid]) low mid 1; else high mid – 1; } return -1; }折半查找的递归算法c运行int RecurBinSearch(int A[], int low, int high, int key) { int mid; if (low high) return -1; else { mid (lowhigh)/2; if (key A[mid]) return mid; if (key A[mid]) return RecurBinSearch(A, mid1, high, key); else return RecurBinSearch(A, low, mid-1, key); } }在按值递增排列且长度为 n 的线性表中折半查找并插入一元素c运行void BinInsert(int A[], int n, int key) { int j, low0, highn-1, mid; while (low high) { mid (lowhigh)/2; if (key A[mid]) low mid 1; else high mid – 1; } for (jn; j low; j--) A[j] A[j-1]; A[low] key; n; }在按值递增排列且长度为 n 的线性表中折半查找值不小于 key 的最小元素c运行int BinSearch(int A[], int n, int key) { int low0, highn-1, mid; while (low high) { mid (lowhigh)/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; }四、排序插入排序c运行void InsertSort(int A[], int n) { int i, j, temp; for (i1; i n-1; i) { if (A[i] A[i-1]) { j i-1; temp A[i]; while (j 0 temp A[j]) { A[j1] A[j]; j--; } A[j1] temp; } } }折半插入排序c运行void BinInsertSort(int A[], int n) { int i, j, low, high, mid, temp; for (i1; i n-1; i) { temp A[i]; low 0; high i – 1; while (low high) { mid (lowhigh)/2; if (temp A[mid]) low mid 1; else high mid – 1; } for (ji; j low; j--) A[j] A[j-1]; A[low] temp; } }冒泡排序c运行void BubbleSort(int A[], int n) { int i, j, temp, flag 1; for (in-1; i 1 flag 1; i--) { flag 0; for (j0; j i; j) { if (A[j] A[j1]) { temp A[j]; A[j] A[j1]; A[j1] temp; flag 1; } } } }选择排序c运行void SelectSort(int A[], int n) { int i, j, min, temp; for (i0; i n; i) { min i; for (ji1; j n; j) if (A[min] A[j]) min j; if (min ! i) { temp A[min]; A[min] A[i]; A[i] temp; } } }快速排序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, pivotloc1, 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; }堆排序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[i1]; A[i1] temp; HeapAdjust(A,1,i); } } void HeapAdjust(int A[], int low, int high) { int i, temp; temp A[low]; for (i2*low; i high; ii*2) { if (i high A[i] A[i1]) i; if (temp A[i]) break; else { A[low] A[i]; low i; } } A[low] temp; }over
复试准备背诵
数据库代码说明表格代码考察内容sqlSQL 语句alg关系代数erER 图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】题目学生 (学号姓名性别专业奖学金)课程 (课程号名称学分)学习 (学号课程号分数)检索 “国际贸易” 专业获奖学金学生信息学号、姓名、课程名、分数检索成绩满分课程的课程号、名称、学分检索无奖学金且至少一门 95 分学生学号、姓名、专业检索无 80 分以下成绩学生学号、姓名、专业答案3 SQL 语句【sql】题目学生 (学号姓名年龄性别)社团 (编号名称负责人办公地点)参加 (学号编号参加日期)定义社团表主码 外键建立视图社团负责人 (社团编号名称负责人学号负责人姓名负责人性别)查询参加 “科协” 学生学号、姓名、性别统计每个社团参加人数赋插入 / 删除权限给李平并允许转授答案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 题表结构英语专业学生课程信息学号、姓名、课程名、分数数据库原理 90 分学生学号、姓名、专业、分数不学 C135 学生学号、姓名、专业无不及格学生学号、姓名、专业答案Π 学号姓名课程名分数 (σ 专业 英语 (学生∞学习∞课程))Π 学号姓名专业分数 (σ 分数 90∧名称 数据库原理 (学生∞学习∞课程))Π 学号姓名专业 (学生)−Π 学号姓名专业 (σ 课程号 C135(学生∞学习))Π 学号姓名专业 (学生)−Π 学号姓名专业 (σ 分数 60 (学生∞学习))8 SQL 语句【sql】题目职工 (职工号姓名性别职务家庭地址部门编号)部门 (部门编号部门名称地址电话)保健 (保健卡编号职工号检查日期健康状况)女科长办公室科长姓名、地址财务科健康良好职工姓名、地址改 3016 健康状况为一般删除 3016 职工建健康差视图保健表加备注列 (20 字符)答案SELECT * FROM 职工 WHERE 性别 女 AND 职务 科长 ;SELECT 姓名家庭地址 FROM 职工部门WHERE 职工。部门编号 部门。部门编号 AND 部门名称 办公室 AND 职务 科长 ;SELECT 姓名家庭地址 FROM 职工部门保健WHERE 职工。部门编号 部门。部门编号 AND 职工。职工号 保健。职工号AND 部门名称 财务科 AND 健康状况 良好 ;UPDATE 保健 SET 健康状况 一般 WHERE 职工号 3016;DELETE FROM 职工 WHERE 职工号 3016;CREATE VIEW VW ASSELECT * FROM 职工 WHERE 职工号 IN (SELECT 职工号 FROM 保健 WHERE 健康状况 差 );ALTER TABLE 保健 ADD 备注 CHAR (20);9 闭包【closure】题目F{AB→CE,A→C,GP→B,EP→A,CDE→P,HB→P,D→HG,ABC→PG}求 DF{AC→PE,PG→A,B→CE,A→P,GA→B,GC→A,PAB→G,AE→GB,ABCP→H}求 (BG)答案D⁺ DHG(BG)⁺ BGCEAPH10 范式【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)至少选 C02、C06 的学号未选 C06 的姓名、班级学全部课程的姓名包含 S08 所学全部课程的学号答案关系代数πsno(σcnoC02(elective))∩πsno(σcnoC06(elective))πsname,class(student)−πsname,class(σcnoC06(student∞elective))πsname(student∞(πsno,cno(elective)÷πcno(course)))πsno,cno(elective)÷πcno(σsnoS08(elective))SQLSELECT DISTINCT a.sno FROM elective a,elective bWHERE a.snob.sno AND a.cnoC02 AND b.cnoC06;SELECT sname,class FROM studentWHERE NOT EXISTS(SELECT * FROM electiveWHERE snostudent.sno AND cnoC06);SELECT sname FROM studentWHERE NOT EXISTS(SELECT * FROM courseWHERE NOT EXISTS(SELECT * FROM electiveWHERE snostudent.sno AND cnocourse.cno));SELECT DISTINCT sno FROM elective XWHERE NOT EXISTS(SELECT * FROM elective YWHERE Y.snoS08 AND NOT EXISTS(SELECT * FROM elective ZWHERE Z.snoX.sno AND Z.cnoY.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 能否导出用推理规则 闭包证明。答案推理AC→BB→D ⇒ AC→DD→BE ⇒ AC→BE(AC)⁺ABCDEBE⊆(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)95001 学生 60 分课程号数据库概论 80/90 分学生学号姓名选全部课程学生信息无人选课程选课 3 门学生学号、门数、均分删除数据结构课程及选课答案关系代数πC#(σS#95001∧G60(SC))πS#,SN (σCN 数据库概论 (C)∞σG80∨G90 (SC)∞S)πS#,SN,SD(S∞(πS#,C#(SC)÷πC#(C)))SQLSELECT C# FROM SC WHERE S#95001 AND G60;SELECT S.S#,SN FROM S,SC,CWHERE C.C#SC.C# AND SC.S#S.S# AND CN 数据库概论 AND (G80 OR G90);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#));SELECT C#,CN FROM C WHERE C# NOT IN(SELECT DISTINCT C# FROM SC);SELECT S#,COUNT(C#),AVG(G) FROM SC GROUP BY S# HAVING COUNT(C#)3;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】题目x1000甲取 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)⁺ CDAEB19 SQL【sql】题目职工 (职工号姓名年龄月工资部门号电话办公室)部门 (部门号部门名负责人代码任职时间)建表、视图、插入判断、视图更新、查询功能。答案(a) PRIMARY KEY(b) FOREIGN KEY (负责人代码) REFERENCES 职工 (职工号)(c) FOREIGN KEY (部门号) REFERENCES 部门 (部门号)(d) 月工资 500 AND 月工资 5000(e) COUNT (*),SUM (月工资),AVG (月工资)(f) GROUP BY 部门号1) 不可插入 (主键重复)2) 可插入3) 不可插入 (部门不存在)视图含聚集函数不可更新可查询查询每个部门工资最高的职工号20 求码 范式【key,pattern】题目项目信息、科研专家、项目研发人员三个关系求候选码、判断范式、分解 3NF。答案项目信息课题编号科研专家人员编号 / 身份证号研发人员(课题编号所在单位职工号)科研专家2NF存在所在单位→单位地址传递依赖研发人员分解研发人员 1 (所在单位职工号姓名年龄学历职称)研发人员 2 (课题编号所在单位职工号分工排名参加月数)21 关系代数【alg】题目同 15 题写关系代数。答案πC#(σS#95001∧G60(SC))πS#,SN (σCN 数据库概论 (C)∞σG80∨G90 (SC)∞S)πS#,SN,SD(S∞(πS#,C#(SC)÷πC#(C)))22 事务【lock】题目AB2T1:AB1T2:BA1并发结果、正确性、封锁填空。答案正确结果A3,B4 或 A4,B3标准可串行化本例 A3,B3不正确(a) SLOCK B(b) XLOCK A(c) 写回 A3(d) XA3(e) UNLOCK A23 闭包【closure】题目求 AE⁺F 含 AE→C,E→D,C→B。答案(AE)⁺ ABCDE24 SQL 关系代数【sql,alg】题目客户、产品、订单、订单明细建表、查询、视图、包含查询。答案(a) PRIMARY KEY(b) CHECK (性别 IN ( 男 , 女 ))(c) FOREIGN KEY (客户号) REFERENCES 客户 (客户号)查询购买 02 号产品 10 件的客户号π 客户号 (订单∞σ 产品号 02∧数量 10 (订单明细))SUM (金额) 购买总额GROUP BY 客户。客户号ORDER BY 购买总额 DESC视图 包含查询用 NOT EXISTS 三层嵌套25 范式【key,pattern】题目旅游线路、订单、员工信息判断 BCNF/3NF/4NF分解。答案线路信息BCNF无部分 / 传递依赖订单信息分解订单 1 (订单号线路编号联系人身份证号人数订单价格出发时间)订单 2 (联系人身份证号联系人名称联系方式)订单 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 的商店名转关系代数画优化树。答案SQLSELECT SNAME FROM P,S,SPWHERE P.PNOSP.PNO AND S.SNOSP.SNO AND PNAMETV;关系代数πSNAME (S∞SP∞σPNAMETV(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)BCNF29 E-R 图【er】题目制药厂客户、类别、销售单、业务员、产品、销售 (多对多)ER 转关系标主外码。答案类别 (客户类别名最低供应扣率资金回笼期限) PK客户类别名客户 (客户编号客户名地址电话税金账号应收款背景客户类别名) PK客户编号 FK客户类别名业务员 (业务员编号姓名销售额销售指标) PK业务员编号销售单 (销售单编号日期到款日期客户编号业务员编号) PK销售单编号 FK客户编号业务员编号产品 (产品编号产品名类别名批发价零售价库存量) PK产品编号销售 (销售单编号产品编号标记数量金额) PK(销售单编号产品编号) FK销售单编号产品编号30 关系代数 SQL【alg,sql】题目同 27 题查卖全部商品、不卖 P2、至少卖 P1/P2 的商店建伦敦卖红色商品视图。答案全部商品用 NOT EXISTS 嵌套不卖 P2WHERE NOT EXISTS (SELECT * FROM SP WHERE PNOP2 AND SNOS.SNO)至少 P1/P2自连接 SP视图CREATE VIEW RLS AS SELECT SNO,SNAME FROM S,SP,PWHERE S.SNOSP.SNO AND SP.PNOP.PNO AND CITYLondon AND COLORRed;31 E-R 图【er】题目车间、工人、产品、零件、仓库画 ER 转关系。答案车间 (车间号主任姓名地址电话厂名)仓库 (仓库号主任姓名电话厂名)零件 (零件号重量价格仓库号)产品 (产品号价格仓库号)工人 (职工号姓名年龄性别工种车间号)制造 (车间号零件号数量 1)组成 (产品号零件号数量 2)32 SQL 关系代数【alg,sql】题目S (SNO,SN,SEX,AGE),C (CNO,CN,PCNO),SC (SNO,CNO,G)查全选课、DB90 分姓名、建 SDB 视图、英语课成绩提 10%。答案全选课NOT EXISTS 嵌套SELECT SN FROM S,SC,CWHERE S.SNOSC.SNO AND SC.CNOC.CNO AND CNDB AND G90;CREATE VIEW SDB AS SELECT SNO,SN FROM S,SC,CWHERE S.SNOSC.SNO AND SC.CNOC.CNO AND CNDB;UPDATE SC SET GG*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(队员编号比赛场次)→进球数队员编号→球队名球队名→队长名主键(队员编号比赛场次)2NFR1 (队员编号比赛场次进球数)R2 (队员编号球队名队长名)3NFR1R21 (队员编号球队名)R22 (球队名队长名)35 范式【key,pattern】题目R (职工名项目名工资部门号部门经理)项目→部门部门→经理求 FD、主键、分解 2NF/3NF。答案FD(职工名项目名)→工资项目名→部门号部门号→部门经理主键(职工名项目名)2NFR1 (职工名项目名工资)R2 (项目名部门号部门经理)3NFR1R21 (项目名部门号)R22 (部门号部门经理)36 最小依赖集【mindep,key】题目系、学生、班级、研究会设计关系、最小依赖、传递依赖、候选码、外码。答案关系学生、班级、系、研究会、入会最小依赖、候选码、外码见原文分解到 3NF。37 查询树【optim】题目查询信息系 (IS) 学生选修课程名画语法树并优化。答案原始πCname (Student∞SC∞CourseσSdeptIS)优化先 σSdeptIS(Student)再连接最后 πCname。数据结构一、线性表逆转顺序表中的所有元素c运行void Reverse(int A[], int n) { int i, t; for (i0; i n/2; i) { t A[i]; A[i] A[n-i-1]; A[n-i-1] t; } }删除线性链表中数据域为 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); } }逆转线性链表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; }复制线性链表 (递归)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; } }将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表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; }二、树二叉树的先序遍历 (非递归算法)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; } }二叉树的中序遍历 (非递归算法)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; } }二叉树的后序遍历 (非递归算法)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; } } }二叉树的按层次遍历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; } } }建立二叉树 (从键盘输入数据先序遍历递归算法)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; } }建立二叉树 (从数组获取数据)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*i1, n); return p; } }求二叉树的深度 (递归算法)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 ldepth1; else return rdepth1; } }求二叉树的深度 (非递归算法)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; }求结点所在层次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 top2; p NULL; } } }交换二叉树中所有结点的左右子树的位置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; } } }删除二叉树中以某个结点为根结点的子树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; } } }三、查找顺序查找的递归算法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, i1); }折半查找c运行int BinSearch(int A[], int n, int key) { int low0, highn-1, mid; while (low high) { mid (lowhigh)/2; if (key A[mid]) return mid; if (key A[mid]) low mid 1; else high mid – 1; } return -1; }折半查找的递归算法c运行int RecurBinSearch(int A[], int low, int high, int key) { int mid; if (low high) return -1; else { mid (lowhigh)/2; if (key A[mid]) return mid; if (key A[mid]) return RecurBinSearch(A, mid1, high, key); else return RecurBinSearch(A, low, mid-1, key); } }在按值递增排列且长度为 n 的线性表中折半查找并插入一元素c运行void BinInsert(int A[], int n, int key) { int j, low0, highn-1, mid; while (low high) { mid (lowhigh)/2; if (key A[mid]) low mid 1; else high mid – 1; } for (jn; j low; j--) A[j] A[j-1]; A[low] key; n; }在按值递增排列且长度为 n 的线性表中折半查找值不小于 key 的最小元素c运行int BinSearch(int A[], int n, int key) { int low0, highn-1, mid; while (low high) { mid (lowhigh)/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; }四、排序插入排序c运行void InsertSort(int A[], int n) { int i, j, temp; for (i1; i n-1; i) { if (A[i] A[i-1]) { j i-1; temp A[i]; while (j 0 temp A[j]) { A[j1] A[j]; j--; } A[j1] temp; } } }折半插入排序c运行void BinInsertSort(int A[], int n) { int i, j, low, high, mid, temp; for (i1; i n-1; i) { temp A[i]; low 0; high i – 1; while (low high) { mid (lowhigh)/2; if (temp A[mid]) low mid 1; else high mid – 1; } for (ji; j low; j--) A[j] A[j-1]; A[low] temp; } }冒泡排序c运行void BubbleSort(int A[], int n) { int i, j, temp, flag 1; for (in-1; i 1 flag 1; i--) { flag 0; for (j0; j i; j) { if (A[j] A[j1]) { temp A[j]; A[j] A[j1]; A[j1] temp; flag 1; } } } }选择排序c运行void SelectSort(int A[], int n) { int i, j, min, temp; for (i0; i n; i) { min i; for (ji1; j n; j) if (A[min] A[j]) min j; if (min ! i) { temp A[min]; A[min] A[i]; A[i] temp; } } }快速排序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, pivotloc1, 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; }堆排序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[i1]; A[i1] temp; HeapAdjust(A,1,i); } } void HeapAdjust(int A[], int low, int high) { int i, temp; temp A[low]; for (i2*low; i high; ii*2) { if (i high A[i] A[i1]) i; if (temp A[i]) break; else { A[low] A[i]; low i; } } A[low] temp; }over
