资源预览内容
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
亲,该文档总共6页全部预览完了,如果喜欢就下载吧!
资源描述
学号: 姓名:数据结构与算法模拟题一、填空题:(共15分)(每空一分)1. 按照排序时,存放数据的设备,排序可分为 排序和 排序。2. 图的常用的两种存储结构是 和 。3. 数据结构中的三种基本的结构形式是 和 、 。4. 一个高度为6的二元树,最多有 个结点。5. 线性查找的时间复杂度为: ,折半查找的时间复杂度为: 、堆分类的时间复杂度为: 。6. 在采用散列法进行查找时,为了减少冲突的机会,散列函数必须具有较好的随机性,在我们介绍的几种散列函数构造法中,随机性最好的是 法、最简单的构造方法是 。7. 线性表的三种存储结构是:数组、 、 。二、回答下列问题:(共30分)1. 现有如右图的树,回答如下问题:A) 根结点有:B) 叶结点有:C) 具有作大度的结点:D) 结点o的祖先是:E) 结点o的后代是:2. 栈存放在数组Am中,栈底位置是m-1。试问:A) 栈空的条件是什么?B) 栈满的条件是什么? 3. 数据结构和抽象数据型的区别与联系: 4. 已知一株非空二元树,其先根与中根遍历的结果为:先根:ABCDEFGHI 中跟:CBEDAGFHI 将此二元树构造出来。5. 分析下列程序的运行时间:A) void mystery(int n)int i, j, k; for(i=1; in; i+) for(j=i+1; j=n; j+) for(k=1; k=j; k+)some statement requiring O(1) time; B)void podd(int n) int I, j, x, y; for(I=1; I=n; I+) if( odd(I ) ) for(j=I; j=n; j+) x=x+1; for(j=1; j=I; j+) y=y+1; 6. 已知数学表达式是(3+b)sin(x+5)a/x2,求该表达式的波兰表示法的前缀和后缀表示(要求给出过程)。三、实现下列算法:(共0分)1. 在指针实现的线性表L中,实现在线性表L 中删除关键字为x的结点。(共7分)2. 设有如下图的双向环形链表L=(a, b, c, d) 。请写出将该表转换为L=(b, a, c, d)的简单操作。(共7分)abcdLL D RLL 3. 在线索二元树中,由结点P求其先根顺序的后继。(共8分)4. 在二元查找树F中,实现插入记录R。(共8分)四、对下面的带权连通无向图,用Prim(普里姆)算法,构造一株最小生成树。画出构造过程的每一步。(12分)jklmop1028161222251418n24五、设要分类的数据存放在数组A3141592653中。要进行堆分类,首先得为其建立一个初始堆,试画出初始建堆过程中,二元树的变化和数组A的变化。(共13分)版 权 所 有,侵 权 必 究 联 系Q Q68843242 本页为自动生成页,如不需要请删除!谢谢!如有侵权,请联系68843242删除!1,侵权必究 联系QQ68843242 1,版 权 所 有,侵 权 必 究 联 系Q Q68843242 本页为自动生成页,如不需要请删除!谢谢!如有侵权,请联系68843242删除!版 权 所 有,侵 权 必 究 联 系Q Q68843242 本页为自动生成页,如不需要请删除!谢谢!如有侵权,请联系68843242删除!侵权必究 联系QQ68843242 第6页(共6页)
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号