作业帮有关于数据结构的问题.（编程）
来源：学生作业帮 编辑：拍题作业网作业帮 分类：综合作业 时间：2024/06/05 10:41:42
有关于数据结构的问题.（编程）
我想知道09年试卷30题和33题如何解出来的 麻烦请说明下解题步骤.
我想知道09年试卷30题和33题如何解出来的 麻烦请说明下解题步骤.
30题：
无向图没接触过 有些概念不大清楚 所以可能不太准确
1.答案 3
2.答案 计算连接图该节点连接在一起的节点的个数
#define MaxNum 20
int visited[MaxNum]；
void DFS(Graph *g,int i)；
/*从顶点vi出发进行深度优先搜索,访问顶点vj时置visited[j]为1*/
int f30(Graph *g)
{ int i,k；
for (i=0； in； i++)／*g->n为图g的顶点数目*／
visited[i]=0；
//从这很显然可以看出是给g每个顶点在数组visited分配一个位置 初始值为0
for (i=k=0； in; i++)
if (visited[i]= =0)
{ k++；
DFS(g,i)；
}
//已经告诉你DFS(g,i)是遍历函数,但是它能保证访问到每一个节点 却不能保证不重复访问某个节点,所以当遍历到每个节点的时候,先去看看数组对应这个节点的位置的值是多少 是0表示没有遍历过, 是1表示已经遍历过 计数就不增加了 k就是计数器
return k；
}
33题：
BSTNode *f33(BSTree T, KeyType x)
{ BSTNode *p;
if (T= =NULL) return NULL; //空树 返回空
p=f33(T->1child, x); //搜索左子树
if (p!=NULL)return p; //从左子树中搜索到了所需要的值
if (T->key>x)return T; //如果树根节点索引值比x大 返回树的根节点
return f33(T-> rchild, x); //从右子树搜索所需要值 并返回
}
算法思想是 先在左子树找,没找到,但是根节点的索引值又比需要找的大,也就是说需要找的应该在左子树吗,那么就返回根节点,其他所有树节点都比根节点大,因为其他节点都在根节点右节点,不是的话继续找右节点.
也就说寻找的结果是返回不比寻找值小的最小一个树节点, 都小于则返回NULL 可以是相等的, 也可以是稍大的
1)对如图所示的二叉排序树T,写出f33(T,8)
返回的指针所指结点的关键字； 8
(2)在哪些情况下算法f33返回空指针? 树为空或者寻找值是树中最大的
(3)简述算法f33的功能.
返回不比寻找值小的最小一个树节点, 都小于则返回
无向图没接触过 有些概念不大清楚 所以可能不太准确
1.答案 3
2.答案 计算连接图该节点连接在一起的节点的个数
#define MaxNum 20
int visited[MaxNum]；
void DFS(Graph *g,int i)；
/*从顶点vi出发进行深度优先搜索,访问顶点vj时置visited[j]为1*/
int f30(Graph *g)
{ int i,k；
for (i=0； in； i++)／*g->n为图g的顶点数目*／
visited[i]=0；
//从这很显然可以看出是给g每个顶点在数组visited分配一个位置 初始值为0
for (i=k=0； in; i++)
if (visited[i]= =0)
{ k++；
DFS(g,i)；
}
//已经告诉你DFS(g,i)是遍历函数,但是它能保证访问到每一个节点 却不能保证不重复访问某个节点,所以当遍历到每个节点的时候,先去看看数组对应这个节点的位置的值是多少 是0表示没有遍历过, 是1表示已经遍历过 计数就不增加了 k就是计数器
return k；
}
33题：
BSTNode *f33(BSTree T, KeyType x)
{ BSTNode *p;
if (T= =NULL) return NULL; //空树 返回空
p=f33(T->1child, x); //搜索左子树
if (p!=NULL)return p; //从左子树中搜索到了所需要的值
if (T->key>x)return T; //如果树根节点索引值比x大 返回树的根节点
return f33(T-> rchild, x); //从右子树搜索所需要值 并返回
}
算法思想是 先在左子树找,没找到,但是根节点的索引值又比需要找的大,也就是说需要找的应该在左子树吗,那么就返回根节点,其他所有树节点都比根节点大,因为其他节点都在根节点右节点,不是的话继续找右节点.
也就说寻找的结果是返回不比寻找值小的最小一个树节点, 都小于则返回NULL 可以是相等的, 也可以是稍大的
1)对如图所示的二叉排序树T,写出f33(T,8)
返回的指针所指结点的关键字； 8
(2)在哪些情况下算法f33返回空指针? 树为空或者寻找值是树中最大的
(3)简述算法f33的功能.
返回不比寻找值小的最小一个树节点, 都小于则返回