2023安徽省数据简介入门

1、1、此题要求建立有序的循环链表。从头到尾扫描数组A，取出Ai0=inext=h; /形成空循环链表for(i=0;inext; while(p!=h & p-datanext; /查找Ai的插入位置 if(p=h | p-data!=Ai) /重复数据不再输入 s=(LinkedList)malloc(sizeof(LNode); s-data=Ai; pre-next=s; s-next=p;/将结点s链入链表中/for return(h);算法结束2、二部图bipartite graph G=V，E是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图，使得：V1中的任何两个结

2、点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。1请各举一个结点个数为5的二部图和非二部图的例子。2请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。设G用二维数组A来表示，大小为n*nn为结点个数。请在程序中加必要的注释。假设有必要可直接利用堆栈或队列操作。【3、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre初值为null和全局变量flag，初值为true。假设非二叉排序树，那么置flag为false。#define true 1#define f

3、alse 0typedef struct node datatype data; struct node *llink,*rlink; *BTree; void JudgeBSTBTree t,int flag/ 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 ift!=null & flag Judgebstt-llink,flag；/ 中序遍历左子树 ifpre=nullpre=t；/ 中序遍历的第一个结点不必判断 else ifpre-datadatapre=t；/前驱指针指向当前结点 elseflag=flase； /不是完全二叉树 Judgebst t-r

4、link,flag；/ 中序遍历右子树/JudgeBST算法结束4、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。void union(int A,B,C,m,n)/整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。i=0; j=n-1; k=0;/ i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始while(i=0) if(aibj) ck+=ai+ else ck+=bj-;while(i=0) ck+

5、=bj-;算法结束4、要求二叉树按二叉链表形式存储。15分1写一个建立二叉树的算法。2写一个判别给定的二叉树是否是完全二叉树的算法。BiTree Creat() /建立二叉树的二叉链表形式的存储结构ElemType x；BiTree bt;scanf(“%d,&x); /此题假定结点数据域为整型if(x=0) bt=null;else if(x0) bt=(BiNode *)malloc(sizeof(BiNode);bt-data=x; bt-lchild=creat(); bt-rchild=creat(); else error(“输入错误)；return(bt);/结束 BiTreei

6、nt JudgeComplete(BiTree bt) /判断二叉树是否是完全二叉树,如是，返回1，否那么，返回0int tag=0; BiTree p=bt, Q; / Q是队列，元素是二叉树结点指针，容量足够大if(p=null) return (1);QueueInit(Q); QueueIn(Q,p); /初始化队列，根结点指针入队while (!QueueEmpty(Q)p=QueueOut(Q); /出队 if (p-lchild & !tag) QueueIn(Q,p-lchild); /左子女入队 else if (p-lchild) return 0; /前边已有结点为空，本

7、结点不空 else tag=1; /首次出现结点为空 if (p-rchild & !tag) QueueIn(Q,p-rchild); /右子女入队 else if (p-rchild) return 0; else tag=1; /whilereturn 1; /JudgeComplete5、给定n个村庄之间的交通图，假设村庄i和j之间有道路，那么将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如下列图的实例。20分void Ho

8、spital(AdjMatrix w,int n) /在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。 for (k=1;k=n;k+) /求任意两顶点间的最短路径 for (i=1;i=n;i+) for (j=1;j=n;j+) if (wik+wkjwij) wij=wik+wkj; m=MAXINT; /设定m为机器内最大整数。 for (i=1;i=n;i+) /求最长路径中最短的一条。 s=0; for (j=1;j=n;j+) /求从某村庄i1=is) s=wij; if (s=m) m=s; k=i;/在最长路径中，取最短的一条。m记最长路

9、径，k记出发顶点的下标。 Printf(“医院应建在%d村庄，到医院距离为%dn,i,m); /for/算法结束对以上实例模拟的过程略。各行中最大数依次是9，9，6，7，9，9。这几个最大数中最小者为6，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。1、对图1所示的连通网G，请用Prim算法构造其最小生成树每选取一条边画一个图。6、设从键盘输入一整数的序列：a1, a2, a3，an,试编写算法实现：用栈结构存储输入的整数，当ai-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况入栈满等给出相应的信息。设有一个背包可以放入的物品重量为S，现有n件物品，重量分

10、别为W1，W2，.，Wn。问能否从这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、数组A和B的元素分别有序，欲将两数组合并到C数组

11、，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。void union(int A,B,C,m,n)/整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。i=0; j=n-1; k=0;/ i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始while(i=0) if(aibj) ck+=ai+ else ck+=bj-;while(i=0) ck+=bj-;算法结束4、要求二叉树按二叉链表形式存储。15分1写一个建立二叉树的算法。2写一个判别给定的二叉树是否是完

12、全二叉树的算法。BiTree Creat() /建立二叉树的二叉链表形式的存储结构ElemType x；BiTree bt;scanf(“%d,&x); /此题假定结点数据域为整型if(x=0) bt=null;else if(x0) bt=(BiNode *)malloc(sizeof(BiNode);bt-data=x; bt-lchild=creat(); bt-rchild=creat(); else error(“输入错误)；return(bt);/结束 BiTreeint JudgeComplete(BiTree bt) /判断二叉树是否是完全二叉树,如是，返回1，否那么，返回0i

13、nt tag=0; BiTree p=bt, Q; / Q是队列，元素是二叉树结点指针，容量足够大if(p=null) return (1);QueueInit(Q); QueueIn(Q,p); /初始化队列，根结点指针入队while (!QueueEmpty(Q)p=QueueOut(Q); /出队 if (p-lchild & !tag) QueueIn(Q,p-lchild); /左子女入队 else if (p-lchild) return 0; /前边已有结点为空，本结点不空 else tag=1; /首次出现结点为空 if (p-rchild & !tag) QueueIn(Q,

14、p-rchild); /右子女入队 else if (p-rchild) return 0; else tag=1; /whilereturn 1; /JudgeComplete8、设从键盘输入一整数的序列：a1, a2, a3，an,试编写算法实现：用栈结构存储输入的整数，当ai-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况入栈满等给出相应的信息。设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，.，Wn。问能否从这n件物品中选择假设干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,.，n

15、)均为正整数，并已顺序存储地在数组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)。9、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，假设不

16、再连通，那么将该边恢复。假设仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) /用“破圈法求解带权连通无向图的一棵最小代价生成树。typedef struct int i,j,wnode; /设顶点信息就是顶点编号，权是整型数 node edge; scanf( %d%d,&e,&n) ; /输入边数和顶点数。 for (i=1;i=e;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) /