《2011福建省数据理论高级》由会员分享，可在线阅读，更多相关《2011福建省数据理论高级（6页珍藏版）》请在金锄头文库上搜索。
1、1、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) /用“破圈法”求解带权连通无向图的一棵最小代价生成树。typedef struct int i,j,wnode; /设顶点信息就是顶点编号，权是整型数 node edge; scanf( %d%d,&e,&n) ; /输入边数和顶点数。 for (i=1;i=e;
2、i+) /输入e条边：顶点，权值。 scanf(%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=0; eg-; /测试下一条边edgek，权值置0表示该边被删除k+; /下条边 /while /算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现，2、设t是给定的一棵二叉树，下面的递归程序count(
3、t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.typedef struct nodeint data; struct node *lchild,*rchild;node;int N2,NL,NR,N0;void count(node *t) if (t-lchild!=NULL) if (1)_ N2+; else NL+;else if (2)_ NR+; else (3)_ ;if(t-lchild!=NULL)(4)_; if
4、 (t-rchild!=NULL) (5)_; 26.树的先序非递归算法。void example(b) btree *b; btree *stack20, *p；int top;if (b!=null) top=1; stacktop=b;while (top0) p=stacktop; top-;printf(“%d”,p-data);if (p-rchild!=null)(1)_; (2)_;if (p-lchild!=null)(3)_; (4)_;3、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。48.有n个
5、记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）4、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。void LongestPath(BiTree bt)/求二叉树中的第一条最长路径长度BiTree p=bt,l,s; /l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点 int i，top=0,tag,longest
6、=0; while(p | top0) while(p) s+top=p；tagtop=0; p=p-Lc; /沿左分枝向下 if(tagtop=1) /当前结点的右分枝已遍历 if(!stop-Lc & !stop-Rc) /只有到叶子结点时，才查看路径长度if(toplongest) for(i=1;i0) tagtop=1; p=stop.Rc; /沿右子分枝向下 /while(p!=null|top0)/结束LongestPath5、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，
7、然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。void Translation（float *matrix，int n）/本算法对nn的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。int i,j,k,l；float sum，min； /sum暂存各行元素之和 float *p, *pi, *pk;for(i=0; in; i+) sum=0.0; pk=matrix+i*n; /pk指向矩阵各行第1个元素. for (j=0; jn; j+)sum+=*(pk); pk+; /求一行元素之和.*(p+i)=sum;
8、/将一行元素之和存入一维数组. /for ifor(i=0; in-1; i+) /用选择法对数组p进行排序 min=*(p+i); k=i; /初始设第i行元素之和最小.for(j=i+1;jn;j+) if(pjmin) k=j; min=pj; /记新的最小值及行号.if(i!=k) /若最小行不是当前行,要进行交换(行元素及行元素之和) pk=matrix+n*k; /pk指向第k行第1个元素. pi=matrix+n*i; /pi指向第i行第1个元素. for(j=0;jn;j+) /交换两行中对应元素. sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=s
9、um; sum=pi; pi=pk; pk=sum; /交换一维数组中元素之和. /if/for i free(p); /释放p数组./ Translation算法分析 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n2).6、设从键盘输入一整数的序列：a1, a2, a3，an,试编写算法实现：用栈结构存储输入的整数，当ai-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，.，Wn。问
10、能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,.，n)均为正整数，并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。Knap(S，n)若S=0则Knaptrue否则若（S0且n1)个整数存放到一维数组R中。设计一个尽可能高效（时间、空间）的算法，将R中保存的序列循环左移p（0pn）个位置，即将R中的数据（x0, x1, x2, xn-1），变换为(xp， xp1, , xn-1 ,x0 , x1, xp-1)。7、#define maxsize 栈空间容量 void InOutS(int smaxsize) /s是元素为整数的栈，本算法进行入栈和退栈操作。 int top=0; /top为栈顶指针，定义top=0时为栈空。 for(i=1; ilchild,q-lchild) & Similar(p-
