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

发布时间：2022-09-16 发布人：admin 分类：说明书资料大小：0.18M 资料格式：doc 举报版权申诉

第1页 / 共3页

2018年山东工商学院算法与数据结构考研真题A卷.doc.pdf-第2页.jpg

第2页 / 共3页

2018年山东工商学院算法与数据结构考研真题A卷.doc.pdf-第3页.jpg

第3页 / 共3页

文本预览

2018 年山东工商学院算法与数据结构考研真题 A 卷一、简答题（共 6 题，每题 10 分） 1.线性表的存储结构有哪两种?区别是什么?若线性表经常需要进行插入和删除操作，应采用哪种存储结构?说出理由。 2.对比分析简单选择排序和堆排序算法，从时间复杂度、空间复杂度、稳定性等方面比较。为什么说堆排序是简单选择排序算法的改进? 3.具有 1500 个结点的完全二叉树有多少个叶子结点?写出推导过程。 4.对比分析顺序查找、折半查找算法的存储结构、时间复杂度和空间复杂度。 5.将两个栈共享存储空间，存储在数组 V[0..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++描述算法，关键之处做出注释。

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料