哈尔滨工业大学数据结构与算法历年考题汇总.pdf

《哈尔滨工业大学数据结构与算法历年考题汇总.pdf》由会员分享，可在线阅读，更多相关《哈尔滨工业大学数据结构与算法历年考题汇总.pdf（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 期末期末 2005 2005 数据结构与算法试卷数据结构与算法试卷试卷类型:期末试卷年份:05授课教师:廖明宏有无答案:无答案哈工大 2005 年春季学期数据结构与算法 试 卷)一填空题（每空 1 分，共 10 分）1假定对线性表(38,25,74,52,48)进行散列存储，采用 H(K)=K%7 作为散列函数，若分别采用线性探查法和链接法处理冲突，则对各自散列表进行查找的平均查找长度分别为_和_。2 假定一组记录的排序码为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的结果为_。3 在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为_，整个堆排序过程

2、的时间复杂度为_。4 有向图的邻接矩阵表示法中某一行非 0 元素的个数代表该顶点的，某一列非0 元素的个数是该顶点的。5对于下面的带权图 G3，若从顶点 v0 出发，则按照普里姆（Prim）算法生成的最小生成树中，依次得到的各条边为_。6由带权为 3，9，6，2，5 的 5 个叶子结点构成一棵哈夫曼树，则带权路径长度为7由三个结点构成的二叉树，共有 种不同结构。二选择题（每题 1 分，共 10 分）1快速分类在 的情况下不利于发挥其长处.A.待分类的数据量太大 B.待分类的数据相同值过多C.待分类的数据已基本有序 D.待分类的数据值差过大.2两路归并排序中，归并的趟数是。A.O(n)B.O(l

3、og2n)C.O(nlog2n)D.O(n2)注意行为规范(遵守考场纪律第 1 页，共 6 页3对外部分类的 K 路平衡归并，采用败者树时，归并的效率与 K。A.有关 B.无关 C.不能确定 D.都不对4对于一个索引顺序文件，索引表中的每个索引项对应主文件中的。A.一条记录 B.多条记录C.所有记录 D.三条以上记录5.若线性表采用顺序存储结构，每个元素占用 4 个存储单元，第一个元素的存储地址为 100，则第 12 个元素的存储地址时。6若频繁地对线性表进行插入和删除操作，该线性表应该采用 存储结构。A.散列 B.顺序 C.链式 D.索引7若长度为 n 的非空线性表采用顺序储存结构，删除表中

4、第 i 个数据元素，需要移动表中 个数据元素。+i +18栈和队列的相同之处是。【A.元素的进出满足先进后出 B.元素的进出满足后进先出C.只允许在端点进行插入和删除操作 D.无共同点9在一棵高度为 k 的二叉树中，最多含有()个结点。A2k-1 B2k-l C2k-1 Dk10任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序()。.A发生改变 B不发生改变 C不能确定 D以上都不对三判断题，正确的在括号内画，错误的在括号内画。（每小题 1 分，共 10 分）1树的父链表示就是用数组表示树的存储结构。（）.2任何二元树都唯一对应一个森林，反之亦然。.（）：3有向图的邻接矩阵一定不是

5、对称的。（）4AOE 网中，只有一个入度为 0 的顶点（起始点），只有一个出度为 0 的顶点（结束点）。（）5关键路径可能不只一条，但缩短某一关键路径一定能够缩短工期。（）6顺序存储方式只能用于存储线性结构。()7用循环链表作为存储结构的队列就是循环队列。()】8倒排文件的主要优点为便于节省空间（）。9一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为 40,38,46,56,79,84（）。10 算法分析的目的是分析算法的易读性（）。四简答题1.简述如何用两个栈模拟一个队列的入队和出队操作.(6 分)2.对于图 G5 所

6、示的树：（7 分）(1)写出先根遍历得到的结点序列；(2)写出按层遍历得到的结点序列；(3)画出转换后得到的二元树&图 G5五算法设计1.设二元树采用左右链存储，写出后序遍历该二元树的非递归算法。(12 分)2.设图中各边上的权值均相等,试以邻接表为存储结构,写出求源点Vi到Vj的最短路径算法。(15 分).,哈工大数据结构与算法哈工大数据结构与算法 2009 2009 年试题年试题$20102010 年春年春 A A 卷卷一、填空题（每空 1 分，共 15 分）1.在顺序存储的二叉树中，编号为i 和 j 的两个结点处在同一层的条件是_。2某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是

7、 CBDAFGE，则其后序遍历序列是_。3在有 n 个叶子的哈夫曼树中，分支结点总数为_个。4对于含有 n 个顶点e 条边的连通图，利用 Prim 算法求最小生成树的时间复杂度为_。5.表达式 a*(b+c)-d 的后缀表达式是_。6.假定一棵二叉树的结点数为18，则它的最小深度为_，最大深度为_。7.设有一个 n 阶的下三角矩阵 A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则Aij与 A00之间有_个数据元素。8.设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建 成 的 初 始 堆 为 _。9.

8、磁 盘 文 件 的 归 并 技 术 有_、_、_。10.设有向图 G 中有向边的集合 E=，则该图的一种拓扑序列为_。11.设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行_趟的分配和回收才能使得初始关键字序列变成有序序列。12.利用 Dijkstra 算法求从有向图顶点 v1 到其他各顶点的最短路径要求$边上权值_。二、选择题（每题 1 分，共 15 分）1若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利 用 _ 存 储 方 式 最 节 省 时 间。A.顺 序 表B.双 链表C.单循环链表D.带头结点的双循环链表02在一

9、个具有 n 个单元的顺序栈中，假定以地址低端（即下标为0 的单元）作为栈底，以top作 为 栈 顶 指 针，当 出 栈 时，top的 变 化 为 _。A.不变B.top=0;=top-1;D.top=top+1;3设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20 为基准记录的一趟快速排序结束后的结果为_。A、10，15，14，18，21，36，40，20B、10，15，14，18，20，40，36，21C、10，15，14，20，18，40，36，2lD、15，10，14，18，20，36，40，214任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中

10、的相对次序_。A.肯定不发生改变B.肯定发生改变C.不能确定D.有时发生变化5用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为_。B.6C.8D.96.对线性表进行二分查找时，要求线性表必须_。A、以顺序方式存储B、以链接方式存储C、以顺序方式存储，且数据元素有序D、以链接方式存储，且数据方式有序7.设散列表表长 m=14，散列函数H(k)=kmod11。表中已有15、38、61、84 四个元素，如果用线性探侧法处理冲突，则元素49 的存储地址是_。A.8B.3C.5D.98.若需在 O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是

11、_。A.快速排序B.堆排序C.归并排序D.插入排序9.下面关于 m 阶 B 树的说法正确的是_。每个结点至少有两株非空子树树中每个结点至多有 m-1 个关键字所有的叶子都在同一层上当插入一个记录引起B 树分裂后，树增高一层A.B.C.D.10.已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当折半查找值为90 的元素时，经过_次比较后查找成功。11.能有效缩短关键路径长度的方法是_。A缩短任意一个活动的持续时间B缩短关键路径上任意一个关键活动的持续时间C 缩短多条关键路径上共有的任意一个关键活动的持续时间D 缩短所有关键路径上共有的任意一个关键活动的持

12、续时间12.在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要-探测多个位置，在查找成功的情况下，所探测的这些位置的关键字值_。A.一定都是同义词B.一定都不是同义词C.不一定都是同义词D.都相同13.设哈夫曼编码的长度不超过4，若已对两个字符编码为 1 和 01，则最多还可以对_个字符编码。A2B3C4D514.已知图的邻接表如下所示，根据算法，则从顶点0 出发深度优先遍历的结点序列是_。132B.0231C.0321D.012315.在具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_。(1)(n)(n2)(nlog2n)三、简答题：每题 10 分，共 20 分

13、.1一个按数组元素有序的一维数组一定是堆吗请说明理由。2.设有一组初始记录关键字为(45，80，48，40，22，78)，可以构造出一棵二叉排序树，若不是平衡树则调整平衡，并给出其前序遍历该树的序列，并写出右旋转函数算法。四、算法设计：每题 10 分，共 20 分要求：描述算法设计的基本思想描述算法的详细实现步骤根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C+或JAVA语言实），关键之处请给出简要注释。（栈、队列的存储结构、基本操作可以直接引用）1对给定的序号 j（1jn），要求在无序记录A1An中找到按关键码从小到大排在第 j 位上的记录，试利用快速排序的划分思想设计算法实现上

14、述查找。lchild;p-lchild=lc-rchild;lc-rchild=p;p=lc;四、算法1.1、本算法不要求将整个记录进行排序，而只进行查找第j 个记录。(1)基本思想：改进划分算法，是一次划分将基准元素定位于k，如果 k=j，则找到第 j 小的元素；否则，递归地在k 的左边或右边进行划分，直到k=j 为止。(2)算法详细步骤：略(3)算法如下：intSearch(intA,intn,intj)s=1;t=nk=Partition(A,s,t);while(k！=j)if(kj)k=Partition(A,k+1，t);$elsek=Partition(A,s，k-1);retu

15、rnAj;intPartition(intA,intlow,inthigh)i=low;j=high;pivot=Alow;while(i=pivot&ij)j-;if(ij)Ai+=Aj;%while(Ajpivot&ij)i+;if(inextarc)k=p-adjvex;if(!visitedk)returnexist_path(k,j);按 照 排 序 时，存 放 数 据 的 设 备，排 序 可 分 为排序和排序。2.图的常用的两种存储结构是和】。3.数据结构中的三种基本的结构形式是和、。4.一个高度为 6 的二元树，最多有个 结 点。5.线 性 查 找 的 时 间 复 杂 度 为：，

16、折半查找的时间复 杂 度 为：。6.在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们介绍的几种散列函数构造法中，随机性最好的是法、最简单的构造方法是。7.线性表的三种存储结构是：数组、。二、回答下列问题：（共30 分）1.现有如右图的树，回答如下问题：；、堆 分 类 的 时 间 复 杂 度 为：A）根结点有：B）叶结点有：C）具有作大度的结点：D）结点的祖先是：E）结点的后代是：2.栈存放在数组 Am中，栈底位置是 m-1。试问：A）栈空的条件是什么B）栈满的条件是什么3.|数据结构和抽象数据型的区别与联系：4.已知一株非空二元树，其先根与中根遍历的结果为：先根

17、：ABCDEFGHICBEDAGFHI将此二元树构造出来。5.分析下列程序的运行时间：A)voidmystery(intn)中跟：inti,j,k;for(i=1;in;i+)for(j=i+1;j=n;j+)&for(k=1;k=j;k+)somestatementrequiringO(1)time;B）voidpodd(intn)intI,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/x2，求该表达式的波兰表示法的前缀和后缀表示（要求给出过程）。第 4 页（共 6 页）三、实现下列算法：（共0 分）1.在指针实现的线性表L 中，实现在线性表 L中删除关键字为x 的结点。(共 7 分)2.设有如下图的双向环形链表L=(a,b,c,d)。请写出将该表转换为 L=(b,a,c,d)的简单操作。（共 7 分）3.在线索二元树中，由结点P 求其先根顺序的后继。（共8 分）4.在二元查找树 F 中，实现插入记录 R。（共 8 分）四、对下面的带权连通无向图，用 Prim（普里姆）算法，构造一株最小生成树。画出构造过程的每一步。（12 分）|