下载文档原格式
试题一一、单项选择题（本大题共20小题，每小题2分，共40分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均无分.1. 数据库系统的核心是( B ）A．数据库B．数据库管理系统C．数据模型D．软件工具2。
下列四项中，不属于数据库系统的特点的是（C ）A．数据结构化B．数据由DBMS统一管理和控制C．数据冗余度大D．数据独立性高3.概念模型是现实世界的第一层抽象，这一类模型中最著名的模型是（ D ）A．层次模型B．关系模型C．网状模型D．实体—联系模型4。
数据的物理独立性是指（ C ）A．数据库与数据库管理系统相互独立B．用户程序与数据库管理系统相互独立C．用户的应用程序与存储在磁盘上数据库中的数据是相互独立的D．应用程序与数据库中数据的逻辑结构是相互独立的5．要保证数据库的逻辑数据独立性，需要修改的是（ A )A．模式与外模式之间的映象B．模式与内模式之间的映象C．模式D．三级模式6．关系数据模型的基本数据结构是（D ）A．树B．图C．索引D．关系7．有一名为“列车运营"实体，含有:车次、日期、实际发车时间、实际抵达时间、情况摘要等属性，该实体主码是( C ）A．车次B．日期C．车次+日期D．车次+情况摘要8.己知关系R和S,R∩S等价于（ B ）A。
（R—S）-S B. S-（S—R)C。
(S-R)-R D。
S—（R—S)9．学校数据库中有学生和宿舍两个关系：学生（学号，姓名)和宿舍(楼名,房间号，床位号，学号)假设有的学生不住宿，床位也可能空闲。
如果要列出所有学生住宿和宿舍分配的情况,包括没有住宿的学生和空闲的床位,则应执行（ A )A。
全外联接B. 左外联接C. 右外联接D。
自然联接10．用下面的T-SQL语句建立一个基本表:CREATE TABLE Student（Sno CHAR（4）PRIMARY KEY,Sname CHAR（8) NOT NULL,Sex CHAR（2）,Age INT)可以插入到表中的元组是（ D ）A。
（2023年）贵州省贵阳市全国计算机等级考试数据库技术真题(含答案) 学校:________ 班级:________ 姓名:________ 考号:________一、1.选择题(10题)1.计算机系统中判别是否有中断事件发生应是在( )A.进程切换时B.执行完一条指令后C.执行P操作后D.由用户态转入核心态时2. SQL语言中的“视图(View)”对应于数据库三级模式结构中的( )。
A.外模式B.模式C.内模式D.概念模式3. 对n个记录的文件进行起泡排序，所需要的输助存储空间为( )。
A.O(1)B.O(1og2n)C.O(n)D.O(n2)4. 关于UNIX的用户标识，下列哪一项是不正确的?A.一为实际的UID，一为有效的SUIDB.UID与SUID可能不同C.SUID与UID更能反映用户的真实身份D.SUID表示用户临时具有执行某个程序的权力5. 计算机网络的主要目的是( )。
A.聊天，浏览网页等B.硬件，软件数据等资源共享C.进行分布式处D.实现不同计算机相互通信6. 设散列函数为H(k)=k mod 7，现欲将关键码23，14，9，6，30，12，18依次散列于地址0～6中，用线性探测法解决冲突，则在地址空间0～6中，得到的散列表是A.14，6，23，9，18，30，12B.14，18，23，9，30，12，6C.14，12，9，23，30，18，6D.6，23，30，14，18，12，97. 在数据库逻辑设计中，当把E-R图转换为关系模式时，下列说法中正确的是( )。
A.一个实体类型转换为一个关系模式B.每一个联系类型都只能转换为一个独立的关系模式C.由联系类型转换成的关系模式的属性是与该联系类型相关的所有实体类型属性中的某一个D.由实体类型转换成的关系模式的码不是该实体类型的码8. 关于计算机语言，下面叙述不正确的是A.高级语言是独立于具体的机器系统的B.汇编语言对于不同类型的计算机，基本上不具备通用性和可移植性C.高级语言是先于低级语言诞生的D.一般来讲，与高级语言相比，机器语言程序执行的速度较快9. 在数据库设计中，用E-R图来描述信息结构，但不涉及信息在计算机中的表示，它是数据库设计中的哪个阶段?A.需求分析B.概念设计C.逻辑设计D.物理设计10. 信息的价值与信息的哪些性质密切相关? ( )①准确性②及时性③可靠性④开放性⑤完整性A.①、②、③和④B.②、③、④和⑤C.①、②、③和⑤D.①、②、④和⑤二、填空题(10题)11.RIP协议中表示距离的参数为___________。
1、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。
所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。
请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。
注：圈就是回路。
2、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。
假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。
#include <stdio.h>typedef char datatype;typedef struct node{datatype data;struct node * next;} listnode;typedef listnode* linklist;/*--------------------------------------------*//* 删除单链表中重复的结点 *//*--------------------------------------------*/linklist deletelist(linklist head){ listnode *p,*s,*q;p=head->next;while(p){s=p;q=p->next;while(q)if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{ s=q; /*找与P结点值相同的结点*/q=q->next;}p=p->next;}return head;}3、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。
4、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注:向量d可视为循环表），其原则为，先将r[l]赋给d[1]，再从r[2] 记录开始分二路插入。
（2021年）贵州省贵阳市全国计算机等级考试数据库技术测试卷(含答案) 学校:________ 班级:________ 姓名:________ 考号:________一、1.选择题(10题)1. 数据管理技术的发展是与计算机技术及其应用的发展联系在一起的，经历了由低级到高级的发展。
分布式数据库、面向对象数据库等新型数据库属于哪一个发展阶段?A.人工管理阶段B.文件系统阶段C.数据库系统阶段D.高级数据库技术阶段2. 操作系统中利用缓冲技术实现设备的I/O操作的主要目的是( )。
A.缓解处理机与设备之间速度不匹配的矛盾，减少对CPU的I/O中断次数B.使CPU可以从I/0操作中解脱出来，由缓冲区来实现相应操作C.由缓冲区中的一段程序来模拟I/O操作，使FO操作可与CPU对数据的处理同时进行D.为I/O专门开辟一段内存区，别的程序不能访问该地址空间，提高了I/O访存速度3. 设有字符序列(Q，H，C，Y，P，A，M，S，R，D，F，X)，问新序列(F，H，C，D，P，A，M，Q，R，S，Y，X)是下列哪一个排序算法的一趟扫描的结果A.起泡排序B.初始步长为4的希尔排序C.二路归并排序D.以第一元素为分析的快速排序4. 数据库管理系统能实现对数据库中数据的查询、插入、修枣和删除，这类功能称为( )。
A.数据定义功能B.数据管理功能C.数据操纵功能D.数据控制功能5. 关系数据库中用( )来表示实体之间的联系。
A.E-R图B.树结构C.三级模式D.二维表6. 设计作业调度算法时，不需要考虑下列哪一个因素?A.友好的用户界面B.均衡使用资源C.公平性D.吞吐量大7. 充分的Web支持是MS SQL SERVER 2000的主要功能之一，下列______ 不是其所支持的内容。
A.XML和Internet标准支持B.方便而安全地通过Web访问数据C.简化管理和优化D.安全的应用程序管理8. 下图给出一棵二叉树，按照前序法周游二叉树的节点序列是A.ABDEGCFHIB.DGEBHIFCAC.ADBGEFCIHD.ADGEBHIFC9. 在分布式数据库系统中，逻辑数据库被划分成若干片段，其中桉投影操作来分片的称为A.水平分片B.垂直分片C.导出分片D.选择分片10. 下列关于文件系统当前目录的描述中，哪个是不正确的?A.每个用户可以有一个当前目录B.引人当前目录可以加快检索速度C.查找文件时可以使用部分路径名D.当前目录不能随意改变二、填空题(10题)11. 虚拟存储管理的效率与程序局部性程度有很大关系，进程运行时，在一段时间内程序的执行呈现出高度的时间局部性和______。
2015年上半年数据库系统工程师考试上午真题（标准参考答案）单项选择题每题的四个选项中只有一个答案是正确的，请将正确的选项选择出来。
1机器字长为n位的二进制数可以用补码来表示（）个不同的有符号定点小数。
A．2nB．2n-1C．2n-1D．2n-1+12计算机中CPU对其访问速度最快的是（）。
A．内存B．CacheC．通用寄存器D．硬盘3Cache的地址映像方式中，发生块冲突次数最小的是（）。
A．全相联映像B．组相联映像C．直接映像D．无法确定的4计算机中CPU的中断响应时间指的是（）的时间。
A．从发出中断请求到中断处理结束B．从中断处理开始到中断处理结束C．CPU分析判断中断请求D．从发出中断请求到开始进入中断处理程序5总线宽度为32bit，时钟频率为200MHz，若总线上每5个时钟周期传送一个32bit的字，则该总线的带宽为（）MB/S。
A．40B．80C．160D．2006以下关于指令流水线性能度量的描述中，错误的是（）。
A．最大吞吐率取决于流水线中最慢一段所需的时间B．如果流水线出现断流，加速比会明显下降C．要使加速比和效率最大化应该对流水线各级采用相同的运行时间D．流水线采用异步控制会明显提高其性能7（）协议在终端设备与远程站点之间建立安全连接。
A．ARPB．TelnetC．SSHD．WEP8安全需求可划分为物理线路安全、网络安全、系统安全和应用安全。
下面的安全需求中属于系统安全的是（），属于应用安全的是（）。
A．机房安全B．入侵检测C．漏洞补丁管理D．数据库安全A．机房安全B．入侵检测C．漏洞补丁管理D．数据库安全9王某是某公司的软件设计师，每当软件开发完成后均按公司规定编写软件文档，并提交公司存档。
那么该软件文档的著作权（）享有。
A．应由公司B．应由公司和王某共同C．应由王某D．除署名权以外，著作权的其他权利由王某10甲、乙两公司的软件设计师分别完成了相同的计算机程序发明，甲公司先于乙公司完成，乙公司先于甲公司使用。
第一部分常识判断（共20题，参考时限10分钟）根据题目要求，在四个选项中选出一个最恰当的答案。
请开始答题：1. 党的十八届三中全会审议通过了《中共中央关于全面深化改革若干重大问题的决定》（以下简称《决定》），对全面深化改革做出了总体部署。
在未来一个阶段，《决定》对普通公民的生活可能带来的改变有（）。
①如果你要考大学，那么可能不必文理分科②如果你是“单独家庭”，那么可以生育二胎③如果你是农村户口，那么宅基地可以私有④如果你是劳动者，那么可以延迟退休A. ①②③B. ②③④C. ①②④D. ①②③④2. 目前我国正大力推进文化体制改革，特别是对国内的动漫产业和影视剧通过内容管控的方式促进其发展。
下列不属于行政手段的是（）。
A. 规定各级电视台每日播出境外各类影视节目时间B. 设立专项经费用于鼓励本土作家创作优秀剧本C. 国家出台“限娱令”规范娱乐节目播出类型D. 每年引进的境外动漫作品同类题材数量设置上限3. 中国古代小说塑造了很多莽汉形象，他们外表威猛如金刚，性格天真似儿童，深受读者的喜爱。
下列小说中莽汉的时代顺序排列正确的是（）。
①张飞②程咬金③李逵④牛皋A. ②①③④B. ②①④③C. ④②①③D. ①②③④4. 呼吸作用是生物体细胞把有机物氧化分解并产生能量的过程。
没有氧气参与的呼吸成为无氧呼吸。
无氧呼吸是指细胞在缺氧的条件下，通过酶的催化作用，把葡萄糖等有机物分解为尚未彻底氧化的产物。
下列现象与无氧呼吸有关的是（）。
A. 人剧烈运动后肌肉酸痛B. 用糯米和酒曲酿制米酒C. 农作物受涝时短时间内不会死亡D. 把生水果和熟苹果放在密闭的缸里催熟5. 在计算机网络通信领域中，防火墙是一项协助确保信息安全的设备，它会依照特定的规则，允许或是限制传输的数据通过。
小张在自己的电脑上安装了防火墙软件，下列论述正确的是（）。
A. 防火墙软件有可能导致小张的电脑不能访问特定的web网站B. 防火墙软件有可能导致小张无法访问自己电脑硬盘上存储的文档C. 防火墙软件使得小张在网络购物时，不容易被虚假广告所欺骗D. 防火墙软件使得小张在和陌生网友聊天时，可以伪装自己的性别和姓名6. 下列不属于心理学效应的是（）。
2015年贵州省信息技术学业水平考试模拟题第一套：第一卷必修部分评析一、单选题（题数：15道，共：60.0分，得分：0.0分）1、(必修)电视台播放新闻：因雨雪天气，贵州省内多条高速公路被封。
这条信息的来源属于（）。
A、人B、事物C、电子媒介D、纸质媒介2、(必修)下列方法中，不能获得数字化视频的是（）。
A、用智能手机拍摄B、用扫描仪扫描老照片C、录制电脑屏幕上的内容D、直接从网上下载3、(必修)下列选项中，属于信息的是（）。
A、U盘B、天气预报C、报纸D、平板电脑4、(必修)校园电视台的记者需要经常在外面采集图片、音频、视频等各种类型的素材。
下列采集设备中不需要的是（）。
A、数码摄像机B、录音笔C、扫描仪D、数码相机5、(必修)“知已知彼，百战不殆”的意思是说对敌我双方的情况都了解透彻，打起仗来就不会失败。
这说明信息具有（）。
A、可转换性B、时效性C、载体依附性D、价值性6、(必修)在Word里，通过（）工具栏能够设置文字的字体、字形、字号。
A、格式B、常用C、文字D、艺术字7、(必修)下列关于电子邮件的说法中，正确的是（）。
A、没有附件的邮件是不能发送的B、视频文件不能作为电子邮件的附件C、一封电子邮件只能发送一个附件D、一封电子邮件可以同时发送给多个收件人8、(必修)利用格式工厂软件将视频文件“元旦节目汇演.avi”转换成“元旦节目汇演.mpg”，文件发生改变的是（）。
A、视频文件的播放时间B、视频文件的声音大小C、视频文件的内容D、视频文件的格式9、(必修)在搜索引擎中，表示逻辑命令“与”的（）。
A、ORB、ANDC、NOTD、XOR10、(必修)下列关于表格信息加工的说法，正确的是( )。
A、MAX()函数可以进行求最小值的运算B、图表一旦创建就不能修改了C、B3表示第3行第2列处的单元格D、一个EXCEL工作簿只能有三张工作表11、(必修)小明经常在网络上下载图片、歌曲、电影，时间一长他的电脑中积累了大量的文件。
1、给定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;}//在最长路径中，取最短的一条。
m记最长路径，k记出发顶点的下标。
Printf(“医院应建在%d村庄，到医院距离为%d\n”,i,m);}//for}//算法结束对以上实例模拟的过程略。
各行中最大数依次是9，9，6，7，9，9。
这几个最大数中最小者为6，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。
1、对图1所示的连通网G，请用Prim算法构造其最小生成树（每选取一条边画一个图）。
2、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。
但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。
1、下列关于队列的叙述中正确的是(C)A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表2、数据库系统的核心是(B)A. 数据模型B. 数据库管理系统C. 软件工具D. 数据库3、结构化程序设计主要强调的是(B)A.程序的规模B.程序的易读性C.程序的执行效率D.程序的可移植性4、下述关于数据库系统的叙述中正确的是(A)A. 数据库系统减少了数据冗余B. 数据库系统避免了一切冗余C. 数据库系统中数据的一致性是指数据类型的一致D. 数据库系统比文件系统能管理更多的数据5、下列工具中属于需求分析常用工具的是(D)A. PADB. PFDC. N-SD. DFD6、数据库概念设计的过程中，视图设计一般有三种设计次序，以下各项中不对的是(D)A. 自顶向下B. 由底向上C. 由内向外D. 由整体到局部7、设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为(B) 注：利用公式n=n0+n1+n2、n0=n2+1和完全二叉数的特点可求出A. 349B. 350C. 255D. 3518、软件需求分析阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书以及(B)A. 阶段性报告B. 需求评审C. 总结D. 都不正确9、数据库系统的核心是(B)A. 数据模型B. 数据库管理系统C. 软件工具D. 数据库10、下列关于栈的叙述中正确的是(D)A. 在栈中只能插入数据B. 在栈中只能删除数据C. 栈是先进先出的线性表D. 栈是先进后出的线性表11、下面不属于软件设计原则的是(C)A. 抽象B. 模块化C. 自底向上D. 信息隐蔽12、下列叙述中正确的是(C)A.数据库是一个独立的系统，不需要操作系统的支持B.数据库设计是指设计数据库管理系统C.数据库技术的根本目标是要解决数据共享的问题D.数据库系统中，数据的物理结构必须与逻辑结构一致13、算法的空间复杂度是指(D)A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 算法执行过程中所需要的存储空间14、在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是(D)A. 概要设计B. 详细设计C. 可行性分析D. 需求分析15、下列叙述中正确的是(A)A. 线性表是线性结构B. 栈与队列是非线性结构C. 线性链表是非线性结构D. 二叉树是线性结构16、下述关于数据库系统的叙述中正确的是(A)A. 数据库系统减少了数据冗余B. 数据库系统避免了一切冗余C. 数据库系统中数据的一致性是指数据类型的一致D. 数据库系统比文件系统能管理更多的数据17、下列工具中属于需求分析常用工具的是(D)A. PADB. PFDC. N-SD. DFD18、软件需求分析阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书以及(B)A. 阶段性报告B. 需求评审C. 总结D. 都不正确。
1、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。
（注：图中不存在顶点到自己的弧）
有向图判断回路要比无向图复杂。
利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。
下面用0，1，2表示这三种状态。
前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。
对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。
void Print(int v,int start ) //输出从顶点start开始的回路。
{for(i=1;i<=n;i++)
if(g[v][i]!=0 && visited[i]==1 ) //若存在边（v,i），且顶点i的状态为1。
{printf(“%d”,v);
if(i==start) printf(“\n”); else Print(i,start);break;}//if
}//Print
void dfs(int v)
{visited[v]=1;
for(j=1;j<=n;j++ )
if (g[v][j]!=0) //存在边(v,j)
if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if
else {cycle=1; Print(j,j);}
visited[v]=2;
}//dfs
void find_cycle() //判断是否有回路，有则输出邻接矩阵。
visited数组为全局变量。
{for (i=1;i<=n;i++) visited[i]=0;
for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i);
}//find_cycle
2、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。
（注：双向起泡排序即相邻两趟排序向相反方向起泡）
3、本题应使用深度优先遍历，从主调函数进入dfs(v)时，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。
将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。
题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。
建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。
int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。
const n=用户定义的顶点数;
AdjList g ; //用邻接表作存储结构的有向图g。
void dfs(v)
{visited [v]=1; num++; //访问的顶点数＋1
if (num==n) {printf(“%d是有向图的根。
\n”,v); num=0;}//if
p=g[v].firstarc;
while (p)
{if (visied[p->adjvex]==0) dfs (p->adjvex);
p=p->next;} //while
visited[v]=0; num--; //恢复顶点v
}//dfs
void JudgeRoot()
//判断有向图是否有根，有根则输出之。
{static int i ;
for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。
{num=0; visited[1..n]=0; dfs(i); }
}// JudgeRoot
算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。
4、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。
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)
}//结束LongestPath
5、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。
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)
}//结束LongestPath
6、假设以I和O分别表示入栈和出栈操作。
栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
（15分）
（1）下面所示的序列中哪些是合法的？
A. IOIIOIOO
B. IOOIOIIO
C. IIIOIOIO
D. IIIOOIOO
（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。
若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
7、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。
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++; //二叉树同层最右结点已处理,层数增1
last=rear; } //last移到指向下层最右一元素
if(level>k) return (leaf); //层数大于k 后退出运行
}//while }//结束LeafKLevel。
