北大数据结构与算法期末考试模拟试卷.docx

2014年春季北大《数据结构与算法B》期末考试模拟试卷（本试卷只是给同学们看看考题形式和范围，难度与真实考卷稍有差别）学号______________ 姓名______________ 教师/教室______________（注：如未标明，本试卷题中的下标、位置都从0开始计数）填空题（共32分）设有字符串变量String A = “This”, B=“is”, C=“just”, D=“a?test”，请计算下列表达式：（1）A+B+D=_“Thisisa?test”_；（2）D.IndexOf(“t”) = __2___；（求字符在字符串中的第一个位置）（3）B.Strlength() = ___2___（4）D.SubStr(1,2) = _“?t” __（注：1为起始下标，2为子串长度）【4分】顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为___n___次；若查找失败，则比较关键字的次数最多为___n___，最少为____n___次。【3分】在散列函数H（key）=key%p中，p值最好取___质数（或素数）___。【1分】对于下图邻接表所对应的有向图，试写出：【2分】(1) 从顶点①出发进行深度优先遍历结果__1, 2, 3, 4, 5__；(2) 从顶点①出发进行广度优先遍历结果__1, 2, 3, 4, 5 _； 当图中各条边上的权值 __都相等__ 时，宽度优先有哪些信誉好的足球投注网站算法可用来解决单源最短路径问题？【2分】一棵有n个结点的满二叉树有_0_个度为1的结点、有_(n-1)/2个分支 （非终端）结点；该满二叉树的深度最大为___(n-1)/2 __, 最小为 int(log2n)或log2n。（独根树深度为0）【4分】对于给定的n个元素,可以构造出的逻辑结构有 线性结构 ， 树形结构 ， 图形结构 ，_集合__四种。【2分】下面程序段的时间复杂度为__O(n)_。(n1) [大O表示法] 【2分】 sum=1； for (i=0;sumn;i++) sum+=1;对于最大堆 65 43 59 24 37 48 57 12 23 28 5 3，删除掉最大元素后，堆中元素为59,43,57,24,37,48,3,12,23,28,5【2分】从空二叉树开始，严格按照二叉有哪些信誉好的足球投注网站树的插入算法（不进行旋转平衡），逐个插入关键码 { 18,73,10,5,68,99,27,41,51,32,25 } 构造出一棵二叉有哪些信誉好的足球投注网站树，该二叉树转换为森林，则该森林的层次遍历序列为 _18 73 99 10 68 5 27 41 51 25 32__【4分】对于的二叉树为用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为12345，为了得到13542出栈顺序，相应的S和X的操作串为_SXSSXSSXXX__。【2分】单选题（18分，每题2分，最后两题每题4分）1. 对初始状态为递增的表按递增顺序排序，最省时间的是（ C ）算法。 A. 基数排序 B. 桶排 C. 直接插入排序 D. 归并排序2. 一个n个顶点的连通无向图，其边的个数至少为（A）。A．n-1 B．n C．n+1 D．nlogn；3． 线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为（ C ）A．O（i） B．O（1） C．O（n） D．O（i-1）4. 使用Prim算法从结点0出发求下图的最小生成树，依次写出每次被加入到最小生成树中边的编号，下面正确的答案是（B）。A. (0, 2) (3, 5) (1, 4) (2, 5) (1, 2) B. (0, 2) (2, 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个结点的图，最多有（ D ）个连通分量。A．0 B．1 C．n-1 D．n6. 用二分（对半）查找法检索元素速度比用顺序法( D ) 。【2分】必然快 B. 必然慢 C. 相等 D. 不能确定7. 已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( D )。【4分】A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE8．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟处理（对应于排序算法中一层循环或一层递归算法）后，数据的排列变为{4，9，-1，8，20，7，