2012年青海省数据概述大纲(2)

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==1) top--; //退栈
if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍历
}//结束while(bt!=null ||top>0)
return(null);//ｑ、p无公共祖先
｝//结束Ancestor

18、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.
typedef struct node
{int data; struct node *lchild,*rchild;}node;
int N2,NL,NR,N0;
void count(node *t)
{if (t->lchild!=NULL) if (1)___ N2++; else NL++;
else if (2)___ NR++; else (3)__ ;
if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____;
}
26.树的先序非递归算法。
void example(b)
btree *b;
{ btree *stack[20], *p；
int top;
if (b!=null)
{ top=1; stack[top]=b;
while (top>0)
{ p=stack[top]; top--;
printf(“%d”,p->data);
if (p->rchild!=null)
{(1)___; (2)___;
}
if (p->lchild!=null)
(3)___; (4)__;
}}}}

19、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。20分
void Hospital(AdjMatrix w,int n)
//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。
{for (k=1;k<=n;k++) //求任意两顶点间的最短路径
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (w[i][k]+w[k][j]<w[i][j
]) w[i][j]=w[i][k]+w[k][j];
m=MAXINT; //设定m为机器内最大整数。
for (i=1;i<=n;i++) //求最长路径中最短的一条。
{s=0;
for (j=1;j<=n;j++) //求从某村

2012年青海省数据概述大纲

庄i（1<=i<=n）到其它村庄的最长路径。
if (w[i][j]>s) s=w[i][j];
if (s<=m) {m=s; k=i;}//在最长路径中，取最短的一条。m记最长路径，k记出发顶点的下标。
Printf(“医院应建在%d村庄，到医院距离为%d\n”,i,m);
}//for
}//算法结束
对以上实例模拟的过程略。各行中最大数依次是9，9，6，7，9，9。这几个最大数中最小者为6，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。

1、对图1所示的连通网G，请用Prim算法构造其最小生成树（每选取一条边画一个图）。

20、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。
21、设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。
22、设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。
23、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）

24、设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。
void quickpass(int r[], int s, int t)
{
int i=s, j=t, x=r[s];
while(i<j){
while (i<j && r[j]>x) j=j-1; if (i<j) {r[i]=r[j];i=i+1;}
while (i<j && r[i]<x) i=i+1; if (i<j) {r[j]=r[i];j=j-1;}
}
r[i]=x;
}

25、 将顶点放在两个集合V1和V2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。
int BPGraph (AdjMatrix g)
//判断以邻接矩阵表示的图g是否是二部图。
{int s[]; //顶点向量，元素值表示其属于那个集合（值1和2表示两个集合）
int Q[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。
int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited
[]是访问数组
for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化，各顶点未确定属于那个集合
Q[1]=1; r=1; s[1]=1;//顶点1放入集合S1
while(f<r)
{v=Q[++f]; if (s[v]==1

2012年青海省数据概述大纲

) jh=2; else jh=1;//准备v的邻接点的集合号
if (!visited[v])
{visited[v]=1; //确保对每一个顶点，都要检查与其邻接点不应在一个集合中
for (j=1,j<=n;j++)
if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;} //邻接点入队列
else if (s[j]==s[v]) return(0);} //非二部图
}//if (!visited[v])
}//while
return(1); }//是二部图
[算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。

26、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。
#define MAX 100
typedef struct Node
{char info; struct Node *llink, *rlink; }TNODE;
char pred[MAX],inod[MAX];
main(int argc,int **argv)
{ TNODE *root;
if(argc<3) exit 0;
strcpy(pred,argv[1]); strcpy(inod,argv[2]);
root=restore(pred,inod,strlen(pred));
postorder(root);
}
TNODE *restore(char *ppos,char *ipos,int n)
{ TNODE *ptr； char *rpos; int k;
if(n<=0) return NULL;
ptr->info=(1)_______;
for((2)_______ ; rpos<ipos+n;rpos++) if(*rpos==*ppos) break;
k=(3)_______;
ptr->llink=restore(ppos+1, (4)_______,k );
ptr-&g …… 此处隐藏：3671字，全部文档内容请下载后查看。喜欢就下载吧 ……