当前位置:首页 >> 其它课程 >>

2011海南省学习数据库深入


1 、 (1)p->rchild (5)ADDQ(Q,p->rchild) 25. 26. (1)t->rchild!=null .(1)top++

(2)p->lchild

(3)p->lchild (3)N0++

(4)ADDQ(Q,p->lchild) (4)count(t

->lchild) (3)top++ (4)ipos (5)ppos+1

(2)t->rchild!=null (2)

(5)count(t->rchild) stack[top]=p->rchild (3)rpos– ipos (4)stack[top]=p->lchild 27. (1)*ppos // 根结点

( 2)rpos=ipos

2、设计一个尽可能的高效算法输出单链表的倒数第 K 个元素。 3、给定 n 个村庄之间的交通图,若村庄 i 和 j 之间有道路,则将顶点 i 和 j 用边连接,边上 的 Wij 表示这条道路的长度,现在要从这 n 个村庄中选择一个村庄建一所医院,问这所医院 应建在哪个村庄, 才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算 法,并应用该算法解答如图所示的实例。 (20 分) 4、 根据二叉排序树中序遍历所得结点值为增序的性质, 在遍历中将当前遍历结点与其前驱结 点值比较,即可得出结论,为此设全局指针变量 pre(初值为 null)和全局变量 flag,初值 为 true。若非二叉排序树,则置 flag 为 false。 #define true 1 #define false 0 typedef struct node {datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST( BTree t,int flag) // 判断二叉树是否是二叉排序树,本算法结束后,在调用程序中由 flag 得出结论。 { if(t!=null && flag) { Judgebst(t->llink,flag) ;// 中序遍历左子树 if (pre==null)pre=t;// 中序遍历的第一个结点不必判断 else if(pre->data<t->data )pre=t ;//前驱指针指向当前结点 else{flag=flase;} //不是完全二叉树 Judgebst ( t->rlink,flag) ; // 中序遍历右子树 }//JudgeBST 算法结束

5、假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列 可表示为仅由 I 和 O 组成的序列,称可以操作的序列为合法序列,否则称为非法序列。 ( 15 分) (1)下面所示的序列中哪些是合法的? A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO (2)通过对(1)的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回 true,否则返回 false(假定被判定的操作序列已存入一维数组中) 。 6、编程实现单链表的就地逆置。 23.在数组 A[1..n] 中有 n 个数据,试建立一个带有头结点的循环链表,头指针为 h ,要求 链中数据从小到大排列,重复的数据在链中只保存一个. 7、若第 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)

