2013春 数据结构二试卷真题

上海大学2012～2013学年度春季学期试卷A 课程名: 数据结构（二）课程号: 08305010 学分: 应试人声明： 我保证遵守《上海大学学生手册》中的《上海大学考场规则》，如有考试违纪、作弊行为，愿意接受《上海大学学生考试违纪、作弊行为界定及处分规定》的纪律处分。 应试人所在院系 应试人学号 应试人 一(10) 二(15) 三(15) 四(24) 五(26) 题号(分值) 得分 ————————————————————————————————————— 一、判断题,叙述正确的标记T，错误的标记F(每题1分，共10分） 1. 任意一棵二叉树都可以转换为树来表示 折半查找进行时间性能分析的判定树不一定是完全二叉树。2. 散列表的平均查找长度只与采用的散列函数及处理冲突的方法有关。3. 对 B 树删除某一关键字值时，可能会引起结点的分裂。 4.有 e条边的无向图，在邻接表中有e个结点。 5.十字链表是有向图的一种存储结构。 6.不同的求最小生成树的方法最后得到的生成树是相同的。7. 若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存8. 在。 9. 顺序表上的直接选择排序是一种稳定的排序方法。 10. 对长度为n的表作快速排序，最坏情况下，算法时间复杂度为O(n 二、选择题（每题1分，共15分） 1. 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，法。 A．分块查找 B．顺序查找 C． 折半查找 D． 基于属性的查找2. 在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍。A．1/2 B．2 C．1 D．3. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，的顶点序列是( )。 A．逆拓扑有序 B．拓扑有序 C．无序的 4. 下列哪一种图的邻接矩阵是对称矩阵？（ ） A．有向图 B．无向图 C．AOV网 D之间是否有长度为Vj和Vi表示图，判定任意两个顶点A用邻接矩阵 5. 成 绩 4 六(10) 得 分（ ） （ ） （ ） （ ） （ ） （ ） （ ） （ ） （ ） 2)。（ ） 得 分 则可采用( ) 4 则输出．AOE网 的路径m 相连，则只要检查（ ）的第i行第j列的元素是否为零即可。 m A．mA B．A C．A D．Am-1 6. 下面哪一方法可以判断出一个有向图是否有环（回路） A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 7. 7. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。 23A. O(n) B. O(n+e) C. O(n) D. O(n) 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条边，则该图至少有______个顶点。 现V={a,b,c,d,e}, E={(a,b),(a,d),(a,c),(d,c),(b,e)}），其中E，V（G=已知一无向图 2. 用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是___ _____遍历方法。 3. 求图的最小生成树有两种算法，其中______________算法适合于求稀疏图的最小生成树。 4. 求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms,则在图的顶点数为40，计算时间约为______ms。 5. 设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间复杂度为____________。 6. 设线性表(a，a，…，a)元素的值由小到大排列。对一个给定的k值，在等概50021率情况下，用顺序查找法查找一个记录，查找成功的平均查找长度ASL为 ；用二分法检索查找表中与k相等的元素，在查找不成功的情况下至多比较_________次。用分块查找（索引表和各块内均用顺序查找），若分成25块，查找成功的其平均查找长度为___________。 7. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半法查找关键码值8，需做的关键码比较次数为___ _，查找关