《哈尔滨工业大学数据结构与算法模拟题.doc》由会员分享，可在线阅读，更多相关《哈尔滨工业大学数据结构与算法模拟题.doc（8页珍藏版）》请在三一文库上搜索。
1、数据结构与算法模拟题一、填空题：（共15分）（每空一分）1. 按照排序时，存放数据的设备，排序可分为<1>排序和<2>排序。2. 图的常用的两种存储结构是<3>和<4>。3. 数据结构中的三种基本的结构形式是<5>和 <6>、 <7>。4. 一个高度为6的二元树，最多有<8>个结点。5. 线性查找的时间复杂度为：<9>，折半查找的时间复杂度为：<10>、堆分类的时间复杂度为：<11>。6. 在采用散列法进行查找时，为了减少冲突的机会，散列函数 必须具有较好的随机性
2、，在我们介绍的几种散列函数构造法中，随机性最好的是<1空法、最简单的构造方法是<13>。7. 线性表的三种存储结构是：数组、 <14>、<15>。二、回答下列问题：（共30分）1. 现有如右图的树，回答如下问题:A）根结点有:B）叶结点有：C）具有作大度的结点：D）结点的祖先是：E）结点的后代是：试问:2. 栈存放在数组Am中，栈底位置是m-1A）栈空的条件是什么？B）栈满的条件是什么？3. 数据结构和抽象数据型的区别与联系:4. 已知一株非空二元树，其先根与中根遍历的结果为：先根： ABCDEFGHI中跟： CBEDAGFHI将此二元树构造出来5.
3、分析下列程序的运行时间：A) void mystery(int n)int i, j, k;for(i=1; i<n; i+)for(j=i+1; j<=n; j+)for(k=1; k<=j; k+)time;some statement requiring O(1)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/x 2，求
4、该表达式的波兰 表示法的前缀和后缀表示（要求给出过程）三、实现下列算法：（共3 0分）1. 在指针实现的线性表L中，实现在线性表L中删除关键字为x的结点。（共7分）2. 设有如下图的双向环形链表L=（a, b, c, d）。请写出将该表转换为L=（b, a, c, d）的简单操作。（共7分）1k>aIk-bcfc-dIFLL D RL3. 在线索二元树中，由结点P求其先根顺序的后继。（共8分）4. 在二元查找树F中，实现插入记录R。（共8分）四、对下面的带权连通无向图，用Prim （普里姆）算法，构造一株最小生成树。画出构造过程的每一步。（12分）28五、设要分类的数据存放在数组 A3141592653中。要进行堆分类，首先得为其建立一个初始堆，试画出初始建堆过程中，二元树的变化和数组 A的变化。（共13分）