2012西藏自治区数据库入门高级

1、在有向图 G 中,如果 r 到 G 中的每个结点都有路径可达,则称结点 r 为 G 的根结点。编写 一个算法完成下列功能: (1) .建立有向图 G 的邻接表存储结构; (2) .判断有向图 G 是否有根,若有,则打印出所有根结点的值。 2、4、 void LinkList_reverse(Linklist &L) //链表的就地逆置;为简化算法,假设表长大于 2 { p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next) { q->next=p;p=q; q=s;s=s->next; //把 L 的元素逐个插入新表表头 } q->next=p;s->next=q;L->next=s; }//LinkList_reverse 3、设计一个尽可能的高效算法输出单链表的倒数第 K 个元素。 4、 假设以邻接矩阵作为图的存储结构, 编写算法判别在给定的有向图中是否存在一个简单有 向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可) 。 (注:图中不存在顶点 到自己的弧) 有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问;已访问但 其邻接点未访问完;已访问且其邻接点已访问完。下面用 0,1,2 表示这三种状态。前面已提 到,若 dfs(v)结束前出现顶点 u 到 v 的回边,则图中必有包含顶点 v 和 u 的回路。对应程 序中 v 的状态为 1,而 u 是正访问的顶点,若我们找出 u 的下一邻接点的状态为 1,就可以输 出回路了。 void Print(int v,int start ) //输出从顶点 start 开始的回路。 {for(i=1;i<=n;i++) if(g[v][i]!=0 && visited[i]==1 ) //若存在边(v,i) ,且顶点 i 的状态为 1。 {printf(“%d”,v); if(i==start) printf(“\n”); else Print(i,start);break;}//if }//Print void dfs(int v) {visited[v]=1; for(j=1;j<=n;j++ ) if (g[v][j]!=0) //存在边(v,j) if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if else {cycle=1; Print(j,j);} visited[v]=2; }//dfs void find_cycle() //判断是否有回路,有则输出邻接矩阵。visited 数组为全局变量。 {for (i=1;i<=n;i++) visited[i]=0; for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i); }//find_cycle

