试题五北京邮电大学1992年硕士研究生入学考试试题-Read(20211109203306)_第1页
试题五北京邮电大学1992年硕士研究生入学考试试题-Read(20211109203306)_第2页
试题五北京邮电大学1992年硕士研究生入学考试试题-Read(20211109203306)_第3页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、试 5田试题五 北京邮电大学1992年硕士研究生入学考试试题一.答复以下问题:1 利用两个栈sl,s2模拟一个队列时,如何用栈的运算实现队列的插入,删除以及判队空 运算。请简述这些运算的算法思想。2现有n*n阶对角矩阵 M非零元素集中在以主对角线为中心的带状区域,其示意图如图1所示。试问:(1) 该对角矩阵有多少非零元素 ?带状区域的非零 mi的下标i , j与a之 间有何关系?试题5图13.设T是一棵二叉树,除叶子结点外,其 它结点的度数皆为2,假设T中有6个叶结点,试问:(1) T树的最大深度 Kmax=?最小可能深度 Kmi n=?(2) T树中共有多少非叶结点?(3) 假设叶结点的权值

2、分别为1, 2, 3, 4, 5, 6。请构造一棵哈曼夫树,并计算该哈曼夫树的权路径长度wpl。、图2中两线性表A和B分别表示两个集合。两表中的元素皆为递增有序。请写一算法表養站点 data MX.E.釦-表头结点 data rwatt述輛52;*A夜b.-求A和B的并集AUB要求该集合中的元素仍保持递增有序。且要利用A和B的原有结点空间。(15分)三、写出以下各题的结果:(25分)1 用无回溯法的模式匹配法 (KMP法)及快速的无回溯的模式匹配法求模式串T的nextj值,添入下面表中:j1 2 3 4 5 6 7ta a b b a a bKmp法求得的 n extj值快速无回溯法求 得的n

3、extj 值2 .广义表L=(a),(b),(c),d),试利用head和tail运算把原子项c从L中别离出来。3 .现有一组关键字序列为(13,29,23,44,55,87,25,21,10,79) 。利用除留余数法(即H(key) = key MOD p)构造哈希表,并用线性探测再散列的方法解决冲突。设P=15,填装因子a=0.7(1) 画出构造出的哈希表。(2) 求在查找此哈希表的元素时,在等概率的情况下,查找成功的平均查找长度ASL=?4 写出图3双链表中对换值为23和l5的两个结点相互位置时修改指针的有关语句。llink15-30dutn rlink试1 Sffl 3-四、二叉树的中序遍历序列为GFBEANH,后序遍历的结点序列为GEBFHNMA20 分1画出此二叉树的形态。2写出根据二叉树的中序和后序遍历的结点序列,建立它的二叉链表存储结构的递归 算法。五、某工程的 AOE网络如图4所示。15分图中弧上的权值分别为aiaio的t个活动的期限。1. 画出该AOE网络的十字链表存储结构。2. 求各事件的最早发生时间ve和最迟发生时间vl,以及各项活动的最早开始时间e和最迟开始时间I.填于下面表中。事件vevl活动eI1a12a23as4a45as6a6a7a8a9a1o3. 完成该项工程

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论