2013年新疆维吾尔自治区数据加强
- 格式：pdf
- 大小：92.72 KB
- 文档页数：2
1、假设以I和O分别表示入栈和出栈操作。
栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
（15分）
（1）A和D是合法序列，B和C 是非法序列。
（2）设被判定的操作序列已存入一维数组A中。
int Judge(char A[])
//判断字符数组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);}
}//算法结束。
2、给定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++) //求从某村庄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算法构造其最小生成树（每选取一条边画一个图）。
3、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
4、本题要求建立有序的循环链表。
从头到尾扫描数组A，取出A[i]（0<=i<n）,然后到链表中去查找值为A[i]的结点，若查找失败，则插入。
LinkedList creat(ElemType A[],int n)
//由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点
{LinkedList h;
h=(LinkedList)malloc(sizeof(LNode));//申请结点
h->next=h; //形成空循环链表
for(i=0;i<n;i++)
{pre=h;
p=h->next;
while(p!=h && p->data<A[i])
{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);
}算法结束。
![[精品]新疆学生体质健康状况正逐步提升](https://imgs-1438308264.cos.ap-hongkong.myqcloud.com/aba35736443610661ed9ad51f01dc281e53a56c8.webp)
