2011年黑龙江省C++语言版大纲
- 格式：docx
- 大小：16.73 KB
- 文档页数：2
1、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任
取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”
求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算
法。注：圈就是回路。
2、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由
已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序
遍历序列，请写出程序所缺的语句。
#define MAX 100
typedef struct Node
{char info; struct Node *llink, *rlink; }TNODE;
char pred[MAX],inod[MAX];
main(int argc,int **argv)
{ TNODE *root;
if(argc<3) exit 0;
strcpy(pred,argv[1]); strcpy(inod,argv[2]);
root=restore(pred,inod,strlen(pred));
postorder(root);
}
TNODE *restore(char *ppos,char *ipos,int n)
{ TNODE *ptr； char *rpos; int k;
if(n<=0) return NULL;
ptr->info=(1)_______;
for((2)_______ ; rpos
ptr->llink=restore(ppos+1, (4)_______,k );
ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);
return ptr;
}
postorder(TNODE*ptr)
{ if(ptr=NULL) return;
postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info);
}
3、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退
栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最
长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。
void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度
{BiTree p=bt,l[],s[]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的
结点
int i，top=0,tag[],longest=0;
while(p || top>0)
{ while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下
if(tag[top]==1) //当前结点的右分枝已遍历
{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度
if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}
//保留当前最长路径到l栈，记住最高栈顶指针，退栈
}
else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下
}//while(p!=null||top>0)
}//结束LongestPath
