




已阅读5页,还剩1页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1. 设计一个非递归算法,从一棵二叉树中查找出所有结点的最大值并返回。答:int InorderTraverse(BiTree T, void (*visit)(TelemType e) int max=0; InitStack(S); p = T; while(p|!StackEmpty(S) if(p)Push(S,p); p =p-lchild; /向左下走到头 else Pop(S,p); visit(t-data); if(t-data)max) max=t-data; p = p-rchild; /向右走一步 /else / whilereturn max; 2. 设树采用定长结点的多重链表表示,设计算法实现树的按层次遍历。答:typedef struct CSTNode char data;struct CSTNode *childone,*childtwo,*childthree;CSTNode,*CSTree;void LevelOrderTraverse(CSTree T) CSTree p=T; SqQueue Q; if(!T) return; InitQueue(Q); EnQueue(Q,p); while(!QueueEmpty(Q) DeQueue(Q,p); printf(%c,p-data); if(p-childone) EnQueue(Q,p-childone); if(p-childtwo) EnQueue(Q,p-childtwo); if(p-childthree) EnQueue(Q,p-childthree); 3. 阅读下列算法,若有错,改正之。BiTree InSucc(BiTree q) / 已知q是指向中序线索二叉树上某个结点的指针, / 本函数返回指向*q的后继的指针。r = q-rchild;if (!r - rtag ) while (!r - rtag ) r = r-rchild; return r;答:共3处错误BiTree InSucc(BiTree q) / 已知q是指向中序线索二叉树上某个结点的指针, / 本函数返回指向*q的后继的指针。r = q-rchild;if (!r - rtag ) while (!r - ltag ) r = r-lchild; return r-lchild;4. 写出二叉树的先序遍历和后序遍历的非递归算法。答:先序遍历非递归算法void PreOrderTraverse(BiTree T)SqStack S;InitStack(S);BiTree *p=T;while (p!=NULL | !StackEmpty(S) while (p!=NULL) /遍历左子树 visit(T-data); Push(s,p); p=p-lchild; if (!StackEmpty(s) /通过下一次循环中的内嵌while实现右子树遍历 Pop(S,p); p=p-rchild; /endif /endwhile 后序遍历非递归算法typedef enum L,R tagtype;typedef struct BiTree ptr;tagtype tag;stacknode;typedef structstacknode Elemmaxsize;int top;SqStack;void PostOrderTraverse(BiTree T)SqStack S;stacknode x;InitStack(S);p=T;do while (p!=null) /遍历左子树 x.ptr = p; x.tag = L; /标记为左子树 push(S,x); p=p-lchild; while (!StackEmpty(S) & S.ElemS.top.tag=R) x = Pop(S); p = x.ptr; visit(p-data); /tag为R,表示右子树访问完毕,故访问根结点 if (!StackEmpty(S) S.ElemS.top.tag =R; /遍历右子树 p=S.Elems.top.ptr-rchild; while (!StackEmpty(S);5. 设计一个非递归算法,计算树的叶子结点数。(要求说明树的存储方式) 答: 设树的存储方式为孩子兄弟链表typedef struct CSTNode char data;struct CSTNode *firstchild,*nextsibling;CSTNode,*CSTree;void Getnum(CSTNode *t,int *n,int *m)/n是叶子节点数,m是非叶子结点数/其中n,m的初值为零 CSTNode *queue=CSTNode50;/初始化一个队列 CSTNode *T=t; int rear=0,front=0; if(!T) return;/若树为空,则返回 queuerear+=T; while(rear!=front) T=queuefront+; if(T-firstchild|T-nextsibling)/结点有左子树或右子树 (*m)+; if(T-firstchild) queuerear+=T-firstchild; if(T-nextsibling) queuerear+=T-nextsibling; else (*n)+; 6. 已知带权无向图如图所示:(1). 根据普里姆(Prim)算法,设计算法,求它的从顶点a出发的最小生成树;(2). 根据克鲁斯卡尔(Kruskal)算法,求该图的最小生成树,给出添加边次序。41375625abced答:(1)struct VertexType adjvex; / U集中的顶点 VRType lowcost; / 边的权值 closedgeMAX_VERTEX_NUM;void MiniSpanTree_P(MGraph G, VertexType a) /用普里姆算法从顶点a出发构造网G的最小生成树 k = LocateVex ( G, a ); for ( j=0; jG.vexnum; +j ) / 辅助数组初始化 if (j!=k) closedgej = a, G.arcskj.adj ; closedgek.lowcost = 0; / 初始,Ua for (i=0; iG.vexnum; +i) k = minimum(closedge); / 求出加入生成树的下一个顶点(k) printf(closedgek.adjvex, G.vexsk); / 输出生成树上一条边 closedgek.lowcost = 0; / 第k顶点并入U集 for (j=0; jG.vexnum; +j) /修改其它顶点的最小边 if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.adj ;a2(2)dcb14e37已知带权有向图如图所示:(1). 画出该图的邻接矩阵存储结构;(2). 求从顶点a到其余各顶点之间的最短路经及最短路经长度,并给出计算过程。2aafbdgcheA69783251302421答: (1) abcdefgha269b301c5d2e87f324gh21(2)终点1234567b2(a,b)c32(a,b,c)32(a,b,c)13(a,b,d,e,c)13(a,b,d,e,c)13(a,b,d,e,c)d6(a,d)3(a,b,d)e5(a,b,d,e)f9(a,f)9(a,f)9(a,f)9(a,f)g12(a,b,d,e,g)12(a,b,d,e,g)h33(a,b,d,e,g,h)18(a,b,d,e,c,h)VjbdefgchSa,ba,b,da,b,d,ea,fa,b,d,e,ga,b,d,e,ca,b,d,e,c,h长度235912138列出图中全部可能的拓扑有序序列,并指出应用7.5.1节中算法Topological Sort算法求得的是哪一个序列?答:全部可能的拓扑有序序列:1-5-2-3-6-4 1-5-2-6-3-4 1-5-6-2-3-4 5-1-2-3-6-4 5-1-2-6-3-4 5-1-6-2-3-4 5-6-1-2-3-4应用7.5.1节中算法Topological Sort算法求得的是 1-5-2-3-6-49 对下图所示AOE网络,计算各活动弧的e(ai)和l(ai)函数值,各事件(顶点)的ve(vi)和vl(vi)函数值,列出各条关键路径。顶点vevl00A 120B624C1726D319E3434F48G33H1313I17J3131K22224444 边eeelel-ee(,A)01919(,B)01818(,D)01616(,F)044(,G)000(,I
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 临聘导游合同范本
- 磷脂销售合同范本
- 婚庆公司承揽合同范本
- 模具研发协议合同范本
- 闲置家居售卖合同范本
- 新车购买合同范本赠品
- 社区工作基础知识培训课件
- 翻砂成品采购合同范本
- 微信销售合同范本
- 外贸口罩销售合同范本
- 中国黄金知识培训课件
- 2025至2030年中国奶牛养殖行业竞争格局分析及投资战略咨询报告
- 人教PEP版(一起)一年级上册英语全册教案
- 光伏施工基本知识培训课件
- 创伤性血气胸的急救与护理
- 2025贵州毕节市赫章县招聘事业单位工作人员123人笔试备考题库及参考答案详解
- 2025关于医疗平台与医疗机构合作合同模板
- 福州工会考试试题及答案
- 学校后勤工作管理培训
- 胰腺炎的营养治疗与护理
- 淋巴水肿健康科普
评论
0/150
提交评论