当前位置:文档下载 > 所有分类 > 外语学习 > 韩语学习 > 2014年吉林省数据总结深入
侵权投诉

2014年吉林省数据总结深入

2014年吉林省数据总结深入

1、假设K1, ,Kn是n个关键词,试解答:

试用二叉查找树的插入算法建立一棵二叉查找树,即当关键词的插入次序为K1,K2, ,Kn时,用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。

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、#define maxsize 栈空间容量

void InOutS(int s[maxsize])

//s是元素为整数的栈,本算法进行入栈和退栈操作。

{int top=0; //top为栈顶指针,定义top=0时为栈空。

for(i=1; i<=n; i++) //n个整数序列作处理。

{scanf(“%d”,&x); //从键盘读入整数序列。

if(x!=-1) // 读入的整数不等于-1时入栈。

if(top==maxsize-1){printf(“栈满\n”);exit(0);}

else s[++top]=x; //x入栈。

else //读入的整数等于-1时退栈。

{if(top==0){printf(“栈空\n”);exit(0);}

else printf(“出栈元素是%d\n”,s[top--]);}

}

}//算法结

4、有一种简单的排序算法,叫做计数排序(count sorting)。这种排序算法对一个待排序

第1页

猜你喜欢

返回顶部