2021年四川省C#语言纲要

1、2021年四川省c#语言纲要 2021年四川省c#语言纲要 1、二部图（bipartite graph） g=（v，e）是一个能将其结点集v分为两不相交子集v 1和v2=v-v1的无向图，使得：v1中的任何两个结点在图g中均不相邻，v2中的任何结点在图g中也均不相邻。 （1）请各举一个结点个数为5的二部图和非二部图的例子。 （2）请用c或pascal编写一个函数bipartite推断一个连通无向图g是否是二部图，并分析程序的时间简单度。设g用二维数组a来表示，大小为n*n（n为结点个数）。请在程序中加必要的解释。若有必要可直接利用堆栈或队列操作。【 2、有一种简洁的排序算法，叫做计数排序（co

2、unt sorting）。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必需留意的是，表中全部待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 (1) (3分)给出适用于计数排序的数据表定义; (2) (7分)使用pascal或c语言编写实现计数排序的算法； (3) (4分)对于有n个记录的表，关键码比较次数是多少? (4) (3分)与简洁选择排序相比较，这种方法是否更好?为什么? 3、我

3、们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的具体算法，并用程序实现你所给出的算法。注：圈就是回路。 4、本题要求建立有序的循环链表。从头到尾扫描数组a，取出ai（0=in）,然后到链表中去查找值为ai的结点，若查找失败，则插入。 linkedlist creat(elemtype a,int n) /由含n个数据的数组a生成循环链表，要求链表有序并且无值重复结点 linkedlist h; h=(linkedlist)malloc(s

4、izeof(lnode);/申请结点 h-next=h; /形成空循环链表 for(i=0;in;i+) pre=h; p=h-next; while(p!=h p-dataai) pre=p; p=p-next; /查找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); 算法结束 5、两棵空二叉树或仅有根结点的二叉树相像；对非空二叉树，可判左右子树是否相像，采纳递归算法。 202

5、1年四川省c#语言纲要 int similar(bitree p,q) /推断二叉树p和q是否相像 if(p=null q=null) return (1); else if(!p q | p !q) return (0); else return(similar(p-lchild,q-lchild) similar(p-rchild,q-rchild) /结束similar 6、对二叉树的某层上的结点进行运算，采纳队列结构按层次遍历最相宜。 int leafklevel(bitree bt, int k) /求二叉树bt 的第k(k1) 层上叶子结点个数 if(bt=null | k1) r

6、eturn(0); bitree p=bt,q; /q是队列，元素是二叉树结点指针,容量足够大 int front=0,rear=1,leaf=0; /front 和rear是队头和队尾指针, leaf是叶子结点数 int last=1,level=1; q1=p; /last是二叉树同层最右结点的指针，level 是二叉树的层数 while(front=rear) p=q+front; if(level=k !p-lchild !p-rchild) leaf+; /叶子结点 if(p-lchild) q+rear=p-lchild; /左子女入队 if(p-rchild) q+rear=p-rchild; /右子女入队 if(front=last) level+; /二叉树同层最右结点已处理,层数增