一组记录的关键字序列为(55,100,17,33,65,50,72,46,95),按关键字从小到大利用直接选择排序法排序,第3次交换和选择后的序号是7的关键字是____。(序号从0开始)
时间: 2024-05-22 12:10:29 浏览: 16
直接选择排序法的基本思想是:第i趟排序在剩余的n-i+1个记录中选取关键字最小的记录与第i个记录交换。按照这个思路,可以得到以下排序过程:
第1趟排序:17, 100, 55, 33, 65, 50, 72, 46, 95
第2趟排序:17, 33, 55, 100, 65, 50, 72, 46, 95
第3趟排序:17, 33, 46, 100, 65, 50, 72, 55, 95
第4趟排序:17, 33, 46, 50, 65, 100, 72, 55, 95
第5趟排序:17, 33, 46, 50, 55, 100, 72, 65, 95
第6趟排序:17, 33, 46, 50, 55, 65, 100, 72, 95
第7趟排序:17, 33, 46, 50, 55, 65, 72, 100, 95
第8趟排序:17, 33, 46, 50, 55, 65, 72, 95, 100
可以看到,第3次交换和选择后的序号是7的关键字是100。
相关问题
设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立 的初始堆为____
首先,我们需要将这些关键字序列转化为一个完全二叉树。然后,我们进行筛选法建立初始堆的操作,即从最后一个非叶子节点(也就是第 n/2 个节点,其中 n 为节点总数)开始,依次向上进行下滤操作,确保每个节点都满足堆的性质。
将这些关键字序列转化为完全二叉树后,得到如下的图示:
```
55
/ \
63 44
/ \ / \
38 75 80 31
/
56
```
从最后一个非叶子节点开始,也就是第 4 个节点(值为 38),进行下滤操作,得到如下的堆:
```
55
/ \
63 44
/ \ / \
56 75 80 31
/
38
```
因此,利用筛选法建立的初始堆为(55,63,44,56,75,80,31,38)。
设一组初始记录关键字序列为(45,80,55,40,42,85),则以第一个记录关键字 45 为基准而得到一趟快速排序的结果是(B )。 (A) 40,42,45,55,80,83 (B) 42,40,45,80,85,88 (C) 42,40,45,55,80,85 (D) 42,40,45,85,55,80
以第一个记录关键字 45 为基准进行一快速排序的过程如下:
1. 以45为基准,从右向左扫描,找到第一个小于45的记录,交换它们的位置。序列变为:(42, 80, 55, 40, 45, 85)。
2. 以45为基准,从左向右扫描,找到第一个大于45的记录,交换它们的位置。序列变为:(42, 40, 55, 80, 45, 85)。
3. 重复上述过程,直到左右指针相遇。最终序列为:(42, 40, 45, 55, 80, 85)。
因此,以第一个记录关键字 45 为基准而得到一趟快速排序的结果是选项C:(42,40,45,55,80,85)。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)