广州大学914数据结构常见非代码题
需积分: 50 70 浏览量
2021-05-12
20:11:45
上传
评论 4
收藏 5.5MB DOCX 举报
最小生成树有两种：prim 算法，kruskal 算法
堆排序 一开始的序列不用排序，直接构造一个完全二叉树，然后在调整
排序二叉树 不用排序，直接构造，左小根中右大的逻辑构造
平均查找长度是 ASL 次数是（本层高度*本层元素个数）与 链式查找一样
哈夫曼编码最短路径长度 WPL 是算 本层分支数*所给的元素个数）
判断下列序列是否是堆。若不是堆，则把它们依次调整为堆。
(1) (100，85，98，77，80，60，82，40，20，10，66)；
把上面的序列构造一棵完全二叉树
由此判断是大顶堆，不需要调整
(2) (100，98，85，82，80，77，66，60，40，20，10)
与 1 思路一样，排成二叉树，判断为大顶堆
(3) (100，85，40，77，80，60，66，98，82，10，20)；
由此不是堆，调整后为
调整后的序列为(100,98,66,85,80,60,40,77,82,10,20) 二叉树的层次遍历
(4) (10，20，40，60，66，77，80，82，85，98，100)；
小顶堆
1. 已知一组元素为(46、25、78、62、18、34、12、40、73)，试画出按元素排列顺序输
入而生成的一棵二叉排序树，并求其平均查找长度。
剩余33页未读，继续阅读
评论0