2023福建省数据理论高级

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是给定的一棵二叉树，下面的递归程序coun

3、t(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)_;

4、if (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=0;

6、 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 Translationfloat *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)=sum;

9、 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中保存的序列循环左移p0pn个位置，即将R中的数据x0, x1, x2, xn-1，变换为(xp， xp1, , xn-1 ,x0 , x1, xp-1)。7、#define maxsize 栈空间容量 void InOutS(int smax

11、size) /s是元素为整数的栈，本算法进行入栈和退栈操作。 int top=0; /top为栈顶指针，定义top=0时为栈空。 for(i=1; ilchild,q-lchild) & Similar(p-rchild,q-rchild)/结束Similar10、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。11、有一种简单的排序算法，叫做计数排序count sorting。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表

12、一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的适宜的存放位置即为c。 (1) (3分)给出适用于计数排序的数据表定义; (2) (7分)使用Pascal或C语言编写实现计数排序的算法； (3) (4分)对于有n个记录的表，关键码比较次数是多少? (4) (3分)与简单项选择择排序相比较，这种方法是否更好?为什么?12、此题要求建立有序的循环链表。从头到尾扫描数组A，取出Ai0=inext=h; /形成空循环链表for(i=0;inext; while(p!=h & p-datanext; /查找Ai的插入位置 if(

13、p=h | p-data!=Ai) /重复数据不再输入 s=(LinkedList)malloc(sizeof(LNode); s-data=Ai; pre-next=s; s-next=p;/将结点s链入链表中/for return(h);算法结束13、有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,写出G的拓扑排序的结果。G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7 14、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置下标。用j记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，假设局部平台长度i

14、-j大于l时，那么修改最长平台的长度kl=i-j和其在b中的起始位置k=j，直到b数组结束，l即为所求。void Platform (int b , int N) /求具有N个元素的整型数组b中最长平台的长度。l=1;k=0;j=0;i=0;while(in-1)while(il) l=i-j+1;k=j; /局部最长平台i+; j=i; /新平台起点printf(“最长平台长度%d，在b数组中起始下标为%d，l，k)；/ Platform15、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否那么称为非法序列。15分1A和D是合法序列，B和C 是非法序列。2设被判定的操作序列已存入一维数组A中。 int Judge(char A) /判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否那么返回false。 i=0; /i为下标。 j=k=