10．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树。
BiTree Create(dataype A[],int i)
/*n个结点的完全二叉树存于一维数组A中，据此建立以二叉链表表示的完全二叉树,初始调用时,i=1*/
{ BiTree T; if (i<=n)
{ T=(BiTree)malloc(sizeof(BiTNode));
T->data=A[i];
if (2*i>n) T->lchild=NULL; else T->lchild=Create(A,2*i); if (2*i+1>n) T->rchild=NULL;
else T->rchild=Create(A,2*i+1); }
return (T); }
11．编写算法判定两棵二叉树是否相似。所谓两棵二叉树s和t相似，即要么它们都为空或都只有一个结点，要么它们的左右子树都相似。 【提示】两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。
int Similar(BiTree s, BiTree t)
{ if(s==NULL && q==NULL) return (1);
else if(!s && t || s && !t) return (0);
else return(Similar(s->lchild,t->lchild) && Similar(s->rchild,t->rchild)) }
12．写出用逆转链方法对二叉树进行先序遍历的算法。
【提示】用逆转链的方法遍历二叉树，不需要附加的栈空间，而是在遍历过程中沿结点的左右子树下降时，临时改变结点lchild或者rchild的值，使之指向双亲，从而为以后的上升提供路径，上升时再将结点的lchild或者rchild恢复。
typedef struct tnode { datatype data;
int tag; /*tag的值初始为0，进入左子树时置1，从左子树回来时，再恢复为0*/ struct tnode *lchild, *rchild; } Bnode, *Btree;
void PreOrder(Btree bt)
{ Bnode *r, *p, *q; /*p指向当前结点，r指向p的双亲，q指向要访问的下一结点*/ if(bt==NULL) return; p=bt; r= NULL: while( p)
{ Visit(p); /*访问p所指结点*/ if(p->lchild) /*下降进入左子树*/ { p->tag=1; q=p->lchild; q=p->lchild=r; r=p; p=q; } else if(p->rchild) /*下降进入右子树*/
{ q=p->rchild; p->rchild=r; r=p; p=q; }
else { /*上升*/
whle((r&&t->tag==0) || (r&&t->tag==1&&r->rchild==NULL))
{ if(r&&t->tag==0)
{ q=r->rchild; r->rchild=p; p=r; r=q;} /*从右子树回来*/
else { r->tag=0; q=r->lchild;
r->lchild=p; p=r; r=q;} /*从左子树回来*/
if (r==NULL) return;
else { r->tag=0; q=r->rchild;
r->rchild= r->lchild; r->lchild=p; p=q;
} /*从左子树回来，准备进入右子树*/
}
}
} }
13．对以孩子－兄弟链表表示的树编写计算树的深度的算法。 【提示】采用递归算法实现。
树的深度＝
{ if (T==NULL )
0
若树为空
Max（第一棵子树的深度＋1，兄弟子树的深度） 若树非空 return ( 0 );
/*若树为空，返回0*/
int high(CSTree T)
else { h1=high (t->lchild ); return(max(h1+1,h2)); } }
14．对以孩子链表表示的树编写计算树的深度的算法。 【提示】采用递归算法实现。 1 若根结点没有子树
树的深度＝
max(所有子树的深度)＋1 若根结点有子树
#define MAXNODE 树中结点的最大个数
int high(SNode t[MAXNODE],int j) { if(t[j].firstchild==NULL) return(1); else { p=t[i].firstchild;
max=high(t,p->data); p=p->nextchild; while(p)
{ h=high(t,p->data); if(h>max) max=h; p=p->nextchild;
/*若根结点没有子树*/
/**h1为T的第一棵子树的深度*/
/*h2为t的兄弟子树的深度*/
h2=high(t->nextsibling );
}
return(max+1);
}
}
15．对以双亲链表表示的树编写计算树的深度的算法。
【提示】从每一个结点开始，从下向上搜索至根结点，记录结点的层次数，其中的最大值就是树的深度。
int high(PNode t[ ], int n) /*求有n个结点的树t的深度*/ { maxh=0; for (i=0 ;i { if (t[i].parent==-1 ) h=1; else { s=i; h=1; while (t[s].parent != -1 ) { s=t[s].parent ; h++;} } } } return(maxh) ; if (h>maxh) maxh=h; 6.3.1 选择题 1．n条边的无向图的邻接表的存储中，边结点的个数有（A）。 A．n B．2n C．n/2 D．n*n 2．n条边的无向图的邻接多重表的存储中，边结点的个数有（A）。 A．n B．2n C．n/2 D．n*n 3．下列哪一种图的邻接矩阵是对称矩阵？（B）。 A．有向图 B．无向图 C．AOV网 D．AOE网 4．最短路径的生成算法可用（C）。 A．普里姆算法 B．克鲁斯卡尔算法 C．迪杰斯特拉算法 D．哈夫曼算法 5．一个无向图的邻接表如下图所示： 序号 vertex firstedge 0 1 2 3 v1 v2 v3 v4 1 0 1 0 ∧ 3 2 ∧ 3 ∧ 1 ∧ （1）从顶点v0出发进行深度优先搜索，经历的结点顺序为（B）。 A．v0, v3, v2, v1 B．v0, v1, v2, v3 C．v0, v2, v1, v3 D．v0, v1, v3, v2 （2）从顶点V0出发进行广度优先搜索，经历的结点顺序为（D）。 A．v0, v3, v2, v1 B．v0, v1, v2, v3 C．v0, v2, v1, v3 D．v0, v1, v3, v2 6．设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为（D）。 A．O (nlog2e) B．O (en ) C．O ( elog2n) D．O (n+e) 7．含有n个顶点e条边的无向连通图，利用Kruskal算法生成最小生成树，其时间复杂度为（A）。 A．O (elog2e) B．O (en ) C．O ( elog2n) D．O (nlog2n) 8．关键路径是事件结点网络中（A）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长的回路 D．最短的回路 9．下面关于求关键路径的说法不正确的是（C）。 A．求关键路径是以拓扑排序为基础的 B．一个事件的最早开始时间与以该事件为尾的弧的活动最早开始时间相同 C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D．关键活动一定位于关键路径上 10．有10个结点的无向图至少有（B）条边才能确保其是连通图。 A．8 B．9 C．10 D．11 6.3.2 判断题 1．求最小生成树的Prim算法在边较少、结点较多时效率较高。（×） 2．图的最小生成树的形状可能不唯一。（√） 3．用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。（√） 4．邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（×） 5．任何有向网络（AOV-网络）拓扑排序的结果是唯一的。（×） 6．有回路的图不能进行拓扑排序。（√） 7．存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。（√） 8．十字链表可以存储无向图和有向图。（×） 9．任何无向图都存在生成树。（×） 10．若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（√） 11．连通分量是无向图中的极小连通子图。（×） 12．强连通分量是有向图中的极大强连通子图。（√） 13．用邻接矩阵A表示图，判定任意两个结点vi和vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为0即可。（√） 14．缩短关键路径上活动的工期一定能够缩短整个工程的工期。（×） 15．AOE网中一定只有一条关键路径。（×） 6.3.3 简答题 1．对于如图1所示的有向图，试给出： （1）每个顶点的入度和出度； （2）邻接矩阵； （3）邻接表； （4）逆邻接表； ① ⑤ ⑥ ② （图1） ④ ③
相关推荐：
loading