一、单项选择题（每小题 2 分，共20分）
（1）B （2）B （3）B （4）C （5）B
（6）D （7）B （8）B （9）B （10）D
二、（每小题4分，共8分）
（1）3 X * Y 2 - / 1 +
（2）2 X Y 3 + * +
三、（每小题4分，共8分）
（1）二叉树的顺序存储表示如下所示：

（2）二叉树的二叉链表存储表示的示意图如下图所示：

四、（每小题4分，共8分）
（1）不是小根堆。调整为：{12,24,33,65,33,56,48,92,86,70}
（2）是小根堆。
五、（本题8分）
普里姆算法从顶点1出发得到最小生成树为：
(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20
六、（每小题2分，共8分）
（1）取散列函数为H(key)=key % 13。
（2）顺次将各个数据散列到表中，并同时列出各元素的比较次数如下表所示。

（4）计算查找成功的平均查找次数=（1×7+2×3+3×2）/12=19/12。
七、（第1小题2分，第2、3小题每小题3分，本题8分）
（1）图G有2个连通分量。
（2）按深度优先搜索所得的树如下图所示：

（3）按深度优先搜索所得的顶点序列：ABHFGCDE
八、（本题8分）
（1）树，如下图所示：

（2）C是根结点。
（3）F，K，L，H，D，M，N是叶子结点。
（3）深度是5。
九、（本题9分）
（1）（12,2,10,20,6,18,4,16,30,8,28）
（2）（6,2,10,4,8,12,28,30,20,16,18）
十、（本题15分）
将算法实现函数声明为二叉树类的友元函数，可采用层次遍历的方式进行复制，将已复制的结点进入一个队列中即可。
具体算法实现如下：

// 文件路径名:exam5\alg.h
template
void CopyBitree(BinaryTree *fromBtPtr, BinaryTree *&toBtPtr)
// 操作结果: 复制二叉树fromBt到toBt的非递归算法
{
if (toBtPtr != NULL) delete toBtPtr; // 释放toBtPtr
if (fromBtPtr->Empty())
{ // 空二叉树
toBtPtr = NULL; // 空二叉树
}
else
{ // 非空二叉树
LinkQueue<BinTreeNode *> fromQ, toQ; // 队列
BinTreeNode *fromPtr, *toPtr, *fromRoot, *toRoot;
fromRoot =(BinTreeNode *) fromBtPtr->GetRoot(); // 取出fromBtPtr的根
toRoot = new BinTreeNode(fromRoot->data); // 复制根结点
fromQ.InQueue(fromRoot); toQ.InQueue(toRoot); // 入队
while (!fromQ.Empty())
{ // fromQ非空
fromQ.OutQueue(fromPtr); // 出队
toQ.OutQueue(toPtr); // 出队
if (fromPtr->leftChild != NULL)
{ // 左子树非空
toPtr->leftChild = new BinTreeNode(fromPtr->leftChild->data);
// 复制fromPtr左孩子
fromQ.InQueue(fromPtr->leftChild); toQ.InQueue(toPtr->leftChild); // 入队
}
if (fromPtr->rightChild != NULL)
{ // 右子树非空
toPtr->rightChild = new BinTreeNode(fromPtr->rightChild->data);
// 复制fromPtr左孩子
fromQ.InQueue(fromPtr->rightChild); toQ.InQueue(toPtr->rightChild); // 入队
}
}
toBtPtr = new BinaryTree(toRoot); // 生成toBtPtr
}
}