2. 计算机
  3. 堆是一种特殊的数据结构，选项(55)是一个最大堆。堆排序是一种(56)排序，其时间复杂性为(57)。(58)是不稳定的排序算法。外排序是指(59)。

堆是一种特殊的数据结构，选项(55)是一个最大堆。堆排序是一种(56)排序，其时间复杂性为(57)。(58)是不稳定的排序算法。外排序是指(59)。

admin2019-04-30  55
问题 堆是一种特殊的数据结构，选项(55)是一个最大堆。堆排序是一种(56)排序，其时间复杂性为(57)。(58)是不稳定的排序算法。外排序是指(59)。
选项 A、用机器指令直接对硬盘中需排序数据排序
B、把需排序数据，用其他大容量机器排序
C、把外存中需排序数据一次性调入内存，排好序后，再输回外存
D、对外存中大于内存允许空间的需排序的数据，通过多次内外存问的交换实现排序。
答案D
解析 堆是一个完全(除最底层外都是满的)二叉树，并满足如下条件：
1、根结点若有子树，则子树一定也是堆。
2、根结点一定大于(或小于)子结点。
  当根结点大于子结点时，称为最大堆，反之称为最小堆。因为要求堆必须是完全二叉树，所以可以用线性的数据结构，比如数组，来实现堆。利用数组实现，则对于长为N的堆中的元素从0到N-1排列，有：
i的父结点：Patent(i)=(i+1)/2-1
i的左叶子：Left(i)=(i+1)*2-1
i的右叶子：Right(i)=(i+1)*2
故97，75，34，56，19，26是一个最大堆，而19，34，26，97，56，75是一个虽小堆。
堆排序是一种选择排序法，对大量的记录进行堆排序是非常有效的。其时间复杂度为
O(nlogn)，n为待排序记录。快速排序、堆排序、希尔排序等都是不稳定的排序，而基数排序、归并排序是一种稳定的排序。
外排序是指待排序记录数量很大，以致内存不能容纳所有记录，在排序过程中尚需对外存进行访问的排序过程。点一定大于(或小于)子结点。
转载请注明原文地址:https://kaotiyun.com/show/XAVZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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