数据结构与算法模拟题一、填空题：（共15分）（每空一分）1. 按照排序时，存放数据的设备，排序可分为 内部 排 序和外部 排序。2. 图的常用的两种存储结构是邻接矩阵和邻接表 。3. 数据结构中的三种基本的结构形式是 x线性结构和树形结构 、图形结构 。4. 一个高度为6的二元树，最多有63个结点。5. 线性查找的时间复杂度为：0（n），折半查找的时间复杂度为：O（nlogn） 、堆分类的时间复杂度为：O（nlogn）。6. 在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们介绍的几种散列函数构造法 中，随机性最好的是 随机数法法、最简单的构造方法是除留余数法。7. 线性表的三种存储结构是：数组、静态链表。二、回答下列问题：（共30 分）1. 现有如右图的树，回答如下问题：A）根结点有：6B）叶结点有：5链表C）具有作大度的结点：9和10D）结点的祖先是：0和2E）结点的后代是：102. 栈存放在数组Am中，栈底位置是m-1。试问:A）栈空的条件是什么？ top=m-1B）栈满的条件是什么？栈满top=03. 数据结构和抽象数据型的区别与联系：数据结构：是相互之间存在一种或多种特定关系的数据元素 的集合。数据元素相互之间的关系称为结构。抽象数据类型：是指一个数学模型（数据结构）以及定义在 该模型（数据结构）上的一组操作。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 0(1) time;这个应该是时间复杂度吧：O( nW)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; jv=l; j+)y=y+i;O (nA2)6. 已知数学表达式是(3+b)sin(x+5) a/x2,求该表达式的波兰表 示法的前缀和后缀表示(要求给出过程)。我感觉它的前缀表示法为-*+3bSIN+x5*/ax0.5 ，后缀表示法为 3b+x5+SIN*ax/0.5*-。三、实现下列算法：(共3 0分)1.在指针实现的线性表L中，实现在线性表L中删除关键字为 x的结点。(共7分)in tdeleteValueList(structList*L,elemTypex)in ti,j;/*从线性表中顺序查找出值为x的第一个元素*/for(i=0;isize;i+)if(L-listi=x)break;/*若查找失败，表明不存在值为x的元素，返回0*/if(i=L-size)return。；/*删除值为x的元素L-listi*/for(j=i+1;jsize;j+)L-listj-1=L-listj;L-size-;returnl;亠abcdrIFLL D RL2.设有如下图的双向环形链表L=(a, b, c, d)。请写出将该表转 换为L=(b, a, c, d)的简单操作。(共7分)dLL D RLLL-RL-RL = D-RL ; D-RL = L-RL; L dRL-LL-RL=D-LL;D-LL=L-RL-LL-LL;L-RL=D;四、对下面的带权连通无向图，用Prim （普里姆）算法，构造一株最小生成树。画出构造过程的每一步。（12分）