数据结构学习记录——堆的小习题(对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的)

简介: 数据结构学习记录——堆的小习题(对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的)

习题一

一、下列序列中哪个是最小堆

AA.2,55,52,72,28,98,71

BB.2,28,71,72,55,98,52

CC.2,28,52,72,55,98,71

DD.28,2,71,72,55,98,52

习题二

二、在最大堆 {97,76,65,50,49,13,27}中插入83后,该最大堆为:

AA.{97,76,65,83,49,13,27,50}

BB.{97,83,65,76,49,13,27,50}

CC.{97,83,65,76,50,13,27,49}

DD.{97,83,65,76,49,50,13,27}

习题三

对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的:

AA.二叉搜索树(查找树)高度大于等于最小堆高度

BB.对该二叉搜索树(查找树)进行中序遍历可得到从小到大的序列

CC..从最小堆根结点到其任何叶结点的路径上的结点值构成从小到大的序列

DD.对该最小堆进行按层序(level order)遍历可得到从小到大的序列

答案区

题目 答案
习题一 C
习题二 B
习题三 D

解析区

习题一

习题一就是一道简单的考察最小堆定义的题目,我们把数组转化成完全二叉树的形式来看,很快就可以得出答案:        

故而最终选择的是C选项。

习题二

习题二考察堆的插入操作。

我们先把这个最大堆画出来:

插入结点83:

然后进行调整:

故而就可以得到插入结点83之后的堆了,选B选项。

习题三

习题三考察的是对二叉搜索树和最小堆两个结构的理解和简单应用。

  • A选项,二叉搜索树高度大于等于最小堆高度。

在二叉搜索树中,每个结点的值都大于其左子树中的所有结点的值,小于其右子树中的所有结点的值。所以,二叉搜索树的高度取决于结点在树中的排列方式。


如果考虑最好的情况,二叉搜索树的排列方式完全平衡,即为一颗平衡二叉树,那么它的高度就为log2N

2

。如果考虑最坏的情况,二叉搜索树的排列方式呈现为斜二叉树,那么它的高度就为N

N

。(N为结点数)


相比之下,最小堆是一种完全二叉树,其中每个结点的值都小于或等于其子结点的值。


因此,最小堆的高度取决于结点数,而不是结点排列方式。具体来说,最小堆的高度为log2N

2

。(N为结点数)


所以一般情况下,二叉搜索树的高度是大于等于最小堆的高度的。

A选项正确。


B选项,对该二叉搜索树(查找树)进行中序遍历可得到从小到大的序列。

前面我们讲过了,在二叉搜索树中,每个结点的值都大于其左子树中的所有结点的值,小于其右子树中的所有结点的值。


而中序遍历的顺序是先左子树->根节点->右子树,因此中序遍历得到的序列是从小到大排列的。


B选项正确。

C选项,从最小堆根结点到其任何叶结点的路径上的结点值构成从小到大的序列。

这句话就是堆的性质,是最小堆的有序性,在“什么是堆”中就已经学习过。


C选项正确。


D选项,对该最小堆进行按层序(level order)遍历可得到从小到大的序列

对于最小堆而言,每个结点的值都小于等于其子结点的值。


而层序遍历是从根结点开始,先遍历根结点,然后按照从上到下、从左到右的顺序依次遍历每一层的结点。很显然,这样遍历一个堆是不一定能拿到一个从小到大的序列的。

例如习题一的C选项:

它为最小堆,但是按层序遍历得到的序列为:2,28,52,72,55,98,71。

并不是从小到大的。

因为最小堆的性质只保证了每个结点的值都小于等于其子结点的值,但并没有保证同一层结点之间的大小关系。

因此,按层序遍历得到的序列可能存在某些结点之间的大小关系不符合从小到大的顺序。

故而,D选项错误。

综上,习题三选择的是不正确的选项,即D选项。

 


end



目录
相关文章
|
26天前
|
存储 算法 Java
散列表的数据结构以及对象在JVM堆中的存储过程
本文介绍了散列表的基本概念及其在JVM中的应用,详细讲解了散列表的结构、对象存储过程、Hashtable的扩容机制及与HashMap的区别。通过实例和图解,帮助读者理解散列表的工作原理和优化策略。
34 1
散列表的数据结构以及对象在JVM堆中的存储过程
|
7天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
28 5
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
28天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
64 16
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
29天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
125 9