2012西藏自治区学习数据库入门

1、设有一个数组中存放了一个无序的关键序列 K1、K2、?、Kn。现要求将 Kn 放在将元素排 序后的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过 n。

51. 借助于快速排序的算法思想,在一组无序的记录中查找给定关键 字值等于 key 的记录。设此组记录存放于数组 r[l..h]中。若查找成功,则输出该记录在 r 数组中的位置及其值,否则显示“not find”信息。请编写出算法并简要说明算法思想。

2、将顶点放在两个集合 V1 和 V2。对每个顶点,检查其和邻接点是否 在同一个集合中,如是,则为非二部图。为此,用整数 1 和 2 表示两个集合。再用一队列结 构存放图中访问的顶点。 int BPGraph (AdjMatrix g)

//判断以邻接矩阵表示的图 g 是否是二部图。

两个集合)

{int s[]; //顶点向量,元素值表示其属于那个集合(值 1 和 2 表示 int Q[];//Q 为队列, 元素为图的顶点, 这里设顶点信息就是顶点编号。

访问数组 确定属于那个集合

int f=0,r,visited[]; //f 和 r 分别是队列的头尾指针,visited[]是 for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化,各顶点未

Q[1]=1; r=1; s[1]=1;//顶点 1 放入集合 S1

while(f<r)

{v=Q[++f]; if (s[v]==1) jh=2; else jh=1;//准备 v 的邻接点的集 合号

if (!visited[v])

{visited[v]=1; //确保对每一个顶点, 都要检查与其邻接点不应在一 个集合中 for (j=1,j<=n;j++)

if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;} //邻接点入队 列

else if (s[j]==s[v]) return(0);} //非二部图

}//if (!visited[v])

}//while

return(1); }//是二部图

[算法讨论] 题目给的是连通无向图,若非连通,则算法要修改。

3、冒泡排序算法是把大的元素向上移(气泡的上浮) ,也可以把小的

元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法。

48.有 n 个记录存储在带头结点的双向链表中, 现用双向起泡排序法对 其按上升序进行排序,请写出这种排序的算法。 (注:双向起泡排序即相邻两趟排序向相反方 向起泡)

4、二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次 遍历序列中的每个结点都是“局部根” 。确定根后,到二叉树的中序序列中,查到该结点,该 结点将二叉树分为“左根右”三部分。若左、右子树均有,则层次序列根结点的后面应是左 右子树的根;若中序序列中只有左子树或只有右子树,则在层次序列的根结点后也只有左子 树的根或右子树的根。这样,定义一个全局变量指针 R,指向层次序列待处理元素。算法中 先处理根结点,将根结点和左右子女的信息入队列。然后,在队列不空的条件下,循环处理 二叉树的结点。队列中元素的数据结构定义如下:

typedef struct

{ int lvl; 次序列中的位置 int l,h;

//层次序列指针,总是指向当前“根结点”在层 //中序序列的下上界

int f;

//层次序列中当前“根结点”的双亲结点的指针


相关文档

2012年西藏自治区学习数据库入门
2012西藏自治区学习数据库基础
2012年西藏自治区学习数据库基础
2012西藏自治区数据库入门入门
2012年西藏自治区数据库入门基础
2012年西藏自治区数据库入门入门
2012西藏自治区学习数据库深入
2012年西藏自治区学习数据库深入
2012西藏自治区数据库入门深入
2012年西藏自治区数据库入门纲要
电脑版