



下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第第页2022年安徽省数据库入门大纲2022年安徽省数据库入门大纲
1、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到帮助向量d[1..n]前半部和后半部〔注:向量d可视为循环表〕,其原那么为,先将r[l]赋给d[1],再从r[2]记录开始分二路插入。编写实现二路插入排序算法。
2、设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求计算出查找关键字62时的比较次数并计算出查找胜利时的平均查找长度。
3、设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求计算出查找关键字62时的比较次数并计算出查找胜利时的平均查找长度。
4、在有向图G中,假如r到G中的每个结点都有路径可达,那么称结点r为G的根结点。编写一个算法完成以下功能:
〔1〕.建立有向图G的邻接表存储结构;
〔2〕.判断有向图G是否有根,假设有,那么打印出全部根结点的值。
5、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。
当n=1时,只有一个根结点,由中序序列和后序序列可以确定这棵二叉树。
设当n=m-1时结论成立,现证明当n=m时结论成立。
设中序序列为S1,S2,,Sm,后序序列是P1,P2,,Pm。因后序序列最末一个元素Pm是根,那么在中序序列中可找到与Pm相等的结点〔设二叉树中各结点互不相同〕Si(1≤i≤m),因中序序列是由中序遍历而得,所以Si是根结点,S1,S2,,Si-1是左子树的中序序列,而Si+1,Si+2,,Sm是右子树的中序序列。
假设i=1,那么S1是根,这时二叉树的左子树为空,右子树的结点数是m-1,那么{S2,S3,,Sm}和{P1,P2,,Pm-1}可以唯一确定右子树,从而也确定了二叉树。
假设i=m,那么Sm是根,这时二叉树的右子树为空,左子树的结点数是m-1,那么{S1,S2,,Sm-1}和{P1,P2,,Pm-1}唯一确定左子树,从而也确定了二叉树。
最末,当1im时,Si把中序序列分成{S1,S2,,Si-1}和{Si+1,Si+2,,Sm}。由于后序遍历是“左子树—右子树—根结点”,所以{P1,P2,,Pi-1}和{Pi,Pi+1,Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1,S2,,Si-1}和{P1,P2,,Pi-1}可唯一确定二叉树的左子树,由{Si+1,Si+2,,Sm}和
{Pi,Pi+1,,Pm-1}可唯一确定二叉树的右子树。
6、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否那么称为非法序列。〔15分〕
〔1〕A和D是合法序列,B和C是非法序列。
〔2〕设被判定的操作序列已存入一维数组A中。
intJudge(charA[])
//判断字符数组A中的输入输出序列是否是合法序列。如是,返回true,否那么返回false。
{i=0;//i为下标。
j=k=0;//j和k分别为I和字母O的的个数。
while(A[i]!=‘\0’)//当未到字符数组尾就作。
{switch(A[i])
{case‘I’:j++;break;//入栈次数增1。
case‘O’:k++;if(kj){printf(“序列非法\n”);e*it(0);}}
2022年安徽省数据库入门大纲
i++;//不论A[i]是‘I’或‘O’,指针i均后移。}
if(j!=k){printf(“序列非法\n”);return(false);}
else{printf(“序列合法\n”);return(true);}
}//算法结束。
7、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7}E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 大宗物品集中采购配送服务合同
- 屋顶飞檐建筑施工方案
- 企业数字化转型与人才发展作业指导书
- 地铁板道床施工方案
- 健康行业营养健康状况调研表
- 荒山造林施工方案
- 包钢加固施工方案
- 天棚装饰施工方案
- 钢管拱施工方案
- 静力压桩施工方案
- 常用数学公式大全
- 护理不良事件相关知识考核试题及答案
- 母乳喂养课件(共68张课件)课件
- 循环流化床锅炉改机械炉排炉项目可行性研究报告模板-立项备案
- 正常分娩过程与护理
- 脓毒血症患者的护理查房
- 2024商品房买卖合同范本下载
- 广东省广州仲元中学2025年高三下学期入学考试试化学试题文试卷含解析
- 第2章-装配式建筑标准化设计
- 医疗器械公司组织机构图以及部门设置和岗位职责说明
- 卫生部病历管理规定
评论
0/150
提交评论