一、问答题（共22分)

1、（共4分）完善下面的数据的逻辑结构和物理结构的分类表。

2、（共4分）给出下列图1的二叉树的静态链表存储、顺序存储和二叉链表存储。

图1 二叉树 图2 二叉树的二叉链表的静态链表

解：二叉树的顺序存储如下： 二叉树的二叉链表存储如下：

二叉树的静态链表存储填入图2。

3、（共4分）有一段报文：

CAST CAST SAT AT A TASA

出现的字符有 C, A, S, T，各字符出现的频度刚好是

W＝{ 2, 7, 4, 5 }

请给出①画出构造的Huffman树；

②给出每个字符的Huffman编码。

4、（共4分）ISAM (索引顺序存取方法文件)是静态索引结构。典型的例子是对磁盘上的数据文件建立盘组、柱面、磁道三级地址的多级索引。ISAM文件用柱面索引对各个柱面进行索引。一个柱面索引项保存该柱面上的最大关键码（最后一个记录）以及柱面开始地址指针。如果柱面太多，可以建立柱面索引的分块索引，即主索引。主索引不太大，一般常驻内存。请对图 的索引基本原理做说明。

图3 ISAM (索引顺序存取方法文件)静态索引结构

5、（共6分）完善下面的基数排序过程。

二、程序题（共21分)

1、（共5分）请给下列定义的类Graphmtx写出语句注释。

template T, class E>

class Graphmtx : public Graph<T, E> { //

friend istream& operator >> ( istream& in, Graphmtx<T, E>& G); //

friend ostream& operator << (ostream& out, Graphmtx<T, E>& G); //

private:

T *VerticesList; //

E **Edge; //

int GetVertexPos (T vertex) { //

for (int i = 0; i < numVertices; i++) if (VerticesList[i] == vertex) return i;

return -1;

}

public:

Graphmtx (int sz = DefaultVertices); //

~Graphmtx (){ delete [ ]VerticesList; delete [ ]Edge; } //

T GetValue (int i) { //

return i >= 0 && i <= numVertices ? VerticesList[i] : NULL;

}

E GetWeight (int v1, int v2) { //

return v1 != -1 && v2 != -1 ? Edge[v1][v2] : 0;

}

int GetFirstNeighbor (int v);

int GetNextNeighbor (int v, int w);

bool InsertVertex (const T vertex);

bool InsertEdge (int v1, int v2, E cost);

bool RemoveVertex (int v);

bool RemoveEdge (int v1, int v2);

};

2、（共4分）画出分别调用下列两个类的方法创建的二叉树。

void BinaryTree::CreateBinTree (ifstream& in, BinTreeNode*& subTree) {

char item;

if ( !in.eof () ) {

in >> item;

if (item != ’#’) {

subTree = new BinTreeNode(item);

if (subTree = = NULL) {cerr << "存储分配错!" << endl; exit (1);}

CreateBinTree (in, subTree->leftChild);

CreateBinTree (in, subTree->rightChild);

}

else subTree = NULL;

}

} //方法一 从文件输入A B C # # D E # G # # F # # #

void BinaryTree:: CreateBinTree(istream& in, BinTreeNode *&BT){

SeqStack s;

BT=NULL;

BinTreeNode *p,*t;

int k;

char ch;

in>>ch;

while (ch!=RefValue){

swith(ch){

case ’(’: s.Push(p); k=1; break;

case ’)’: s.Pop(p); break;

case ’,’: k=2; break;

default: p = new BinTreeNode(ch);

if (BT = = NULL) BT=p;

else if ( k= =1){

s.GetTop(t); t->left Child = p;

}

else{

s.GetTop(t); t->rightChild = p;

}

}

in >> ch;

}

} //方法二 从键盘输入A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))#

解：方法一创建的二叉树如下： 方法二创建的二叉树如下：

3、（共6分）下面的二叉树类的方法Height求树的高度，请分析在图4的递归展开图中填入subTree的树调用Height方法的相应的递归展开过程；标出展开的序号；给出各树高度；在图4中指出是何种遍历方法的应用。

int BinaryTree::Height ( BinTreeNode * subTree) const {

if (subTree == NULL) return 0;

else {

int i = Height (subTree->leftChild);

int j = Height (subTree->rightChild);

return (i < j) ? j+1 : i+1;

}

}

图4 Height方法的递归展开图

