2010安徽省数据简介入门

1、本题要求建立有序的循环链表。从头到尾扫描数组A，取出A[i]（0<=i<n）,然后到链表中去查找值为A[i]的结点，若查找失败，则插入。LinkedListcreat(ElemTypeA[],intn)//由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点{LinkedListh;h=(LinkedList)malloc(sizeof(LNode));//申请结点h->next=h;//形成空循环链表for(i=0;i<n;i++){pre=h;p=h->next;while(p!=h&&p->data<A[i]){pre=p;p=p->next;}//查找A[i]的插入位置if(p==h||p->data!=A[i])//重复数据不再输入{s=(LinkedList)malloc(sizeof(LNode));s->data=A[i];pre->next=s;s->next=p;//将结点s链入链表中}}//forreturn(h);}算法结束2、二部图（bipartitegraph）G=（V，E）是一个能将其结点集V分为两不相交子集V1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。（1）．请各举一个结点个数为5的二部图和非二部图的例子。（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。设G用二维数组A来表示，大小为n*n（n为结点个数）。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【3、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。#definetrue1#definefalse0typedefstructnode{datatypedata;structnode*llink,*rlink;}*BTree;voidJudgeBST（BTreet,intflag）//判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。{if（t!=null&&flag）{Judgebst（t->llink,flag）；//中序遍历左子树if（pre==null）pre=t；//中序遍历的第一个结点不必判断elseif（pre->data<t->data）pre=t；//前驱指针指向当前结点else{flag=flase；}//不是完全二叉树Judgebst（t->rlink,flag）；//中序遍历右子树}//JudgeBST算法结束4、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。voidunion(intA[],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<m&&j>=0)if(a[i]<b[j])c[k++]=a[i++]elsec[k++]=b[j--];while(i<m)c[k++]=a[i++];while(j>=0)c[k++]=b[j--];}算法结束4、要求二叉树按二叉链表形式存储。15分（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。BiTreeCreat()//建立二叉树的二叉链表形式的存储结构{ElemTypex；BiTreebt;scanf(“%d”,&x);//本题假定结点数据域为整型if(x==0)bt=null;elseif(x>0){bt=(BiNode*)malloc(sizeof(BiNode));bt->data=x;bt->lchild=creat();bt->rchild=creat();}elseerror(“输入错误”)；return(bt);}//结束BiTreeintJudgeComplete(BiTreebt)//判断二叉树是否是完全二叉树,如是，返回1，否则，返回0{inttag=0;BiTreep=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)return0;//前边已有结点为空，本结点不空elsetag=1;//首次出现结点为空if(p->rchild&&!tag)QueueIn(Q,p->rchild);//右子女入队elseif(p->rchild)return0;elsetag=1;}//whilereturn1;}//JudgeComplete5、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院elsetag=1;//首次出现结点为空if(p->rchild&&!tag)QueueIn(Q,p->rchild);//右子女入队elseif(p->rchild)return0;elsetag=1;}//whilereturn1;}//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)均为正整数，并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。Knap(S，n)若S=0则Knap←true否则若（S<0）或(S>0且n<1)则Knap←false否则若Knap(1),_=true则print(W[n])；Knap←true否则Knap←Knap(2)_,_设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如：设str1和str2是分别指向两个单词的头结点，请设计一个尽可能的高效算法，找出两个单词共同后缀的起始位置，分析算法时间复杂度。将n(n>1)个整数存放到一维数组R中。设计一个尽可能高效（时间、空间）的算法，将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据（x0,x1,x2,…,xn-1），变换为(xp，xp＋1,…,xn-1,x0,x1,…,xp-1)。9、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。voidSpnTree(AdjListg)//用“破圈法”求解带权连通无向图的一棵最小代价生成树。{typedefstruct{inti,j,w}node;//设顶点信息就是顶点编号，权是整型数nodeedge[];scanf("%d%d",&e,&n);//输入边数和顶点数。for(i=1;i<=e;i++)//输入e条边：顶点，权值。scanf("%d%d%d",&edge[i].i,&edge[i].j,&edge[i].w);for(i=2;i<=e;i++)//按边上的权值大小，对边进行逆序排序。{edge[0]=edge[i];j=i-1;while(edge[j].w<edge[0].w)edge[j+1]=edge[j--];edge[j+1]=edge[0];}//fork=1;eg=e;while(eg>=n)//破圈，直到边数e=n-1.{if(connect(k))//删除第k条边若仍连通。{edge[k].w=0;eg--;}//测试下一条边edge[k]，权值置0表示该边被