05到09年福建专升本数据结构真题详解

/ \\ B F

/ \\ \\ A D H / / \\ C G I \\ K / J 后序是：A C D B G J K I H F E

23．根据PRIM算法画出图2的最小生成树，要求画出从顶点1开始生成的过程。

解答：

四、 算法设计题（共2小题，每小题10 分，共20分）

24．下列程序将集合A和集合B归并成一个集合C，归并前集合A和集合B中的元素按非递减排列，归并后集合C的元素仍按非递减顺序排列，而且C不需

要新建节点空间。请完善程序。 typedef struct node{ ElemType data; struct node * next; }*LinkList

说明：*LinkList是指针类型，基类型是LNode。

void MergeSet(LinkList La, LinkList Lb){

LinkList pa , pb, pc , p;

pa=La; pb=Lb; pc=NULL;

while(_____pa!=NULL&& pb!=NULL __________){

if(pa->data<=pb->data){ if(pc!=NULL) {

______p->next=pa;________________ p=p->next; } else{ pc=pa; p=pc; }//if

_____pa=pa->next_______________; } else{

if(pc!=NULL) {

____p->next=pb;_______________

p=p->next; } else{ pc=pb; p=pc; }//if

____pb=pb->next_____________; }//if }//while

p->next=(pa!=NULL)?pa:pb; /*处理一个链表为空的情况*/ }

25．二叉排序（搜索）树t以二叉表为存储结构，请编写算法实现在该树上查找值为x的节点。 typedef int TreeItem; typedef struct btnode *btlink; typedef struct btnode{ TreeItem data;

Btlink lchild, rchild; /*左右孩子指针*/ }BiTNode

算法函数原型BiTNode Locate(BiTNode *t, TreeItem x) 解答：

BiTNode Locate(BiTNode *t, TreeItem x){

if(t = =NULL)return NULL:

if( x = = t-> data ) return *t; /* 注意*，因为返回类型是BiTNode*/ else if( x < t-> data )

return Locate(t->lchild, x); /*左子树*/ else