数据结构与算法模拟题1111.doc

《数据构造与算法》模拟题一、填空题：（共15分）（每空一分）1. 按照排序时，寄存数据的设备，排序可分为<1> 内部 排序和<2> 外部 排序2. 图的常用的两种存储构造是<3> 邻接矩阵 和<4> 邻接表 3. 数据构造中的三种基本的构造形式是<5> x线性构造 和<6> 树形构造 、<7> 图形构造 4. 一种高度为6的二元树，最多有<8> 63 个结点5. 线性查找的时间复杂度为：O(n) ，折半查找的时间复杂度为：O(nlogn) 、堆分类的时间复杂度为：O(nlogn) 6. 在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们简介的几种散列函数构造法中，随机性最佳的是随机数法 法、最简朴的构造措施是除留余数法 7. 线性表的三种存储构造是：数组、链表 、静态链表 二、回答问题：（共30分）1. 既有如右图的树，回答如下问题：A） 根结点有：6B） 叶结点有：5C） 具有作大度的结点：9和10D） 结点o的祖先是：0和2E） 结点o的后裔是：102. 栈寄存在数组A[m]中，栈底位置是m-1。

试问：A） 栈空的条件是什么？top==m-1B） 栈满的条件是什么？栈满top==0 3. 数据构造和抽象数据型的区别与联系：数据构造：是互相之间存在一种或多种特定关系的数据元素的集合数据元素互相之间的关系称为构造抽象数据类型：是指一种数学模型（数据构造）以及定义在该模型（数据构造）上的一组操作 4. 已知一株非空二元树，其先根与中根遍历的成果为：先根：ABCDEFGHI 中跟：CBEDAGFHI 将此二元树构造出来5. 分析下列程序的运营时间：A) void mystery(int n){int i, j, k; for(i=1; i

我感觉它的前缀表达法为-*+3bSIN+x5*/ax0.5，后缀表达法为3b+x5+SIN*ax/0.5*- 三、实现下列算法：（共３0分）1. 在指针实现的线性表L中，实目前线性表L 中删除核心字为x的结点共7分)intdeleteValueList(structList*L,elemTypex){　　 inti,j;　　 /*从线性表中顺序查找出值为x的第一种元素*/　　 for(i=0;isize;i++){　　　　 if(L->list[i]==x){　　　　　　　　 break;　　　　 }　　 }　　 /*若查找失败，表白不存在值为x的元素，返回0*/　　 if(i==L->size){　　　　 return0;　　 }　　 /*删除值为x的元素L->list[i]*/　　 for(j=i+1;jsize;j++){　　　　 L->list[j-1]=L->list[j];　　 }　　 L->size--;　　 return1;2. 设有如下图的双向环形链表L=(a, b, c, d) 请写出将该表转换为L=(b, a, c, d)的简朴操作共7分）abcdLL D RLL abcdLL D RLL L->RL->RL = D->RL ; D->RL = L->RL; LàRL->LL->RL=D->LL; D->LL=L->RL->LL->LL; L->RL=D; 四、对下面的带权连通无向图，用Prim（普里姆）算法，构造一株最小生成树。

画出构造过程的每一步12分）。