精品文档 成 上海大学2012～2013学年度春季学期试卷A 绩 课程名: 数据结构（二）课程号: 08305010 学分: 4 应试人声明： 我保证遵守《上海大学学生手册》中的《上海大学考场规则》，如有考试违纪、作弊行为，愿意接受《上海大学学生考试违纪、作弊行为界定及处分规定》的纪律处分。 应试人 应试人学号 应试人所在院系 一(10) 二(15) 三(15) 四(24) 五(26) 六(10) 得 分 题号(分值) 得分 ————————————————————————————————————— 一、判断题,叙述正确的标记T，错误的标记F(每题1分，共10分） 1. 2. 3. 4. 5. 6. 7. 8. 任意一棵二叉树都可以转换为树来表示 （ ） 折半查找进行时间性能分析的判定树不一定是完全二叉树。 （ ） 散列表的平均查找长度只与采用的散列函数及处理冲突的方法有关。（ ） 对 B 树删除某一关键字值时，可能会引起结点的分裂。 （ ） 有e条边的无向图，在邻接表中有e个结点。 （ ） 十字链表是有向图的一种存储结构。 （ ） 不同的求最小生成树的方法最后得到的生成树是相同的。 （ ） 若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。 （ ） 9. 顺序表上的直接选择排序是一种稳定的排序方法。 （ ） 10. 对长度为n的表作快速排序，最坏情况下，算法时间复杂度为O(n2)。（ ） 得 二、选择题（每题1分，共15分） 分 1. 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )法。 A．分块查找 B．顺序查找 C． 折半查找 D． 基于属性的查找 2. 在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍。 A．1/2 B．2 C．1 D．4 3. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。 A．逆拓扑有序 B．拓扑有序 C．无序的 4. 下列哪一种图的邻接矩阵是对称矩阵？（ ） 精品文档 精品文档 A．有向图 B．无向图 C．AOV网 D．AOE网 5. 用邻接矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m 的路径相连，则只要检查（ ）的第i行第j列的元素是否为零即可。 A．mA B．A C．Am D．Am-1 6. 下面哪一方法可以判断出一个有向图是否有环（回路） A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 7. 7. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 8. 8．下列关于AOE网的叙述中，不正确的是（ ）。 A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 9. 二叉查找树在( )时其查找效率最低。 A．结点太多 B．完全二叉树 C．呈单枝树 D．结点太复杂 10. 设有一个用线性探测法解决冲突得到的散列表： 0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 散列函数为H(k)=k mod 11,若要查找元素14，探测的次数是( )。 A．18 B． 9 C． 3 D． 6 11. 下列排序方法中，( )是稳定的排序方法 A．直接选择排序 B．折半插入排序 C．希尔排序 D．快速排序 12. 下述排序方法中，比较次数与待排序记录的初始状态无关的是（ ）。 A. 插入排序和快速排序 B. 归并排序和快速排序 C. 选择排序和基数排序 D.插入排序和归并排序 13. 设有5000个元素，希望用最快的速度挑选出前10个最大的，下列排序方法中采用（ ）方法最好。 A. 快速排序 B. 堆排序 C. 希尔排序 D. 归并排序 14. 并查集的结构是（ ） A. 二叉链表存储的二叉树 B. 双亲表示法存储的树 C. 三叉链表存储的二叉树 D. 线性链表 15. 下列哪一个关键码序列不符合堆的定义?（ ） A. A,C,D,G,H,M,P,Q,R,X B. A,C,M,D,H,P,X,G,Q,R C. A,D,P,R,C,Q,X,M,H,G D. A,D,C,M,P,G,H,X,R,Q 精品文档 精品文档 三、填空题（每空1分，共15分） 1. G是一个非连通无向图，共有28条边，则该图至少有______个顶点。 2. 已知一无向图G=（V，E），其中V={a,b,c,d,e}, E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是___ _____遍历方法。 3. 求图的最小生成树有两种算法，其中______________算法适合于求稀疏图的最小生成树。 4. 求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms,则在图的顶点数为40，计算时间约为______ms。 5. 设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间复杂度为____________。 6. 设线性表(a1，a2，…，a500)元素的值由小到大排列。对一个给定的k值，在等概率情况下，用顺序查找法查找一个记录，查找成功的平均查找长度ASL为 ；用二分法检索查找表中与k相等的元素，在查找不成功的情况下至多比较_________次。用分块查找（索引表和各块内均用顺序查找），若分成25块，查找成功的其平均查找长度为___________。 7. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半法查找关键码值8，需做的关键码比较次数为___ _，查找关键码值20，需做的关键码比较次数为___ _. 8. 对于一个高度为h（空树的高度为-1）的AVL树，其最少结点数是 。反之，对于一个有n个结点的AVL树, 其最大高度是 ，最小高度是 。 9. 设用希尔排序对数组{98，36，19，5，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是5、3、1，则写出第一趟结束后，数组中数据的排列第三个元素是（从0开始计数 ） 。 10. 对一组记录（54, 38, 106, 21, 15, 72, 60, 45, 83）进行直接插入排序，当把元素60插入到有序表时，为寻找插入位置需比较 次。 四、简答题（共24分） 1. (8分)已知2棵2-3 树（3阶B-树）如下： （1） 对树（a）,请分别画出先后插入26，85两个新结点后的树形； （2） 对树（b）,请分别画出先后删除53，37两个结点后的树形。 得 分 得 分 【解答】： 精品文档 精品文档 （1） （2） 2. （8分）给定5个村庄(A、B、C、D、E)之间的交通图如下所示，若村庄i到j有道路，则将顶点i到j用有向边连接，边上的Wij表示这条道路的长度。现在请回答以下问题： （1）画出该有向图的邻接表存储结构 （2）求其它各村庄到村庄B的最短路径和最短路径长度。 （3）要从这5个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能各村到医院的来回路程最短?说明解答上述问题的算法。 【解答】： （1） （2） （3） 精品文档 精品文档 3. （8分）对初始序列(58，85，47，39，70，47*，101，68，10，66，34)按递增方式进行排序。 （1）给出快速排序的第一趟排序结果（以第1个元素58为基准元素）。 （2）选取d = {5，3，1}，给出希尔排序的第一趟排序结果。 （3）写出二路归并的第一趟排序结果。 （4）给出基数排序的第一趟的回收结果。 【解答】：（1）快速排序的第一趟排序结果为： （2）希尔排序的第一趟排序结果为： （3）二路归并的第一趟排序结果为： （4）基数排序的第一趟回收结果是： 五、算法分析题（每空2分，共26分） 得 分 1．（8分）下列递归算法的功能是：从大到小输出给定二叉排序树中所有关键字不小于x的数据元素。该算法的时间复杂度为O(log2n+m)，其中n为二叉排序树中的结点数，m为输出的数据元素个数。请完善该算法。 提示：算法可以借助逆中序遍历二叉排序树来实现。所谓逆中序遍历二叉树是指：如果当前结点p非空，则先逆中序遍历p的右二叉树；然后访问p结点；最后再逆中序遍历p的左二叉树。在本算法中访问p结点时，如果p的值小于x，则算法结束，否则输出p的值。 void PrintNLT (BSTreeNode