(论文)东北大学2000年数据结构试题_第1页
(论文)东北大学2000年数据结构试题_第2页
(论文)东北大学2000年数据结构试题_第3页
(论文)东北大学2000年数据结构试题_第4页
全文预览已结束

下载本文档

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

文档简介

东北大学2000年数据结构试题 1 （20分） 简要回答下列问题 （注意：请将答案写在答题纸上，并注明题号） （3分） 内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。 （5分） 假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。 （4分） 一棵共有n个结点的树，其中所有分枝结点的度均为k，求该树中叶子结点的子数。 （4分） 图1表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。（4分） 在起泡（汽泡）排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。快速排序过程中有没有这种现象？ 2 （15分） 设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法： 找出最小值结点，且打印该数值； 若该数值是奇数，则将其与直接后继结点的数值交换； 若该数值是偶数，则将其直接后继结点删除； 3 （14分） 解答下列问题： (4分） 将算术表达式 (a+b)+c*(d+e)+f)*(g+h) 转化为二叉树； (10分） 假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。 4（21） 解答下列问题： （5分） 画出有向图的十字链表存储结构中头结点和表结点的结点结构。 (4分） 下面哪一个方法可以判断出一个有向图中是否有环（回路）？ (1)深度优先遍历 (2)拓朴排序 (3)求最短路径 (4)求关键路径 (12分） 假设一个有向图g已经以十字链表形式存储在内中，试写一个判断该有向图中是否有环（回路）的算法。 5（15分） 写出删除二叉排序树bt中值为x的结点的算法（二叉排序树以二叉链表形式存储，删除后仍然保持二叉排序性质）。 6（15分） 设有大小不等的n个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内，每个数据占一个存储单元，数据组的首地址由数组s给出（如下图所示），试编写将新数据
人人文库> 全部分类> 图纸下载 > 毕业设计

温馨提示

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

最新文档

评论

0/150

提交评论