1、编程实现单链表的就地逆置。
23．在数组 a[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个。
2、在有向图g中，如果r到g中的每个结点都有路径可达，则称结点r为g的根结点。编写一个算法完成下列功能：
1）．建立有向图g的邻接表存储结构；
2）．判断有向图g是否有根，若有，则打印出所有根结点的值。
3、有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。
(1) (3分)给出适用于计数排序的数据表定义；
(2) (7分)使用pascal或c语言编写实现计数排序的算法；
(3) (4分)对于有n个记录的表，关键码比较次数是多少？
(4) (3分)与简单选择排序相比较，这种方法是否更好？为什么？
4、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。
void translation（float *matrix，int n）
/本算法对n×n的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。
int i,j,k,l；
float sum，min； /sum暂存各行元素之和
float *p, *pi, *pk;
for(i=0; i //for i
for(i=0; i
sum=p[i]; p[i]=p[k]; p[k]=sum; /交换一维数组中元素之和。
}//if//for i
free(p); 释放p数组。
// translation
算法分析] 算法中使用选择法排序，比较次数较多，但数据交换(移动)较少。若用其它排序方法，虽可减少比较次数，但数据移动会增多。算法时间复杂度为o(n2).
5、矩阵中元素按行和按列都已排序，要求查找时间复杂度为o（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是a[i,j]>x， 这情况下向j 小的方向继续查找；二是a[i,j]void search(datatype a[ ]int a,b,c,d, datatype x)
//n*m矩阵a,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵a中。
else if (a[i][j]>x) j--;else i++;
if(flag) printf(“a[%d][%d]=%d”,i,j,x假定x为整型。
else printf(“矩阵a中无%d 元素”，x)；
}算法search结束。
算法讨论]算法中查找x的路线从右上角开始，向下（当x>a[i,j]）或向左（当x6、假设以i和o分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由i和o组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）
（1）a和d是合法序列，b和c 是非法序列。
（2）设被判定的操作序列已存入一维数组a中。
int judge(char a)
判断字符数组a中的输入输出序列是否是合法序列。如是，返回true，否则返回false。
i++;不论a[i]是‘i’或‘o’，指针i均后移。}
if(j!=k)
else 算法结束。
7、假设以i和o分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由i和o组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）
（1）下面所示的序列中哪些是合法的？
a. ioiioioo b. iooioiio c. iiioioio d. iiiooioo
（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
8、若第n件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-w[n]）。若第n件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s）。若最终s=0,则有一解；否则，若s<0或虽然s>0但物品数n<1,则无解。
1）s-w[n],n-1 //knap(s-w[n],n-1)=true
2）s,n-1knap←knap(s,n-1)
9、矩阵中元素按行和按列都已排序，要求查找时间复杂度为o（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是a[i,j]>x， 这情况下向j 小的方向继续查找；二是a[i,j]void search(datatype a[ ]int a,b,c,d, datatype x)
//n*m矩阵a,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵a中。
else if (a[i][j]>x) j--;else i++;
if(flag) printf(“a[%d][%d]=%d”,i,j,x假定x为整型。
else printf(“矩阵a中无%d 元素”，x)；
}算法search结束。
算法讨论]算法中查找x的路线从右上角开始，向下（当x>a[i,j]）或向左（当x10、在有向图g中，如果r到g中的每个结点都有路径可达，则称结点r为g的根结点。编写一个算法完成下列功能：
1）．建立有向图g的邻接表存储结构；
2）．判断有向图g是否有根，若有，则打印出所有根结点的值。
11、本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。
建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。
int num=0， visited=0 //num记访问顶点个数，访问数组visited初始化。
const n=用户定义的顶点数；
2023年吉林省基础数据入门
1 设一组有序的记录关键字序列为 13，18，24，35，47，50，62，83，90 查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。2 假设以i和o分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由i和o组成的序列，称可以操作...
2023年江苏省数据要领基础
edge j 1 edge 0 for k 1 eg e while eg n破圈，直到边数e n 1.if connect k 删除第k条边若仍连通。edge k w 0 eg 测试下一条边edge k 权值置0表示该边被删除。k 下条边。while 算法结束。connect 是测试图是否连通的函...
2023年贵州省数据要领加强
1 设指针变量p指向双向链表中结点a，指针变量q指向被插入结点b，要求给出在结点a的后面插入结点b的操作序列 设双向链表中结点的两个指针域分别为llink和rlink 2 约瑟夫环问题 josephus问题 是指编号为 n的n n 0 个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数...