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

题目

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

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

正确答案：

（5）【答案】n
【解析】二路归并排序是在折半插入顺序的基础上再改进，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。

第2题：

编写算法,对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;
　　}

第3题：

对n个记录的序列进行堆排序,最坏情况下的时间复杂度为______。

A、O(logn)

B、O(nlogn)

C、O(n)

D、O(n^2)

正确答案：B

第4题：

对有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。

第5题：

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

参考答案：正确

第6题：

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

参考答案：错误

第7题：

有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为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

第8题：

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

参考答案：

第9题：

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

A、n-1

B、n

C、n+1

D、n(n-1)/2

答案：D

第10题：

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

A.1

B.12

C.60

D.15

正确答案：A

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

题目

相似问题和答案

更多相关问题

相关内容