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

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

第1页 / 共3页

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

第2页 / 共3页

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

第3页 / 共3页

文本预览

2018 年山东工商学院算法与数据结构考研真题 B 卷一、简答题（共 6 题，每题 10 分） 1.基本的数据结构有哪几类?简述其逻辑特点。对于社交网站中处理的数据应该选择什么数据结构?给出你的理由。 2.比较栈和队列两种数据结构的异同，举例说明哪些算法中会用到栈或者队列。 3.若线性表中元素总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构?为什么? 4.具有 1000 个结点的完全二叉树有多少个叶子结点?写出推导过程。 5.设 A[0.，9，0..9]是 10 阶对称矩阵，若采用压缩存储的方式存储其下三角矩阵，以行序为主序，每个元素占 2 个单元，矩阵第一个元素 A[0，0]的地址是 1000，A[4，5]的地址是多少?写出计算过程。 6.什么是 A0V 网?什么是 AOE 网?分析二者的异同点，分别有什么应用? 二、综合应用题（共 7 题，每题 10 分） 1.请写出如图 1 所示的二叉树的先序遍历和中序遍历序列，并将其转换成树或者森林。 2.设有无向图 G 如下图所示∶

（1）请画出图 G 的邻接矩阵和邻接表。（2）并在（1）所画的邻接表的基础上，写出从顶点 1 出发的深度优先遍历和广度优先遍历序列。（3）简述深度优先算法和广度优先算法的不同点。 3.设有无向图 G（如图 3），（1）简述普里姆（prim）算法的基本思想。（2）请按普里姆算法从顶点 v1 开始构造最小生成树。请写出并入边的次序。 4.已知某系统在通信联络中出现的字符为{a，b，c，d，e，f，g，h}，其概率分别为{0.07， 0.19，0.02，0.06，0.32，0.03，0.21，0.10}。要求∶ （1）简述构造 Huffman 树的算法思想。（2）树画出对应的 Huffman 树，计算加权路径长度 WPL。（3）写出每个字符的哈夫曼编码。 5.已知一组关键字序列{38，23，7，79，9，45，3，19，30，62，23*，47}，要实现非递减有序排列，请完成如下操作∶ （1）冒泡排序，写出第 1、2 趟排序结果。（2）快速排序（选第一个记录为枢轴），写出第 1 趟快速排序的结果。（3）分析冒泡排序和快速排序算法的异同。6.如图 4 所示的是一个具有 11 个活动（al，…， al1）的某个工程的 AOE 网，顶点 V1 表示工程开始，顶点 V9 表示工程结束，边上的权值表示活动所需的时间。

（1）计算各顶点事件的最早和最迟发生时间。（2）计算各活动的最早和最迟开始时间。（3）求关键活动和关键路径。 7.设数据集合 D=2，28，15.18，10，20，17，35，19}试完成下列各题∶ （1）什么是二叉排序?依次取 D 中各数据，构造一棵二叉排序树 T。（2）如何依据此二叉树 T 得到 D 的一个有序序列。（3）画出在二叉树 T 中删除"28"后的树结构。三、算法题（共 2 题，每题 10 分） 1.设有两个栈 sl，s2 都采用顺序栈方式，并且共享一个存储区 data[0..MAXSIZE-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。请编写 s1，s2 的入栈、出栈的操作算法。（1）采用 C 或 C++，写出该栈的数据类型定义; （2）采用 C 或 C++描述算法，关键之处做出注释。 2.二叉排序树采用二叉链表存储，结点结构为[Lchild|key|factor|Rchild]，其中 key 为 char 类型关键字，factor 为结点的平衡因子，Lchild 和 Rchild 分别是左、右孩子指针。编写算法计算并输出每个结点的平衡因子。（1）采用 C 或 C++，给出二叉链表的数据类型定义; （2）写出算法的基本设计思想; （3）结合设计思想，采用 C 或 C++描述算法，关键之处做出注释。

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料