首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明,将应填入(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
57
问题
阅读以下说明,将应填入(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
以下关于测试时机的叙述中,正确的是_______。①应该尽可能早地进行测试②软件中的错误暴露得越迟,则修复和改正错误所花费的代价就越高③应该在代码编写完成后开始测试④项目需求分析和设计阶段不需要测试人员参与
以下对用户口令进行限定的措施中,(66)对提高安全性来说是无用的。
在结构化分析方法中,依据______来进行接口设计。
关于软件质量,______的叙述是正确的。①软件满足规定或潜在用户需求特性的总和②软件特性的总和,软件满足规定用户需求的能力③是关于软件特性具备“能力”的体现④软件质量包括“代码质量”、“外部质量”和“使用质量”3部分A.
双层双面只读DVD盘片的存储容量可以达到(59)。
()不属于程序的基本控制结构。
某财务系统在使用过程中,因个人所得税政策变化,需修改计算工资的程序。这种修改属于______维护。
软件工程概念的提出是由于______。A.计算技术的发展B.软件危机的出现C.程序设计方法学的影响D.其他工程科学的影响
系统交付后,修改原来打印时总是遗漏最后一行记录的问题,该行为属于______维护。
阅读以下说明,回答问题1至问题4。【说明】网络工程师经常会面对服务器性能不足的问题,尤其是网络系统中的核心资源服务器,其数据流量和计算强度之大,使得单一计算机无法承担。可以部署多台Linux服务器组成服务器集群,采用负载均衡技术提供服务。
随机试题
有关胃癌的转移,错误的描述是
以下哪一种激素是由神经垂体释放的
患者女,50岁。皮肤瘀斑并牙龈出血2年,近期牙龈出血症状加重,并伴乏力、胸闷、咳嗽。查血常规:WBC48.60×109/L↑,原始细胞40%↑,Hb86g/L↓,RBC2.26×1012/L↓,PLT38×109/L↓。患者骨髓象示骨髓增生明显一
我国的政策性银行有()。
在移动模架上浇筑预应力混凝土连续梁时,浇筑分段工作缝必须设在()附近。
下列关于个人教育贷款的表述,错误的是()。
农民一户只能拥有一处宅基地,农民在()住房后,再申请宅基地的,不予批准。
截至2010年10月25日,上海世博会参观人数超过了7000万人.游园最大的痛苦就是人太多.假设游客到达中国馆有三条路径,沿第一条路径走3个小时可到达;沿第二条路径走5个小时又回到原处;沿第三条路径走7个小时也回到原处.假定游客总是等可能地在三条路径中选择
A、10:30PM.B、11:00PM.C、11:30PM.D、12:00PM.D男士说,餐馆周末的营业时间一直到午夜,即12:00pm。故答案是D。关键是分辨weekdays和weekend的不同营业时间,做笔记时要迅速和完整地记下细节,例如:w
Lookingforanewweightlossplan?Trylivingontopofamountain.Mountainaircontainslessoxygenthanairatloweraltitud
最新回复
(
0
)