2012西藏自治区数据库入门加强

1、约瑟夫环问题(Josephus 问题)是指编号为 1、2、?,n 的 n(n>0)个人按顺时针方向 围坐成一圈,现从第 s 个人开始按顺时针方向报数,数到第 m 个人出列,然后从出列的下一 个人重新开始报数,数到第 m 的人又出列,?,如此重复直到所有的人全部出列为止。现要 求采用循环链表结构设计一个算法,模拟此过程。 2、矩阵中元素按行和按列都已排序,要求查找时间复杂度为 O(m+n) ,因此不能采用常规的 二层循环的查找。 可以先从右上角 (i=a,j=d) 元素与 x 比较, 只有三种情况: 一是 A[i,j]>x, 这情况下向 j 小的方向继续查找; 二是 A[i,j]<x, 下步应向 i 大的方向查找; 三是 A[i,j]=x, 查找成功。否则,若下标已超出范围,则查找失败。 void search(datatype A[ ][ ], int a,b,c,d, datatype x) //n*m 矩阵 A,行下标从 a 到 b,列下标从 c 到 d,本算法查找 x 是否在矩阵 A 中. {i=a; j=d; flag=0; //flag 是成功查到 x 的标志 while(i<=b && j>=c) if(A[i][j]==x) {flag=1;break;} else if (A[i][j]>x) j--; else i++; if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定 x 为整型. else printf(“矩阵 A 中无%d 元素” ,x); }算法 search 结束。 [算法讨论]算法中查找 x 的路线从右上角开始, 向下 (当 x>A[i,j]) 或向左 (当 x<A[i,j]) 。 向下最多是 m, 向左最多是 n。 最佳情况是在右上角比较一次成功, 最差是在左下角 (A[b,c]) , 比较 m+n 次,故算法最差时间复杂度是 O(m+n) 。 3、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归算法,栈 中存放二叉树结点的指针,当访问到某结点时,栈中所有元素均为该结点的祖先。本题要找 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 4 、二路插入排序是将待排关键字序列 r[1..n] 中关键字分二路分别按序插入到辅助向量 d[1..n]前半部和后半部(注:向量 d 可视为循环表) ,其原则为,先将 r[l]赋给 d[1],再从 r[2] 记录开始分二路插入。编写实现二路插入排序算法。 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}唯一确定左子树,从而也确定了二叉树。 最后,当 1<i<m 时,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、设有一个数组中存放了一个无序的关键序列 K1、K2、?、Kn。现要求将 Kn 放在将元素排 序后的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过 n。 51. 借助于快速排序的算法思想,在一组无序的记录中查找给定关键字值等于 key 的记录。 设此组记录存放于数组 r[l..h]中。若查找成功,则输出该记录在 r 数组中的位置及其值, 否则显示“not find”信息。请编写出算法并简要说明算法思想。


相关文档

2012年西藏自治区数据库入门加强
2012年西藏自治区学习数据库加强
2012年西藏自治区数据库入门纲要
2012年西藏自治区数据库入门摘要
2012西藏自治区数据库考试含答案入门
2012西藏自治区数据库入门深入
2012西藏自治区数据库入门高级
2012西藏自治区数据库入门入门
2012西藏自治区数据库期末考试入门
2012年西藏自治区数据库入门大纲
电脑版