首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
设有关键码序列(Q,G,M,Z,A,N,B,P,X,H,Y,
[单选题]
设有关键码序列(Q,G,M,Z,A,N,B,P,X,H,Y,S,T,L,K,E),采用堆排序法进行排序,经过初始建小根堆后关键码值A在序列中的序号是( )
1
4
8
12
添加笔记
邀请回答
收藏(136)
分享
纠错
7个回答
添加回答
4
推荐
Jino.
选
A
。
堆排序的基本思想:
对二组待排序的关键码,首先把它们按堆的定义排列成一个序列,找到其中最小的关键码,接着将最小的关键码取出,然后将剩下的关键码再建堆排序,依次进行,直到将全部关键码排好为止。
建堆的算法:首先
将要排序的所有关键码放到一棵完全二叉树的各个结点中
(这时的二叉树不具备堆的特性),然后,
从i=[n/2](n为结点的个数)的结点K
i
开始,逐步把以K
[n/2]
,K
[n/2]-1
,K
[n/2]-2
,…为根的子树排成堆,直到以K
1
为根的树排成堆,就完成了建堆过程。
此题中,n=16,i=[16/2]=8,即从第8个结点开始,建堆完成后如下图所示:
经过初始建堆后关键码值A在序列中的序号是1。
综上,本题选
A
。
编辑于 2020-01-21 15:40:09
回复(3)
9
FLKID
题目没说按升序排还是降序排。我按升序排建堆,发现A在11号位,没答案。。。。。
发表于 2020-06-06 23:27:18
回复(5)
4
白驹之过隙
选
A
。考察的是堆构建。
根据给定的序列构成一个初始完全二叉树,按照层序将序列添加到完全二叉树节点上。
然后从n/2个节点(最后一个分支点)p开始进行构建。字母顺序排列进行节点的下沉和上浮
最终构成A节点成为根节点,所以序号为1
发表于 2020-01-19 20:22:09
回复(4)
0
CodeBunny
为什么不说一下是大顶堆还是小顶堆呢
发表于 2020-09-25 14:38:57
回复(0)
0
DifferentialPrivacy
A是最小的,还是最大的哦?
A是最大的:大顶堆,A在堆顶,在数组中是第一个。
A是最小的:小顶堆,A在堆顶,在数组中是第一个。
发表于 2020-08-07 10:09:08
回复(0)
0
_ooops_
建立小堆,A肯定在一开始的位置
发表于 2020-03-26 08:54:16
回复(0)
0
只有更坑,没有最坑
题目也不说明白是最大堆还是最小堆
发表于 2020-03-06 13:23:05
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
排序
上传者:
zsw3
难度:
7条回答
136收藏
3783浏览
热门推荐
相关试题
数据链路层滑动窗口机制中发送窗口(...
网络基础
评论
(1)
供受文者使用的具有法定效用的正式文...
京东
产品运营
2018
常识判断
行政
评论
(1)
有关linux线程的描述,正确的是...
京东
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
2018
评论
(1)
用一种动物介绍你自己
通用能力
评论
(1)
请你说几个海量数据存储常见问题以及...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题