2007级数据结构考试(A).doc

北京工业大学 计算机学院20082009（第2学期）数据结构与算法分析期末考试卷（A）考试形式：“A4一纸开卷” 班级 学号 姓名 题号一二三四五总分分数一、 选择题（10分）1数据对象是指 ( ) 。A数据的基本单位B性质相同的数据元素的集合C相互之间存在一种或多种特定关系的数据元素的集合D描述客观事物且由计算机处理的数值、字符等符号的总称2假设某个栈的输入序列为123n，如果输出序列的第一个元素是n，则输出序列的第i（1in）个元素是 ( ) 。An-i+1BiCn-iD不确定3假设在某个森林F中包含三棵树，它们的结点个数分别为m1，m2和m3。与森林F对应的二叉树根结点的右子树上的结点个数是 ( )。Am1Bm1+m2Cm3Dm2+m34如果采用邻接表表示AOV网，拓扑排序算法的时间复杂度为( ) 。AO(n) BO(ne) CO(n*n)DO(n*n*n)5如果需要在O(nlog2n)的时间复杂度内完成对含有n个元素的数组进行稳定性排序，可以选择的排序方法是 ( )。 A快速排序B堆排序C归并排序D直接插入排序二、 填空题（10分）1假设某个循环队列的队头指针与队尾指针分别为front和rear，队列中的元素个数为 。2如果采用分块查找，数据的组织方式为：将n个数据平均分成b块，每块包含s个数据。如果对块索引及块内查找都采用顺序查找方式，ASL = 。3已知某棵二叉树的后序遍历序列是jheigfdcba，中序遍历序列是bjhecfigda， 则这棵二叉树所对应的树的深度为 。4AOE网是一种用顶点表示事件，用弧表示活动的有向网。在这个网中的关键路径是指 _。5在对多关键字进行排序时，可以选用高位优先或低位优先的排序策略，基数排序采用的是 _ _。三、 简答题（45分）1已知广义表GL=(a),b),d),e)，试写出该广义表的表头、表尾、长度和深度，并画出其存储结构。 表头 _表尾 _长度 _ 深度 _存储结构：2已知某个有向图G中的顶点之间的关系用右侧邻接矩阵表示。试根据深度优先搜索和广度优先搜索算法的执行过程，画出该有向图的深度优先生成森林和广度优先生成森林。深度优先生成森林广度优先生成森林3对于下图给出的带权无向图，试写出利用Prim算法得到最小生成树的closedge数组的变化过程，并给出Prim算法的时间复杂度。1234567adjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostPrim算法的时间复杂度：_4依次读入给定的整数序列（50，19，35，55，20，5，100，52，88，53，92），并完成下列操作：1）构造一棵二叉排序树，并计算 ASL二叉排序树ASL = _2）应该如何调整上述整数序列的排列顺序才能够得到一棵平衡二叉树？写出调整后的整数序列及相应的平衡二叉树，并计算ASL调整后的整数序列( _ )平衡二叉树ASL = _5如果只想在一个有n个元素的任意序列中得到其中最小的第k（kn）各元素之前的部分排序序列，而且这个n是比较小的值。试问采用什么排序方法能得到比用堆排序的比较次数更少？例如，有这样一个序列（503,017,512,908,170,897,275,653,612,154,509,677,765,094），要得到第4个元素之前的部分有序列（017,094,154,170），用所选择的排序算法（非堆排序）实现时，要执行多少次比较？若用堆排序算法，要执行多少次比较？ 选择的排序算法_比较次数 _堆排序算法需要的比较次数 _四、算法阅读（15分）阅读算法programXP1，并回答两个问题。void programXP1(int a, int n, int max) int temp = new intmax; int count = new intmax;for ( int i = 0; i n; i+ ) tempi = ai;for ( int i = 0; i n; i+ ) counti = 0;for ( int i = 0; i n; i+ )countai = countai + 1; （1）for ( int i = 1; i = 0; i- )a-counttempi = tempi; （3）问题1 对于整数序列（7,3,8,9,6,1,8,1,2,7,7,3,4,5），写出执行算法programXP1(a,14,10) 的（1）、（2）和（3）语句之后，数组a与count的状态。执行（1）语句之后count数组的状态：0123456789执行（2）语句之后count数组的状态： 0123456789执行（3）语句之后 a数组的状态：012345678910111213问题2 分析这个算法的时间复杂度及适用场合。时间复杂度 _适用场合 _五、算法设计（20分）1 假设有一个无向图采用邻接矩阵表示。 试设计一个算法，输出从某个顶点v开始，k步到达的所有顶点。 例如，在下图中，从顶点A开始，3步到达的顶点有E、 F和 G。假设算法的原型为： Status Digraph (MGraph g，int v，int k )/ g是无向图，v是开始顶点，k是步数邻接矩阵的存储表示类型定义如下：#define MAX_VERTEX_NUM 20typedef struct intvexsMAX_VERTEX_NUM MAX_VERTEX_NUM;intvexnum, arcnum; MGraph;算法：Status Digraph (MGraph g，int v，int k )2 试设计一个算法，对于给定的后缀表达式E，构造相应的二叉树BT。 例如，某个后缀表达式为 a b c d - * + e f / - 相应的二叉树为：假设算法的原型为： Status Exp (char exp，BiTree &BT )/ exp是字符型数组，用