2023年云南省重要数据要领

1、设指针变量p指向双向链表中结点a，指针变量q指向被插入结点b，要求给出在结点a的后面插入结点b的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。

2、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。

注：圈就是回路。

3、约瑟夫环问题（josephus问题）是指编号为、…n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。

#include<>

typedef int datatype;

typedef struct node

datatype data;

struct node *next;

listnode;

typedef listnode *linklist;

void jose(linklist head,int s,int m)

linklist k1,pre,p;

int count=1;

pre=null;

k1=headk1为报数的起点*/

while (count!=s) /找初始报数起点*/

while(k1->next!=k1) /当循环链表中的结点个数大于1时*/

pre->next=p->next; /输出该结点，并删除该结点*/

printf("%4d",p->data);

free(p);

k1=pre->next新的报数起点*/

printf("%4d",k1->data); 输出最后一个结点*/

free(k1);

main()

linklist head,p,r;

int n,s,m,i;

printf("n=")

scanf("%d",&n);

printf("s=")

scanf("%d",&s);

printf("m=",m);

scanf("%d",&m);

if (n<1) printf("n<0");

elser->next=head; /生成循环链表*/

jose(head,s,m); 调用函数*/

4、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。