内容发布更新时间 : 2024/12/25 14:49:49星期一 下面是文章的全部内容请认真阅读。
0*/
{if(t!=NULL)
{if((t->lchild==NULL)&&(t->rchild==NULL))________; countleaf(t->lchild,&count); ________ } }
13.以下程序是二叉链表树中序遍历的非递归算法,请填空使之完善。二叉树链表的结点类型的定义如下:
typedef struct node /*C语言/
{char data; struct node *lchild,*rchild;}*bitree;
void vst(bitree bt) /*bt为根结点的指针*/ { bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/
while(p || !empty(s)) /*栈s不为空*/
if(p) { push (s,p); (1)___ ; } /*P入栈*/
else { p=pop(s); printf(“%c”,p->data);(2)__ __; }/*栈顶元素出栈*/
}
14.二叉树存储结构同上题,以下程序为求二叉树深度的递归算法,请填空完善之。
int depth(bitree bt) /*bt为根结点的指针*/ {int hl,hr;
if (bt==NULL) return((1)_ __); hl=depth(bt->lchild); hr=depth(bt->rchild);
if((2)_ __) (3)_ ____; return(hr+1); }
15.将二叉树bt中每一个结点的左右子树互换的C语言算法如下,其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队,出队和判别队列是否为空的函数,请填写算法中得空白处,完成其功能。
typedef struct node
{int data ; struct node *lchild, *rchild; }btnode; void EXCHANGE(btnode *bt) {btnode *p, *q;
if (bt){ADDQ(Q,bt);
while(!EMPTY(Q))
{p=DELQ(Q); q=(1)_ __; p->rchild=(2)_ __; (3)__ _=q;
if(p->lchild) (4)_ __; if(p->rchild) (5)_ __; }
} }//
24
四、应用题
1.树和二叉树之间有什么样的区别与联系?
2.分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
3.分别给出下图所示二叉树的先根、中根和后根序列。
4.一个深度为L的满K叉树有以下性质:第L层上的结点都是叶子结点,其余各层上每个结点都有K棵非空子树,如果按层次顺序从1开始对全部结点进行编号,求:
1)各层的结点的数目是多少?
2)编号为n的结点的双亲结点(若存在)的编号是多少?
3)编号为n的结点的第i 个孩子结点(若存在)的编号是多少?
4)编号为n的结点有右兄弟的条件是什么?如果有,其右兄弟的编号是多少? 请给出计算和推导过程。
5.将下列由三棵树组成的森林转换为二叉树。(只要求给出转换结果) D G A J H I E B C K N O L M F P 6.设二叉树BT的存储结构如下:
1 2 3 4 5 6 7 8 9 10 Lchild Data Rchild 0 0 J H 0 0 2 F 0 3 D 7 B 5 A 8 C 0 10 1 I 0 0 E G 9 4 0 0 0 其中BT为树根结点的指针,其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data
为结点的数据域。试完成下列各题:
(l)画出二叉树BT的逻辑结构;
(2)写出按前序、中序、后序遍历该二叉树所得到的结点序列; (3)画出二叉树的后序线索树。 7.设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码,使得上述正文
的编码最短。
25
五、算法设计题
1.要求二叉树按二叉链表形式存储,
(1)写一个建立二叉树的算法。
(2)写一个判别给定的二叉树是否是完全二叉树的算法。
完全二叉树定义为:深度为K,具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。 2.设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针,p和q分别为指向该二叉树中任意两个结点的指针,试编写一算法ANCESTOR(ROOT,p,q,r),该算法找到p和q的最近共同祖先结点r。
3.有一二叉链表,试编写按层次顺序遍历二叉树的算法。
4.已知二叉树按照二叉链表方式存储,利用栈的基本操作写出先序遍历非递归形式的算法。
5.对于二叉树的链接实现,完成非递归的中序遍历过程。
6.试写出复制一棵二叉树的算法。二叉树采用标准链接结构。。
7.请设计一个算法,要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表,表头指针为head。 二叉树按二叉链表方式存储,链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。
8.已知二叉树以二叉链表存储,编写算法完成:对于树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间。
9.设一棵二叉树的根结点指针为T,C为计数变量,初值为0,试写出对此二叉树中结点计数的算法:BTLC(T,C)。
10.分别写出算法,实现在中序线索二叉树T中查找给定结点*p在中序序列中的前驱与后继。在先序线索二叉树T中,查找给定结点*p在先序序列中的后继。在后序线索二叉树T中,查找给定结点*p在后序序列中的前驱。
26
习题七 图
一、单项选择题
1.设有无向图G=(V,E)和G’=(V’,E’),如G’为G的生成树,则下面不正确的说法是( )
A.G’为G的子图 B.G’为G的连通分量 C.G’为G的极小连通子图且V’=V D.G’是G的无环子图 2.任何一个带权的无向连通图的最小生成树( )
A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3.以下说法正确的是( )
A.连通分量是无向图中的极小连通子图。 B.强连通分量是有向图中的极大强连通子图。
C.在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧。 D.对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点,则该图一定是完全图。 4.图中有关路径的定义是( )。
A.由顶点和相邻顶点序偶构成的边所形成的序列 B.由不同顶点所形成的序列 C.由不同边所形成的序列 D.上述定义都不是 5.设无向图的顶点个数为n,则该图最多有( )条边。
2
A.n-1 B.n(n-1)/2 C. n(n+1)/2 D.0 E.n 6.要连通具有n个顶点的有向图,至少需要( )条边。
A.n-l B.n C.n+l D.2n
7.在一个无向图中,所有顶点的度数之和等于所有边数( )倍,在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的( )倍。
A.1/2 B.2 C.1 D.4 8.下列哪一种图的邻接矩阵是对称矩阵?( )
A.有向图 B.无向图 C.AOV网 D.AOE网 9. 下列说法不正确的是( )。
A.图的遍历是从给定的源点出发每一个顶点仅被访问一次 B.遍历的基本算法有两种:深度遍历和广度遍历 C.图的深度遍历不适用于有向图 D.图的深度遍历是一个递归过程
10.下面哪一方法可以判断出一个有向图是否有环(回路):
A.深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
11. 在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为( )。
23
A. O(n) B. O(n+e) C. O(n) D. O(n) 12.已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},
E={
A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7 C.V1,V3,V4,V5,V2,V6,V7 D.V1,V2,V5,V3,V4,V6,V7
13. 在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是( )。
27
A.G中有弧
A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C.最长回路 D.最短回路 15.下列关于AOE网的叙述中,不正确的是( )。
A.关键活动不按期完成就会影响整个工程的完成时间
B.任何一个关键活动提前完成,那么整个工程将会提前完成 C.所有的关键活动提前完成,那么整个工程将会提前完成 D.某些关键活动提前完成,那么整个工程将会提前完成
二、填空题
1.具有10个顶点的无向图,边的总数最多为______。
2. 设无向图 G 有n 个顶点和e 条边,每个顶点Vi 的度为di(1<=i<=n),则e=______
3. 在有n个顶点的有向图中,若要使任意两点间可以互相到达,则至少需要______条弧。
4.下图中的强连通分量的个数为______个。
5.N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。
6. 在有向图的邻接矩阵表示中,计算第I个顶点入度的方法是__ ____。
7. 对于一个具有n个顶点e条边的无向图的邻接表的表示,则表头向量大小为______,邻接表的边结点个数为______。
8. 已知一无向图G=(V,E),其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图,得到的序列为abecd,则采用的是______遍历方法。
9.构造连通网最小生成树的两个典型算法是__ ____。
10. 有向图G可拓扑排序的判别条件是__ ____。 11. Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按__ ____次序依次产生,该算法弧上的权出现___ ___情况时,不能正确产生最短路径。
12.有向图G=(V,E),其中 V(G)={0,1,2,3,4,5},用三元组表示弧及弧上的权d.E(G)为{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>},则
28