数据结构和算法模拟试题.doc

学号： 姓名： 第 PAGE 2页（共 NUMPAGES 11页） WORD文档下载可编辑 专业资料整理分享 《数据结构与算法》模拟题 一、填空题：（共15分）（每空一分） 按照排序时，存放数据的设备，排序可分为1 内部 排序和2 外部 排序。 图的常用的两种存储结构是3 邻接矩阵存储 和4 邻接表面存储 。 数据结构中的三种基本的结构形式是5 x线性结构 和6 树形结构 、7 图形结构 。 一个高度为6的二元树，最多有8 63 个结点。 线性查找的时间复杂度为：9 ，折半查找的时间复杂度为：10 、堆分类的时间复杂度为：11 。 在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们介绍的几种散列函数构造法中，随机性最好的是12随机数 法、最简单的构造方法是13 除留余数法 。 线性表的三种存储结构是：数组、14 链表 、15 静态链表 。 二、回答下列问题：（共30分） 现有如右图的树，回答如下问题： 根结点有： 6 叶结点有： 5 具有作大度的结点：9和10 结点?的祖先是：0和2 结点?的后代是：10 栈存放在数组A[m]中，栈底位置是m-1。试问： 栈空的条件是什么？ 栈满的条件是什么？ 数据结构和抽象数据型的区别与联系： 已知一株非空二元树，其先根与中根遍历的结果为：先根：ABCDEFGHI 中跟：CBEDAGFHI 将此二元树构造出来。 分析下列程序的运行时间： 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; } } 已知数学表达式是(3+b)sin(x+5)—a/x2，求该表达式的波兰表示法的前缀和后缀表示（要求给出过程）。 三、实现下列算法：（共３0分） 在指针实现的线性表L中，实现在线性表L 中删除关键字为x的结点。(共7分) 设有如下图的双向环形链表L=(a, b, c, d) 。请写出将该表转换为L=(b, a, c, d)的简单操作。（共7分） ab a b c d LL D RL L 在线索二元树中，由结点P求其先根顺序的后继。（共8分） 先根：ABCDEFGHI 中跟：CBEDAGFHI 将此二元树构造出来。遍历的基本方法：先左子树后右子树。 1,先根遍历可以确定根节点为A, 2,依据1步，可以在中根遍历中确定左子树为：CBED,右为：GFHI 3,在可以重复1,2步。就可以得到结果。 A B F C D G H I 4, O(n^3)+O(1)  在二元查找树F中，实现插入记录R。（共8分） 四、对下面的带权连通无向图，用Prim（普里姆）算法，构造一株最小生成树。画出构造过程的每一步。（12分） ??? ? ? ? ? ? ? 10 28 16 12 22 25 14 18 ? 24 3 1 4 1 5 9 2 6 5 3 中。要进行堆分类，首先得为其建立一个初始堆，试画出初始建堆过程中，二元树的变化和数组A的变化。（共13分）