《2018年山东工商学院算法与数据结构考研真题B卷.doc》由会员分享，可在线阅读，更多相关《2018年山东工商学院算法与数据结构考研真题B卷.doc（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2018年山东工商学院算法与数据结构考研真题B卷一、简答题（共6题，每题10分）1.基本的数据结构有哪几类?简述其逻辑特点。对于社交网站中处理的数据应该选择什么数据结构?给出你的理由。2.比较栈和队列两种数据结构的异同，举例说明哪些算法中会用到栈或者队列。3.若线性表中元素总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构?为什么?4.具有1000个结点的完全二叉树有多少个叶子结点?写出推导过程。5.设A0.，9，0.9是10阶对称矩阵，若采用压缩存储的方式存储其下三角矩阵，以行序为主序，每个元素占2个单元，矩阵第一个元素A0，0的地址是1000，
2、A4，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，
3、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网
4、，顶点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都采用顺序栈方式，并且共享一个存储区data0.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+描述算法，关键之处做出注释。