Question

几个数据结构的题目，大家帮下忙。

98．设m, n为一棵二叉树上的两个结点，在中序遍历时， n在m前的条件是 。
A．n在m右方 B．n是m 祖先 C．n在m左方 D．n是m子孙
99. 下列说法不正确的是______。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次
B．图的深度遍历不适用于有向图
C．遍历的基本算法有两种：深度遍历和广度遍历
D．图的深度遍历是一个递归过程

101．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_______。
A．(38,40,46,56,79,84) B. (40,38,46,79,56,84)
C．(40,38,46,56,79,84) D. (40,38,46,84,56,79)
102．以下算法的功能是______(栈和队列的元素类型均为int)。
void algo（Stack S, int e）｛
Stack T； int d；
InitStack（T）；
while (!StackEmpty(S)) {
pop(S, d); if (d!=e ) push(T, d); }
while (!StackEmpty(T)) {
pop(T, d); push(S, d); }
｝
A．删除栈S中的数据e B. 判断栈S中是否存在数据e
C．将栈S中的数据逆置 D.将栈S中的数据放入栈T中

Answer 1

//随即迷宫与最短路径
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<time.h>
#define max_m 1000
#define max_n 1000
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int maze[max_m][max_n];
int m,n,start_row,start_col;
char c;
void read_maze()
{
int i,j,num=0;
time_t t;
srand(time(&t));
start_row=m-1,start_col=n-1;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
maze[i][j]=rand()%2;
if(maze[i][j])
num++;
}
if(num>m*n/2)
{
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(maze[i][j])
maze[i][j]-=rand()%2;
}
maze[0][0]=0;
maze[m-1][n-1]=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
printf("%d ",1-maze[i][j]);
if(j==n-1)puts("");
}
}

int new_value(int row, int col)
{
int i,new_row,new_col;
int result;
result = maze[row][col];
if (result == 0)
{
for (i = 0; i < 4; i++)
{
new_row=row+dir[i][0];
new_col=col+dir[i][1];
if(new_row>=0&&new_row<m&&new_col>=0&&new_col<n&&maze[new_row][new_col]<0&&(result==0||maze[new_row][new_col]-1>result))
{
result = maze[new_row][new_col] - 1;
}
}
}
return result;
}

int find_shortest_path()
{
int changed,i,j,new_val,expect_val;
changed = 1;
maze[0][0] = -1;
expect_val = -2;
while (changed && maze[start_row][start_col] == 0)
{
changed = 0;
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
{
new_val = new_value(i,j);
if (new_val == expect_val && new_val != maze[i][j])
{
maze[i][j] = new_val;
changed = 1;
}
}
expect_val--;
}
return (maze[start_row][start_col] < 0);
}

void print_shortest_path()
{
int i,j,new_i,new_j,expect_val,k;
if (maze[start_row][start_col] >= 0)
{
printf("There is no path\n");
return;
}
printf("(%d,%d)\n", start_row+1, start_col+1);
i = start_row;
j = start_col;
for (expect_val = maze[start_row][start_col]+1; expect_val <= -1; expect_val++)
{
for (k = 0; k < 4; k++)
{
new_i = i + dir[k][0];
new_j = j + dir[k][1];
if (new_i >= 0 && new_i < m && new_j >= 0 && new_j < n && maze[new_i][new_j] == expect_val)
{
i = new_i;
j = new_j;
printf("(%d,%d)\n", i+1,j+1);
break;
}
}
}
}

int main()
{
while(scanf("%d%d",&m,&n))
{
read_maze();
if (find_shortest_path())
{
print_shortest_path();
}
else
{
printf("There is no path\n");
}
}
return 0;
}

Answer 2

98C99B101C102B