数据结构和算法模拟试题

《数据结构和算法模拟试题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、学号：姓名：《数据结构与算法》模拟题一、填空题：（共15分）（每空一分）1.按照排序时，存放数据的设备，排序可分为<1>内部排序和<2>外部排序。2.图的常用的两种存储结构是<3>邻接矩阵存储和<4>邻接表面存储。3.数据结构中的三种基本的结构形式是<5>x线性结构和<6>树形结构、<7>图形结构。4.一个高度为6的二元树，最多有<8>63个结点。5.线性查找的时间复杂度为：<9>，折半查找的时间复杂度为：<10>、堆分类的时间复杂度为：<11>。6.在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们介绍的几种散列函数构造法中，随机性最

2、好的是<12>随机数法、最简单的构造方法是<13>除留余数法。7.线性表的三种存储结构是：数组、<14>链表、<15>静态链表。二、回答下列问题：（共30分）1.现有如右图的树，回答如下问题：A）根结点有：6B）叶结点有：5第12页（共12页）学号：姓名：A）具有作大度的结点：9和10B）结点o的祖先是：0和2C）结点o的后代是：101.栈存放在数组A[m]中，栈底位置是m-1。试问：A）栈空的条件是什么？B）栈满的条件是什么？2.数据结构和抽象数据型的区别与联系：3.已知一株非空二元树，其先根与中根遍历的结果为：先根：ABCDEFGHI中跟：CBEDAGFHI将此

3、二元树构造出来。第12页（共12页）学号：姓名：1.分析下列程序的运行时间：A)voidmystery(intn){inti,j,k;for(i=1;i

4、b)sin(x+5)—a/x2，求该表达式的波兰表示法的前缀和后缀表示（要求给出过程）。第12页（共12页）学号：姓名：三、实现下列算法：（共３0分）1.在指针实现的线性表L中，实现在线性表L中删除关键字为x的结点。(共7分)2.3.设有如下图的双向环形链表L=(a,b,c,d)。请写出将该表转换为L=(b,a,c,d)的简单操作。（共7分）abcdLLDRLL第12页（共12页）学号：姓名：1.在线索二元树中，由结点P求其先根顺序的后继。（共8分）先根：ABCDEFGHI中跟：CBEDAGFHI将此二元树构造出来。遍历的基本方法：先左子树后右子树。1,先根遍历可以

5、确定根节点为A,2,依据1步，可以在中根遍历中确定左子树为：CBED,右为：GFHI3,在可以重复1,2步。就可以得到结果。ABFCDGHI4,O(n^3)+O(1)第12页（共12页）学号：姓名：1.在二元查找树F中，实现插入记录R。（共8分）第12页（共12页）学号：姓名：第12页（共12页）学号：姓名：四、对下面的带权连通无向图，用Prim（普里姆）算法，构造一株最小生成树。画出构造过程的每一步。（12分）第12页（共12页）学号：姓名：第12页（共12页）学号：姓名：jklmop1028161222251418n24第12页（共12页）学号：姓名：五、设要分

6、类的数据存放在数组A3141592653中。要进行堆分类，首先得为其建立一个初始堆，试画出初始建堆过程中，二元树的变化和数组A的变化。（共13分）第12页（共12页）