发布时间 : 星期二 文章2015吉林省数据分析基础更新完毕开始阅读bc82b7b5f78a6529657d533d
1、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。 #include
struct node * next; } listnode;
typedef listnode* linklist;
/*--------------------------------------------*/ /* 删除单链表中重复的结点 */
/*--------------------------------------------*/ linklist deletelist(linklist head) { listnode *p,*s,*q; p=head->next; while(p) {s=p;
q=p->next; while(q)
if(q->data==p->data)
{s->next=q->next;free(q); q=s->next;} else
{ s=q; /*找与P结点值相同的结点*/ q=q->next; }
p=p->next; }
return head; }
2、本题要求建立有序的循环链表。从头到尾扫描数组A，取出A[i]（0<=i //由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点 {LinkedList h; h=(LinkedList)malloc(sizeof(LNode));//申请结点 h->next=h; //形成空循环链表 for(i=0;i while(p!=h && p->data {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链入链表中 } }//for return(h); }算法结束 3、将顶点放在两个集合V1和V2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。 int BPGraph (AdjMatrix g) //判断以邻接矩阵表示的图g是否是二部图。 {int s[]; //顶点向量，元素值表示其属于那个集合（值1和2表示两个集合） int Q[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。 int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited[]是访问数组 for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化，各顶点未确定属于那个集合 Q[1]=1; r=1; s[1]=1;//顶点1放入集合S1 while(f {v=Q[++f]; if (s[v]==1) jh=2; else jh=1;//准备v的邻接点的集合号 if (!visited[v]) {visited[v]=1; //确保对每一个顶点，都要检查与其邻接点不应在一个集合中 for (j=1,j<=n;j++) if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;} //邻接点入队列 else if (s[j]==s[v]) return(0);} //非二部图 }//if (!visited[v]) }//while return(1); }//是二部图 [算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。 4、矩阵中元素按行和按列都已排序，要求查找时间复杂度为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中. {i=a; j=d; flag=0; //flag是成功查到x的标志 while(i<=b && j>=c) if(A[i][j]==x) {flag=1;break;} 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]）或向左（当x 向下最多是m，向左最多是n。最佳情况是在右上角比较一次成功，最差是在左下角（A[b,c]），比较m+n次，故算法最差时间复杂度是O(m+n）。 5、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。 6、若第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-1 // Knap←Knap(s,n-1) 7、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={ G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7 8、约瑟夫环问题（Josephus问题）是指编号为1、2、?，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，?，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。 9、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分） （1）A和D是合法序列，B和C 是非法序列。 （2）设被判定的操作序列已存入一维数组A中。 int Judge(char A[]) //判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。 {i=0; //i为下标。 j=k=0; //j和k分别为I和字母O的的个数。 while(A[i]!=‘\\0’) //当未到字符数组尾就作。 {switch(A[i]) {case‘I’: j++; break; //入栈次数增1。 case‘O’: k++; if(k>j){printf(“序列非法\\n”)；exit(0);} } i++; //不论A[i]是‘I’或‘O’，指针i均后移。} if(j!=k) {printf(“序列非法\\n”)；return(false);} else {printf(“序列合法\\n”)；return(true);} }//算法结束。 10、设计一个尽可能的高效算法输出单链表的倒数第K个元素。 11、二部图（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为结点个数）。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【 12、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。 void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2) //将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。 {if(h1>=l1) {post[h2]=pre[l1]; //根结点 half=(h1-l1)/2; //左或右子树的结点数 PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列 PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列 } }//PreToPost 32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。 LinkedList head,pre=null; //全局变量 LinkedList InOrder(BiTree bt) //中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head {if(bt){InOrder(bt->lchild); //中序遍历左子树 if(bt->lchild==null && bt->rchild==null) //叶子结点 if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点 else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表 InOrder(bt->rchild); //中序遍历左子树 pre->rchild=null; //设置链表尾 } return(head); } //InOrder 时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n) 13、约瑟夫环问题（Josephus问题）是指编号为1、2、?，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，?，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。 #include