2022年黑龙江省数据理论纲要

《2022年黑龙江省数据理论纲要》由会员分享，可在线阅读，更多相关《2022年黑龙江省数据理论纲要（3页珍藏版）》请在金锄头文库上搜索。

1、Word2022年黑龙江省数据理论纲要 2022年黑龙江省数据理论纲要 1、题目中要求矩阵两行元素的平均值按递增挨次排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，留意在排序时若有元素移动，则与之相应的行中各元素也必需做相应变动。 void Translation /本算法对nn的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。 int i,j,k,l； float sum，min； /sum暂存各行元素之和 float *p, *pi, *pk; for(i=0; in;

2、i+) sum=0.0; pk=matrix+i*n; /pk指向矩阵各行第1个元素. for (j=0; jn; j+)sum+=*(pk); pk+; /求一行元素之和. *(p+i)=sum; /将一行元素之和存入一维数组. /for i for(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行

3、第1个元素. pi=matrix+n*i; /pi指向第i行第1个元素. for(j=0;jn;j+) /交换两行中对应元素. sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum; sum=pi; pi=pk; pk=sum; /交换一维数组中元素之和. /if /for i free(p); /释放p数组. / Translation 算法分析 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它排序方法,虽可削减比较次数,但数据移动会增多.算法时间简单度为O(n2). 2、有一种简洁的排序算法，叫做计数排序。这种排序算法对一个待排序的表(用数

4、组表示)进行排序，并将排序结果存放到另一个新的表中。必需留意的是，表中全部待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 (1) (3分)给出适用于计数排序的数据表定义; (2) (7分)使用Pascal或C语言编写实现计数排序的算法； (3) (4分)对于有n个记录的表，关键码比较次数是多少? (4) (3分)与简洁选择排序相比较，这种方法是否更好?为什么? 3、约瑟夫环问题是指编号为1、2、，n的n个人按顺时针方向围坐成一圈，现从第s个人开头按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开头报数，数到第m的人又出列，如此重复直到全部的人全部出列为止。现要求采纳循环链表结构设计一个算法，模拟此过程。 - 3 -