文档文库
手机版
投诉建议
热门搜索： 心得体会 演讲稿 思想汇报
首页 > 2015山东省数据结构分析高级

2015山东省数据结构分析高级

发布时间：   来源：文档文库   
小 中 大
字号：
手机查看
1、设计一个尽可能的高效算法输出单链表的倒数第K个元素。
2、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q的最近共同祖先结点r,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p和q的最近公共祖先。
typedefstruct
{BiTreet;inttag;//tag=0表示结点的左子女已被访问，tag=1表示结点的右子女已被访问}stack;
stacks[],s1[];//栈，容量够大
BiTreeAncestor(BiTreeROOT,p,q,r//求二叉树上结点p和q的最近的共同祖先结点r。{top=0;bt=ROOT;while(bt!=null||top>0
{while(bt!=null&&bt!=p&&bt!=q//结点入栈{s[++top].t=bt;s[top].tag=0;bt=bt->lchild;}//沿左分枝向下
if(bt==p//不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点{for(i=1;i<=top;i++s1[i]=s[i];top1=top;}//将栈s的元素转入辅助栈s1保存if(bt==q//找到q结点。
for(i=top;i>0;i--//；将栈中元素的树结点到s1去匹配{pp=s[i].t;
for(j=top1;j>0;j--
if(s1[j].t==pp{printf(“p和q的最近共同的祖先已找到”；return(pp;}｝
while(top!=0&&s[top].tag==1top--;//退栈
if(top!=0｛s[top].tag=1;bt=s[top].t->rchild;｝//沿右分枝向下遍历}//结束while(bt!=null||top>0return(null;//ｑ、p无公共祖先｝//结束Ancestor
3、设一棵二叉树的结点结构为(LLINK,INFO,RLINK,ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。4、编程实现单链表的就地逆置。
23．在数组A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.
5、有一种简单的排序算法，叫做计数排序（countsorting）。这种排序算法对一个待排序的表(用数组表示进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。(1(3分给出适用于计数排序的数据表定义;

(2(7分使用Pascal或C语言编写实现计数排序的算法；(3(4分对于有n个记录的表，关键码比较次数是多少?(4(3分与简单选择排序相比较，这种方法是否更好?为什么?
6、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能：（1）．建立有向图G的邻接表存储结构；（2）．判断有向图G是否有根，若有，则打印出所有根结点的值。
7、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。当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时，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}可唯一确定二叉树的右子树。
8、4、voidLinkList_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_reverse9、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。
10、约瑟夫环问题（Josephus问题）是指编号为1、2、„，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一

个人重新开始报数，数到第m的人又出列，„，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。#includetypedefintdatatype;typedefstructnode{datatypedata;structnode*next;}listnode;
typedeflistnode*linklist;
voidjose(linklisthead,ints,intm{linklistk1,pre,p;intcount=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(
{linklisthead,p,r;intn,s,m,i;printf("n=";scanf("%d",&n;printf("s=";scanf("%d",&s;printf("m=",&m;scanf("%d",&m;

if(n<1printf("n<0";else{/*建表*/
head=(linklistmalloc(sizeof(listnode;/*建第一个结点*/head->data=n;r=head;
for(i=n-1;i>0;i--/*建立剩余n-1个结点*/{p=(linklistmalloc(sizeof(listnode;p->data=i;p->next=head;head=p;}
r->next=head;/*生成循环链表*/jose(head,s,m;/*调用函数*/}}
11、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。29.①试找出满足下列条件的二叉树
1）先序序列与后序序列相同2）中序序列与后序序列相同3）先序序列与中序序列相同4）中序序列与层次遍历序列相同
12、(1p->rchild(2p->lchild(3p->lchild(4ADDQ(Q,p->lchild(5ADDQ(Q,p->rchild
25.(1t->rchild!=null(2t->rchild!=null(3N0++(4count(t->lchild(5count(t->rchild
26..(1top++(2stack[top]=p->rchild(3top++(4stack[top]=p->lchild
27.(1*ppos//根结点（2）rpos=ipos(3rpos–ipos(4ipos(5ppos+1
13、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）
（1）下面所示的序列中哪些是合法的？
A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
14、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。当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时，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}可唯一确定二叉树的右子树。
15、二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：typedefstruct
{intlvl;//层次序列指针，总是指向当前“根结点”在层次序列中的位置intl,h;//中序序列的下上界
intf;//层次序列中当前“根结点”的双亲结点的指针intlr;//1—双亲的左子树2—双亲的右子树}qnode;
BiTreeCreat(datatypein[],level[],intn
//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。n是二叉树的结点数{if(n<1{printf(“参数错误\n”;exit(0;}
qnodes,Q[];//Q是元素为qnode类型的队列，容量足够大init(Q;intR=0;//R是层次序列指针，指向当前待处理的结点BiTreep=(BiTreemalloc(sizeof(BiNode;//生成根结点p->data=level[0];p->lchild=null;p->rchild=null;//填写该结点数据
for(i=0;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;}
elseif(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=(bitreptrmalloc(sizeof(binode;//申请结点空间
p->data=level[s.lvl];p->lchild=null;p->rchild=null;//填写该结点数据if(s.lr==1father->lchild=p;
elsefather->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;}
elseif(i==s.h
{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(Qreturn(p;}//算法结束

本文来源：https://www.2haoxitong.net/k/doc/b319b5c327284b73f24250ea.html

《2015山东省数据结构分析高级.doc》
将本文的Word文档下载到电脑，方便收藏和打印
推荐度：
点击下载文档

文档为doc格式
相
关
案
例

相关推荐

推荐内容

2011二级山东省建造师市政考试答题技巧 青岛版数学七年级下册第十四章《位置与坐标》复习导学案 招新工作与讲座注意事项 模拟卷公司2001年度业务招待费使用情况报告 编出大快乐 拒绝室内桑拿天 脑力冲击波答案 卫浴装修5大要点须牢记哪些 泉州实验中学2014届高三上学期第四次月考英语试题 形容骄傲的词语有哪些
网站内容来自网络，如有侵权请联系我们，立即删除！ Copyright © 范文写作网京ICP备16605803号