首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明,将应填入(n)处的字句写在答卷纸的对应栏内。 【说明】 下面的程序为堆排序程序,其中函数adjust(i,n)是把以R[i](1≤i≤┕i/2┙)为根的二叉树调整成堆的函数,假定R[i]的左、右子树已经是堆,程序中的,是在主函数中说明
阅读以下说明,将应填入(n)处的字句写在答卷纸的对应栏内。 【说明】 下面的程序为堆排序程序,其中函数adjust(i,n)是把以R[i](1≤i≤┕i/2┙)为根的二叉树调整成堆的函数,假定R[i]的左、右子树已经是堆,程序中的,是在主函数中说明
admin
2009-02-15
84
问题
阅读以下说明,将应填入(n)处的字句写在答卷纸的对应栏内。
【说明】
下面的程序为堆排序程序,其中函数adjust(i,n)是把以R
(1≤i≤┕i/2┙)为根的二叉树调整成堆的函数,假定R
的左、右子树已经是堆,程序中的,是在主函数中说明的结构数组,它含有要排序的n个记录。
【程序】
Void adjust(i,n)
Int i,n;
{
iht k,j;
element extr;
extr=r
;
k=i;
j=2*i;
while (j<=n )
{if ((j<n) && (r[j].key<r[j+1].key))
(1);
if (extr. key<r[j].key)
{
r[k]=r[j];
k=j;
(2);
}
else
(3);
}
r[k]=extr;
}
/*让i从┗i/2┛逐步减到1, 反复调用函数adjust, 便完成建立初始堆的过程。*/
void heapsort (r,n)
list r;
int n;
{
int i,1;
element extr;
for (i=n/2;i>=1;- -i)
(4); /* 建立初始堆*/
for (k--n;k>=2;k- -)
{
extr=r[1];
r[1]=r[k];
r[k]=extr;
(5);
}
}
选项
答案
(1)j++ (2)j*=2或j=k*2 (3)j=n+1或break (4)adjust(i,n) (5)adjust(1,k-1)
解析
函数adjust(i,n)是把以R
(1≤i≤┗i/2┛)为根的二叉树调整成堆的函数,假定R
的左、右子树已经是堆,程序中的r是在主函数中说明的结构数组,它含有要排序的n个记录。
Void adjust(i,n)
Int i,n;
{
int k,j;
element extr;
extr=r
;
k=i;
j=2*i;
while(j<=n)
{if((j<n)&&(r[j].key<r[j+ 1].key))
j++;
if(extr.key<r[j].key)
{
r[k]=r[j];
k=j;
j*=2;
}
else
j=n+1;
}
r[k]=extr;
}
/* 让i从┗i/2 ┛逐步减到1, 反复调用函数adjust, 便完成建立初始堆的过程。堆排序程序heapsort 如下*/
void heapsort(r,n)
list r;
int n;
{
int i,l;
element extr;
for (i=n/2;i>= 1 ;--i)
adjust(i,n); /*建立初始堆*/
for(k=n;k>=2;k--)
{
extr=r[1];
r[1]=r[k];
r[k]=extr;
adjust(1,k-1);
}
}
函数heapsoff的第一个for循环建立初始化。没待排序的n个记录组成—棵深度为h的完全二叉树,因此有2h-1<n≤2h+1-1,即2h≤n<2h+1。完全二叉树的第i层(设根结点的层次为0)上最多有2i个结点,对每个非叶结点,都要调用过程adjust,同时可能移动结点(向下移动),第i层上的结点可能要移动的最大距离为h-i,若设向下移动一层花费的时间为c,则第i层2i个结点调整的时间最多为c*(h-i)*2i建立初始堆的全部时间应是:
令j=h-1,则i=h-j,所以有:
对第二个for循环,调用adjust函数n-1次,每次总是由根向下调整,调整的最大距离为log2n(实际上,调整的距离是逐渐变小的),所以总的时间不多于c*(n-1)log2n=O(log2n).堆排序总的时间为:
O(n)+O(nlog2n)=O(max(n,n log2n))=O(n log2n)
算法需要的存储空间是存储n个记录的数组以及少量暂存单元。
堆排序算法是不稳定的。
转载请注明原文地址:https://kaotiyun.com/show/bMDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在机器指令的地址字段中,直接指出操作数本身的寻址方式称为___________。
根据ANSI/IEEE829标准,以下(37)属于《测试程序说明》中程序步骤的内容。 ①启动 ②目的 ③日志 ④设置
关于软件测试与软件开发的认识,不正确的是______。A.软件生命周期各个阶段都可能产生错误B.软件测试是独立于软件开发的一个工作C.软件开发的需求分析和设计阶段就应开始测试工作D.测试越早进行,越有助于提高被测软件的质量
在结构化分析方法中,利用分层数据流图对系统功能建模。以下关于分层数据流图的叙述中,不正确的是___________(32)。采用数据字典为数据流图中的每个数据流、文件、加工以及组成数据流或文件的数据项进行说明,其条目不包括____________(33)。
设有关系模式R(A1,A2,A3,A4,A5,A6),其中:函数依赖集F={A1→A2,A1A3→A4,A5A6→A1,A2A5→A6,A3A5→A6),则___________(21)是关系模式R的一个主键,R规范化程度最高达到____________(
设系统中有R类资源m个,现有n个进程互斥使用。若每个进程对R资源的最大需求为w,那么当m、n、w取下表的值时,对于下表中的a~e五种情况,(26)两种情况可能会发生死锁。对于这两种情况,若将(27),则不会发生死锁。
设系统中有R类资源m个,现有n个进程互斥使用。若每个进程对R资源的最大需求为w,那么当m、n、w取下表的值时,对于下表中的a~e五种情况,(26)两种情况可能会发生死锁。对于这两种情况,若将(27),则不会发生死锁。
某软盘有40个磁道,磁头从一个磁道移至另一个磁道需要5ms。文件在磁盘上非连续存放,逻辑上相邻数据块的平均距离为10个磁道,每块的旋转延迟时间及传输时间分别为100ms和25ms,则读取一个100块的文件需要时间为(24)。
某文件管理系统采用位示图(bitmap)记录磁盘的使用情况。如果系统的字长为32位,磁盘物理块的大小为4MB,物理块依次编号为:0、1、2、…,位示图字依次编号为:0、1、2、…,那么16385号物理块的使用情况在位示图中的第(24)个字中描述;如果磁盘的
随机试题
有一单层单跨框架,假设屋盖平面内刚度为无穷大,质量都集中于屋盖处。已知设防烈度为8度,I类场地;设计地震分组为第二组;集中于屋盖处的重力荷载代表值为G=700kN,框架柱线刚度i=EI/h=2.6×104kN.m,框架高度h=5m。试求该结构的自振周期和多
移植后不会发生排斥反应的是()。
国家助学贷款的发放对象是全日制高等学校经济确实困难的()。
企业无法左右产品价格,属于均衡价格的被动接受者的市场是()。
烟台山上有清光绪三十一年建的烟台港湾的夜明珠——灯塔。()
下图斜线部分表示7月7日,非斜线部分表示7月8日,每条经线之间的间隔相等,箭头表示地球自转方向,据此回答问题。有关A、B、C三点正午太阳高度角的关系正确的是()。
想象主要借助于综合、()、拟人化、典型化等方式形成。
赵文和周成共同出资购买了一间房并将其出租给郑流。在租赁期间,周成欲转让自己的共有份额。现赵文和郑流都表示愿意购买,则下列说法正确的是()。
在分布式数据库系统中,逻辑数据库被划分成若干片段,其中按投影操作来分片的称为
EconomicReforminChinaMoreUSsinologistshaveexpressedconfidenceinChina’seconomicreformandtheprospectsforChina’s
最新回复
(
0
)