首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明,将应填入(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
81
问题
阅读以下说明,将应填入(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
安全日志是软件产品的一种被动防范措施,是系统重要的安全功能,因此安全日志测试是软件系统安全性测试的重要内容,下列不属于安全日志测试基本测试内容的是_______。
针对以下C语言程序段,假设sta[10]=-1,对于x的取值,需要______个测试用例能够满足分支覆盖的要求。intMathMine(intx){intm=0;inti;for(i=x-1;i<=x+1;
编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段,其中,(22)并不是每种编译器都必需的。
GB/T18905-2002《软件工程产品评价》中确定的通用评价过程包括四个方面,即:确立评价需求,规定评价,设计评价和执行评价,其中有关“规定评价”部分包含的内容有(52)。
以下属于影响软件可靠性因素的是()。①软件运行剖面②软件规模③软件内部结构④软件的开发方法和开发环境⑤软件的可靠性投入
在面向对象分析和设计中,用类图给出系统的静态设计视图,其应用场合不包括___________(45)。下图是一个UMI,类图,其中类University和类School之间是___________(46)关系,类Person和类PersonRecord之间
以下用例图中,A1和A2为(47)。A1和A2的关系为(48)。(47)
系统交付后,修改原来打印时总是遗漏最后一行记录的问题,该行为属于______维护。
软件测试使用各种术语描述软件出现的问题,以下叙述正确的是______。A.软件错误(error)是指在软件生命周期内的不希望或不可接受的人为错误,其结果是导致软件故障的产生B.软件缺陷(defect)是存在于软件(文档、数据、程序)之中的那些不希望或不
流程图中文件F的纪录格式设定为见表4形式: 其中的①、②应定义为何种数据项?简述处理2、处理3和处理4作何种处理,若有排序处理则需指明排序的键及序(升序或降序)。
随机试题
一个完整的法律规范在结构上由哪几个要素组成?
有关暗适应的描述,错误的是
在统计分析中,为了使显著性检验的两类错误同时减少,可采取的措施是
高压发生器内不包括
动力基础设计中需选用的天然地基土的动力参数一般有()。
雨期填筑路堤时,填料选择应注意的问题是()。
ABC会计师事务所的A注册会计师担任多家被审计单位2013年度财务报表审计业务的项目负责人,在审计过程中遇到下列事项:(1)因持续经营能力存在重大不确定性,组成部分注册会计师对甲公司的子公司出具了带有强调事项的无保留意见的审计报告,甲公司管理层认为该事项
联合订购中的主品用经济订货批量,副品视运输包装单元情况可以用经济订货批量或附属经济批量。()
某市A区法院受理一起盗窃案件,因该案被告人与该法院院长具有亲属关系,市中级人民法院遂指定将该案移交B区法院审判。对于该案的全部案卷材料,A区法院应按下列哪一选项处理?()
【B1】【B10】
最新回复
(
0
)