2012年江苏省分析数据深入
更新时间:2024-05-18 07:04:01 阅读量: 综合文库 文档下载
- 江苏省地域分析推荐度:
- 相关推荐
1、请设计一个算法,要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表,表头指针为head。二叉树按二叉链表方式存储,链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。 2、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={
G拓扑排序的结果是:V1、V2、V4、V3、V5、V6、V7
3、设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。 4、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归算法,栈中存放二叉树结点的指针,当访问到某结点时,栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性,设p在q的左边。后序遍历必然先遍历到结点p,栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时,将栈中元素从栈顶开始逐个到辅助栈中去匹配,第一个匹配(即相等)的元素就是结点p 和q的最近公共祖先。
typedef struct
{BiTree t;int tag;//tag=0 表示结点的左子女已被访问,tag=1表示结点的右子女已被访问 }stack;
stack s[],s1[];//栈,容量够大
BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。 {top=0; bt=ROOT; while(bt!=null ||top>0)
{while(bt!=null && bt!=p && bt!=q) //结点入栈 {s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下
if(bt==p) //不失一般性,假定p在q的左侧,遇结点p时,栈中元素均为p的祖先结点 {for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈s的元素转入辅助栈s1 保存 if(bt==q) //找到q 结点。
for(i=top;i>0;i--)//;将栈中元素的树结点到s1去匹配 {pp=s[i].t;
for (j=top1;j>0;j--)
if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”);return (pp);} }
while(top!=0 && s[top].tag==1) top--; //退栈
if (top!=0){s[top].tag=1;bt=s[top].t->rchild;} //沿右分枝向下遍历 }//结束while(bt!=null ||top>0) return(null);//q、p无公共祖先 }//结束Ancestor 5、根据二叉排序树中序遍历所得结点值为增序的性质,在遍历中将当前遍历结点与其前驱结点值比较,即可得出结论,为此设全局指针变量pre(初值为null)和全局变量flag,初值为true。若非二叉排序树,则置flag为false。
#define true 1 #define false 0 typedef struct node
{datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST(BTree t,int flag)
// 判断二叉树是否是二叉排序树,本算法结束后,在调用程序中由flag得出结论。 { if(t!=null && flag)
{ Judgebst(t->llink,flag);// 中序遍历左子树
if(pre==null)pre=t;// 中序遍历的第一个结点不必判断
else if(pre->data
6、数组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
if(a[i]=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); }//结束 BiTree
int 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; } //while
return 1; } //JudgeComplete
7、设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C用链式存储结构表示。
typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) {
lklist *p,*q,*t;
for(p=ha,hc=0;p!=0;p=p->next)
{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;
if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } }
正在阅读:
2012年江苏省分析数据深入05-18
新人教版七年级下册英语重点短语与重点句型收录Unit 1-1209-09
品牌培育建功立业征文03-29
川大《法理学1015》15秋在线作业1 100分答案01-06
《病理学》期中考试卷06-12
龙书 第四章课后作业答案12-06
单招计算机理论第四次月考试卷06-14
“好书伴我成长”演讲比赛方案01-10
党员思想作风整顿心得体会通用范文8篇08-04
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 江苏省
- 深入
- 分析
- 数据
- 2012
- 一上生字卡片 带拼音组词
- 2018届湖南省浏阳一中高三下学期调研考试生物试题及答案
- 八年级英语上第5单元第3课时学案
- 基于ANSYS WORKBENCH的通电导线的热分析
- 苏教版小学三年级下册体育教案
- 我院小儿血液细菌培养及药敏分析
- 财务管理论述题
- 小儿常见肛肠疾病护理常规
- 四川省包虫病流行情况调查报告
- 四川省塔山中学高中生物课时学案:4.2《基因对性状的控制》(新人
- 2018年四川省成都市中考语文试题及参考答案(word解析版)
- 陕西施工技术资料整编目录
- 舍生取义的事例
- 2017年出口收汇核销网上报审服务系统操作指南(word版)
- 北京市人防工程信息统计表
- 井上下轨道运输管理规定
- 全国导游基础知识_教案
- 台州市区饮用水水源地环境保护规划最终版 - 图文
- 2017年西电电院数字信号处理上机实验报告三
- 毕业设计说明书-手机后壳注射模设计