k=（3）_______;
ptr->llink=restore（ppos+1,（4）_______,k）;
ptr->rlink=restore（（5）_______+k,rpos+1,n-1-k）;
returnptr;
}
postorder（TNODE*ptr）
{if（ptr=NULL）return;
postorder（ptr->llink）;postorder（ptr->rlink）;printf（“%c”,ptr->info）;
}
28.证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
29.①试找出满足下列条件的二叉树
1）先序序列与后序序列相同2）中序序列与后序序列相同
3）先序序列与中序序列相同4）中序序列与层次遍历序列相同
30.设一棵二叉树的结点结构为（LLINK,INFO,RLINK）,ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。
31.设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
32.请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。
二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。
分析你的算法的时、空复杂度。
33.设两棵二叉树的的根结点地址分别为p和q，采用二叉链表的形式存储这两棵树上所有的结点。
请编写程序，判断它们是否相似。
34.一棵二叉树以二叉链表来表示，求其指定的某一层k（k>1）上的叶子结点的个数。
35.二叉树T的中序遍历序列和层次遍历序列分别是BAFDGCE和ABCDEFG，试画出该二叉树，并写出由二叉树的中序遍历序列和层次遍历序列确定二叉树的算法。
36.设二叉树的结点结构是（Lc,data,Rc），其中Lc、Rc分别为指向左、右子树根的指针，data是字符型数据。
试写出算法，求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。
2、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。
（注：
图中不存在顶点到自己的弧）
5、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?
试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。
（20分）
图1连通网G
1、对图1所示的连通网G，请用Prim算法构造其最小生成树（每选取一条边画一个图）。
4、已知有向图G=（V,E），其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,,,}
写出G的拓扑排序的结果。
37.在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。
编写一个算法完成下列功能：
（1）．建立有向图G的邻接表存储结构；
（2）．判断有向图G是否有根，若有，则打印出所有根结点的值。
38．二部图（bipartitegraph）G=（V，E）是一个能将其结点集V分为两不相交子集V1和V2=V-V1的无向图，使得：
V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。
（1）．请各举一个结点个数为5的二部图和非二部图的例子。
（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。
设G用二维数组A来表示，大小为n*n（n为结点个数）。
请在程序中加必要的注释。
若有必要可直接利用堆栈或队列操作。
【
39．我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。
所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。
请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。
注：
圈就是回路。
40.请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。
41.假设K1，…，Kn是n个关键词，试解答：
试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn时，用算法建立一棵以LLINK/RLINK链接表示的二叉查找树。
42.给出折半查找的递归算法，并给出算法时间复杂度性分析。
43.写出从哈希表中删除关键字为K的一个记录的算法，设哈希函数为H，解决冲突的方法为链地址法。
44.在用除余法作为散列函数、线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不致于断裂。
45.假设一棵平衡二叉树的每个结点都标明了平衡因子b,试设计一个算法，求平衡二叉树的高度。
46.有一个100*100的稀疏矩阵，其中1%的元素为非零元素，现要求用哈希表作存储结构。
（1）请你设计一个哈希表
（2）请写一个对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对你的算法所需时间和用一维数组（每个分量存放一个非零元素的行值，列值，和元素值）作存储结构时存取元素的算法.
2、画出向小顶堆中加入数据4,2,5,8,3,6,10,1时，每加入一个数据后堆的变化。
47.冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。
（注：
双向起泡排序即相邻两趟排序向相反方向起泡）
49.6.有一种简单的排序算法，叫做计数排序（countsorting）。
这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。
必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。
（1）（3分）给出适用于计数排序的数据表定义;
（2）（7分）使用Pascal或C语言编写实现计数排序的算法；
（3）（4分）对于有n个记录的表，关键码比较次数是多少?
（4）（3分）与简单选择排序相比较，这种方法是否更好?
为什么?
50.9．设有一个数组中存放了一个无序的关键序列K1、K2、…、Kn。
现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。
51.借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。
设此组记录存放于数组r[l..h]中。
若查找成功，则输出该记录在r数组中的位置及其值，否则显示“notfind”信息。
请编写出算法并简要说明算法思想。
52.二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注:
向量d可视为循环表），其原则为，先将r[l]赋给d[1]，再从r[2]记录开始分二路插入。
编写实现二路插入排序算法。
二、算法设计题（每题15分，共60分）
1、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。
假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。
#include
typedefchardatatype;
typedefstructnode{
datatypedata;
structnode*next;
}listnode;
typedeflistnode*linklist;
/*--------------------------------------------*/
/*删除单链表中重复的结点*/
/*--------------------------------------------*/
linklistdeletelist（linklisthead）
{listnode*p,*s,*q;
p=head->next;
while（p）
{s=p;
q=p->next;
while（q）
if（q->data==p->data）
{s->next=q->next;free（q）;
q=s->next;}
else
{s=q;/*找与P结点值相同的结点*/
q=q->next;
}
p=p->next;
}
returnhead;
}
3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。
现要求采用循环链表结构设计一个算法，模拟此过程。
#include
typedefintdatatype;
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<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）;/*调用函数*/
}
}
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_reverse
23、[题目分析]本题要求建立有序的循环链表。
从头到尾扫描数组A，取出A[i]（0<=iLinkedListcreat（ElemTypeA[],intn）
//由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点
{LinkedListh;
h=（LinkedList）malloc（sizeof（LNode））;//申请结点
h->next=h;//形成空循环链表
for（i=0;i{pre=h;
p=h->next;
while（p!
=h&&p->data{pre=p;p=p->next;}//查找A[i]的插入位置
if（p==h||p->data!
=A[i]）//重复数据不再输入
{s=（LinkedList）malloc（sizeof（LNode））;
s->data=A[i];pre->next=s;s->next=p;//将结点s链入链表中
}
}//for
return（h）;
}算法结束
3、假设以I和O分别表示入栈和出栈操作。
栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
（15分）
（1）A和D是合法序列，B和C是非法序列。
（2）设被判定的操作序列已存入一维数组A中。
intJudge（charA[]）
//判断字符数组A中的输入输出序列是否是合法序列。
如是，返回true，否则返回false。
{i=0;//i为下标。
j=k=0;//j和k分别为I和字母O的的个数。
while（A[i]!
=‘\0’）//当未到字符数组尾就作。
{switch（A[i]）
{case‘I’:
j++;break;//入栈次数增1。
case‘O’:
k++;if（k>j）{printf（“序列非法\n”）；exit（0）;}
}
i++;//不论A[i]是‘I’或‘O’，指针i均后移。
}
if（j!
=k）{printf（“序列非法\n”）；return（false）;}
else{printf（“序列合法\n”）；return（true）;}
}//算法结束。
5．#definemaxsize栈空间容量
vo
升级会员 