kl800.com省心范文网

2013新疆维吾尔自治区数据库考试含答案基础


1、假设 K1,?,Kn 是 n 个关键词,试解答: 试用二叉查找树的插入算法建立一棵二叉查找树,即当关键词的插入次序为 K1,K2,?,Kn 时,用算法建立一棵以 LLINK / RLINK 链接表示的二叉查找树。 2、请设计一个算法,要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表,表 头指针为 head。二叉树按二叉链表方式存储,链接时用叶子结点的右指针域来存放单链表指 针。分析你的算法的时、空复杂度。 3、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。 当 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}可唯一确定二叉树的右子树。 4、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 5、 假设以邻接矩阵作为图的存储结构, 编写算法判别在给定的有向图中是否存在一个简单有 向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可) 。 (注:图中不存在顶点 到自己的弧) 有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问;已访问但 其邻接点未访问完;已访问且其邻接点已访问完。下面用 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 6、 编写一个过程, 对一个 n×n 矩阵, 通过行变换, 使其每行元素的平均值按递增顺序排列。


赞助商链接

2013新疆维吾尔自治区高考试卷含解析试题及答案

2013新疆维吾尔自治区高考试卷含解析试题及答案_韩语学习_外语学习_教育专区。2013新疆维吾尔自治区高考试卷含解析试题及答案 1、下列词语中加点的字,每对读音都不...

2015新疆维吾尔自治区公务员考试公共基础知识试题及答案

2015新疆维吾尔自治区公务员考试公共基础知识试题及答案_韩语学习_外语学习_教育专区。2015新疆维吾尔自治区公务员考试公共基础知识试题及答案 ...

2015新疆维吾尔自治区公共基础知识试题及答案

2015新疆维吾尔自治区公共基础知识试题及答案_韩语学习_外语学习_教育专区。2015新疆维吾尔自治区公共基础知识试题及答案 1、 “假定一切物质都具有在本质上跟感觉相近...

新疆维吾尔自治区新疆生产建设兵团 2016年初中学业水平...

2016年初中学业水平考试语文(含答案)_语文_初中教育...年初中学业水平考试试题卷 语 一、基础知识与...2013新疆维吾尔族自治区... 9页 2下载券 新疆维吾尔...

2015新疆维吾尔自治区教师资格证考试试题及答案

2015新疆维吾尔自治区教师资格证考试试题及答案_韩语学习_外语学习_教育专区。2015...2014新疆维吾尔自治区教... 3页 5下载券 2013新疆维吾尔自治区教... 暂无评...

新疆维吾尔自治区新疆生产建设兵团2017年中考语文试卷(...

新疆维吾尔自治区新疆生产建设兵团2017年中考语文试卷(word版含答案) - 新疆维吾尔自治区新疆生产建设兵团 2017 年初中学业水平考试 语文试题卷 一、基础知识与运用(...

2013年新疆维吾尔自治区、生产建设兵团中考语文真题及...

2013新疆维吾尔自治区、生产建设兵团中考语文真题及答案_中考_初中教育_教育专区 暂无评价|0人阅读|0次下载2013新疆维吾尔自治区、生产建设兵团中考语文真题及答案...

2013年新疆维吾尔自治区、新疆生产建设兵团中考语文试...

2013新疆维吾尔自治区、新疆生产建设兵团中考语文试题含答案 - 2013 年中考真題 新疆维吾尔自治区、新疆生产建设兵团 2013 年初中学业水平考试 语文试题卷 一、积累...

2013年新疆维吾尔自治区、新疆生产建设兵团中考数学试...

2013新疆维吾尔自治区、新疆生产建设兵团中考数学试题(word版,含答案) - 新疆维吾尔族自治区、新疆生产建设兵团 2013 年初中学业水平考试 数学试卷 一、选择题(本...

[真卷]2013年新疆维吾尔自治区小升初数学模拟试卷含答案

[真卷]2013新疆维吾尔自治区小升初数学模拟试卷含答案 - 2013新疆维吾尔自治区小升初数学模拟试卷(1) 一、填空题(25 分) 1. (3 分)1.6 时= 时分;...