第 7 页精品文档---下载后可任意编辑数据结构算法试卷 1、2024 年春季《数据结构与算法 B》期末考试模拟试卷学号姓名老师/教室(注：如未标明，本试卷题中的下标、位 H 都从 o 开始计数)一、填空题(共 32分)1.设有字符串变董StringA=“This”，B=“is’’，C=“just”，D=“ajest”，请计算以下表达式：(1)A+B+D=“”(2)D.IndexOf(‘‘t”)=(3)B.Strlength()=(4)D.SubStr(1.2)=“”2.顺序查找 n 个元素的顺序表，若查找胜利，则比较关键字的次数最多为次；若查找失败，则比较关键字的次数最多为，最少为次。3. 2、在散列函数 H(key)=key%p 屮，p 值最好取。4.对于下列图邻接表所对应的有向图，试写出：(1)从顶点①出发进行深度优先遍历结果:(2)从顶点①出发进行广度优先遍历结果；5.当图中各条边上的权伉时，宽度优先搜寻算法可用来解决单源最短路径问题？6.—棵有 n 个结点的满二叉树有个度为 1 的结点、有个分支(非终端)结点；该满二叉树的深度最大为，最小为。(独根树深度为 0)7.对于给定的 n 个元素，可以构造出的规律结构有，，四种。8.下而程序段的时间冗杂度为。(n〉l)［大 O 表示法］【2 分】sum=l；for(i=0;sumn 3、;i-H-)sum+=l;9.对于最大堆 6543592437485712232853,删除掉最大元素后，堆屮元素为 10.从空二叉树开始，严格根据二叉搜寻树的插入算法(不进行旋转平衡)，逐个插入关键码｛18,73,10,5,68,99,27,41,51,32,25｝构造出一棵二义搜寻树，该二义树转换为森林，则该森林的层次遍历序列为。11.用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 12345,％了得到 13542 出栈顺序，相应的 S 和 X 的操作串为。二、单项选择题(18 分，每题 2 分，最终两题每题 4 分)1.对初始状态为 4、递增的表按递增顺序排序，最省时间的是()算法。A.基数排序 B.桶排C.直接插入排序 D.归并排序 2.—个 n 个顶点的连通无向图，其边的个数至少为()。A.n-1B.nC.n+1D.nlogn；3.线性表(aha2，...，a?)以链接方式存储时，访问第 i 位賈元素的时间冗杂度为()A.0(i)B.0(1)C.0(n)D.0(i-1)4.使用 Prim 算法从结点 0 出发求下列图的最小生成树，依次写出每次被加入到最小生成树中边的编号，下面正确的答案是()。A.(0,2)(3,5)(1,4)(2,5)(1,2)B.(0,2)(2, 5、5)(3,5)(1,2)(1,4)C.(0,2)(3,5)(1,4)(1,2)(2,5)B.(0,2)(1,2)(1,4)(2,5)(3,5)5.一个有 n 个结点的图，最多有()个连通重量。A.0B.1C.n-1D.n6....
