2009山东专升本真题 数据结构

山东校园网：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