学海网 文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 外语学习 > 韩语学习 > 2011年河南省理论数据基础

2011年河南省理论数据基础

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++) //在中序序列中查找根结点,然后,左右子女信息入队列

第1页

TOP相关主题

  • 数据库理论基础
  • 大数据理论基础
  • 数据分析基础理论
  • 数据分析师基础理论
  • 数据通信的基础理论
  • 数据挖掘基础理论
  • 空间数据库理论基础
  • 数据科学基础理论

我要评论

相关文档

  • 2011年河南省数据基础理论基础

    2011年河南省数据基础理论基础_韩语学习_外语学习_教育专区。2011年河南省数据基础理论基础 1、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序...

  • 2011年河南省数据基础理论基础

    2011年河南省数据基础理论基础_韩语学习_外语学习_教育专区。2011年河南省数据基础理论基础 1、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序...

  • 2011年河南省数据基础理论基础

    2011年河南省数据基础理论基础_韩语学习_外语学习_教育专区。2011年河南省数据基础理论基础 1、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序...

  • 2011年河南省理论数据基础

    2011年河南省理论数据基础_韩语学习_外语学习_教育专区。2011年河南省理论数据基础 1、矩阵中元素按行和按列都已排序,要求查找时间复杂度为O(m+n),因此不能采用...

  • 2011年河南省理论数据基础

    2011年河南省理论数据基础_韩语学习_外语学习_教育专区。2011年河南省理论数据基础 1、矩阵中元素按行和按列都已排序,要求查找时间复杂度为 O(m+n) ,因此不能...

  • 2011年河南省理论数据基础

    2011年河南省理论数据基础_韩语学习_外语学习_教育专区。2011年河南省理论数据基础 1、矩阵中元素按行和按列都已排序,要求查找时间复杂度为 O(m+n) ,因此不能...

  • 2011年河南省数据理论基础

    2011年河南省数据理论基础_韩语学习_外语学习_教育专区。2011年河南省数据理论基础 1、4、 void LinkList_reverse(Linklist &L) //链表的就地逆置;为简化算法,...

  • 2011年河南省理论数据基础

    2011年河南省理论数据基础_韩语学习_外语学习_教育专区。2011年河南省理论数据基础 1、 将顶点放在两个集合 V1 和 V2。对每个顶点,检查其和邻接点是否在同一个...

  • 2011年河南省数据基础理论要领

    2011年河南省数据基础理论要领_韩语学习_外语学习_教育专区。2011年河南省数据基础理论要领 1、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序...

  • 2011年河南省数据理论基础

    2011年河南省数据理论基础_韩语学习_外语学习_教育专区。2011年河南省数据理论基础 1、对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。 int LeafK...

站点地图 | 文档上传 | 侵权投诉 | 手机版
新浪认证  诚信网站  绿色网站  可信网站   非经营性网站备案
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.xuehai.net All Rights Reserved.  email
返回顶部