2021国开大学电大本科《人文英语3》期末试题及答案
书面表达（10分）
第 77 题 请设计一个教案，达到以下目的：
1．学生能够用英语描述一段旅行。
2．能够听说读"Where are you going on holiday? I' m going to... ",用现在进行时表将来。
3．培养学生运用英语的能力。
Teaching Plan：(one possible version)
Step l．Warming up
1．Ask some questions：
Do you often travel? Where have you been ?
2．Follow the steps of the warm．up．
Step 2．Pre—reading
1．Show some traveling pictures of the teacher’s．
2. Ask students：Which fiver is the longest one in the world and which is the largest one?
Which river is the longest one in China?
3. Ask students：How people who live along a flyer use it?
Step 3．While—reading
1．Scanning：Students read quickly and answer：
What are they going to do?
2. Skimmin9：Students read again and finish Comprehension l on Page l9．
3. Students read and get the main idea of each paragraph．
4. Students list the countries that the Mekong River flows through．
Step 4．After．reading Students discuss in pairs：Wang Wei’s and Wang Kun’s similar and different attitudes about the trip．
Step 5. Assignment
1. Surf the Internet and get more information about the Mekong River.
2. Retell the passage using your own words.
●试题二
阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明2．1】
以下C语言函数用二分插入法实现对整型数组a中n个数的排序功能。
【函数2．1】
void fun1(int a［］)
{int i，j，k，r，x，m；
for(i=2；i<=n；i＋＋)
{ (1) ；
k=1；r=i-1；
while(k<=r)
{m=(k+r)/2；
if(x<a［m］)r=m-1；
else (2) ；
}
for(j=i-1；j>=k；j--)
a［j+1］=a［j］；
(3) ；
}
}
【说明2．2】
以下程序可以把从键盘上输入的十进制数(1ong型)以二～十六进制形式输出。
【程序2．2】
#include<stdio．h>
main()
{char b［16］={′0′，′1′，′2′，′3′，′4′，′5′，′6′，′7′，′8′，′9′，′A′，′B′，′C′，′D′，′E′，′F′}；
int c［64］，d，i=0，base；
long n；
printf(″enter a number：′n″)；
scanf(″％1d″，&n)；
printf(″enter new basc：kn″)；
scanf(″％d″，&base)；
do
{c［i］= (4) ；
i＋＋；n=n／base；
}while(n!=0)；
printf("transmite new base：＼n")；
for(--i；i>=0；--i)
{ d=c［i］；
printf("％c"， (5) )；
}
}
●试题二
【答案】(1)x=a［i］(2)a［k］=x(3)k=m+1(4)n％base(5)b［d］
【解析】函数3．1的思想是依次将数组中的每一个元素插入到有序段中，使有序段的长度不断地扩大。对于待插入元素，先用二分查找法找出应该插入的位置。然后将元素插入。对数组来说，就是将该位置以后的元素依次后移，然后将待插入元素放到移出来的空位中。
程序3．2用的思想是除base(base在二～十六进制之间)取余法求得相应进制数，然后再转换输出。
●试题一
阅读下列算法说明和算法，将应填入(n)处的语句写在答题纸的对应栏内。
【说明】
为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R［1..n］进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置(假设R［］中的元素互不相同)。
【算法】
1．变量声明
X：DataType
i，j，low，high，mid，R0..n
2．每循环一次插入一个R［i］
循环：i以1为步长，从2到n，反复执行
①准备
X<-R［i］； (1) ；high<-i-1；
②找插入位置
循环：当 (2) 时，反复执行
(3)
若X．key<R［mid］．key
则high<-mid-1
否则 (4)
③后移
循环：j以-1为步长，从 (5) ，反复执行
R［j+1］<-R［j］
④插入
R［low］<-X
3．算法结束
●试题一
【答案】(1)low<-1(2)low≤high(3)mid<-int((low+high)/2)(4)low<-mid+1
(5)i-1到low
【解析】这是一个通过自然语言描述二分插入排序的过程。整个过程由一个大循环来完成，在大循环中又包含两个循环，第一个循环是一个二分查找过程，第二循环是后移过程。
查找过程是在有序序列R［1］．R［i-1］中查找R［i］的过程，这是一个典型的折半查找过程。初始时指针low指向第一个元素，即R［1］，指针high指向第后一个元素，因此(1)空处应填写"low-1"。要查找R［i］，先与中间元素进行比较，中间元素使用mid指向，因此，(3)空处应填入"mid<-int((low+high)/2)"。当R［i］<R［mid］时，则在前半部分查找，将high<-mid-1，如果R［i］>R［mid］时，则在后半部分查找，因此(4)空处应填"low<-mid+1"。那什么时候结束呢?显然，一种情况是已经找该元素，由于题目中已经假设元素互不相同，这种情况不会发生，二是没有找到该元素，即指针low和指针high之间的没有元素了，所以(2)空处应填写"low≤high"。(5)空所在循环是进行数据移动，结合下面语句，可以判断循环是从i-1开始，到什么时候结束呢?通过分析，可以知道，最终要把R［i］放在R［low］的位置，循环要到low时结束，因此(5)空处应填写"i-1到low"。
阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。
【说明】
为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R[1..n]进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置。(假设R[]中的元素互不相同)
[算法]
1．变量声明
X: Data Type
i,j,low, high,mid,r:0..n
2．每循环一次插入一个R[i]
循环：i以1为步长，从2到n，反复执行。
(1)准备
X←R[i];(1); high←i-1;
(2)找插入位置
循环：当(2)时，反复执行。
(3)
若X.key＜R[mid].key
则high←mid-1;
否则 (4)
(3)后移
循环：j以-1为步长，从(5)，反复执行。
R[j+1]←R[j]
(4)插入
R[low]←X
3．算法结束
(1)low←1 (2)low=high (3)mid←int((low+high)/2) (4)low←mid+1 (5)i-1到low 解析： 本题考查使用二分插入法对无序数组排序的伪码实现。
在做题前，我们需要先大概明白二分插入法的基本思想和步骤，其基本思想是(设 R[low，…，high]是当前的插入区间)：
(1)将要插入的数取出放在X中；
(2)确定区间的中点位置：mid=[(low+high)/2]；
(3)确定插入位置，将待插入的k值与R[mid].key比较，具体方法如下：
·若R[mid].key＞k，则由排序后表的有序性可知R[mid,…，n].key均大于k，因此，插入区间是左子表R[low,…，high]，其中high=mid-1。
·若R[mid].keyk，则要插入的k必在mid的右子表R[mid+1，…，high]中，其中 low=mid+1。
(4)在上面的过程中，low逐步增加，而high逐步减少，直到highlow，则找到插入位置为low，然后循环移动位置low后面的元素，再插入数值。
(5)重复上述过程，直到所有数都被插入。
有了上面的分析，我们再来看程序伪代码，第(1)空处在准备阶段，准备阶段要完成的任务是给变量赋初值，high←i-1将数组中的最后一个位置赋给了插入指针high，因为插入的范围是数组的整个范围，那么第(1)空应该用来将数组的第一个位置赋给插入指针low，因此答案为low←1。
第(2)空是找插入位置用的循环条件，根据我们上面的分析，要直到highlow时，才能确定插入的位置；而在low=high时，循环一直执行，结合程序的内容，知道此空答案为low=high。
第(3)空很明显是用来确定区间的中间位置，但mid有可能为小数，在程序中我们用取整的方法来去掉小数部分，因此，此空答案为mid-int((low+high)/2)。
第(4)空是条件X.keyR[mid].key不成立的情况下执行的语句，如果条件为假，则说明要插入的数大于中间位置的数，应该在其右区间里进行插入，根据分析知道，这时左指针low应该改变，这个空就是用来实现这个功能的，因此，答案为low←mid+1。
第(5)空在后移的循环操作中，作为后移的循环判断条件，在找到插入位置后，进行插入前，我们需要一个空间来存放插入的值。从程序中不难看出，是将待插入位置后面的所有元素向后移动一位，而待插入位置存放在low中，因此，此空答案为i-1到 low。
(英语作文)1. 大学生享有很大的自由
2. 过多的自由对大学生来说有利有弊
3. 我的观点
On College Students' Freedom
Compared with high school students, college students enjoy much more freedom. They get a lot of time at their own disposal, they have diverse courses to choose from, and they can also make decisions on their daily affairs.
If the students can make good use of this freedom, they may benefit a lot in many aspects. For students who have particular interest in some subjects, they may pursue further study in those fields. For students who are keen in social work, they can join various organizations or associations to develop and display their abilities. And for students who want to support themselves, they may take some part-time jobs to make money.
On the other hand, excessive freedom can also have negative influence on college students. Faced with so much free time and so many choices, some students may get puzzled. Some of them may feel overwhelmed or aimless due to too many courses they register for or various activities they get involved in. Moreover, some students even get lost in the face of too much liberty. Eventually, they will be spoiled and lose their self-control. As a result, they may become addicted to computer games or idle away their precious time in various meaningless entertainments.
As a college student, I think two things may help us take full advantage of freedom. First, we must set up clear goals for life and study, and learn to prioritize things. Second, we should realize that freedom means responsibility. We have to be rational in every single decision that we make. In this way freedom can make our college life more colorful and more meaningful.
国家开放大学电大本科人文英语3期末试题及答案(试卷号：1379)2022盗传必究一. 交际用增(共计1。分,电小18 2分)151：堆择正折的阔旬完成下列M话并将答)8序号写在答1!岖上1. Wh r ir John J 1 njdldn (ind hitnA.Shr i、vrfy buny working in hin projcuIk I urn Murr v hul 1r hi nfraid I vnn * I ngf r will) you(I wu|)|io?tr hr cntild hnvi gnnr Id fhr HHMlifig nx)nt2. I io you hnvr nny oboui h“w t drlivcr u pfri h?A. Molly# Ate you rrady (or th，wrrkrnd speech?H. I Itt of speech in not totally dcpriHliriK on ihr conu nb( Firn! you should rernrrnher to keep ryr cuntArt with your HHihrnt r.3. Thflt Mnidt I Mtill ptvicr trndilionnl (orninl rducfttion if poiwibkaA. I柘 you do ny online ho|ipinK r IrnrninR?IL Yrnlu tlufi nr I? I fni iioitK t5. How dew* it rxplnin the couhcji (ur flic in( rrnntng juvrnilr crimen?It w ihnt.A part r| I hr rrnMan t* the inlluencr of Intvrnrt violenceH. a hridihy Intrrnvt ntirfing cnvironrnrnr i needed( iht oprriitiriK compnnirM dan*t filter ihr rontrni nnlinr二、顽iLl法(转什分小1 2分)fi-的句于从三个选项中选出一个入空白处的JB佳选单,并将答言序号可在答B6帐上.hohrlwrrn Uce ru-hcr UnchifiH nnl diinncr inluctiiion itre im rcminKlyblurrrd.A.而好.Ik boundfiriew liKtnncc7. T Mdvnerment i( ivrhrmlogy hz boa1rd thr pace of our llvru. mid rvquirr* m tn hsn 一 vvrry ihy |unt tu May current in thr workplncr.Mimrthinic nvwII new amcfhingC. rvrry nrw thirty* lh rrnnnckd lha*r inthnt thvir homm n;uld be mii open invitnnon (omminl.A. tmiiionHt aHcntionI Hrrtdancc9 Wt nil tend to think thnt wc wrr imfe in out homes, but . . niatiy homes are nol 倡 tnfc they nrc up|%oird tu Lr,A. huprlullyH, unfurtunnlelyC iurkilyI。，will not only mukc thrm (rcl godcl： by MixidrniE Hrtiplr ciltrn work ovrrtiniv Ih CiHiar ol too murh workin queuA tu br wAitvdBt wh( wnmnR12. I le niked hut ncighlHir tohl. bounc-z 虹叩 nn rye onB. keep their ryea ont krep eye* up n li13. Join a local support group if you are having trouble undrrMan.lmg h“w e dt!idplincA, peHorm玖C. practiceH. Whh the cob1 of livinK higher every mWe ysr hdV,n fl b，K ,，un,ly ,a r，longer ttuniidrrcd a pructic/il ppfioru( gelBr conf lined15. You may “y “m。“me，u 仙y with your Wee bur remember thr game. ahouldnfl be H. look atC. look up17. On September 13. 2013. the Stole Councd issued n 心仙港州drvclopmcnl ol Chinn eMrrly 顷e 眠rvim , 11 tn be ped UpA. to peed uplC by Bpeodinit upIS. The impact of technology on modern Mt i immrourtblr.A. hZEB won，tUihr qiinluy n( Crtrr you ion pvulr.H. Ihc brtthe hifiheMC. hn1! hyou know the pcrwnA. Bettrf* higherQ The betterthe highercurrent20. The Advancement of Mg 血 boatlrd .he RCt。项，岫 and rg.E 顾 learn omethlng new every d” 呻 e Uy thr workplace.A. apparentinv lC. applicRblc三qt解供计仲分小 I分)2I25牡：阅域短文,从AJh三个选项中选出一个正确答宴.井将答案停号场在答fi!纸上. 1* 皿 r IThree Klnd of (；om1s1 here arc three kinds of unl*t hort-trrm. medium-rangr nnd lunirtc
某考试卷中有若干选择题，每答对一题加2分，答错或不答一题扣1分，一考生答对的选择题数量是答错或不答的5倍，选择题共得到45分。问试卷中有多少道选择题？（ ）
A.50
B.30
C.25
D.20
这是一道和差倍比问题。
（1）设答错的题目数为x，则答对的题目数为5x，有2×5x-x=45，可得x=5，则答对的题目数为5×5=25，题目总数为5+25=30。因此，本题的正确答案为B选项。
（2）如果答对5题，答错1题，得分应该是9分。现在得了45分，因此试卷中有45/9×（5+1）=30道题目，选B选项。
请将每一个空的正确答案写在答题卡【1】～【20】序号的横线上，答在试卷上不得分。
1.计算并填写下表
(1)
【1】B类【解析】题目中给定的lP地址191.23.181.13的第一字节范围属于128～191之间，可以判断该IP地址属于B类地址；或者将IP 地址写成二进制形式为：10111111.0 0010111.10110101.00001101，第一字节以“10”开头，也可以判断出该lP地址属于B类地址。
【2】191.23.128.0 【解析】由题目知，该lP地址的子网掩码为255.255.192.0，写成二进制表示法为11111111.11111111.11000000.00 00000，子网掩码的前18位为“1”，说明前18位为网络号，后14位为主机号。用子网掩码与lP地址做“与”运算，得到网络地址为 10111111.00010111.10000000.00000000，写成十进制即191.23.128.0 或191.23.128.0/18。
【3】191.23.191.255 【解析】把lP地址的主机号全部置“1”即可得到直接广播地址，即10111111.00 010111.10111111.11111111，写成十进制，即 191.23.191.255。
【4】 0.0.53.13 【解析】将网络号地址全部置“0”，便可得到该lP的主机号，即00000000.00000000.00110101.00001101，写成十进制即0.0.53.13。
【5】191.23.191.254 【解析】由于主机号全置“1”时为广播地址，是不可用的IP 地址。所以最后一个lP地址为主机号的广播地址减去l，即 191.23.191.254.
阅读以下说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
说明
某单位举办了一场知识竞赛，参加竞赛的选手为300名，依次从1～300进行编号。竞赛时间为9:00～11:00。8道竞赛题目依次从“A”～“H”编号，选手可按任意次序答
题，每完成一道题目，可立即提交答案。若答案正确(Y)，则选择其他题目进行解答，否则，可继续做该题目或选择其他题目进行解答，直至竞赛结束。
选手提交答案的情况及判定结果由专人即时录入，录入的数据如表1所示，对竞赛情况进行统计和排名的结果如表2所示。
统计和排名的规则如下：
1．若选手X在竞赛时提交的题目P解答正确，则解答该题目所用时间如下计算；
解答题目P的用时=提交题目P正确的时间-竞赛的开始时间+罚时
罚时=提交题目P错误解答的次数×20
例如=表1中14号选手在10:27提交了题目A的正确解答，因此该选手正确解答该题目所用时间为87分钟，由于之前的两次提交错误解答，罚时为2×20=40分钟，所以14号选手解答题目A的用时=87+40=127(分钟)。
2．已经提交正确答案的题目再次提交时不再计算。
3．竞赛结束时，选手的总用时为所有解答正确的题目用时累加所得，解答不正确的题目不计时。
4．排名时，完成题目数量多者排名靠前；若完成的题目数相同，则用时少者排名靠前；若完成的题目数和所用时间均相等，则名次相同；完成题目数为。的选手不参加排名。
函数void Statistic()的功能是：读取输入数据，进行统计、排名并输出结果。
define MAXN 300
typedef stmct{
int no； /*选手编号*/
int num; /*完成的题目数量*/
int time; /*完成题目的总用时*/
int d[8]; /*d[i]用于记录提交第i个题目错误答案的次数*/
int a[8]; /*a[i]用于记录第i个题目是否已经提交正确答案*/
}Info;
void Statistic() {
char ch,pass;
int i,j,k,h,m,t,time,Maxlndex;
Info R[MAXN+1 ];
for(i=1; i＜=MAXN; i++){ /*数组R的元素置初值0*/
R[i].no = 0;R[i].num = 0; R[i].time = 0;
for(j=0; j＜8; j++) {R[i].d[j] = 0; R[i].a[j] = 0;}
}/*for*/
MaxIndex = 0;
while (1){
/*录入一名选手提交答案的信息(小时：分钟，选取手编号，题目号，是否正确)*/
scanf("%d:%d,%d,%c,%c",&h,&m,&k,&ch,&pass);
if(h==0) break;
R[k].no = k; /*k为选手编号码*/
time=(1); /*计算答题时间，以分钟为单位*/
if(isupper(ch)) ch = 'a' + ch- 'A';
if(pass != 'Y' && pass != 'y') {R[k].d[ch-'a']++; continue;}
if (R[k].a[ch-'a']==1) continue;
R[k].a[ch-'a'] = 1;
R[k] .num++;
R[k].time +=(2);
if (k ＞ MaxIndex) Maxlndex = k;
}/*while*/
for(i=l; i＜MaxIndex; i++) { /*选取择排序*/
for(t=i,j=i+1; j＜=Maxlndex; j++)
if(R[t].num＜R[j].num|| (3))t=j;
if((4)) {R[0]=R[t];R[t]=R[i];R[i]=R[0];}
}/*for*/
k=1; R[0] = R[l];
for(i=1; i＜=Maxlndex; i++) /*输出排名情况*/
if (R,[i].num ＞ 0) {
if(R[i].num!=R[0].num||R[i].time!=R[0].time) k++；
R[0]=(5)；
printf("%d：%3d %4d %5d\n",k,R[i].no,R[i]．num,R[i]．time)；
)/*if*l<
(1)(h-9)*60+m，及其等价形式 (2)time+R[k].d[ch-'a']*20 其中ch-'a'可以表示为ch-97，R[k]可以表示为R[R[k].no] (3)Rrq.num=R[j]．num && R[t].time＞R[j].time，及其等价形式 (4)t!=i及其等价形式 (4)R[i]，及其等价形式 解析：本题考查的是通过阅读程序说明，在限定条件下进行程序设计的能力。
在函数Statistic()中，h:m表示竞赛选手提交解答的时间。根据注释，空(1)处用于计算以分钟为单位的答题时间。用提交时间减去竞赛开始时间，就是解答一个题目所用的时间，即空(1)处填入：(h-9)*60+m。
统计过程中采用小写英文字母表示题目的编号，因此语句
if(isupper(ch))ch='a'+ch-'A'；
用于将题目编号ch统一为小写字母。
函数中，while循环用于统计每个选手提交答案的情况，采用了直接存取的方法，即k号选手的数据记录在下标为k的数组元素中，即k号选手提交编号为ch的题目情况用R[k]．d[ch-'a']和R[k].a[ch-'a']记录，其中，d[ch-'a']用于记录提交编号为ch的题目的错误答案次数，a[ch-'a']则用于记录编号为ch的题目是否已经提交正确答案，以防止一个正确答案被同一名选手反复提交造成重复统计，相应的语句为
if(R[k].a[ch-'a']＝=1)continue；
因此，“R[k]．a[ch-'a']=1；”表示选手k首次正确提交了题目ch的解答，同时记录他解答正确的题目数加1，即“R[k).num++；”。已正确解答的题目总用时，由解答用时和罚时两部分组成，因此空(2)处应填入“time+R[k].d[ch-'a']*20”。
完成统计后，排名所需的数据都记录在结构体数组R[]的成员NO、nurn和time中，数组成员d[]和a[]就不再有用了。
根据输入数据完成统计之后，需要进行排序。函数Statistic()中采用的是简单选择排序，n个元素进行简单选择排序的基本思想是：通过n-1(1≤i≤n)次元素值之间的比较，从 n-i+1个元素中选出值最小的元素(用t记录该最小元素在数组中的下标)，，并和第i个元素进行交换，当i等于n时所有记录有序排列。根据排序规则，完成题目数量相同时，总用时少者排名靠前，因此空(3)处应填入“R[t].num==R[j].num && R[t].time＞R[j].time”，显然，若第i个元素本来就是最小元素，则无需交换，即空(4)处填入“t!=i”或其等价形式。
输出排名情况时，应注意并列名次问题。下面的代码段用于输出排名情况。
k=-1；R[0]=R[1]；
for(i=1；i=Maxlndex；i++)/*严输出排名情况*/
if(R[i].num＞0){
if(R[i].num!=R[0].num||R[i].time!=R[0]．time)k++；
R[0]=(5)；
printf("%d：%3d%4d%5d\n",k,R[i].no,R[i].num,R[i]．time)；
}/*if*/
显然，k表示选手的名次。R[0]记录的是R[i-1]的值，因此，排序后相邻的两个记录若完成题目数和总用时相同，则输出相同的名次号(即k不变)。因此，空(5)处填入“R[i]。
请将每一个空的正确答案写在答题卡【 】~【 】序号的横线上。答在试卷上不得分。
某二叉树有5个度为2的结点以及3个度为1的结点，则该二叉树中共有【 】个结点。
14 解析：在二叉树中，度为0的结点数是度为2的结点数加1，故二叉树中结点数的总和为度为0的结点数、度为1的结点数及度为2的结点数三者相加，得出结果为14个结点。
阅读以下说明，将应填入(n)处的字句写在答卷纸的对应栏内。
【说明】
下面的程序为堆排序程序，其中函数adjust(i,n)是把以R[i](1≤i≤┕i/2┙)为根的二叉树调整成堆的函数，假定R[i]的左、右子树已经是堆，程序中的，是在主函数中说明的结构数组，它含有要排序的n个记录。
【程序】
Void adjust(i，n)
Int i，n；
{
iht k,j;
element extr;
extr=r[i];
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[i](1≤i≤┗i/2┛)为根的二叉树调整成堆的函数，假定R[i]的左、右子树已经是堆，程序中的r是在主函数中说明的结构数组，它含有要排序的n个记录。
Void adjust(i,n)
Int i,n；
{
int k,j;
element extr;
extr=r[i];
k=i;
j=2*i;
while(j=n)
{if((jn)&&(r[j].keyr[j+ 1].key))
j++;
if(extr.keyr[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-1n≤2h+1-1，即2h≤n2h+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个记录的数组以及少量暂存单元。
堆排序算法是不稳定的。