2012澳门特别行政区小学英语试题

  • 格式:pdf
  • 大小:89.07 KB
  • 文档页数:2

1、如果从初三(1)、(2)、(3)班中随机抽取一个班与初三(4)班进行一场拔河比赛,那么恰好抽到初三(1)班的概率是_________ .
2、判断。

1、小数都比整数小。

()
2、把一根长为1米的绳子分成5段,每段长1/5米。

()
3、甲数的1/4等于乙数的1/6,则甲乙两数之比为2:3。

()
4、任何一个质数加上1,必定是合数。

()
5、半径为2厘米的加,圆的周长和面积相等。

()
3、假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。

(注:图中不存在顶点到自己的弧)
有向图判断回路要比无向图复杂。

利用深度优先遍历,将顶点分成三类:未访问;已访问但其邻接点未访问完;已访问且其邻接点已访问完。

下面用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
4、在边长为a厘米的正方形上剪下一个最大的圆,这个圆与正方形的周长比是()。

5、将顶点放在两个集合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); }//是二部图
[算法讨论] 题目给的是连通无向图,若非连通,则算法要修改。

6、已知传送带与水平面所成斜坡的坡度i=1:2.4,如果它把物体送到离地面10米高的地方,那么物体所经过的路程为_________ 米.。