广东工业大学98.txt

考研数据结构各个高校的考试习题

        广东工业大学1998
一。判断题（20分）
   1，树是图的一种特殊形式
   2，哈希技术是一种排序方法
3，在有向图中，强连通分量是极大强连通子图
4，链式队列队满条件是尾指针加一等于头指针
5，已知二叉树前根排序和后根排序能唯一确定一棵二叉树
6，ISAM（索引顺序存储方法）是一种专为磁盘存取文件设计的文件组织方式
7.如果结点A有4个兄弟，且B是A的双亲,B的度是4
8.用折半查找算法在关键字序列1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
中查找关键字为2的比较次数3次.
二.证明题
如果一棵树有n1个度1为的结点,n2个度为2的结点,nm个度为m的结点,试证明其
叶结点数为
n0=1*n1+2*n3+......+(m-1)*nm
三.写出求二叉树叶结点数目的算法,并分析算法的时间复杂性
四.