企业自己做网站的成本,淘客网站佣金建设,代加工手工活外发免费 来料加工,西安seo关键词查询数据结构阶段测试2的一点小补充 1.已知⼩根堆为8,15,10,21,34,16,12#xff0c;删除关键字8之后需重建堆#xff0c;最后的叶⼦ 节点为()
A. 34 B. 21 C. 16 D. 12
解题思路
向下调整算法删除堆顶元素
#x1f4a1; 答案#xff1a;C
删除堆顶元素的思路#xff1a; …数据结构阶段测试2的一点小补充 1.已知⼩根堆为8,15,10,21,34,16,12删除关键字8之后需重建堆最后的叶⼦ 节点为()
A. 34 B. 21 C. 16 D. 12
解题思路
向下调整算法删除堆顶元素 答案C
删除堆顶元素的思路
先将堆顶元素和当前堆结构的最后⼀个元素交换堆有效元素个数 减⼀从⽽实现堆顶元素的删除。但是交换后的堆顶元素还需要进⾏向下调整的操作从 ⽽保持现有堆的性质。 运用到的知识
堆的概念与结构
如果有⼀个关键码的集合 把它的所有元素按完全⼆叉树的顺序存储⽅ 式存储在⼀个⼀维数组中并满⾜ 且 i 0、1、2… 则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆根结点最⼩的堆叫做最⼩堆或⼩根堆。
堆具有以下性质
• 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值
• 堆总是⼀棵完全⼆叉树。
进阶结论
小堆的堆顶是最小值大堆的堆顶是最大值
虽然堆的底层是数组但是不一定有序的 ⼆叉树性质
• 对于具有 n 个结点的完全⼆叉树如果按照从上⾄下从左⾄右的数组顺序对所有结点从 0 开始编号则对于序号为 i 的结点有
若 i0 i 位置结点的双亲序号 (i-1)/2 i0 i 为根结点编号⽆双亲结点若 2i1n 否则⽆左孩⼦若 2i2n 否则⽆右孩⼦
注意点
第一点是求父节点的第二第三点是求左右孩子节点的
堆的实现
堆的基本结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;HPDataType size;//有效的数据个数HPDataType capacity;//空间大小
}HP;堆的初始化类似于顺序表
void HPInit(HP* php)
{assert(php);php-arr NULL;php-size php-capacity 0;
}堆的销毁
void HPDestory(HP* php)
{assert(php);if (php-arr)free(php-arr);php-arr NULL;php-size php-capacity 0;
}堆的插入
这里会用到堆的向上调整算法
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void AdjustUp(HPDataType* arr,int child)
{int parent (child - 1) / 2;while (child 0)//不需要等于child只要走到根节点的位置根节点没有父节点不需要交换{if (arr[child] arr[parent]){Swap(arr[parent], arr[child]);child parent;parent (child - 1) / 2;}else{break;}}}void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间是否足够if (php-size php-capacity){//扩容int newCapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDataType* tmp (HPDataType*)realloc(php-arr, newCapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc fail!);exit(1);}php-arr tmp;php-capacity newCapacity;}php-arr[php-size] x;AdjustUp(php-arr, php-size);php-size;
}堆的删除删除元素删除的是堆顶的元素 这里会用到堆的向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{int child parent * 2 1;//左孩子while (child n){//找左右孩子中最小的if (child 1 n arr[child] arr[child 1]){child;}if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}}
void HPPop(HP* php)
{assert(php php-size);Swap(php-arr[0], php-arr[php-size - 1]);--php-size;AdjustDown(php-arr,0, php-size);}对于序列{ 12,13,11,18,60,15,7,19,25,100 }⽤筛选法建堆应该从值为 的数据开始建初始堆。
A. 100 B. 12 C. 60 D. 15
解析思路 答案C
筛选法建堆
就是从最后⼀个⾮叶⼦节点开始向下调整建堆。这⾥其实就是要计算最后⼀ 个⾮叶⼦节点的数据。
即从最后⼀个结点的⽗亲结点开始所以是n/2。
3.将整数数组 7-6-3-5-4-1-2 按照堆排序的⽅式进⾏升序排列请问在第⼀ 轮排序结束之后数组的顺序是()
A. 1-2-3-4-5-6-7 B. 2-6-3-5-4-1-7 C. 6-5-3-2-4-1-7 D. 5-4-3-2-1-6-7 答案C
堆排序的原理
每次将堆顶元素和当前堆结构的最后⼀个元素进⾏交换从⽽将当前堆中的最值交换到最 后从⽽将数据进⾏排序。
不同的顺序排序应该建⽴什么堆
排升序需要建⽴⼤堆排降序需要建⽴⼩堆。
4.以30为基准设⼀组初始记录关键字序列为 (30,15,40,28,50,10,70)则第⼀ 趟快速排序结果为()
A. 10281530504070
B. 10152830504070
C. 10281530405070
D. 10152830405070
解题思路 答案B
**下⾯的思路是使⽤挖坑法 **
初始化左指针为1右指针为6
从右指针开始⽐较右指针⾃减到10的时候发现⽐30⼩两者交换得到
10,15,40,28,50,30,70
从左指针开始⽐较左指针⾃增到40的时候发现⽐30⼤两者交换得到
10,15,30,28,50,40,70
从右指针开始⽐较右指针⾃减到28的时候发现⽐30⼩两者交换得到
10,15,28,30,50,40,70
此时完成第⼀趟排序已经满⾜30的左边都⽐30⼩右边都⽐30⼤
知识点
挖坑法
思路 创建左右指针。⾸先从右向左找出⽐基准⼩的数据找到后⽴即放⼊左边坑中当前位置变为新 的坑然后从左向右找出⽐基准⼤的数据找到后⽴即放⼊右边坑中当前位置变为新的坑结 束循环后将最开始存储的分界值放⼊当前的坑中返回当前坑下标即分界值下标
从右指针开始⽐较右指针⾃减到28的时候发现⽐30⼩两者交换得到
10,15,28,30,50,40,70
此时完成第⼀趟排序已经满⾜30的左边都⽐30⼩右边都⽐30⼤
知识点
挖坑法
思路 创建左右指针。⾸先从右向左找出⽐基准⼩的数据找到后⽴即放⼊左边坑中当前位置变为新 的坑然后从左向右找出⽐基准⼤的数据找到后⽴即放⼊右边坑中当前位置变为新的坑结 束循环后将最开始存储的分界值放⼊当前的坑中返回当前坑下标即分界值下标
