2012浙江省数据结构分析入门

《2012浙江省数据结构分析入门》由会员分享，可在线阅读，更多相关《2012浙江省数据结构分析入门（3页珍藏版）》请在文档大全上搜索。

1、1、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。voidSpnTree(AdjListg)/用“破圈法”求解带权连通无向图的一棵最小代价生成树。typedefstructinti,j,wnode;/设顶点信息就是顶点编号，权是整型数nodeedge;scanf(%d%d,&e,&n);/输入边数和顶点数。for(i=1;i=e;i+)/输入e条边：顶点，权值。sc

2、anf(%d%d%d,&edgei.i,&edgei.j,&edgei.w);for(i=2;i=e;i+)/按边上的权值大小，对边进行逆序排序。edge0=edgei;j=i-1;while(edgej.w=n)/破圈，直到边数e=n-1.if(connect(k)/删除第k条边若仍连通。edgek.w=O;eg-;/测试下一条边edgek,权值置0表示该边被删除k+;/下条边/while/算法结束。connect()是测试图是否连通的函数，可用图的遍历实现，2、假设K1,，Kn是n个关键词，试解答：试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2,，Kn时，用算

3、法建立一棵以LLINK/RLINK链接表示的二叉查找树。3、设有一个数组中存放了一个无序的关键序列K1、K2、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。51.借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组rl.h中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“notfind”信息。请编写出算法并简要说明算法思想。4、有一种简单的排序算法，叫做计数排序(countsorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注

4、意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c,那么，这个记录在新的有序表中的合适的存放位置即为c。(1) (3分)给出适用于计数排序的数据表定义;(2) (7分)使用Pascal或C语言编写实现计数排序的算法；(3) (4分)对于有n个记录的表，关键码比较次数是多少？(4) (3分)与简单选择排序相比较，这种方法是否更好?为什么?5、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C,只要注意A和B数组指针的使用，以及正确处理一数组

5、读完数据后将另一数组余下元素复制到C中即可。voidunion(intA,B,C,m,n)/整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组Coi=0;j=n-l;k=0;/i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始while(i=0)if(aibj)ck+=ai+elseck+=bj-;while(i=0)ck+=bj-;算法结束4、要求二叉树按二叉链表形式存储。15分(1)写一个建立二叉树的算法。(2)写一个判别给定的二叉树是否是完全二叉树的算法。BiTreeCreat()/建立二叉树的二叉链表形式的存储结构ElemType