2010年广西壮族自治区数据基础

1、二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：

typedef struct

{ int lvl; //层次序列指针，总是指向当前“根结点”在层次序列中的位置

int l,h; //中序序列的下上界

int f; //层次序列中当前“根结点”的双亲结点的指针

int lr; // 1—双亲的左子树 2—双亲的右子树

}qnode;

BiTree Creat(datatype in[],level[],int n)

//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。 n是二叉树的结点数

{if (n<1) {printf(“参数错误\n”); exit(0);}

qnode s,Q[]; //Q是元素为qnode类型的队列，容量足够大

init(Q); int R=0; //R是层次序列指针，指向当前待处理的结点

BiTree p=(BiTree)malloc(sizeof(BiNode)); //生成根结点

p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点数据

for (i=0; i

if (in[i]==level[0]) break;

if (i==0) //根结点无左子树，遍历序列的1—n-1是右子树

{p->lchild=null;

s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s);

}

else if (i==n-1) //根结点无右子树，遍历序列的1—n-1是左子树

{p->rchild=null;

s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);

}

else //根结点有左子树和右子树

{s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信息入队列s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信息入队列

}

while (!empty(Q)) //当队列不空，进行循环，构造二叉树的左右子树

{ s=delqueue(Q); father=s.f;

for (i=s.l; i<=s.h; i++)

if (in[i]==level[s.lvl]) break;

p=(bitreptr)malloc(sizeof(binode)); //申请结点空间

p->data=level[s.lvl]; p->lchild=null; p->rchild=null; //填写该结点数据

if (s.lr==1) father->lchild=p;

else father->rchild=p； //让双亲的子女指针指向该结点

if (i==s.l)

{p->lchild=null; //处理无左子女

s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s);

}

else if (i==s.h)

{p->rchild=null; //处理无右子女

s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);

}

else{s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);//左子树有关信息入队列

s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); //右子树有关信息入队列

}

}//结束while (!empty(Q))

return(p);

}//算法结束

2、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。

#include

typedef char datatype;

typedef struct node{

datatype data;

struct node * next;

} listnode;

typedef listnode* linklist;

/*--------------------------------------------*/

/* 删除单链表中重复的结点 */

/*--------------------------------------------*/

linklist deletelist(linklist head)

{ listnode *p,*s,*q;

p=head->next;

while(p)

{s=p;

q=p->next;

while(q)

if(q->data==p->data)

{s->next=q->next;free(q);

q=s->next;}

else

{ s=q; /*找与P结点值相同的结点*/

q=q->next;

}

p=p->next;

}

return head;

}

3、本题应使用深度优先遍历，从主调函数进入dfs(v)时，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。

int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。

const n=用户定义的顶点数;

AdjList g ; //用邻接表作存储结构的有向图g。

void dfs(v)

{visited [v]=1; num++; //访问的顶点数＋1

if (num==n) {printf(“%d是有向图的根。\n”,v); num=0;}//if

p=g[v].firstarc;

while (p)

{if (visied[p->adjvex]==0) dfs (p->adjvex);

p=p->next;} //while

visited[v]=0; num--; //恢复顶点v

}//dfs

void JudgeRoot()

//判断有向图是否有根，有根则输出之。

{static int i ;

for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。

{num=0; visited[1..n]=0; dfs(i); }

}// JudgeRoot

算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。

4、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。

#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

k=(3)_______;

ptr->llink=restore(ppos+1, (4)_______,k );

ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);

return ptr;

}

postorder(TNODE*ptr)

{ if(ptr=NULL) return;

postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); }

本文来源：https://www.bwwdw.com/article/7sfl.html