山东省旅游数据分析 2012年山东省分析数据入门.doc

山东省旅游数据分析 2012年山东省分析数据入门 1、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。2、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）3、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。void union(int A[],B[],C[],m,n)//整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。{i=0; j=n-1; k=0;// i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始while(ilt;m amp;amp; jgt;=0)if(a[i]lt;b[j]) c[k++]=a[i++] else c[k++]=b[j--];while(ilt;m) c[k++]=a[i++];while(jgt;=0) c[k++]=b[j--];}算法结束4、要求二叉树按二叉链表形式存储。15分（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。BiTree Creat() //建立二叉树的二叉链表形式的存储结构{ElemType x；BiTree bt;scanf(“%d”,amp;x); //本题假定结点数据域为整型if(x==0) bt=null;else if(xgt;0){bt=(BiNode *)malloc(sizeof(BiNode));bt-gt;data=x; bt-gt;lchild=creat(); bt-gt;rchild=creat(); }else error(“输入错误”)；return(bt);}//结束 BiTreeint JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0{int tag=0; BiTree p=bt, Q[]; // Q是队列，元素是二叉树结点指针，容量足够大if(p==null) return (1);QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队while (!QueueEmpty(Q)){p=QueueOut(Q); //出队if (p-gt;lchild amp;amp; !tag) QueueIn(Q,p-gt;lchild); //左子女入队else {if (p-gt;lchild) return 0; //前边已有结点为空，本结点不空else tag=1; //首次出现结点为空if (p-gt;rchild amp;amp; !tag) QueueIn(Q,p-gt;rchild); //右子女入队else if (p-gt;rchild) return 0; else tag=1; } //whilereturn 1; } //JudgeComplete4、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。void SpnTree (AdjList g) //用“破圈法”求解带权连通无向图 的一棵最小代价生成树。{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数node edge[];scanf( quot;%d%dquot;,amp;e,amp;n) ; //输入边数和顶点数。for (i=1;ilt;=e;i++) //输入e条边：顶点，权值。scanf(quot;%d%d%dquot; ,amp;edge[i].i ,amp;edge[i].j ,