2014湖南省分析数据库的考试题目基础

2、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。

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

3、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。

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

4、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）

  （1）下面所示的序列中哪些是合法的？

         A. IOIIOIOO     B. IOOIOIIO      C. IIIOIOIO     D. IIIOOIOO

  （2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

5、#define maxsize 栈空间容量                                    

   void InOutS(int s[maxsize])

      //s是元素为整数的栈，本算法进行入栈和退栈操作。

   {int top=0;             //top为栈顶指针，定义top=0时为栈空。  

for(i=1; i<=n; i++) //n个整数序列作处理。                 

     {scanf(“%d”,&x);    //从键盘读入整数序列。

      if(x!=-1)           // 读入的整数不等于-1时入栈。

         if(top==maxsize-1){printf(“栈满\\n”);exit(0);}

else s[++top]=x; //x入栈。                              

      else   //读入的整数等于-1时退栈。

       {if(top==0){printf(“栈空\\n”);exit(0);} 

else printf(“出栈元素是%d\\n”,s[top--])；}                

}

}//算法结

6、#define maxsize 栈空间容量                                    

   void InOutS(int s[maxsize])

      //s是元素为整数的栈，本算法进行入栈和退栈操作。

   {int top=0;             //top为栈顶指针，定义top=0时为栈空。  

for(i=1; i<=n; i++) //n个整数序列作处理。                 

     {scanf(“%d”,&x);    //从键盘读入整数序列。

      if(x!=-1)           // 读入的整数不等于-1时入栈。

         if(top==maxsize-1){printf(“栈满\\n”);exit(0);}

else s[++top]=x; //x入栈。                              

      else   //读入的整数等于-1时退栈。

       {if(top==0){printf(“栈空\\n”);exit(0);} 

else printf(“出栈元素是%d\\n”,s[top--])；}                

}

}//算法结

7、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）

有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用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

8、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。

9、二部图（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为结点个数）。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【

10、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。

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、给出折半查找的递归算法，并给出算法时间复杂度性分析。

13、编程实现单链表的就地逆置。

23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.

14、设有一个数组中存放了一个无序的关键序列K1、K2、…、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。

51. 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请编写出算法并简要说明算法思想。

15、有一种简单的排序算法，叫做计数排序（count  sorting）。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。

   (1) (3分)给出适用于计数排序的数据表定义;

   (2) (7分)使用Pascal或C语言编写实现计数排序的算法；

   (3) (4分)对于有n个记录的表，关键码比较次数是多少?

   (4) (3分)与简单选择排序相比较，这种方法是否更好?为什么?