4. 设某棵二叉树中度数为 0 的结点数为 N
0
,度数为 1 的结点数为 N
1
,则该二叉树中度
数为 2 的结点数为___N
0
-1___;若采用二叉链表作为该二叉树的存储结构,则该二叉
树中共有___2N
0
+N
1
___个空指针域。
5. 设 某 无 向 图 中 顶 点 数 和 边 数 分 别 为 n 和 e , 所 有 顶 点 的 度 数 之 和 为 d , 则
e=__d/2__。
6. 设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选
法建立的初始堆为___________________________。
8. 已知一有向图的邻接表存储结构如下:从顶点 1 出发,DFS 遍历的输出序列是
( 1,3,4,5,2 ) ,BFS 遍历的输出序列是 ( 1,3,2 , 4 , 5 )
三、应用题(36 分)
1.设一组初始记录关键字序列为(45,80,48,40,22,78),则分别给出第 4 趟简单
选择排序和第 4 趟直接插入排序后的结果。
(22,40,45,48,80,78);(40,45,48,80,22,78)
1. 设指针变量 p 指向双向链表中结点 A,指针变量 q 指向被插入结点 B,要求给出在结
点 A 的后面插入结点 B 的操作序列(设双向链表中结点的两个指针域分别为 llink 和
rlink)。 q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q;
2.设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找
方法用二分查找,要求计算出查找关键字 62 时的比较次数并计算出查找成功时的平均
查找长度。2,ASL=
3.设一棵树 T 中边的集合为{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要
求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉
树。
4.设有无向图 G,要求给出用普里姆算法构造最小生成树所走过的边的集合。
(1,3)( 1,2)( 3,5)( 5,6)( 6,4)
5.设有一组初始记录关键字为(45,80,48,40,22,78),要求构造一棵二叉排序树
并给出构造过程。二叉树性质:中序遍历为递增序列
四、算法设计题(16 分)
6