8、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历序列中的每个结 点都是 “局部根” 。 确定根后, 到二叉树的中序序列中, 查到该结点, 该结点将二叉树分为 “左 根右”三部分。若左、右子树均有,则层次序列根结点的后面应是左右子树的根;若中序序 列中只有左子树或只有右子树,则在层次序列的根结点后也只有左子树的根或右子树的根。 这样,定义一个全局变量指针 R,指向层次序列待处理元素。算法中先处理根结点,将根结 点和左右子女的信息入队列。然后,在队列不空的条件下,循环处理二叉树的结点。队列中 元素的数据结构定义如下: typedef struct { int lvl; int l,h; int f; //层次序列指针,总是指向当前“根结点”在层次序列中的位置 // 中序序列的下上界 // 层次序列中当前“根结点”的双亲结点的指针

int lr; // 1—双亲的左子树 2—双亲的右子树 }qnode; BiTree Creat(datatype in[],level[],int n) //由二叉树的层次序列 level[n]和中序序列 in[n]生成二叉树。 n 是二叉树的结点数 {if (n<1) {printf( “参数错误\n”); exit(0);} qnode s,Q[]; //Q 是元素为 qnode 类型的队列,容量足够大 init(Q); int R=0; //R 是层次序列指针,指向当前待处理的结点 BiTree p=(BiTree)malloc(sizeof(BiNode)); //生成根结点 p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点数据 for (i=0; i<n; i++) // 在中序序列中查找根结点,然后,左右子女信息入队列 if (in[i]==level[0]) break; if (i==0) //根结点无左子树,遍历序列的 1—n-1 是右子树 {p->lchild=null; s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s); } else if (i==n-1) // 根结点无右子树,遍历序列的 1 —n-1 是左子树 {p->rchild=null; s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); } else //根结点有左子树和右子树 {s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信息入队列 s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信息入队列 } while (!empty(Q)) //当队列不空,进行循环,构造二叉树的左右子树 { s=delqueue(Q); father=s.f; for (i=s.l; i<=s.h; i++) if (in[i]==level[s.lvl]) break;

p=(bitreptr)malloc(sizeof(binode)); if (s.lr==1) father->lchild=p; else father->rchild=p; // 让双亲的子女指针指向该结点 if (i==s.l) {p->lchild=null; // 处理无左子女 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); } else if (i==s.h) {p->rchild=null; } //处理无右子女

//申请结点空间 //填写该结点数据

p->data=level[s.lvl]; p->lchild=null; p->rchild=null;

s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); else{s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);//左子树有关信息入队 列 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); // 右子树有关信息入队列 } }//结束 while (!empty(Q)) return(p); }//算法结束 9、设有一个数组中存放了一个无序的关键序列 K1、K2、?、Kn。现要求将 Kn 放在将元素排 序后的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过 n。 51. 借助于快速排序的算法思想,在一组无序的记录中查找给定关键字值等于 key 的记录。 设此组记录存放于数组 r[l..h]中。若查找成功,则输出该记录在 r 数组中的位置及其值, 否则显示“not find ”信息。请编写出算法并简要说明算法思想。 10、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历序列中的每个结 点都是 “局部根” 。 确定根后, 到二叉树的中序序列中, 查到该结点, 该结点将二叉树分为 “左 根右”三部分。若左、右子树均有,则层次序列根结点的后面应是左右子树的根;若中序序 列中只有左子树或只有右子树,则在层次序列的根结点后也只有左子树的根或右子树的根。 这样,定义一个全局变量指针 R,指向层次序列待处理元素。算法中先处理根结点,将根结 点和左右子女的信息入队列。然后,在队列不空的条件下,循环处理二叉树的结点。队列中 元素的数据结构定义如下: typedef struct { int lvl; int l,h; int f; int lr; //层次序列指针,总是指向当前“根结点”在层次序列中的位置 // 中序序列的下上界 // 层次序列中当前“根结点”的双亲结点的指针 // 1—双亲的左子树 2—双亲的右子树

}qnode; BiTree Creat(datatype in[],level[],int n) //由二叉树的层次序列 level[n]和中序序列 in[n]生成二叉树。 n 是二叉树的结点数 {if (n<1) {printf( “参数错误\n”); exit(0);} qnode s,Q[]; //Q 是元素为 qnode 类型的队列,容量足够大 init(Q); int R=0; //R 是层次序列指针,指向当前待处理的结点

BiTree p=(BiTree)malloc(sizeof(BiNode)); for (i=0; i<n; i++) if (i==0)

//生成根结点

p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点数据 // 在中序序列中查找根结点,然后,左右子女信息入队列 if (in[i]==level[0]) break; //根结点无左子树,遍历序列的 1—n-1 是右子树 enqueue(Q,s); {p->lchild=null; s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; } else if (i==n-1) // 根结点无右子树,遍历序列的 1 —n-1 是左子树 {p->rchild=null; s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); } else //根结点有左子树和右子树 {s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信息入队列 s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信息入队列 } while (!empty(Q)) //当队列不空,进行循环,构造二叉树的左右子树 { s=delqueue(Q); father=s.f; for (i=s.l; i<=s.h; i++) if (in[i]==level[s.lvl]) break; p=(bitreptr)malloc(sizeof(binode)); //申请结点空间 p->data=level[s.lvl]; p->lchild=null; p->rchild=null; //填写该结点数据 if (s.lr==1) father->lchild=p; else father->rchild=p; // 让双亲的子女指针指向该结点 if (i==s.l) {p->lchild=null; // 处理无左子女 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); } else if (i==s.h) {p->rchild=null; } else{s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);//左子树有关信息入队 列 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); // 右子树有关信息入队列 } }//结束 while (!empty(Q)) return(p); }//算法结束 11、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。 当 n=1 时,只有一个根结点,由中序序列和后序序列可以确定这棵二叉树。 设当 n=m-1 时结论成立,现证明当 n=m 时结论成立。 设中序序列为 S1 , S2, ?, Sm, 后序序列是 P1,P2,?, Pm。 因后序序列最后一个元素 Pm 是根, //处理无右子女

s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);

