我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 栈作业处理 >

数据结构最后的作业 参考

归档日期:07-05       文本归类:栈作业处理      文章编辑:爱尚语录

  数据结构最后的作业 参考_工学_高等教育_教育专区。二叉树和栈用于计算的过程和示意图 最小二叉树的生成 树,森林,二叉树的相互转换 哈弗曼树的生成 索引表的范例

  数据结构作业 {提示:这个版本仅供参考,可能有些不正确的细节。} 提示:这个版本仅供参考,可能有些不正确的细节。 个元素为:12,33,40,51。用单链表( 一,已知有 4 个元素为:12,33,40,51。用单链表(约定 头指针为 head,新结点指针为 new, head,新结点指针为 new, 搜索指针为 p) 从左 到右依次存储。 分别画出 1) ( 进栈 39 (2) 到右依次存储。 进队 39 (3) 等三种情况的工作示意图。 有序表插入 39 等三种情况的工作示意图。并标注上改 链的次序和主要的工作语句。 链的次序和主要的工作语句。 答:(1) 进栈: head null 51 40 33 12 ^ (2) (1) new 39 ^ Top-next=new; op- 改链次序:new-next=head改链次序:new-next=head-next; (2)进队: (2)进队: 进队 head- eadnull 12 33 40 51 ^ 1 rear (2) 改链次序:rear改链次序:rear-next=new; 39 ^ rear= rear=new; (3)有序表的插入: (3)有序表的插入: 有序表的插入 headhead- null 12 33 40 51 ^ p newnew- (2) 39 (1) ^ 改链次序:new-next=p改链次序:new-next=p-next; p-next=new; 的稀疏矩阵(比如: 二,自己画一个 6*7 的稀疏矩阵(比如:非 0 元只有 4 个) 。 画出三元组表示法。并画出对应的转置矩阵的三元组。 画出三元组表示法。并画出对应的转置矩阵的三元组。 答: 0 0 0 1 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 6 0 1 3 5 三元组 7 3 0 2 4 4 1 2 3 9 7 0 2 3 4 转置三元组 6 1 3 0 5 4 2 3 1 9 6*3/(2-1)的二叉树表示 的二叉树表示。 三,画出表达式 8-6*3/(2-1)的二叉树表示。写出四种遍历 的结果。画出利用栈进行计算的完整过程。 的结果。画出利用栈进行计算的完整过程。 答:表达式的二叉树表示法如下: 表达式的二叉树表示法如下: 8 / * 6 3 2 1 先跟遍历: 先跟遍历:- 8 / * 6 3 – 2 1; 中跟遍历:8 – 6 * 3 / 2 – 1; 跟遍历:8 后跟遍历:8 后跟遍历:8 6 3 * 2 1 - / -; 层次遍历: 层次遍历:- 8 / * - 6 3 2 1; 利用栈计算得过程: 利用栈计算得过程: (1),遇到操作数进栈: (1),遇到操作数进栈: 遇到操作数进栈 3 4 3 toptop-2 1 0 (2)遇到操作符出栈两次: (2)遇到操作符出栈两次:计算结果进栈 遇到操作符出栈两次 4 3 2 top-1 top0 其中:6*3=18; 其中:6*3=18; (3)重复以上过程: (3)重复以上过程: 重复以上过程 18 8 6 8 4 toptop-3 2 1 0 1 2 18 8 4 3 toptop-2 1 0 2-1=1; 4 3 2 toptop-1 0 8-18=-10; 18=4 3 2 1 toptop-0 1 18 8 18 8 -10 结束 图的存储结构。 自己画一个图, 至少五个结点, 多条边。 四,图的存储结构。 自己画一个图, 至少五个结点, 多条边。 画出邻接矩阵和邻接表示意图。 画出邻接矩阵和邻接表示意图。 答:图如下: 图如下: d0 d1 d2 d3 其邻接矩阵: 其邻接矩阵: B= 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 d4 d5 邻接表: 邻接表: 0 1 2 d0 d1 d2 1 0 1 3 2 5 ^ 4 ^ ^ 3 4 5 d3 d4 d5 0 1 2 4 3 4 ^ 5 ^ ^ 二叉树, 森林的互助转换。 自己画一个有三层深度, 五, 树, 二叉树, 森林的互助转换。 自己画一个有三层深度, 的一颗树,改划成二叉树。 树的度为 3 的一颗树,改划成二叉树。 答:三层深度的树: 三层深度的树: 12 23 45 46 69 35 37 52 改链: 改链 12 23 45 46 69 35 37 52 12 拉直: 拉直: 23 45 46 69 35 37 52 旋转 45 度: 12 23 69 45 46 35 37 52 最优二叉树的建立。权值序列: 六,最优二叉树的建立。权值序列:25,12,27,6,15 答: 排序:6 排序:6 12 15 25 27 建立二叉树: 建立二叉树: 18 (1)(1)- 33 (2)(2)- 33 52 6 12 15 18 15 18 25 27 6 12 6 12 (3)(3)- 15 25 27 6 12 二分查找法的示意图。自己产生十个数据。 七,二分查找法的示意图。自己产生十个数据。画出其中一 个元素查找成功的过程。 个元素查找成功的过程。 63) 答:给出得十个数据如下(假设查找数据 63) 给出得十个数据如下( 32 41 44 51 53 57 60 63 64 89 分别标上下标: 分别标上下标: 1 2 3 4 5 6 7 8 9 10 51( 89) 32 41 44 51(53 57 60 63 64 89) 32 41 44 51(53 57 60)63 64 89 32 41 44 51 53 57(60 63 64 89) 32 41 44 51 53 57 60(63)64 89 八,哈希查找法。对于数据序列 39,24,15,7,16,10.哈希函 哈希查找法。 39,24,15,7,16,10.哈希函 9。假如冲突采用挂链法。 数为 hash(x)=x mod 9。假如冲突采用挂链法。画出完 整的示意图。 整的示意图。 答: 0 1 2 3 4 5 6 7 8 ^ 10 ^ 39 ^ ^ 24 7 ^ ^ ^ 15 16 其中采用队列来解决冲突问题 ^ ^ 快速排序法。 45,12,78,35,49,87, 九,快速排序法。对于数据序列 45,12,78,35,49,87, 26, 95。 叙述主要的算法思路。 26, 。 95 画出第一轮排序的过程。 画出第一轮排序的过程。 叙述主要的算法思路。 答:第一轮的基数是第一个数据 45: [45 12 78 35 49 87 26 95] [26 12 78 35 49 87 45 95] [26 12 45 35 49 87 78 95] [26 12 35 45 49 87 78 95] ……… 算法思路: 算法思路: 以第一个数据为基准数据,从后往前扫描并比较, 以第一个数据为基准数据,从后往前扫描并比较,当扫描到比 基准数据小的时候立即和基准数据交换位置, 基准数据小的时候立即和基准数据交换位置,然后从基准数 据的下一个数据开始从前往后扫描,重复以上过程, 据的下一个数据开始从前往后扫描,重复以上过程,直到所有 数据都于基准数据比较完,第一轮排序结束.然后依次类推. 数据都于基准数据比较完,第一轮排序结束.然后依次类推. 直到所有数据都按顺序排序结束. 直到所有数据都按顺序排序结束. 堆排序。 15,24,72,35,49,25,64。 十,堆排序。 对于数据序列 15,24,72,35,49,25,64。 画出对 应的顺序存储示意图。画出对应的完全二叉树。 应的顺序存储示意图。画出对应的完全二叉树。画出初 始大跟堆。画出初始大跟堆对应的存储结构。 始大跟堆。画出初始大跟堆对应的存储结构。画出产生 已排序空间一个数据的逻辑结构示意图。 已排序空间一个数据的逻辑结构示意图。 64]待排数据为线型表. 待排数据为线]待排数据为线型表. 其顺序存储的示意图如下: 其顺序存储的示意图如下: 0 1 15 2 24 3 72 4 35 5 49 6 25 7 64 对应的完全二叉树: 对应的完全二叉树: 15 24 72 35 49 25 64 初始大根堆: 初始大根堆: 72 49 64 35 24 25 15 初始堆对应的存储结构: 初始堆对应的存储结构: 0 1 72 2 49 3 64 4 35 5 24 6 25 15 7 已排空间第一个数据的逻辑示意图: 已排空间第一个数据的逻辑示意图: [49 64 35 24 25 15](72) 十一,讨论题:顺序存储和链表存储的优点对比分析。 十一,讨论题:顺序存储和链表存储的优点对比分析。 答:顺序存储结构——按逻辑次序把线性表的结点依次存放在一 顺序存储结构——按逻辑次序把线性表的结点依次存放在一 —— 组地址连续的存储单元中 组地址连续的存储单元中。 用顺序存储的优点是:可以随机访问数据, 用顺序存储的优点是:可以随机访问数据,存储空间的利用 率高,存取速度快。 率高,存取速度快。 链表存储――用链接存储方式存储, 链表存储――用链接存储方式存储,链表中的结点用存储单 ――用链接存储方式存储 元(就是若干个连续字节)来存放,一个结点对应一个存储 就是若干个连续字节)来存放, 单元,存储单元之间既可以是(空间上)连续的, 单元,存储单元之间既可以是(空间上)连续的,也可以是 不连续的,甚至可以零散分布在存储空间中的任何位置。 不连续的,甚至可以零散分布在存储空间中的任何位置。 用链表存储的优点是:可以做到高效的动态操作,插入,删 用链表存储的优点是:可以做到高效的动态操作,插入, 除等操作都不会引起数据的移动。 除等操作都不会引起数据的移动。 十二,讨论题:循环队列解决了什么问题?优点是什么?如 十二, 讨论题: 循环队列解决了什么问题? 优点是什么? 何巧妙的实现环状? 何巧妙的实现环状? 循环队列解决了空间利用率的问题, 防止了数据的 假溢出” “假溢出” 。 答: 循环队列解决了空间利用率的问题, 优点是: 分利用可用空间,提高了数据的访问时间。 优点是:充分利用可用空间,提高了数据的访问时间。 实现环状方法如下: front==rear==0, 实现环状方法如下:约定初始状态为 front==rear==0,每次 的位置上, 入队把数据存入当前 rear 的位置上,之后用 rear=rear+1 向前移动尾指针。 前移。 向前移动尾指针。出队时用 front=front+1 前移。使用求模 函数实现环状, 不论什么整数 address, address, 函数实现环状, 进行 address mod 10 时,结果永远在 0~9 之间。入队地址改为: rear=(rear+1)%MaxSize, 出 队 时 地 址 计 算 为 : front=(front+1)%MaxSize。 front=(front+1)%MaxSize。 )%MaxSize 区分队满和队空时使用一个记数 下标位置上, rear+1== 认为队满。 器,放在 0 下标位置上,当 rear+1==front 时,认为队满。 十三,讨论题:一般而言, 十三,讨论题:一般而言,如何比较递归和非递归算法的优 缺点? 缺点? 答:递归优点是可以简洁的模拟现实生活中的一些复杂关系,所 递归优点是可以简洁的模拟现实生活中的一些复杂关系, 以可提供一个很好的解决问题的角度, 以可提供一个很好的解决问题的角度,但是它的时间效率相 对较低。并且要考虑函数调用的开销,其阅读性不高。 对较低。并且要考虑函数调用的开销,其阅读性不高。 相对来说非递归算法时间效率较高,不考虑函数调用开销, 相对来说非递归算法时间效率较高,不考虑函数调用开销, 阅读性也好,但很难间接模拟较复杂的问题。 阅读性也好,但很难间接模拟较复杂的问题。 十四,讨论题:常规的排序算法的共同点是什么? 十四,讨论题:常规的排序算法的共同点是什么? 常规的排序算法的共同点是:都得通过一下三种操作, 答:常规的排序算法的共同点是:都得通过一下三种操作,即: 比较, 交换, 移动。 并且它们得算法时间复杂度均为: 2)。 O(n2) 比较, 交换, 移动。 并且它们得算法时间复杂度均为: 2)。 O(n 十五,讨论题:字符串和线性表的关系是什么? 十五,讨论题:字符串和线性表的关系是什么?字符串的操 作主要体现在什么方面? 作主要体现在什么方面? 答:字符串也是一种特殊的线型表,其操作的基本单位是“字符 字符串也是一种特殊的线型表,其操作的基本单位是“ ,很多时候是一次性处理“大量字符” 。 串” 很多时候是一次性处理“大量字符” 而线性表则是以 “单个元素”作为操作对象。 单个元素”作为操作对象。 十六,讨论题:栈和队列的工作原理以及各自的应用范例? 十六,讨论题:栈和队列的工作原理以及各自的应用范例? 答:栈的工作原理是:先进后出,即 LAST IN FIRST OUT 栈的工作原理是:先进后出, 其应用范例是:数值转换问题,函数调用机制的实现问题, 其应用范例是:数值转换问题,函数调用机制的实现问题, 括号匹配问题, 括号匹配问题,表达式求值处理问题等 队列工作原理是:先进先出, 队列工作原理是:先进先出,即 FIRST IN FIRST OUT 其应用范例是: 应用范例是:打印机共享问题, 打印机共享问题, 多用户共享 CPU 资源问题, 资源问题, 飞机场跑道管理模拟系统等。 飞机场跑道管理模拟系统等。 十七,讨论题:索引存储的特点和优点? 十七,讨论题:索引存储的特点和优点? 答:索引存储的特点和优点是: 索引存储的特点和优点是: 1, 2, 3, 4, 无数据的移动(动态操作) ; 无数据的移动(动态操作) 并非顺序存储; 并非顺序存储; 存储空间无链表,读取操作可随即访问,并且速度快; 存储空间无链表,读取操作可随即访问,并且速度快; 加快了检索的速度,但是减慢了插入和删除的速度。 加快了检索的速度,但是减慢了插入和删除的速度。 十八,讨论题:诸如迷宫,八皇后, 十八,讨论题:诸如迷宫,八皇后,棋盘等课题使用什么数 据结构比较好的选择?为什么? 据结构比较好的选择?为什么? 答:应使用栈的数据结构比较好,因为在迷宫中要考虑那些路已 应使用栈的数据结构比较好, 经走了,那些路可以走,那些路是死路,在八皇后中的函数 经走了,那些路可以走,那些路是死路,在八皇后中的函数 递归调用机制,棋盘的悔棋机制都需要栈的思想来解决。 递归调用机制,棋盘的悔棋机制都需要栈的思想来解决。因 需要栈的思想来解决 此因该用栈的数据结构。 此因该用栈的数据结构。 十九,讨论题:图的邻接表中, 十九,讨论题:图的邻接表中,挂链的结点中为什么不能存 放实际要处理的数据? 放实际要处理的数据? 因为挂链的结点中存放的是地址,也就是说是关系, 答:因为挂链的结点中存放的是地址,也就是说是关系,如果存放 数据,则当改动数据时数据的关系会丢失. 数据,则当改动数据时数据的关系会丢失.应此结点中不能存 放处理的数据. 放处理的数据. 二十,讨论题: O(1)级的查找算法 二十,讨论题:哈希存储法线)级的查找算法 吗?为什么?你如何评价这个的思路? 为什么?你如何评价这个的思路? 答:如果满足以下两个条件: 如果满足以下两个条件: (1),构造好的哈希函数; (1),构造好的哈希函数; 构造好的哈希函数 (2)制定解决冲突的方案; (2)制定解决冲突的方案; 制定解决冲突的方案 90%-95%能做到 O(1)级的查找算法 级的查找算法. 那么哈希存储法 90%-95%能做到 O(1)级的查找算法.

本文链接:http://mezzomagazine.com/zhanzuoyechuli/189.html