数据结构---B卷---软件1091 1171 1172---2012年---集美大学试卷纸(包括答题纸)

1、集 美 大 学 试 卷 纸 2011 2012 学年 第 二 学期课程名称数据结构试卷卷别B卷适 用学院、专业、年级诚毅学院 软件工程专业1091 1171 1172考试方式闭卷 开卷 备注总分题号一二 三四 得分阅卷人得分一、问答题（共22分)1、（共4分）完善下面的数据的逻辑结构和物理结构的分类表。 2、（共4分）假设图1 非连通图的邻接表相邻的顶点在邻接表中按升序排列，画出该邻接表表示的非连通图的深度优先搜索的连通分量或深度优先生成森林。图1 非连通图3、（共4分）设一段报文：GOOD_GOOD_GOOD_GOOOOO_OOO_OFF出现字符集合有O,G,_,D,F，各个字符出现的频度刚

2、好是W = 15, 4, 5, 3, 2请给出画出构造的Huffman树；给出每个字符的Huffman编码；给出GOOD的编码。4、（共4分）ISAM (索引顺序存取方法文件)是静态索引结构。典型的例子是对磁盘上的数据文件建立盘组、柱面、磁道三级地址的多级索引。ISAM文件用柱面索引对各个柱面进行索引。一个柱面索引项保存该柱面上的最大关键码（最后一个记录）以及柱面开始地址指针。如果柱面太多，可以建立柱面索引的分块索引，即主索引。主索引不太大，一般常驻内存。请对图2的索引基本原理做说明。图2 ISAM (索引顺序存取方法文件)静态索引结构5、（共6分）设待排序的排序码序列为12, 2, 16,

3、30, 28, 10, 16*, 20, 6, 18, 请给出使用快速排序方法每趟排序后的结果。并说明做了多少次排序码比较。得分 二、程序题（共21分)1、（共5分）请给下列定义的类Graphlnk写出注释。（选其中的5个/ 语句注释）template class Graphlnk : public Graph /friend istream& operator (istream& in, Graphlnk& G); /friend ostream& operator (ostream& out, Graphlnk& G); /private: Vertex *NodeTable; / int

4、 GetVertexPos (const T vertx) / for (int i = 0; i = 0 & i leftChild) + Size (subTree-rightChild);图3 Size方法的递归展开图3、（共4分）画出分别调用下列两个类的方法创建的二叉树。void BinaryTree:CreateBinTree (ifstream& in, BinTreeNode*& subTree) char item; if ( !in.eof () ) in item; if (item != #) subTree = new BinTreeNode(item); if (su

5、bTree = = NULL) cerr 存储分配错! 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;inch;while (ch!=RefValue)swith(ch)case (: s.Push

6、(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-leftChild = p;elses.GetTop(t); t-rightChild = p;in ch; /方法二 从键盘输入A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)#解：方法一创建的二叉树如下： 方法二创建的二叉树如下：4、（共6分）分析图4的二叉树t调用下面的二叉树类的层序遍历

7、方法，给出调用过程的队列情况，标出队列的头尾指针；描述每次队列变化时发生的情况。void BinaryTree:LevelOrder (BinTreeNode *t) if (root = = NULL) return; SeqQueue Q; BinTreeNode *p = root; Q.EnQueue (p); while (!Q.IsEmpty () Q.DeQueue (p); coutdata; if (p-leftChild != NULL) Q.EnQueue (p-leftChild); if (p-rightChild != NULL) Q.EnQueue (p-righ

8、tChild); 解：图4 二叉树的层序遍历得分三、分析题（共32分)1、（共5分）二叉查找树的性能分析：已知关键码集合 a1, a2, a3 = do, if, to，对应查找概率p1, p2, p3, 在各查找不成功间隔内查找概率分别为q0, q1, q2, q3。根据画出的可能的五种二叉查找树，求等概率查找成功的平均查找长度ASLsucc和不成功的平均查找长度ASLunsucc ，分析出等概率的最优二叉查找树。解：等概率的最优二叉查找树是：2、（共6分）如果在一棵平衡的二叉查找树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。平衡化旋转有两类：单旋转和双旋转，单旋转有左

9、单旋和右单旋，双旋转有左右双旋和右左双旋。输入关键码序列为 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。而关键码集合比散列表地

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

11、abcac的next值；根据该next值画出KMP算法的匹配过程。6、（共6分）按照广义表的图形表示和广义表结点定义，给下面的广义表链表表示补充完整的内容。得分四、综合应用题（共25分)1、（共5分）图5用Kruskal算法如何构造出最小生成树？请给出构造的逻辑过程。图5 城市网2、（共10分）图6的AOV网络和图7的的邻接表和入度数组count。请利用入度为零的顶点栈产生拓扑排序的方法，画出图的count数组在各个顶点随着拓扑排序输出时的变化图，标出其中的堆栈的从栈底到栈顶的连线图；给出图6按照顶点栈的方法产生的唯一的拓扑排序。 图6 AOV网络 图7 邻接表和入度数组count解：count数组在各个顶点随着拓扑排序输出时的变化图,标出其中的堆栈的连线图 唯一的拓扑排序为：3、（共10分）利用Dijkstra