H(Aug) = ?1/2? = 0，= 1，成功. H(Sep) = ?19/2? = 9，= 10，成功.
H(Oct) = ?15/2? = 7，= 8，= 9，= 10，= 11，成功.
H(Nov) = ?14/2? = 7，= 8，= 9，= 10，= 11，= 12，成功.
H(Dec) = ?4/2? = 2，成功.
(1)相应的散列表
0 1 2 3 4 5 6 7 8 9 10 11 12 13
(1) (2) (1) (1) (1) (1) (2) (4) (5) (2) (5) (6)
(2) 搜索成功的平均搜索长度为
1/12 * (1 + 2 + 1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 5 + 6) = 31 / 12
五、算法设计题
已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BTreeNode { char data; BinTreeNode *leftChild, *rightChild; };其中data 为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。
Int BTreeLeafCount ( BinTreeNode* BT );
解：int BTreeLeafCount ( BinTreeNode* BT )
{ if ( BT == NULL )
return 0;
else if (BT->leftChild == NULL && BT->rightChild == NULL)
return 1;
else
return BTreeLeafCount ( BT->leftChild ) + BTreeLeafCount ( BT->rightChild );
}
5