硕数2005.doc

数据结构部分（共50分）一、 简答题（15分）1. 什么是线性表？线性表的每一个表元素是否必须类型相同？为什么？2. 线性表有两种存储表示：顺序存储表示（顺序表）和链接存储表示（单链表）。如果将它们定义为抽象基类和两个具体派生类的关系class linearList/抽象基类：线性表class seqList : public linearList/派生类：顺序表class linkedList : public linearList/派生类：单链表如果需要定义和使用一个线性表对象，试问在程序中如何选用某种存储表示？3. 已知二叉树的前序遍历序列为ABDEGCFHIJ，中序遍历序列为DBGEAHFIJC，则该二叉树的后序遍历序列是什么？4. 利用B树作文件索引时，若假设磁盘页块的大小是4,000字节（实际也许是4,096字节，为了计算方便，就取成4,000字节），指示磁盘地址的指针需要5个字节。现在有20,000,000个记录构成的文件，每个记录为200字节，其中包括关键码5个字节。试问在此采用B树作索引的文件中，B树的阶数应为多少？假定文件数据部分未按关键码有序排列，则索引部分需要占用多少磁盘页块？5. 假定把关键码key散列到有n个表项（从0到n-1编址）的散列表中。对于下面的每一个函数H(key)（key为整数），这些函数能够当作散列函数吗？（即对于插入和查找，散列程序能正常工作吗？）如果能够，它是一个好的散列函数吗？请说明理由。设函数random(n)返回一个0到n-1之间的随机整数（包括0与n-1在内）。(1) H(key) = key / n;(2) H(key) = 1;(3) H(key) = (key + random(n) % n;(4) H(key) = key % p(n); 其中p(n) 是不大于n的最大素数二、证明题（5分）试证明：在同一棵二叉树的前序序列、中序序列和后序序列中，所有叶结点都按相同的（先后）相对位置出现。三、简作题（15分）在AVL树的插入和删除过程中，每插入一个结点都要判断从插入结点到树根的路径上是否有失去平衡的结点，如果有，就要做平衡化旋转。平衡化旋转有4种类型：左单旋转、右单旋转、先左后右双旋转、先右后左双旋转。(1) 若关键码的输入序列为20, 9, 3, 12, 13, 27, 22, 16, 17, 15, 18, 10，试从空树开始顺序输入各关键码建立AVL树。画出每次插入时树的形态。若需要平衡化旋转则做旋转并注明旋转的类型。(2) 基于上面建树的结果，画出从树中删除22，删除3，删除10与9后树的形态和旋转的类型。要求以被删关键码的中序下的直接前驱替补该被删关键码。四、编程题（共15分）设Graph是一个带权有向图,可以直接使用的操作有int NumberOfVertices ( ); /函数返回图中顶点个数int NumberOfEdges ( ); /函数返回图中边数T GetValue ( int i ); /函数返回第i个顶点上的数据值float GetWeight ( int u, int v ); /函数返回边上的权值int GetFirstNeighbor ( int v ); /函数返回顶点v的第一个邻接顶点int GetNextNeighbor ( int v, int w ); /函数返回顶点v的相对于邻接顶点w的下一邻接顶点(1) 下面是一个函数，利用Dijkstra算法在图G中求从顶点v到图中其他各顶点的最短路径和最短路径长度。函数中有5条语句缺失，请阅读程序并将它们补上。（5分）template void ShortestPath (Graph G, int v, float dist , int path ) /数组dist 存放求到的从顶点v到各顶点的最短路径长度，数组path 存放求到的最短路径。/其中，常量maxWeight是float类型数据在机器中能够表示的最大数，代表无穷边。int n = G.NumberOfVertices( );int *S = new intn;int i, j; float w;for ( j = 0; j n; j+) distj = G.GetWeight ( v, j );Sj = 0;if ( j != v & distj maxWeight ) ;/记路径上顶点j的前一顶点else pathj = -1; /* end of for */Sv = 1; distv = 0;for ( i = 1; i n; i+ ) float min = maxWeight; int u = v;for ( j = 0; j n; j+ )if ( & distj min ) u = j; min = distj; ;for ( j = 0; j n; j+ ) w = G.GetWeight (u, j);if ( & w maxWeight & distu + w distj ) distj = distu + w; /* end of if */ /* end of for */ /* end of for */ delete S; /* end of ShortestPath */(2) 设有一个带权有向图G = ( V, E )，w是G的一个顶点，w的偏心距定义为 max 从u到w的最短路径长度| uV .其中的路径长度指的是路径上各边权值的和。将G中偏心距最小的顶点称为G的中心，试设计一个函数返回带权有向图的中心（如有多个中心，可任取其中之一）。函数的首部为template int centre ( Graph G, float& biasdist ) (10分)参数表中的引用型参数biasdist返回最小偏心距的值，函数返回该中心的顶点号。数据结构部分 参考答案（共50分）一、简答题（每小题3分，共15分）1、 线性表是n（n0）个数据元素的有限（有穷）序列。其中每一个表元素的数据空间一般要求相同，但数据类型可以不同，可以用等价类型（unoin）变量来定义每一个数据元素的类型。例如 union /联合 int intergerInfo;/整型 char charInfo;/字符型 float floatInfo;/浮点型 info;利用等价类型，可以在同一空间（空间大小相同）存放不同基本数据类型的元素。2、 当给出线性表和它的两种存储表示的情况下，可以如下定义使用linearList * p;seqList seqList_obj;p = &seqList_obj;int add = p-Locate (5);/按顺序表使用线性表或linearList * p;linkedList linkedList_obj;p = &linkedList_obj;int add = p-Locate (5); /按单链表使用线性表ABCDEFGHIJ3、 通过二叉树的前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC，可以唯一构造出二叉树：则后序遍历的结果是DGEBHJIFCA。4、 根据B树的概念，一个索引结点最大不应超过一个磁盘页块的大小。假设B树为m阶，一个B树结点最多存放m-1个关键码和对应的记录地址，外加m个子树指针和1个指示结点中实际关键码个数的整数2个字节。根据假设，每个关键码和指针都占用5个字节，则有( 2 * (m-1) + m ) * 5+24000计算结果，m267。 一个索引结点最多可以存放m-1 = 266个索引项，最少可以存放m/2-1 = 133个索引项。全部有n = 20,000,000个记录，每个记录占用空间200个字节，每个页块可以存放4000/200 = 20个记录，则全部记录分布在20,000,000/20 = 1,000,000个页块中，则最多需要占用1,000,000/133 = 7519个磁盘页块作为B树索引，最少需要占用1,000,000/266 = 3759个磁盘页块作为B树索引。5、(1) 不能当作散列函数，因为key / n可能大于n，这样就找不到适合的位置。(2) 能够作为散列函数，但不是一个好的散列函数，因为所有关键码都映射到同一位置，造成大量的冲突机会。(3) 不能当作散列函数，因为该函数的返回值不确定，这样无法进行正常的查找。(4) 能够作为散列函数，是一个好的散列函数。二、二、采用归纳法证明：对二叉树的结点个数n做归纳，当n = 0或n = 1时，结论显然成立；（1分）假设当n = k时结论成立，（1分）则当n = k+1时，可把二叉树分解为树根、左子树和右子树（子树均可为空）。由于子树中结点个数均小于或等于k，根据归纳假设，在左子树和右子树中，所有叶结点在其前序序列、中序序列和后序序列中都按相同的（先后）相对位置出现。由于二叉树的三种遍历在树中走了一条相同的路线，左子树中的叶结点总比右子树的叶结点先访问，从这一点看，不论哪一种遍历，结果序列中左子树的叶结点总在右子树的叶结点前面，（先后）相对位置相同。因为左、右子树的叶结点就是二叉树的叶结点，于是可得二叉树的所有叶结点在其前序序列、中序序列和后序序列中都按相同的相对位置（先后）出现。（3分）三、画图 （每插入1次1分，共12分；每删除1次1分，共3分）209209320右单旋转209320931220931213先左后右双旋转加3加9加20加13加122093121327222093121327209312132720931213先右后左双旋转左单旋转加22加272293121327202293121327201617229312132717162022931213272016加17加1617931213221527201618179312132215271620左单旋转右单旋转229312132717162015先左后右双旋转加18加15右单旋转16201727151393121018删3182017271513169312101822172715131620931210删22182217271513162093121018221727151316209312加101620172715131218删10, 916201727151391210181620172715139121018先右后左双旋转2017271615131218左单旋转四、(1) pathj = v !Sj Su = 1 !Sj pathj = u(5分)(2) 参考函数过程如下template int centre ( Graph G, float& biasdist ) int i, j, n = G.NumberOfVertices( );(1分)float *fromDist = new floatn; (1分)int *fromPath = new intn;float *toDist = new floatn;for ( i = 0; i n; i+ ) toDisti = 0; (1分)for ( i = 0; i n; i+ ) (3分) Shorfloat *toDist = new float n;float *fromDist = new float n;int *fromPath = new into n;for ( i = 0; i n; i+ ) toDisti = 0;for ( i = 0; i n; i+ ) ShorttestPath ( G, i, fromDist, fromPath ); for ( j = 0; j toDistj ) toDistj = fromDistj;j = 0; (1分)f