《数据结构 - C语言描述》习题及答案 耿国华 下载本文

(2)找结点的中序后继结点

BiTNode *InSucc (BiTNode *p)

/*在中序线索二叉树中查找p的中序后继结点,并用succ指针返回结果*/ { if (p->Rtag= =1) succ = p->RChild; /*直接利用线索*/ else

{/*在p的右子树中查找“最左下端”结点*/ for ( q=p->RChild; q->Ltag= =0; q=q->LChild); succ= q; }

return (succ); }

(3) 找结点的先序后继结点

BiTNode *PreSucc (BiTNode *p)

/*在先序线索二叉树中查找p的先序后继结点,并用succ指针返回结果*/ { if (p->Ltag= =0) succ = p->LChild; else succ= p->RChild; return (succ); }

(4) 找结点的后序前驱结点

BiTNode *SuccPre (BiTNode *p)

/*在后序线索二叉树中查找p的后序前驱结点,并用pre指针返回结果*/ { if (p->Ltag= =1) pre = p->LChild; else pre= p->RChild; return (pre); }

6.21已知二叉树按照二叉链表方式存储,试利用栈的基本操作写出先序遍历非递归形式的算法。 【解答】

Void PreOrder(BiTree root) /*先序遍历二叉树的非递归算法*/ {

InitStack(&S); p=root;

while(p!=NULL || !IsEmpty(S) )

{ if(p!=NULL) {

Visit(p->data); push(&S,p); p=p->Lchild;

}

else {

Pop(&S,&p); p=p->RChild; } } }

6.24已知二叉树按照二叉链表方式存储,编写算法,将二叉树左右子树进行交换。 【解答】 算法(一)

Void exchange ( BiTree root ) {

p=root;

if ( p->LChild != NULL || p->RChild != NULL ) {

temp = p->LChild; p->LChild = p->RChild;

算法(二)

Void exchange ( BiTree root ) {

p=root; }

}

p->RChild = temp; exchange ( p->LChild ); exchange ( p->RChild );

if ( p->LChild != NULL || p->RChild != NULL ) {

exchange ( p->LChild ); exchange ( p->RChild );

temp = p->LChild;

p->LChild = p->RChild;

p->RChild = temp;

}

}

第七章 图

习 题

7.1

已知如图所示的有向图,请给出该图的: (1) 每个顶点的入度、出度; (2) 邻接矩阵; (3) 邻接表; (4) 逆邻接表; (5) 十字链表; (6) 强连通分量。

题1图

题2图

3 6 3 2 4 6 5 4 2 1 5 1

7.2 已知如图所示的无向图,请给出该图的:

(1) 邻接多重表;(要求每个边结点中第一个顶点号小于第二个顶点号,且每个顶点

的各邻接边的链接顺序,为它所邻接到的顶点序号由小到大的顺序。)

(2) 从顶点1开始,深度优先遍历该图所得顶点序列和边的序列;(给出深度优先搜

索树)

(3) 从顶点1开始,广度优先遍历该图所得顶点序列和边的序列。(给出广度优先搜

索树)

7.3 7.4

5 1 3 4 3 4 6 3 1 2 3 4 4 7 5 5 6 4 0 6 2 8 2 9

图7.31 题7.3 用图

已知如图7.31所示的AOE-网,试求:

(1) 每个事件的最早发生时间和最晚发生时间; (2) 每个活动的最早开始时间和最晚开始时间; (3) 给出关键路径。

7.5 7.6 7.7

15 4 10 2 2 20 6 20 10 30 4 15 5 10 3 1

图7.30 题7.4 用图