4、（共6分）分析图5的二叉树t调用下面的二叉树类的层序遍历方法，给出调用过程的队列情况，标出队列的头尾指针；描述每次队列变化时发生的情况。

void BinaryTree::LevelOrder (BinTreeNode *t) {

if (root = = NULL) return;

SeqQueue Q;

BinTreeNode *p = root;

Q.EnQueue (p);

while (!Q.IsEmpty ()) {

Q.DeQueue (p);

cout<<p->data;

if (p->leftChild != NULL) Q.EnQueue (p->leftChild);

if (p->rightChild != NULL) Q.EnQueue (p->rightChild);

}

}

解：

图5 二叉树的层序遍历

三、分析题（共32分)

1、（共5分）二叉查找树的性能分析：已知关键码集合 {a1, a2, a3} = {do, if, to}，对应查找概率p1, p2, p3, 在各查找不成功间隔内查找概率分别为q0, q1, q2, q3。根据画出的可能的五种二叉查找树，求等概率查找成功的平均查找长度ASLsucc和不成功的平均查找长度ASLunsucc ，分析出等概率的最优二叉查找树。

解：

等概率的最优二叉查找树是：

2、（共6分）如果在一棵平衡的二叉查找树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。平衡化旋转有两类：单旋转和双旋转，单旋转有左单旋和右单旋，双旋转有左右双旋和右左双旋。输入关键码序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }，给出从空树开始的建立平衡二叉树插入和调整过程。

3、（共6分）一棵 m 阶B 树是一棵平衡的 m 路搜索树, 它或者是空树, 或者是满足下列性质的树：根结点至少有 2 个子女。除根结点以外的所有结点 (不包括失败结点)至少有 m/2 个子女。所有的失败结点都位于同一层。给出从空树开始加入关键码53、75、139、49,145、36、101建立3阶B树的过程。

解：

4、（共4分）散列函数是一个压缩映象函数。除留余数法的哈希函数为h(k)=k mod p。而关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这就产生了冲突。线性探查法是从发生冲突的地址(设为d)开始,依次循环探查d的下一个地址(当到达下标为m-1的哈希表表尾时,下一个探查的地址是表首地址0),直到找到一个空闲单元为止(当m≥n时一定能找到一个空闲单元)。拉链法是把冲突的项目用链表串在一起的方法。假设哈希表长度m=13,采用除留余数法哈希函数建立如下关键字集合的哈希表：{16,74,60,43,54,90,46,31,29,88,77}，如果存在冲突，请给出解决冲突的方法。画出最后建立的线性探测的哈希表和拉链法的哈希表。

P=

5、（共5分）给出模式串p：abaabcac的next值；根据该next值画出KMP算法的匹配过程。

6、（共6分）按照广义表的图形表示和广义表结点定义，给下面的广义表链表表示补充完整的内容。

四、综合应用题（共25分)

1、（共5分）图6用Prim算法如何构造出最小生成树？模仿第一个构造，请给出利用最小堆H构造最小生成树的逻辑过程。

图6

2、（共10分）图7的AOV网络和图8的的邻接表和入度数组count[]。请利用入度为零的顶点栈产生拓扑排序的方法，画出图的count[]数组在各个顶点随着拓扑排序输出时的变化图，标出其中的堆栈的从栈底到栈顶的连线图；给出图7按照顶点栈的方法产生的唯一的拓扑排序。

图7 AOV网络 图8 邻接表和入度数组count[]

解：count[]数组在各个顶点随着拓扑排序输出时的变化图,标出其中的堆栈的连线图

唯一的拓扑排序为：

3、（共10分）试对图9所示的AOE网络，解答下列问题。

(1) 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]。 （3分）

(2) 求每个活动的最早开始时间e[k]和最迟开始时间l[k]，活动完成的时间余量d[k]。 （3分）

(3) 这个工程最早可能在什么时间结束。 （1分）

(4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。（3分）

图9 AOE网络

解：（1）

事件可能发生的最早时刻 事件发生所允许的最晚时刻

Ve(A)=

Ve(B)=

Ve(C)=

Ve(D)=

Ve(E)=

Ve(F)=

Ve(G)=

Ve(H)=

Ve(I)=

（2）

(3) 这个工程最早可能在 时间结束。

(4) 关键活动有：

活动 加速可使整个工程提前完成。

由所有关键活动构成的图如下：

关键路径有：

数据结构复习 - 集美大学（包括答题纸）