下载文档原格式
【2023年】四川省成都市全国计算机等级考试数据库技术真题(含答案)学校:________ 班级:________ 姓名:________ 考号:________一、1.选择题(10题)1. 在逻辑结构设计中，关系已达到规范化，但因某些属性过多时，可将它分为两个或多个关系模式，这叫做A.模式评价B.优化模式C.合并D.分解2. 若某二叉树的前序遍历节点访问顺序是abdgcefh：中序遍历的节点访问顺序是dgbaechf，则其后序遍历的节点访问顺序是______。
A.bdgcefhaB.gdbecfhaC.bdgechfaD.gdbehfca3.在设备管理中，缓冲技术主要用于（）。
A.解决主机和设备之间的速度差异B.提高设备利用率C.提供内存与外存之间的接口D.扩充相对地址空间4. 有关系S(S#,SNAME,SEX）,C(C#,CNAME）,SC(S#,C#）。
其中S#为学生号,SNAME为学生姓名,SEX为性别,C#为课程号,CNAME为课程名。
要查询选修"计算机"课的全体女学生姓名的SQL语句是"SELECT SNAME FROM S,C,SC WHERE"子句。
这里WHERE子句的内容是A.S S#=SC S# AND SEX=′女′ AND CNAME=′计算机′B.S S#=SC S# AND C C#=SC C# AND CNAME=′计算机′C.SEX=′女′ AND CNAME=′计算机′D.S S#=SC S# AND C C#=SC C# AND SEX=′女′ AND CNAME=′计算机′5. 设关系模式R(A，B，C)，F是R上成立的FD集，F={B→C)，则分解P={AB,BC}相对于F( )A.是无损联接，也是保持FD的分解B.是无损联接，但不保持FD的分解C.不是无损联接，但保持FD的分解D.既不是无损联接、也不保持FD的分解6. 在完全二叉树中除最下面一层外，每一层结点个数是上一层结点个数的A.1倍B.2倍C.3倍D.n倍7. 用高级语言编写的程序A.只能在某种计算机上运行B.无需经过编译或解释，即可被计算机直接执行C.具有通用性和可移植性D.几乎不占用内存空间8. 下面关于线性表的叙述中，错误的是A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用链接存储，不必占用一片连续的存储单元C.线性表采用顺序存储，便于进行插入和删除操作D.线性表采用链接存储，便于插入和删除操作9. 数据库设计的需求阶段主要设计A.程序流程图B.程序结构图C.框图D.数据流程图10. 在关系代数中，从两个关系的笛卡尔积中选取它们属性间满足一定条件的元组的操作，称为A.并B.选择C.自然连接D.θ连接二、填空题(10题)11.在X.800中将安全攻击分为两类：被动攻击和___________。
1、在一棵二叉树上第5层的结点数最多是(B) 注：由公式2（k-1）得A. 8B. 16C. 32D. 152、对建立良好的程序设计风格，下面描述正确的是(A)A. 程序应简单、清晰、可读性好B. 符号名的命名要符合语法C. 充分考虑程序的执行效率D. 程序的注释可有可无3、数据库系统的核心是(B)A. 数据模型B. 数据库管理系统C. 软件工具D. 数据库4、按条件f对关系R进行选择，其关系代数表达式为(C)A. R|X|RB. R|X|RfC. бf(R)D. ∏f(R)5、数据库系统的核心是(B)A. 数据模型B. 数据库管理系统C. 软件工具D. 数据库6、在一棵二叉树上第5层的结点数最多是(B) 注：由公式2（k-1）得A. 8B. 16C. 32D. 157、以下数据结构中不属于线性数据结构的是(C)A. 队列B. 线性表C. 二叉树D. 栈8、下列工具中属于需求分析常用工具的是(D)A. PADB. PFDC. N-SD. DFD9、下列工具中属于需求分析常用工具的是(D)A. PADB. PFDC. N-SD. DFD10、设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为(B) 注：利用公式n=n0+n1+n2、n0=n2+1和完全二叉数的特点可求出A. 349B. 350C. 255D. 35111、希尔排序法属于哪一种类型的排序法(B)A.交换类排序法B.插入类排序法C.选择类排序法D.建堆排序法12、希尔排序法属于哪一种类型的排序法(B)A.交换类排序法B.插入类排序法C.选择类排序法D.建堆排序法13、下列工具中属于需求分析常用工具的是(D)A. PADB. PFDC. N-SD. DFD14、在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送(D)A. 调用语句B. 命令C. 口令D. 消息15、数据库概念设计的过程中，视图设计一般有三种设计次序，以下各项中不对的是(D)A. 自顶向下B. 由底向上C. 由内向外D. 由整体到局部16、软件需求分析阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书以及(B)A. 阶段性报告B. 需求评审C. 总结D. 都不正确17、在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。
2010年(下)全国信息技术水平考试数据库应用系统设计技术水平证书（SQL Server）试卷答案三．设计题（共60分）评分说明：有些查询要求的实现方式有多种，因此如果考生所给答案和参考答案不一致，应根据考生答案实际情况判断其正确与否。
1.（6分）评分准则：创建每个表及主键1分，共3分；插入每个表的数据1分，共3分。
create table book(bno char(4) primary key,bname char(20),author char(10),publish char(20),pubdate datetime);create table reader(rno char(4) primary key,rname char(10));create table borrow(borrowno int primary key,bno char(4),rno char(4),borrowdate datetime);insert into book values('0001','数据库原理','李明','出版社A','2008-10-01');insert into book values('0002','软件工程','张永','出版社B','2008-08-09');insert into book values('0003','操作系统','赵明哲','出版社A','2009-03-06');insert into book values('0004','数据结构','张辉','出版社C','2009-05-28');insert into reader values('0001','李莎');insert into reader values('0002','陈世杰');insert into reader values('0003','吴忠');insert into borrow values(1,'0001','0001','2010-03-15');insert into borrow values(2,'0002','0001','2010-03-20');insert into borrow values(3,'0002','0002','2010-03-30');insert into borrow values(4,'0003','0002','2010-04-05');insert into borrow values(5,'0003','0001','2010-04-12');insert into borrow values(6,'0004','0001','2010-04-21');2.（3分）评分准则：创建了1个外键给2分；创建了两个外键给3分。
2010年四川省公务员考试（行政职业能力测验）真题试卷(题后含答案及解析)题型有：1. 数字推理 2. 数学运算 3. 图形推理 4. 定义判断 5. 类比推理6. 逻辑判断7. 言语理解与表达8. 资料分析9. 常识判断数字推理给你一个数列，但其中缺少一项，要求你仔细观察数列的排列规律，然后从四个供选择的选项中选择你认为最合理的一项，来填补空缺项，使之符合原数列的排列规律。
1．0，0，6，24，60，120，( )A．180B．196C．210D．216正确答案：C解析：本题为立方修正数列，0=03-0，0=13-1，6=23-2，24=33-3，60=43-4，120=53-5，(210=63-6)，所以选择C选项。
2．2，3，7，45，2017，( )A．4068271B．4068273C．4068275D．4068277正确答案：B解析：本题为平方递推数列，3=22-1，7=32-2，45=72-4，2017=452-8，(4068273=20172-16)，最后计算直接用尾数判断即可，所以选择B选项。
3．2，2，3，4，9，32，( )A．129B．215C．257D．283正确答案：D解析：本题为递推数列。
2×2-1=3，2×3-2=4，3×4-3=9，4×9-4=32，9×32-5=(283)。
所以选择D选项。
4．0，4，16，48，128，( )A．280B．320C．350D．420正确答案：B解析：本题为递推数列，与2010年国考题第一个数字推理题规律相同。
从第三项开始，递推式为an+2=(an+1-an)×4。
或者用乘法拆分，分别为：2×0，4×1，8×2，16×3，32×4，下一项为64×5=320。
故选B。
5．0．5，1，2，5，17，107，( )A．1947B．1945C．1943D．1941正确答案：C解析：本题为递推数列，递推式为an-1×(an+1)+an=an+2，n≥1。
四川省对⼝⾼考信息⼀类《计算机⽂化基础》综合试卷（带答案）四川省对⼝⾼考信息⼀类《计算机⽂化基础》综合试卷（win7+office2010）考试时间：90分钟满分：100⼀、单项选择(1分/题，共30⼩题30分，)1.计算机中最重要的核⼼部件是( )。
A、CPUB、DRAMC、CD-ROMD、CRT2. 把硬盘上的数据传送到计算机的内存中去，称为( )。
A、输出B、打印C、写盘D、读盘3. 存储容量1GB等于( )。
A、1000BB、1024KBC、1024MBD、1000MB4. 打印机的种类有点阵式打印机、喷墨打印机及( )。
A、光电打印机B、⾮击打式打印机C、击打式打印机D、激光打印机5. 冯·诺依曼结构计算机包括输⼊设备、输出设备、存储器、控制器、( )5⼤组成部分。
A、处理器B、运算器C、显⽰器D、模拟器6. 根据所传递的内容不同，可将系统总线分为3类：数据总线、地址总线和( )。
A、系统总线D、I／0总线7. 计算机保存⼀个汉字通常占⽤的存储空间为( )。
A、1BB、2BC、1bD、2b8. “剪贴板”是( )的⼀块区域。
A、内存上B、软盘上C、硬盘上D、CPU中9. Windows 7是⼀种( )。
A、诊断程序B、系统软件C、⼯具软件D、应⽤软件10. Windows中，在不同的应⽤程序之间切换的快捷键是( )。
A、Ctrl+TabB、Alt+TabC、Shift+TabD、Ctrl+Break11. 操作系统的主要功能是( )。
A、实现软、硬件转换B、管理系统的所有软、硬件资源C、把源程序转换为⽬标程序D、进⾏数据处理12、计算机系统启动的加电顺序应是（）。
A、先开主机，后开外部设备B、先开外部设备，后开主机C、先开主机，后开显⽰器D、任意先开那⼀部分都可以13、⼗进制数127转换为⼋进制数是（）。
A、207B、17714、⼋进制数75转换为⼗进制是（）。
A、57B、61C、66D、7015、如果⼀计算机的字长是32位，则该计算机的⼀个字是（）字节。
（2023年）四川省德阳市全国计算机等级考试数据库技术真题(含答案) 学校:________ 班级:________ 姓名:________ 考号:________一、1.选择题(10题)1. SQL语言集数据定义功能、数据操纵功能和数据控制功能于一体。
在如下所列语句中，哪一个是属于数据控制功能的?A.GRANTB.CREA TEC.INSERTD.SELECT2. 下面所列各项，哪些属于数据库技术的研究领域? ( )①数据库管理系统软件的研究②数据库设计③数据库管理④操作系统A.①和②B.①和③C.①、②和③D.全部3. 文件系统采用多级目录结构的好处是______。
A.可以进行多道程序设计B.提高内存利用率C.不同用户可以给不同文件取相同名字D.文件可以共享4. 设有一个关系：DEPT(DNO，DNAME)，如果要找出倒数第3个字母为W，并且至少包含4个字母的DNAME，则查询条件子句应写成WHERE DNAME LIKEA.'W %'B.'_% W_ _'C.'W'D.'W %'5. 一个进程执行V操作意味着A.该进程从等待队列进入就绪队列B.该进程从磁盘调入内存C.可能有另一个进程从等待队列进入就绪队列D.可能有另一个进程从磁盘调入内存6. 目前Internet还没有提供的服务是A.电子邮件B.远程登录C.信息检索D.电视广播7.在下列性质中，()不是分时系统的特征。
A.交互性B.多路性C.成批性D.独占性8. 在中断处理中，输入输出中断是指A.设备出错B.数据传输结束C.设备出错和数据传输结束D.都不是9.数据库系统的核心是__。
( )A.编译系统B.数据库C.操作系统D.数据库管理系统10. 数据流图和数据字典这两个工具共同完成对需求分析调查结果的描述。
以下哪一项不是数据字典中的项目?A.数据项说明、数据结构说明B.数据流说明、数据存储说明C.处理过程说明D.数据完整性说明二、填空题(10题)11. 现有关键码值分别为10、20、30、40的4个结点，按所有可能的插入顺序构造二叉排序树，能构造______不同的二叉排序树。
【2023年】四川省雅安市全国计算机等级考试数据库技术测试卷(含答案) 学校:________ 班级:________ 姓名:________ 考号:________一、1.选择题(10题)1.下列SQL语句中，修改表结构的是( )。
A.ALTERB.CREATEC.UPDATED.INSERT、2. S-Designer是一种可视化的数据库设计工具，它的后续版本是Power-Designer，使用它可以完成如下的哪些功能? ( )。
A.Ⅰ，Ⅰ和ⅠB.Ⅰ，Ⅰ和ⅠC.Ⅰ，Ⅰ和ⅠD.都可以3. 对包含n个元素的散列表进行检索，平均检索长度为A.为O(log2n)B.为O(n)C.为O(n*log2n)D.不直接依赖于n4. SQL语言集数据定义功能、数据操纵功能和数据控制功能于一体。
如下所列语句中，哪一个是属于数据控制功能的?A.GRANTB.CREA TEC.INSERTD.SELECT5. 在以下各条叙述中，正确的叙述有几条( )。
(1)数据库避免了一切数据重复(2)数据库减少了数据冗余(3)数据库中，如果模式改变、则需将与其有关的子模式做相应改变，否则用户程序需改写(4)数据库中的存储模式如有改变，模式可以不变A.1B.2C.3D.46. 下面不属于数据管理技术发展过程中人工管理阶段的特点的是A.数据不保存B.数据不共享C.数据无专门软件进行管理D.数据具有独立性7. 数据库管理系统由三级模式组成，其中决定DBMS功能的是______。
A.逻辑模式B.外模式C.内模式D.物理模式8.在关系模式R(A,B,C,D) 中，有函数依赖F={B→C，C→D，D→A}存在，则R能达到______范式。
A.1NFB.2NFC.3NFD.BCNF9. 在关系数据库中，允许______。
A.不同属性来自同一个域B.同一个关系中两个元组相同C.同一列的数据类型不同D.属性可以进一步分解10. 对一组记录的关键码(25，38，48，52，63，74)采用二分法查找52时，第几次查找成功?A.4B.3C.2D.1二、填空题(10题)11. 在SQL语言中，为了修改基本表的结构，可以使用的语句是______。
【2023年】四川省乐山市全国计算机等级考试数据库技术真题(含答案) 学校:________ 班级:________ 姓名:________ 考号:________一、1.选择题(10题)1.数据独立性是指（）。
A.数据依赖于程序B.数据库系统C.数据库管理系统D.数据不依赖于程序2. 数据库系统的三级模式结构是指______。
A.外模式、模式、子模式B.子模式、模式、概念模式C.模式、内模式、存储模式D.外模式、模式、内模式3. 栈结构不适用于下列________应用。
A.表达式求值B.冒泡排序法的实现C.二叉树对称序周游算法的实现D.快速排序算法的实现4. 数据库系统的三级模式结构是指( )。
A.外模式、模式、子模型B.子模型、模式、概念模式C.模式、内模式、存储模式D.外模式、模式、内模式5. 对于IP地址为218.194.43.107的主机来说，其网络号为( )。
A.218.194B.218.194.43.107C.218.194.43.0D.1076. 以下关于B树运算的叙述中，哪一条是正确的?A.若插入过程中根结点发生分裂，则B树的高度加1B.每当进行插入运算，就在B树的最下面一层增加一个新结点C.若要删除的关键码出现在根结点中，则不能真正删除，只能做标记D.删除可能引起B树结点个数减少，但不会造成B树高度减少7. 所谓概念模型，指的是A.客观存在的事物及其相互联系B.将信息世界中的信息进行数据化C.实现模型在计算机中的数据化表示D.现实世界到机器世界的一个中间层次，即信息世界8. 在对数据库的系统故障进行恢复时，需要对日志文件进行________。
A.反向扫描B.正向扫描C.双向扫描D.随机扫描9. 在中断处理中，输入输出中断是指A.设备出错B.数据传输结束C.设备出错和数据传输结束D.都不是10. DDBS的“局部映像透明性”位于A.全局外模式与全局概念模式之间B.全局概念模式与分片模式之间C.分片模式与分布模式之间D.分布模式与局部概念模式之间二、填空题(10题)11.IP电话系统有4个基本组件：终端设备、___________、多点控制单元和网守。
1、有一种简单的排序算法，叫做计数排序（count sorting）。
这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。
必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。
(1) (3分)给出适用于计数排序的数据表定义;(2) (7分)使用Pascal或C语言编写实现计数排序的算法；(3) (4分)对于有n个记录的表，关键码比较次数是多少?(4) (3分)与简单选择排序相比较，这种方法是否更好?为什么?2、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。
20分void Hospital(AdjMatrix w,int n)//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。
{for (k=1;k<=n;k++) //求任意两顶点间的最短路径for (i=1;i<=n;i++)for (j=1;j<=n;j++)if (w[i][k]+w[k][j]<w[i][j]) w[i][j]=w[i][k]+w[k][j];m=MAXINT; //设定m为机器内最大整数。
for (i=1;i<=n;i++) //求最长路径中最短的一条。
{s=0;for (j=1;j<=n;j++) //求从某村庄i（1<=i<=n）到其它村庄的最长路径。
if (w[i][j]>s) s=w[i][j];if (s<=m) {m=s; k=i;}//在最长路径中，取最短的一条。
《四川省达州市中职计算机应用试卷（数据库维护）》一、单项选择题（每题3分，共30分）1.数据库系统的核心是（）。
A.数据库B.数据库管理系统C.数据模型D.数据库管理员2.在关系型数据库中，一行数据被称为（）。
A.字段B.记录C.表D.数据库3.以下哪种数据类型通常用于存储文本信息且有长度限制，如存储姓名、地址等（）。
A.INTB.VARCHARC.FLOATD.DATE4.用于从数据库表中选取满足特定条件数据的语句是（）。
A.INSERTB.UPDATEC.DELETED.SELECT5.在数据库维护中，为了防止数据丢失，经常需要进行（）操作。
A.数据备份B.数据还原C.数据删除D.数据修改6.数据库索引的主要作用是（）。
A.增加数据存储量B.提高数据查询速度C.改变数据结构D.降低数据安全性7.以下哪个是常见的数据库管理系统（）。
A.PhotoshopB.OracleC.ExcelD.Premiere8.如果要在数据库表中添加一列新的数据，通常会使用（）语句。
A.ALTER TABLE ADDB.INSERT INTOC.UPDATE SETD.DELETE FROM9.关系数据库中，表与表之间通过（）来建立联系。
A.字段B.记录C.主键和外键D.索引10.在数据库中，用来确保数据完整性的机制不包括（）。
A.约束条件B.数据备份C.触发器D.参照完整性规则二、填空题（每题3分，共30分）1.数据库的三级模式结构包括外模式、模式和________。
2.数据在数据库中是以________的形式存储的。
3.在SQL语言中，用于创建数据库表的语句是________。
4.数据库维护工作主要包括数据备份、数据还原、________等方面。
5.为了保证数据库的安全性，通常会设置用户________和权限。
6.当对数据库表进行更新操作时，如修改某条记录的值，常用的语句是________。
7.数据库的完整性包括实体完整性、参照完整性和________完整性。
1、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置（下标）。
用j 记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，若局部平台长度（i-j）大于l时，则修改最长平台的长度k（l=i-j）和其在b中的起始位置（k=j），直到b数组结束，l即为所求。
void Platform (int b[ ], int N)//求具有N个元素的整型数组b中最长平台的长度。
{l=1;k=0;j=0;i=0;while(i<n-1){while(i<n-1 && b[i]==b[i+1]) i++;if(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台i++; j=i; } //新平台起点printf(“最长平台长度%d，在b数组中起始下标为%d”，l，k)；}// Platform2、将顶点放在两个集合V1和V2。
对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。
为此，用整数1和2表示两个集合。
再用一队列结构存放图中访问的顶点。
int BPGraph (AdjMatrix g)//判断以邻接矩阵表示的图g是否是二部图。
{int s[]; //顶点向量，元素值表示其属于那个集合（值1和2表示两个集合）int Q[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。
int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited[]是访问数组for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化，各顶点未确定属于那个集合Q[1]=1; r=1; s[1]=1;//顶点1放入集合S1while(f<r){v=Q[++f]; if (s[v]==1) jh=2; else jh=1;//准备v的邻接点的集合号if (!visited[v]){visited[v]=1; //确保对每一个顶点，都要检查与其邻接点不应在一个集合中for (j=1,j<=n;j++)if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;} //邻接点入队列else if (s[j]==s[v]) return(0);} //非二部图}//if (!visited[v])}//whilereturn(1); }//是二部图[算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。
3、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。
int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数{if(bt==null || k<1) return(0);BiTree p=bt,Q[]; //Q是队列，元素是二叉树结点指针,容量足够大int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针，level 是二叉树的层数while(front<=rear){p=Q[++front];if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点if(p->lchild) Q[++rear]=p->lchild; //左子女入队if(p->rchild) Q[++rear]=p->rchild; //右子女入队if(front==last) {level++; //二叉树同层最右结点已处理,层数增1last=rear; } //last移到指向下层最右一元素if(level>k) return (leaf); //层数大于k 后退出运行}//while }//结束LeafKLevel4、假设K1，…，Kn是n个关键词，试解答：试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn 时，用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。
5、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。
所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。
void Translation（float *matrix，int n）//本算法对n×n的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。
{int i,j,k,l；float sum，min； //sum暂存各行元素之和float *p, *pi, *pk;for(i=0; i<n; i++){sum=0.0; pk=matrix+i*n; //pk指向矩阵各行第1个元素.for (j=0; j<n; j++){sum+=*(pk); pk++;} //求一行元素之和.*(p+i)=sum; //将一行元素之和存入一维数组.}//for ifor(i=0; i<n-1; i++) //用选择法对数组p进行排序{min=*(p+i); k=i; //初始设第i行元素之和最小.for(j=i+1;j<n;j++) if(p[j]<min) {k=j; min=p[j];} //记新的最小值及行号.if(i!=k) //若最小行不是当前行,要进行交换(行元素及行元素之和){pk=matrix+n*k; //pk指向第k行第1个元素.pi=matrix+n*i; //pi指向第i行第1个元素.for(j=0;j<n;j++) //交换两行中对应元素.{sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;}sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和.}//if}//for ifree(p); //释放p数组.}// Translation[算法分析] 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n2).6、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。
void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度{BiTree p=bt,l[],s[]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点int i，top=0,tag[],longest=0;while(p || top>0){ while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下if(tag[top]==1) //当前结点的右分枝已遍历{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}//保留当前最长路径到l栈，记住最高栈顶指针，退栈}else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下}//while(p!=null||top>0)}//结束LongestPath7、4、void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2{p=L->next;q=p->next;s=q->next;p->next=NULL;while(s->next){q->next=p;p=q;q=s;s=s->next; //把L的元素逐个插入新表表头}q->next=p;s->next=q;L->next=s;}//LinkList_reverse8、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。
void union(int A[],B[],C[],m,n)//整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。
{i=0; j=n-1; k=0;// i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始while(i<m && j>=0)if(a[i]<b[j]) c[k++]=a[i++] else c[k++]=b[j--];while(i<m) c[k++]=a[i++];while(j>=0) c[k++]=b[j--];}算法结束4、要求二叉树按二叉链表形式存储。
15分（1）写一个建立二叉树的算法。
（2）写一个判别给定的二叉树是否是完全二叉树的算法。
BiTree Creat() //建立二叉树的二叉链表形式的存储结构{ElemType x；BiTree bt;scanf(“%d”,&x); //本题假定结点数据域为整型if(x==0) bt=null;else if(x>0){bt=(BiNode *)malloc(sizeof(BiNode));bt->data=x; bt->lchild=creat(); bt->rchild=creat();}else error(“输入错误”)；return(bt);}//结束 BiTreeint JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0{int tag=0; BiTree p=bt, Q[]; // Q是队列，元素是二叉树结点指针，容量足够大if(p==null) return (1);QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队while (!QueueEmpty(Q)){p=QueueOut(Q); //出队if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队else {if (p->lchild) return 0; //前边已有结点为空，本结点不空else tag=1; //首次出现结点为空if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队else if (p->rchild) return 0; else tag=1;} //whilereturn 1; } //JudgeComplete9、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}写出G的拓扑排序的结果。
