2011年河南省理论数据基础
1、矩阵中元素按行和按列都已排序,要求查找时间复杂度为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)。
2、设有一个数组中存放了一个无序的关键序列K1、K2、 、Kn。现要求将Kn放在将元素排序后的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过n。
51. 借助于快速排序的算法思想,在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功,则输出该记录在r数组中的位置及其值,否则显示“not find”信息。请编写出算法并简要说明算法思想。
3、二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历序列中的每个结点都是“局部根”。确定根后,到二叉树的中序序列中,查到该结点,该结点将二叉树分为“左根右”三部分。若左、右子树均有,则层次序列根结点的后面应是左右子树的根;若中序序列中只有左子树或只有右子树,则在层次序列的根结点后也只有左子树的根或右子树的根。这样,定义一个全局变量指针R,指向层次序列待处理元素。算法中先处理根结点,将根结点和左右子女的信息入队列。然后,在队列不空的条件下,循环处理二叉树的结点。队列中元素的数据结构定义如下:
typedef struct
{ int lvl; //层次序列指针,总是指向当前“根结点”在层次序列中的位置 int l,h; //中序序列的下上界
int f; //层次序列中当前“根结点”的双亲结点的指针
int lr; // 1—双亲的左子树 2—双亲的右子树
}qnode;
BiTree Creat(datatype in[],level[],int n)
//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。 n是二叉树的结点数 {if (n<1) {printf(“参数错误\n”); exit(0);}
qnode s,Q[]; //Q是元素为qnode类型的队列,容量足够大
init(Q); int R=0; //R是层次序列指针,指向当前待处理的结点
BiTree p=(BiTree)malloc(sizeof(BiNode)); //生成根结点
p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点数据
for (i=0; i<n; i++) //在中序序列中查找根结点,然后,左右子女信息入队列
2011年河南省数据基础理论基础_韩语学习_外语学习_教育专区。2011年河南省数据基础理论基础 1、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序...
2011年河南省数据基础理论基础_韩语学习_外语学习_教育专区。2011年河南省数据基础理论基础 1、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序...
2011年河南省数据基础理论基础_韩语学习_外语学习_教育专区。2011年河南省数据基础理论基础 1、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序...
2011年河南省理论数据基础_韩语学习_外语学习_教育专区。2011年河南省理论数据基础 1、矩阵中元素按行和按列都已排序,要求查找时间复杂度为O(m+n),因此不能采用...
2011年河南省理论数据基础_韩语学习_外语学习_教育专区。2011年河南省理论数据基础 1、矩阵中元素按行和按列都已排序,要求查找时间复杂度为 O(m+n) ,因此不能...
2011年河南省理论数据基础_韩语学习_外语学习_教育专区。2011年河南省理论数据基础 1、矩阵中元素按行和按列都已排序,要求查找时间复杂度为 O(m+n) ,因此不能...
2011年河南省数据理论基础_韩语学习_外语学习_教育专区。2011年河南省数据理论基础 1、4、 void LinkList_reverse(Linklist &L) //链表的就地逆置;为简化算法,...
2011年河南省理论数据基础_韩语学习_外语学习_教育专区。2011年河南省理论数据基础 1、 将顶点放在两个集合 V1 和 V2。对每个顶点,检查其和邻接点是否在同一个...
2011年河南省数据基础理论要领_韩语学习_外语学习_教育专区。2011年河南省数据基础理论要领 1、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序...
2011年河南省数据理论基础_韩语学习_外语学习_教育专区。2011年河南省数据理论基础 1、对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。 int LeafK...
我要评论