设有n个待排序的记录关键字，则在堆排序中需要()个辅助记录单元。

题目
设有n个待排序的记录关键字，则在堆排序中需要()个辅助记录单元。

相似考题

1.对n个记录的序列进行堆排序,最坏情况下的时间复杂度为______。A、O(logn)B、O(nlogn)C、O(n)D、O(n^2)

2.（5）对 n 个记录的文件进行二路归并排序，所需要的辅助存储空间为___________。

3.堆排序所需的时间与待排序的记录个数无关。()

4.在堆排序的过程中,对n个记录建立初始堆需要进行()次筛运算,由初始堆到堆排序结束,需要对树根结点进行()次筛运算。

更多“设有n个待排序的记录关键字，则在堆排序中需要()个辅助记录单元。 ”相关问题

  • 第1题：

    编写算法,对n个关键字取整数值的记录序列进行整理,以使所有关键字为负值的记录排在关键字为非负值的记录之前,要求: ① 采用顺序存储结构,至多使用一个记录的辅助存储空间; ② 算法的时间复杂度为O(n)。


    参考答案：
    　　[算法描述]
    　　void process (int A[n]){
    　　low = 0;
    　　high = n-1;
    　　while ( low　　while (low　　low++;
    　　while (low0)
    　　high++;
    　　if (low　　x=A[low];
    　　A[low]=A[high];
    　　A[high]=x;
    　　low++;
    　　high--;
    　　}
    　　}
    　　return;
    　　}

  • 第2题：

    对n个记录的文件进行堆排序，最坏情况下的执行时间是O(nlog2n)。()


    参考答案：正确

  • 第3题：

    对有n个记录的表r[1…n]进行直接选择排序，所需要进行的关键字间的比较次数为______。


    正确答案：n(n-1)/2
    n(n-1)/2 解析：选择排序的思想为：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。第一个元素需要比较n-1次，第二次元素需要比较n-2次，依次类推，倒数第二个元素只须比较1次即可，所以总的比较次数为：(n-1)+(n-2)+…2+1=n(n-1)/2。

  • 第4题：

    若待排序记录按关键字基本有序，则直采用的排序方法是（ ）。

    A. 直接插入排序 B. 堆排序C. 快速排序 D. 简单选择排序


    正确答案：A

  • 第5题：

    对n个记录的文件进行二路归并排序，所需要的辅助存储空间为（）。


    正确答案:O(n)

  • 第6题：

    关于冒泡排序的比较次数和排序趟数描述正确的是（）。

    • A、N个记录最多N-1趟排序即可完成
    • B、N个记录最少比较N-1次，可完成排序，这是记录完全有序的情况
    • C、N个记录最多比较N*（N-1）/2次可完成排序，这是记录完全逆序的情况
    • D、在一趟排序中若无记录交换，就会停止排序

    正确答案:A,B,C,D

  • 第7题：

    设有10000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。

    • A、快速排序
    • B、堆排序
    • C、归并排序
    • D、插入排序

    正确答案:B

  • 第8题：

    次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（）。

    • A、堆排序
    • B、插入排序
    • C、快速排序
    • D、归并排序

    正确答案:C

  • 第9题：

    填空题
    在堆排序的过程中，对n个记录建立初始堆需要进行（）次筛运算，由初始堆到堆排序结束，需要对树根结点进行（）次筛运算。

    正确答案： [n/2],n-1
    解析： 暂无解析

  • 第10题：

    单选题
    设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。
    A

    快速排序

    B

    堆排序

    C

    归并排序

    D

    插入排序


    正确答案： C
    解析： 暂无解析

  • 第11题：

    填空题
    对n个待排序记录序列进行快速排序，所需要的最好时间是（），最坏时间是（）。

    正确答案： O（nlog2n）,O（n2）
    解析： 暂无解析

  • 第12题：

    单选题
    次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（）。
    A

    堆排序

    B

    插入排序

    C

    快速排序

    D

    归并排序


    正确答案： D
    解析： 暂无解析

  • 第13题：

    有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。

    ① 给出适用于计数排序的顺序表定义;

    ② 编写实现计数排序的算法;

    ③ 对于有n个记录的表，关键字比较次数是多少?

    ④ 与简单选择排序相比较，这种方法是否更好?为什么?


    参考答案：
    　　[算法描述]
    　　① typedef struct
    　　{int key;
    　　datatype info
    　　}RecType
    　　② void CountSort(RecType a[],b[],int n)
    　　//计数排序算法，将a中记录排序放入b中
    　　{for(i=0;i　　{for(j=0,cnt=0;j　　if(a[j].key　　b[cnt]=a[i];
    　　}
    　　}//Count_Sort
    　　③ 对于有n个记录的表，关键码比较n2次。
    　　④ 简单选择排序算法比本算法好。简单选择排序比较次数是n(n-1)/2,且只用一个交换记录的空间;而这种方法比较次数是n2，且需要另一数组空间。
    　　[算法讨论]因题目要求“针对表中的每个记录，扫描待排序的表一趟”，所以比较次数是n2次。若限制“对任意两个记录之间应该只进行一次比较”，则可把以上算法中的比较语句改为：
    　　for(i=0;i　　for(i=0;i　　for(j=i+1;j　　if(a[i].key

  • 第14题：

    对有n个记录的表进行直接插入排序,在最坏情况下需要比较()次关键字。

    A、n-1

    B、n

    C、n+1

    D、n(n-1)/2


    答案：D

  • 第15题：

    设n个待排序的记录关键字，则在堆排序中需要()个辅助记录单元。

    A.1

    B.12

    C.60

    D.15


    正确答案：A

  • 第16题：

    对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()。


    答案：C
    解析：

  • 第17题：

    若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变，则这种排序方法是（）的排序方法。


    正确答案:稳定

  • 第18题：

    对n个待排序记录序列进行快速排序，所需要的最好时间是（），最坏时间是（）。


    正确答案:O（nlog2n）；O（n2）

  • 第19题：

    冒泡排序N个记录需要N-1趟排序，就可以完成排序。


    正确答案:正确

  • 第20题：

    排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置，这是（）排序的基本思想。

    • A、堆排序
    • B、直接插入排序
    • C、快速排序
    • D、冒泡排序

    正确答案:D

  • 第21题：

    填空题
    若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变，则这种排序方法是（）的排序方法。

    正确答案： 稳定
    解析： 暂无解析

  • 第22题：

    多选题
    关于冒泡排序的比较次数和排序趟数描述正确的是（）。
    A

    N个记录最多N-1趟排序即可完成

    B

    N个记录最少比较N-1次，可完成排序，这是记录完全有序的情况

    C

    N个记录最多比较N*（N-1）/2次可完成排序，这是记录完全逆序的情况

    D

    在一趟排序中若无记录交换，就会停止排序


    正确答案： B,C
    解析： 暂无解析

  • 第23题：

    判断题
    堆排序所需的时间与待排序的记录个数无关。
    A

    对

    B

    错


    正确答案： 对
    解析： 堆排序最好、最坏及平均时间均为Ο（nlog2n），是待排序的记录个数n的函数。一般来说，待排序的记录个数越多，排序所消耗的时间也就越多。

相关内容