山东校园网：www.xyw.me 山东招生考试资讯网 2．用克鲁斯卡尔所算法将下面的图构造成最小生成树，画出生成过程。
更多专升本资料 请到山东校园网：www.xyw.me
5
山东校园网：www.xyw.me 山东招生考试资讯网 四、程序填空（10分，每空1分） 1．将下面折半查找算法补充完整
算法说明：已知r[1…n]是n个记录的递增有序表，用折半查找法查找关键字为k的记录，若查找失败返回零；否则返回该记录的序号值。查找表顺序存储结构定义如下：
#define MAXSIZE 100 typedef struct {
keytype key； }
Nodetype；
typedef Nodetype Sqlist[MAXSIZE] 算法（C函数）：
int binsearch（Sqlist r， datatype k，int n） {
int low=1， high=n， mid while（______________________） {
___________________________； if（r[mid].key= =k）
_________________________；
else if（r[mid].key>k）
_________________________；
else
_________________________；
}
Return（0）； }
更多专升本资料 请到山东校园网：www.xyw.me 6
山东校园网：www.xyw.me 山东招生考试资讯网 2．将下面单链表的插入算法补充完整。 typedef ______________ {
DataType data； struct node *next； }LNode，*Linklist；
int listinsert（LinkList head，int i，DataType x） {
LinkList p=head，s； int j=0;
while（p！=NULL&&j ______________________； j＋＋； } if（p= =NULL）return（0）； s=_________________malloc（sizeof（LNode））； s->data=x； ______________________； ______________________； return（1）； } 更多专升本资料 请到山东校园网：www.xyw.me 7 山东校园网：www.xyw.me 山东招生考试资讯网 五、算法设计（10分） 已知S为顺序栈。写出S的存储结构类型描述。编写算法实现将元素x入栈操作Push（S，x），入栈成功返回1，否则返回0和删除栈顶元素的出栈操作Pop（S）出栈成功返回1，否则返回0。 更多专升本资料 请到山东校园网：www.xyw.me 8
