学海网 文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 资格考试/认证 > 公务员考试 > 2012年江西省数据整理要领

2012年江西省数据整理要领

1、假设K1,…,Kn是n个关键词,试解答:
试用二叉查找树的插入算法建立一棵二叉查找树,即当关键词的插入次序为K1,K2,…,Kn时,用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。

2、假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注:图中不存在顶点到自己的弧)
有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问;已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0,1,2表示这三种状态。前面已提到,若dfs(v)结束前出现顶点u到v的回边,则图中必有包含顶点v和u的回路。对应程序中v的状态为1,而u是正访问的顶点,若我们找出u的下一邻接点的状态为1,就可以输出回路了。
void Print(int v,int start ) //输出从顶点start开始的回路。
{for(i=1;i<=n;i++)
if(g[v][i]!=0 && visited[i]==1 ) //若存在边(v,i),且顶点i的状态为1。
{printf(“%d”,v);
if(i==start) printf(“\n”); else Print(i,start);break;}//if
}//Print
void dfs(int v)
{visited[v]=1;
for(j=1;j<=n;j++ )
if (g[v][j]!=0) //存在边(v,j)
if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if
else {cycle=1; Print(j,j);}
visited[v]=2;
}//dfs
void find_cycle() //判断是否有回路,有则输出邻接矩阵。visited数组为全局变量。
{for (i=1;i<=n;i++) visited[i]=0;
for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i);
}//find_cycle

3、有一种简单的排序算法,叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键码互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键码比该记录的关键码小,假设针对某一个记录,统计出的计数值为c,那么,这个记录在新的有序表中的合适的存放位置即为c。
(1) (3分)给出适用于计数排序的数据表定义;
(2) (7分)使用Pascal或C语言编写实现计数排序的算法;
(3) (4分)对于有n个记录的表,关键码比较次数是多少?
(4) (3分)与简单选择排序相比较,这种方法是否更好?为什么?


第1页

TOP相关主题

  • 江西省土地整理中心
  • 整理着装动作要领
  • 整理着装动作要领视频
  • 军人整理着装动作要领
  • 2012江西省考
  • 2012 2014江西省优
  • 2012年江西省高考试题
  • 2012年江西省三好学生

我要评论

相关文档

  • 2012年江西省数据整理要领

    2012年江西省数据整理要领_韩语学习_外语学习_教育专区。2012年江西省数据整理要领 1、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。 29. ① ...

  • 2012年江西省数据整理要领

    2012年江西省数据整理要领_韩语学习_外语学习_教育专区。2012年江西省数据整理要领 1、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。 29. ①试...

  • 2012年江西省数据整理要领

    2012年江西省数据整理要领_韩语学习_外语学习_教育专区。2012年江西省数据整理要领 1、假设 K1,?, Kn 是 n 个关键词,试解答: 试用二叉查找树的插入算法建立一...

  • 2012年江西省数据整理要领

    2012年江西省数据整理要领_韩语学习_外语学习_教育专区。2012年江西省数据整理要领 1、假设 K1,?,Kn 是 n 个关键词,试解答: 试用二叉查找树的插入算法建立一棵...

  • 2012年江西省数据整理要领

    2012年江西省数据整理要领_韩语学习_外语学习_教育专区。2012年江西省数据整理要领 1、设有一个数组中存放了一个无序的关键序列K1、K2、…、Kn。现要求将Kn放在...

  • 2012年江西省数据要领要领

    2012年江西省数据要领要领_韩语学习_外语学习_教育专区。2012年江西省数据要领要领 1、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT 为指向该二叉树根结点...

  • 2012年江西省数据要领要领

    2012年江西省数据要领要领_韩语学习_外语学习_教育专区。2012年江西省数据要领要领 1、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT 为指向该二叉树根结点...

  • 2012年江西省数据要领入门

    2012年江西省数据要领入门_公务员考试_资格考试/认证_教育专区。1、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树,下面程序的作用是实现由已知某二叉树...

  • 2012年江西省数据要领

    2012年江西省数据要领_韩语学习_外语学习_教育专区。2012年江西省数据要领 1、设T是一棵满二叉树,编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。 2...

  • 2012年江西省数据要领要领

    2012年江西省数据要领要领_韩语学习_外语学习_教育专区。2012年江西省数据要领要领 1、根据二叉排序树中序遍历所得结点值为增序的性质,在遍历中将当前遍历结点与其...

  • 2012年江西省数据要领摘要

    2012年江西省数据要领摘要_韩语学习_外语学习_教育专区。2012年江西省数据要领摘要 1、设t是给定的一棵二叉树,下面的递归程序count(t)用于求得:二叉树t中具有非...

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