5、 将顶点放在两个集合 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<r) {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); }//是二部图 [算法讨论] 题目给的是连通无向图,若非连通,则算法要修改。 6、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。 当 n=1 时,只有一个根结点,由中序序列和后序序列可以确定这棵二叉树。 设当 n=m-1 时结论成立,现证明当 n=m 时结论成立。 设中序序列为 S1, S2, ?, Sm,后序序列是 P1,P2,?, Pm。 因后序序列最后一个元素 Pm 是根, 则在中序序列中可找到与 Pm 相等的结点(设二叉树中各结点互不相同)Si(1≤i≤m),因中 序序列是由中序遍历而得,所以 Si 是根结点,S1,S2,?,Si-1 是左子树的中序序列,而 Si+1,Si+2,?,Sm 是右子树的中序序列。 若 i=1,则 S1 是根,这时二叉树的左子树为空,右子树的结点数是 m-1,则{S2,S3,?,Sm} 和{P1,P2,?,Pm-1}可以唯一确定右子树,从而也确定了二叉树。 若 i=m,则 Sm 是根, 这时二叉树的右子树为空, 左子树的结点数是 m-1, 则{S1, S2, ?, Sm-1} 和{P1,P2,?,Pm-1}唯一确定左子树,从而也确定了二叉树。 最后,当 1<i<m 时,Si 把中序序列分成{S1,S2,?,Si-1}和{Si+1,Si+2,?,Sm}。由于后 序遍历是“左子树—右子树—根结点” ,所以{P1,P2,?,Pi-1}和{Pi,Pi+1,?Pm-1}是二叉树 的左子树和右子树的后序遍历序列。因而由{S1,S2,?,Si-1}和{P1,P2,?,Pi-1} 可唯一确定二叉树的左子树,由{Si+1,Si+2,?,Sm}和 {Pi,Pi+1,?,Pm-1}可唯一确定二叉树的右子树 。 7、两棵空二叉树或仅有根结点的二叉树相似;对非空二叉树,可判左右子树是否相似,采用 递归算法。 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 8、约瑟夫环问题(Josephus 问题)是指编号为 1、2、?,n 的 n(n>0)个人按顺时针方向 围坐成一圈,现从第 s 个人开始按顺时针方向报数,数到第 m 个人出列,然后从出列的下一 个人重新开始报数,数到第 m 的人又出列,?,如此重复直到所有的人全部出列为止。现要 求采用循环链表结构设计一个算法,模拟此过程。 #include<stdlib.h> 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=head; /*k1 为报数的起点*/ while (count!=s) /*找初始报数起点*/ {pre=k1; k1=k1->next; count++; } while(k1->next!=k1) /*当循环链表中的结点个数大于 1 时*/ { p=k1; /*从 k1 开始报数*/ count=1; while (count!=m) /*连续数 m 个结点*/ { pre=p; p=p->next; count++; } 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"); else {/*建表*/ head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/ head->data=n; r=head; for (i=n-1;i>0;i--) /*建立剩余 n-1 个结点*/ { p=(linklist)malloc(sizeof(listnode)); p->data=i; p->next=head; head=p; } r->next=head; /*生成循环链表*/ jose(head,s,m); /*调用函数*/ } } 9、给出折半查找的递归算法,并给出算法时间复杂度性分析。 10、假设 K1,?,Kn 是 n 个关键词,试解答: 试用二叉查找树的插入算法建立一棵二叉查找树,即当关键词的插入次序为 K1,K2,?,Kn 时,用算法建立一棵以 LLINK / RLINK 链接表示的二叉查找树。 11、因为后序遍历栈中保留当前结点的祖先的信息,用一变量保存栈的最高栈顶指针,每当 退栈时,栈顶指针高于保存最高栈顶指针的值时,则将该栈倒入辅助栈中,辅助栈始终保存 最长路径长度上的结点,直至后序遍历完毕,则辅助栈中内容即为所求。 void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度 {BiTree p=bt,l[],s[]; //l, s 是栈,元素是二叉树结点指针,l 中保留当前最长路径中的 结点 int i,top=0,tag[],longest=0; while(p || top>0) { while(p) {s[++top]=p;tag[top]=0; p=p->Lc;} //沿左分枝向下 if(tag[top]==1) //当前结点的右分枝已遍历 {if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时,才查看路径长度 if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;} //保留当前最长路径到 l 栈,记住最高栈顶指针,退栈 } else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下

}//while(p!=null||top>0) }//结束 LongestPath 12、假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单 有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可) 。 (注:图中不存在顶 点到自己的弧) 有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问;已访问但 其邻接点未访问完;已访问且其邻接点已访问完。下面用 0,1,2 表示这三种状态。前面已提 到,若 dfs(v)结束前出现顶点 u 到 v 的回边,则图中必有包含顶点 v 和 u 的回路。对应程 序中 v 的状态为 1,而 u 是正访问的顶点,若我们找出 u 的下一邻接点的状态为 1,就可以输 出回路了。 void Print(int v,int start ) //输出从顶点 start 开始的回路。 {for(i=1;i<=n;i++) if(g[v][i]!=0 && visited[i]==1 ) //若存在边(v,i) ,且顶点 i 的状态为 1。 {printf(“%d”,v); if(i==start) printf(“\n”); else Print(i,start);break;}//if }//Print void dfs(int v) {visited[v]=1; for(j=1;j<=n;j++ ) if (g[v][j]!=0) //存在边(v,j) if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if else {cycle=1; Print(j,j);} visited[v]=2; }//dfs void find_cycle() //判断是否有回路,有则输出邻接矩阵。visited 数组为全局变量。 {for (i=1;i<=n;i++) visited[i]=0; for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i); }//find_cycle 13、 连通图的生成树包括图中的全部 n 个顶点和足以使图连通的 n-1 条边, 最小生成树是边 上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每 删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍 连通,继续向下删;直到剩 n-1 条边为止。 void SpnTree (AdjList g) //用“破圈法”求解带权连通无向图的一棵最小代价生成树。 {typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数 node edge[]; 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]; }//for k=1; eg=e; while (eg>=n) //破圈,直到边数 e=n-1. {if (connect(k)) //删除第 k 条边若仍连通。 {edge[k].w=0; eg--; }//测试下一条边 edge[k],权值置 0 表示该边被删除 k++; //下条边 }//while }//算法结束。 connect()是测试图是否连通的函数,可用图的遍历实现, 14、 编写一个过程, 对一个 n×n 矩阵, 通过行变换, 使其每行元素的平均值按递增顺序排列。 15、给定 n 个村庄之间的交通图,若村庄 i 和 j 之间有道路,则将顶点 i 和 j 用边连接,边 上的 Wij 表示这条道路的长度,现在要从这 n 个村庄中选择一个村庄建一所医院,问这所医 院应建在哪个村庄, 才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的 算法,并应用该算法解答如图所示的实例。 (20 分)


相关文档

2012年西藏自治区数据库入门高级
2012西藏自治区数据库入门入门
2012年西藏自治区数据库入门入门
2012年西藏自治区数据库入门纲要
2012年西藏自治区学习数据库高级
2012年西藏自治区数据库入门大纲
2012年西藏自治区数据库入门基础
2012年西藏自治区数据库入门摘要
2012西藏自治区学习数据库入门
2012西藏自治区数据库入门深入
电脑版