您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168939

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

作业存档2(无用)

1、有下面键值的元素在大顶堆(最大化堆)的什么位置?

(a)第二大键值

(b)第三大键值

(c)最小键值

a) min{ array[2],array[3] }
b) 第二大键值的两个儿子结点和与第二大键值在同一层的另一个结点,这三者取最大值为第三大键值
c) 遍历array[currentSize/2+1]到array[currentSize](也就是所有的叶子结点),取最小值即为最小键值

2、设计算法,在最大化堆中查找最小键值元素,给出算法时间复杂度分析。

(第一题的c小问?)不过查找最小元素我只会遍历,如果有好的方法欢迎评论,这道题只需要弄明白遍历的范围,其他的都很简单

int findMin() {
	int Min = array[currentSize];//随意赋个初值,没什么影响
	for (int i = currentSize / 2 + 1;i <= currentSize;i++) {
		if (array[i] < Min) Min = array[i];
	}
	return Min;
}

时间复杂度:O(N),没什么最好最坏,肯定要遍历一遍。

3、下列序列中哪一个是最大化堆?

a) 8,6,4,3,2
b) 7
c) 9,7,5,6,3
d) 9,4,8,3,2,5,7
e) 9,4,7,2,1,6,5,3

a,b,c,d都是,我猜题想问哪一个不是…
(个人方法:序列不长就直接看,看不出来画个图也行)

4、从最大化堆(30,26,13,17,11,8,7,10,3,4)中删除最大值后,得到的堆是什么?

先画出初始状态:在这里插入图片描述
(其实,我不确定它想问的是什么)
刚删除最大值时,堆的样子:在这里插入图片描述
4相当于是在外面准备进行向下过滤
过滤完毕时,堆的状态:在这里插入图片描述

5、给定⼀棵顺序存储的完全二叉树,设计算法判断它是否为最小化堆

思路:判断是否是最小化堆只需看儿子的值是否都大于父亲,此外,顺序存储的下标都是有关系的。

bool ifminHeap() {
	for (int i = 1;i < currentSize / 2;i++) {
		if (array[i] > array[2 * i] || array[i] > array[2 * i + 1]) return false;
	}
	if (array[currentSize / 2] > array[(currentSize / 2) * 2]) return false;
	if (currentSize % 2 == 1) {
		if (array[currentSize / 2] > array[currentSize]) return false;
	}//因为(currentSize/2)*2+1不一定存不存在,所以处理下这种情况,写的并不便捷,可自行简化
	return true;
}

如有错误或问题欢迎在评论区指出,点个赞再走叭~


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进