2. 计算机
  3. 堆是一种数据结构，分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则________________是一个小顶堆结构。堆结构用二叉树表示，则适宜的二叉树类型为________________。对于10个结点的小顶堆，其

堆是一种数据结构，分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则________________是一个小顶堆结构。堆结构用二叉树表示，则适宜的二叉树类型为________________。对于10个结点的小顶堆，其

admin2021-01-11  59
问题 堆是一种数据结构，分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则________________是一个小顶堆结构。堆结构用二叉树表示，则适宜的二叉树类型为________________。对于10个结点的小顶堆，其对应的二叉树的高度(层数)为________________。堆排序是一种基于堆结构的排序算法，该算法的时间复杂度为________________。
选项 A、lgn
B、nlgn
C、n
D、n2
答案B
解析 本题考查数据结构与算法的基础知识。要求考生熟悉常用的数据结构和基本算法。
    用二叉树画出每个选项中的数列，选项A对应的二叉树为：

    因此，(A)是一个小顶堆。可以画出(B)、(C)和(D)对应的二叉树，并不是小顶堆。对于堆结构中的结点i，其左右孩子结点为2i和2i+1，因此，这样的结构是完全二叉树。
    上述二叉树就是表示10个数的小顶堆，其层数为4。也可以根据完全二叉树的性质来计算，结果为4。
    堆排序是一种经典的排序算法，其时间复杂度为O(nlgn)。
转载请注明原文地址:https://www.kaotiyun.com/show/AhPZ777K
本试题收录于： 软件评测师上午基础知识考试题库软考中级分类
0

软件评测师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)