首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明,将应填入(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
53
问题
阅读以下说明,将应填入(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
以下关于不同类型的软件测试的叙述,正确的是______。A.单元测试不是模块测试B.多个模块不能平行地独立进行测试,应该顺序执行C.系统测试是检验程序单元或部件之间的接口关系D.确认测试是通过检验和/或核查所提供的客观证据,证实软件是否满足特定预期
以下关于模块耦合关系的叙述中,耦合程度最低的是__________(39),其耦合类型为___________(40)耦合。(39)
软件工程每一个阶段结束前,应该着重对可维护性进行复审。在系统设计阶段的复审期间,应该从(8)出发;评价软件的结构和过程。
设有学生实体Students(学号,姓名,性别,年龄,家庭住址,家庭成员,关系,联系电话),其中“家庭住址”记录了邮编、省、市、街道信息;“家庭成员,关系,联系电话”分别记录了学生亲属的姓名、与学生的关系以及联系电话。学生实体Students中的“
在分层体系结构中,(41)实现与实体对象相关的业务逻辑。在基于Java,EE技术开发的软件系统中,常用(42)技术来实现该层。(42)
在结构化分析方法中,数据流图描述数据在系统中如何被传送或变换,反映系统必须完成的逻辑功能,用于(38)建模。在绘制数据流图时,(39)。(39)
假设磁盘块与缓冲区大小相同,每个盘块读入缓冲区的时间为10μs,由缓冲区送至用户区的时间是5μs,系统对每个磁盘块数据的处理时间为2μs。若用户需要将大小为10个磁盘块的Docl文件逐块从磁盘读入缓冲区,并送至用户区进行处理,那么采用单缓冲区需要花费的时间
系统交付后,修改偶尔会出现乱码的问题,该行为属于________________维护。
阅读以下说明和流程图(如图3所示),回答问题1和问题2。【说明】本流程图实现从成绩文件生成学生成绩一览表。某中学某年级的学生成绩数据(分数)登录在成绩文件10中,其记录格式见表2: 由该成绩文件生成见表3的学生成绩一览表
随机试题
按照《会计法》的规定,会计机构、会计人员的基本职责有()。
某孕妇,35岁,孕42周,临产10小时。检查:胎心音120次/分,宫高34cm,有水囊感,S=0,B超双顶径9cm,羊水深度2.5cm,其处理以下哪项为最佳()。
肾上腺素对血管作用的叙述,错误的是
洁净空调风管系统其中洁净度等级N6至N9的按()系统的风管制作要求。
()是负责基金公司合规工作的具体组织和执行部门,依照所规定的职责、权限、方法和程序独立开展工作,负责公司各部门和全体员工的合规管理工作,合规管理部门对总经理负责。
联系和发展的观点是唯物辩证法的实质和核心。()
犯罪未完成形态存在于()。
用市场法对在制品进行评估,应考虑的因素主要是()。
Everycultureattemptstocreatea"universeofdiscourse"foritsmembers,awayinwhichpeoplecaninterprettheirexperience
TheFrenchdivisionofMcDonald’shasrunadvertisementsthatincludedasurprising【C1】______:Kidsshouldn’teatatMcDonald’s
最新回复
(
0
)