则在中序序列中可找到与 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} 可唯一确定二叉树的右子树 。 12、#define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s 是元素为整数的栈,本算法进行入栈和退栈操作。 {int top=0; for(i=1; i<=n; i++) {scanf(“%d”,&x); //top 为栈顶指针,定义 top=0 时为栈空。 //n 个整数序列作处理。 //从键盘读入整数序列。

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--]);} } }//算法结 13、给出折半查找的递归算法,并给出算法时间复杂度性分析。 14、本题应使用深度优先遍历,从主调函数进入 dfs(v) 时 ,开始记数,若退出 dfs()前,已 访问完有向图的全部顶点(设为 n 个) ,则有向图有根,v 为根结点。将 n 个顶点从 1 到 n 编 号,各调用一次 dfs()过程,就可以求出全部的根结点。题中有向图的邻接表存储结构、记 顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图 g 的邻接表存储结构 参见上面第 2 题,这里只给出判断有向图是否有根的算法。 int num=0, visited[]=0 //num 记访问顶点个数 ,访问数组 visited 初始化。 const n= 用户定义的顶点数 ; AdjList g ; //用邻接表作存储结构的有向图 g。 void dfs(v) {visited [v]=1; num++; //访问的顶点数+1 if (num==n) {printf( “%d 是有向图的根。\n ”,v); num=0;}//if p=g[v].firstarc; while (p) {if (visied[p->adjvex]==0) dfs (p->adjvex);

p=p->next;} //while visited[v]=0; num--; //恢复顶点 v }//dfs void JudgeRoot() //判断有向图是否有根,有根则输出之。 {static int i ; for (i=1;i<=n;i++ ) //从每个顶点出发,调用 dfs() 各一次。 {num=0; visited[1..n]=0; dfs(i); } }// JudgeRoot 算 法 中 打 印 根 时, 输 出 顶 点在 邻 接 表 中的 序 号 ( 下标 ) , 若 要 输 出 顶 点 信息 , 可使 用 g[i].vertex 。

15、#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--]);} } }//算法结


相关文章:
2011年海南省学习数据库深入
2011海南省学习数据库深入_韩语学习_外语学习_教育专区。2011海南省学习数据库深入 1、设有一个数组中存放了一个无序的关键序列 K1、K2、?、Kn。现要求将 ...
2011海南省数据库入门深入
2011海南省数据库入门深入_公务员考试_资格考试/认证_教育专区。1 、已知有向图 G=(V,E) ,其中 V={V1,V2,V3,V4,V5,V6,V7} E={<V1,V2>,<V1,V3>...
2011海南省学习数据库加强
2011海南省学习数据库加强_公务员考试_资格考试/认证_教育专区。1、 编写一个过程, 对一个 n×n 矩阵, 通过行变换, 使其每行元素的平均值按递增顺序排列。 2...
2011年海南省学习数据库要领
2011海南省学习数据库要领_韩语学习_外语学习_教育专区。2011海南省学习数据库要领 1 、已知有向图 G=(V,E) ,其中 V={V1,V2,V3,V4,V5,V6,V7} E=...
2011海南省学习数据库基础
2011海南省学习数据库基础_公务员考试_资格考试/认证_教育专区。1、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归算法,栈 中存放二叉...
2011年海南省学习数据库高级
2011海南省学习数据库高级_韩语学习_外语学习_教育专区。2011海南省学习数据库高级 1、给定 n 个村庄之间的交通图,若村庄 i 和 j 之间有道路,则将顶点 i...
2011年海南省学习数据库入门
2011海南省学习数据库入门_韩语学习_外语学习_教育专区。2011海南省学习数据库入门 1、二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历序列中...
2011年海南省学习数据库高级
2011海南省学习数据库高级_数学_小学教育_教育专区。2011海南省学习数据库高级 1、约瑟夫环问题(Josephus 问题)是指编号为 1、2、?,n 的 n(n>0)个人按...
2013海南省学习数据库深入
2013海南省学习数据库深入_IT/计算机_专业资料。1、冒泡排序算法是把大的元素向上移(气泡的上浮) ,也可以把小的元素向下移(气泡的下 沉)请给出上浮和下沉过程...
2013年海南省学习数据库深入
2013年海南省学习数据库深入_数学_小学教育_教育专区。2013年海南省学习数据库...2015年海南省学习数据库... 暂无评价 2页 5下载券 2011年海南省学习数据库...
更多相关标签: