2018年山东工商学院算法与数据结构考研真题A卷.doc

2018年山东工商学院算法与数据结构考研真题A卷一、简答题（共6题，每题10分）1.线性表的存储结构有哪两种?区别是什么?若线性表经常需要进行插入和删除操作，应采用哪种存储结构?说出理由。2.对比分析简单选择排序和堆排序算法，从时间复杂度、空间复杂度、稳定性等方面比较。为什么说堆排序是简单选择排序算法的改进?3.具有1500个结点的完全二叉树有多少个叶子结点?写出推导过程。4.对比分析顺序查找、折半查找算法的存储结构、时间复杂度和空间复杂度。5.将两个栈共享存储空间，存储在数组V0.MAXSIZE-1中，如何设计才能尽量利用空间，给出栈的数据类型定义，写出栈空、栈满的条件是什么?6.对比分析图的深度优先搜索和广度优先搜索算法的异同点。二、综合应用题（共7题，每题10分）1.（1）请写出如图1所示的二叉树先序遍历和中序遍历序列（2）将图1所示的二叉树转换成树或者森林。（3）图1对应的先序线索树中，结点B和E是否有线索，若有，在原图上画出二者的先序线索。2.设关键字序列为（39，15，66，23，54，40，25），哈希函数为H（key）=key%9，采用线性探测法解决冲突，请回答（1）什么是冲突?（2）画出哈希表的示意图;（3）查找40需要和哪些关键字进行比较?（4）计算等概率下查找成功的ASL。3.设有无向图G如下图所示（1）请画出图 G的邻接矩阵。（2）简述克鲁斯卡尔（kruskal）算法的基本思想。（3）克鲁斯卡尔（kruskal）算法构造最小生成树。要求画出最小生成树，并写出各条边的并入顺序。4.假设用于通信的电文由字符集a，b，c，d，e，f，g中的字母构成。它们在电文中出现的频度分别为0.31，0.16，0.10，0.08，0.11，0.20，0.04，要求（1）简述 Huffman 树算法的基本步骤。（2）画出对应的 Huffman 树，计算加权路径长度 WPL。（3）写出每个字符的哈夫曼编码。5.已知待排序记录的关键字序列46，28，90，65，3，65*，20，要实现按关键字非递减有序排列，请完成如下操作（1）简单选择排序写出第1、2趟排序结果。（2）堆排序写出初始堆、输出3以后的重建堆。（3）快速排序的第1趟排序结果。6.设有一组初始记录关键字为（45，80，50，30，22，78）。（1）构造一棵二叉排序树（不必写过程），并计算平均查找长度 ASL。（2）什么是平衡二叉树?构造一棵平衡二叉树（要求给出构造过程），并计算平均查找长度ASL。7.如图3所示的是一个具有11个活动（al，;a9）的某个工程的AOE 网，顶点V1表示工程开始，顶点 V6 表示工程结束，边上的权值表示活动所需的时间。（1）计算各顶点事件的最早和最迟发生时间。（2）计算各活动的最早和最迟开始时间。（3）求关键活动和关键路径。三、算法题（共2题，每题10分）1.一组非递减有序排列的整数用顺序表存储，编写算法在有序表中插入一个新元素x，插入后该表仍然有序。（1）采用C或C+，给出顺序表的类型定义;（2）写出算法的基本设计思想;（3）结合设计思想，采用C或C+描述算法，关键之处做出注释。2.一棵树采用孩子兄弟表示法存储，试编写算法统计树中叶子结点的个数。要求（1）采用C或C+，给出孩子兄弟表示法的数据类型定义;（2）写出算法的基本设计思想;（3）结合设计思想，采用C或C+描述算法，关键之处做出注释。