1、数据结构与算法模拟题一、填空题：（共 15 分） （每空一分）1. 按照排序时，存放数据的设备，排序可分为 排序和 排序。2. 图的常用的两种存储结构是 和 。3. 数据结构中的三种基本的结构形式是 和、 。4. 一个高度为 6 的二元树，最多有 个结点。5. 线性查找的时间复杂度为： ，折半查找的时间复杂度为： 、堆分类的时间复杂度为： 。6. 在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们介绍的几种散列函数构造法中，随机性最好的是 法、最简单的构造方法是。7. 线性表的三种存储结构是：数组、 、 。二、回答下列问题：（共 30 分）1. 现有如右图的树，回
2、答如下问题：A） 根结点有：B） 叶结点有：学号： 姓名：第 2 页（共 6 页）C） 具有作大度的结点：D） 结点的祖先是：E） 结点的后代是：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
3、+)for(k=1; k=j; k+)学号： 姓名：第 3 页（共 6 页）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，求该表达式的波兰表示法的前缀和后缀表示（要求给出过程） 。学号： 姓名：第 4 页（共 6 页）三、实现下列算法：（共0 分）1. 在指针实现的线性表 L 中，实现在线性表 L
4、 中删除关键字为 x 的结点。(共 7 分)2. 设有如下图的双向环形链表 L=(a, b, c, d) 。请写出将该表转换为 L=(b, a, c, d)的简单操作。 （共 7 分）3. 在线索二元树中，由结点 P 求其先根顺序的后继。 （共 8 分）4. 在二元查找树 F 中，实现插入记录 R。 （共 8 分）L a b c dLL D RL学号： 姓名：第 5 页（共 6 页）四、对下面的带权连通无向图，用 Prim（普里姆）算法，构造一株最小生成树。画出构造过程的每一步。 （12 分） 102816122225141824学号： 姓名：第 6 页（共 6 页）五、设要分类的数据存放在数组 A3 1 4 1 5 9 2 6 5 3中。要进行堆分类，首先得为其建立一个初始堆，试画出初始建堆过程中，二元树的变化和数组 A 的变化。 （共 13 分）
