信息学初赛模拟试题(三)
(普及组PASCAL语言二小时完成满分100分)
一、选择一个正确答案代码(A/B/C/D),填入每题的括号内(每题1.5分,多选无分,共30分)
1、MAN英文缩写的含义是(b )A.局域网 B.城域网 C.广域网 D.增值网
A局域网local area network;LAN定义:一种覆盖一座或几座大楼、一个校园或者一个厂区等地理区域的小范围的计算机网。
B城域网metropolitan area network;MAN 一种界于局域网与广域网之间,覆盖一个城市的地理范围,用来将同一区域内的多个局域网互连起来的中等范围的计算机网。
C.广域网WAN,Wide Area Network 一种用来实现不同地区的局域网或城域网的互连,可提供不同地区、城市和国家之间的计算机通信的远程计算机网。
D.增值网V AN Value Added Network 租用公用网的通信线路与计算机连接,进行信息的存储、处理的通信网系统。
2、小张用十六进制,八进制和十进制写了如下一个等式:64-13=33
式中三个数是各不相同进位制的数,试问64,13,33,分别为____c____。
A.八进制,十进制,十六进制B.十进制,十六进制,八进制64=4*8^0+6*8^1=52 13=3*16^0+1*16^1=19 33=33 52-19=33
C.八进制,十六进制,十进制D.十进制,八进制,十六进制
1.R进制转换为十进制数 先将R进制数按权位展开式展开,然后按十进制规则进行计算,其计算结果就是转换后的十进制数。
2.十进制转换为R进制数 这里的R通常表示2、8、16。转换规则分成整数部分和小数部分。 整数部分:采用“除以R取余法”。即用十进制数反复除以R,记下每次所得的余数,直至商为0,将所得的余数按最后一个余数到第一个余数的顺序依次排列起来即为转换结果。 小数部分:采用“乘以R取整法”。即用十进制小数乘以R,得到一个乘积,将乘积的整数部分取出,
3、表达式(4 MOD (-3))与(-4 MOD 3)的值为:_b______。
A.-1,-1 B.1,-1 C.-1,1 D.1,1
div是整除求商div的结果接近答案符号是被除数与除数符号相乘 mod是两个整型数相除取余数,余数符号与被除数符号相同。
4、试指出:下列if语句中,当x=80时, 运行的结果为______。
begin
y:=0;
readln(x);
if x<0 then y:=5
else
if x<10 then begin
y:=10;
if x<100 then y:=100;
end
else y:=200;
write('y=',y);
end.
A.y=9 B.y=200 C.y=10 D.y=100
5、设栈S的初始状态为空,现有5个元素组成的序列{1,2,3,4,5},对该序列在S栈上依次进行如下操作(从序列中的1开始,出栈后不再进栈):进栈,进栈,进栈,出栈,进栈,出栈,进栈,试问出栈的元素序列是________。
A.{5,4,3,2,1} B.{2,1} C.{2,3} D.{3,4}
“栈”是一种先进后出(First In Last Out)或后进先出(Last In First Out)的数据结构。“栈”是一种只能在一端进行插入和删除的特殊的线性表,进行插入和删除的一端称为“栈顶”,而不动的一端称为栈底(如下图)。插入的操作也称为进栈(PUSH),删除的操作也称为出栈(POP)。
6、ASCII码是()。
A.国标码B.二进制编码C.十进制编码D.美国标准信息交换码
ASCII码是目前计算机中用得最广泛的字符集及其编码,是由美国国家标准局(ANSI)制定的ASCII码(American Standard Code for Information Interchange,美国标准信息交换码),它已被国际标准化组织(ISO)定为国际标准,称为ISO 646标准。适用于所有拉丁文字字母,ASCII码有7位码和8位码两种形式。
7、一台计算机的字长是4个字节,这意味着()。
A.能处理的数值最大为4位十进制数9999
B.能处理的字符串最多由4个英文字母组成
C.在CPU中能够同时处理32位二进制数据
D.在CPU中运算的最大结果为2的32次方
字长:一个字中包含二进制数位数的多少称为字长。字长是标志计算机精度的一项技术指标。字长:电脑技术中对CPU在单位时间内(同一时间)能一次处理的二进制数的位数叫字长。所以能处理字长为8位数据的CPU通常就叫8位的CPU。同理32位的CPU就能在单位时间内处理字长为32位的二进制数据。 字节和字长的区别:由于常用的英文字符用8位二进制就可以表示,所以通常就将8位称为一个字节。字长的长度是不固定的,对于不同的CPU、字长的长度也不一样。8位的CPU一次只能处理一个字节,而32位的CPU一次就能处理4个字节,同理字长为64位的CPU 一次可以处理8个字节。
8、假设一台计算机的地址总线为16,那么中央处理器CPU能访问的最大存储器容量为( )
A.2 * 16 KB B.16KB C.2^16B D.16*1024*8 B
地址总线Address Bus是专门用来传送地址的,由于地址只能从CPU传向外部存储器或I/O端口,所以地址总线总是单向三态的,这与数据总线不同。地址总线的位数决定了CPU可直接寻址的内存空间大小,比如8位微机的地址总线为16位,则其最大可寻址空间为2^16=64KB,16位微型机的地址总线为20位,其可寻址空间为2^20=1MB。一般来说,若地址总线为n位,则可寻址空间为2^n字节。
9、计算机最终处理的信息形式是()
A.ASCII码B.BCD码C.二进制D.十六进制
10、与十六进制数6F等值的八进制数是()6f=f*16^0+6*16^1=111
A.166 B.139 C.157 D.183
11、以下属非法用户自定义标识符的是()。
A.date B.dir C.list D.type
12、设X和Y是同一种枚举类型变量,则下列语句中合法的是()。
A.X:=ORD(Y)B.X:=Y C.READ(X,Y)D.WRITE(T,Y)
(一)枚举类型的定义
枚举类型是一种自定义类型,要使用枚举类型当然也要先说明枚举类型。
枚举类型的一般格式:
说明:①括号中的每一个标识符都称为枚举元素或枚举常量。
②定义枚举类型时列出的所有枚举元素构成了这种枚举类型的值域(取值范围),也就是说,该类型的变量所有可能的取值都列出了。
例如,下列类型定义是合法的:
type days=(sun,mon,tue,wed,thu,fri,sat);
colors=(red,yellow,blue,white,black,green);
而下列类型定义是错误的(因为枚举元素非标识符):
type colortype=('red','yellow','blue','white');
numbers=(1,3,5,7,9);
ty=(for,do,while);
(二)枚举类型变量
定义了枚举类型,就可以把某些变量说明成该类型。如:
var holiday,workday:day;
incolor:colors;
也可以把变量的说明与类型的定义合并在一起,如:
var holiday,workday:(sun,mon,tue,wed,thu,fri,sat);
incolor:(red,yellow,blue,white,black,green);
(三)枚举类型的性质
⒈枚举类型属于顺序类型
根据定义类型时各枚举元素的排列顺序确定它们的序号,第一个枚举元素的序号为0。例如:设有定义:
type days=(sun,mon,tue,wed,thu,fri,sat);
则:
ord(sun)=0,ord(mon)=1,ord(sat)=6;succ(sun)=mon,succ(mon)=tue,
succ(fri)=sat;pred(mon)=sun,pred(tue)=mon,pred(sat)=fri。
应注意的是:枚举类型中的第一个元素无前趋,最后一个元素无后继。
⒉对枚举类型只能进行赋值运算和关系运算
一旦定义了枚举类型及这种类型的变量,则在语句部分只能对枚举类型变量赋值,或进行关系运算,不能进行算术运算和逻辑运算。在枚举元素比较时,实际上是对其序号的比较。当然,赋值或比较时,应注意类型一致。
例如,设程序有如下说明:
type days=(sun,mon,tue,wed,thu,fri,sat);
colors=(red,yellow,blue,white,black,green);
var color:colors;
weekday:days;
则下列比较或语句是合法的:
weekday:=mon;
if weekday=sun then write('rest');
weekday<>sun
而下面比较或语句是不合法的:
mon:=weekday;
mon:=1;
if weekday=sun or sat then write('rest');
sun>red
weekday<>color
⒊枚举变量的值只能用赋值语句来获得
也就是说,不能用read(或readln)读一个枚举型的值。同样,也不能用write(或writeln)输出一个枚举型的值。如write(red)是非法的,会发生编译错误。千万不要误认为,该语句的结果是输出"red"三个字符。
但对枚举数据的输入与输出可通过间接方式进行。输入时,一般可输入一个代码,通过程序进行转换,输出时,也只是打印出与枚举元素相对应的字符串。这在后面的例题中将有使用示例。
⒋同一个枚举元素不能出现在两个或两个以上的枚举类型定义中。
如:
type color1=(red,yellow,white);
color2=(blue,red,black);
是不允许的,因为red属于两个枚举类型。
13、计算机能够直接识别和处理的程序是_______程序
A.汇编语言B.源程序 C.机器语言 D.高级语言
14、设有说明
V AR A:ARRAY['A'..'E',1..4,BOOLEAN] OF REA1;
则A['A',3]是( )。
A.一个实型的数组元素
B.一个数组,该数组具有两个实型数组元素
C.一个数组,该数组具有4*2个实型数组元素
D.一个数组,该数组具有5*4*2个实型数组元素
var a:array['A'..'E',1..4,boolean]of real 相当于 var a:array['A'..'E'] of
array[1..4] of
array[boolean] of real a['A',3]
相当于a['A'][3]
所以a['A',3] 是B,一个数组,该数组具有两个实型数组元素 【答案】B
15、下列属于线性时间的排序算法是:()
A. 快速排序
B. 桶排序
C. 冒泡排序
冒泡排序
1、排序方法
将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。
(1)初始
R[1..n]为无序区。
(2)第一趟扫描
从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(R[n],R[n-1]),(R[n-1],R[n-2]),…,(R[2],R[1]);对于每对气泡(R[j+1],R[j]),若R[j+1].key 第一趟扫描完毕时,"最轻"的气泡就飘浮到该区间的顶部,即关键字最小的记录被放在最高位置R[1]上。 (3)第二趟扫描 扫描R[2..n]。扫描完毕时,"次轻"的气泡飘浮到R[2]的位置上…… 最后,经过n-1 趟扫描可得到有序区R[1..n] 注意: 第i趟扫描时,R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时,该区中最轻气泡飘浮到顶部位置R[i]上,结果是R[1..i]变为新的有序区。 2、冒泡排序过程示例 对关键字序列为49 38 65 97 76 13 27 49的文件进行冒泡排序的过程 3、排序算法 (1)分析 因为每一趟排序都使有序区增加了一个气泡,在经过n-1趟排序之后,有序区中就有n-1个气泡,而无序区中气泡的重量总是大于等于有序区中气泡的重量,所以整个冒泡排序过程至多需要进行n-1趟排序。 若在某一趟排序中未发现气泡位置的交换,则说明待排序的无序区中所有气泡均满足轻者在上,重者在下的原则,因此,冒泡排序过程可在此趟排序后终止。为此,在下面给出的算法中,引入一个布尔量exchange,在每趟排序开始前,先将其置为FALSE。若排序过程中发生了交换,则将其置为TRUE。各趟排序结束时检查exchange,若未曾发生过交换则终止算法,不再进行下一趟排序。 (2)具体算法 void BubbleSort(SeqList R) { //R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序 int i,j; Boolean exchange;//交换标志 for(i=1;i exchange=FALSE;//本趟排序开始前,交换标志应为假 for(j=n-1;j>=i;j--) //对当前无序区R[i..n]自下向上扫描 if(R[j+1].key R[0]=R[j+1];//R[0]不是哨兵,仅做暂存单元 R[j+1]=R[j]; R[j]=R[0]; exchange=TRUE;//发生了交换,故将交换标志置为真 } if(!exchange) //本趟排序未发生交换,提前终止算法 return; } //endfor(外循环) } //BubbleSort 快速排序(QuickSort) 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。 (1)分治法的基本思想 分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。 (2)快速排序的基本思想 设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为: ①分解: 在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。 注意: 划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos]): R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys 其中low≤pivotpos≤high。 ②求解: 通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。 ③组合: 因为当"求解"步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,"组合"步骤无须做什么,可看作是空操作。 2、快速排序算法QuickSort void QuickSort(SeqList R,int low,int high) { //对R[low..high]快速排序 int pivotpos;//划分后的基准记录的位置 if(low pivotpos=Partition(R,low,high);//对R[low..high]做划分 QuickSort(R,low,pivotpos-1);//对左区间递归排序 QuickSort(R,pivotpos+1,high);//对右区间递归排序 } } //QuickSort 注意: 为排序整个文件,只须调用QuickSort(R,1,n)即可完成对R[l..n]的排序。 桶排序 定义 假定:输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数基本思想将区间[0, 1)划分为n个大小相等的子区间(桶),每桶大小1/n:[0, 1/n),[1/n, 2/n),[2/n, 3/n),…,[k/n, (k+1)/n ),…将n个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组,指向桶(链表)。 算法思想 平均情况下桶排序以线性时间运行。像计数排序一样,桶排序也对输入作了某种假设,因而运行得很快。具体来说,计数排序假设输入是由一个小范围内的整数构成,而桶排序则假设输入由一个随机过程产生,该过程将元素一致地分布在区间[0,1)上。桶排序的思想就是把区间[0,1)划分成n个相同大小的子区间,或称桶,然后将n个输入数分布到各个桶中去。因为输入数均匀分布在[0,1)上,所以一般不会有很多数落在一个桶中的情况。为得到结果,先对各个桶中的数进行排序,然后按次序把各桶中的元素列出来即可。在桶排序算法的代码中,假设输入是个含n个元素的数组A,且每个元素满足0≤ A[i]<1。另外还需要一个辅助数组B[O..n-1]来存放链表实现的桶,并假设可以用某种机制来维护这些表。桶排序的算法如下,其中floor(x)是地板函数,表示不超过x的最大整数。procedure Bin_Sort(var A:List); begin 桶排序算法 1 n:=length(A); 2 for i:=1 to n do 3 将A[i]插到表B[floor(n*A[i])]中; 4 for i:=0 to n-1 do 5 用插入排序对表B[i]进行排序; 6 将表B[0],B[1],...,B[n-1]按顺序合并; end; 右图演示了桶排序作用于有10个数的输入数组上的操作过程。(a)输入数组A[1..10]。(b)在该算法的第5行后的有序表(桶)数组B[0..9]。桶i中存放了区间[i/10,(i+1)/10]上的值。排序输出由表B[O]、B[1]、...、B[9]的按序并置构成。要说明这个算法能正确地工作,看两个元素A[i]和A[j]。如果它们落在同一个桶中,则它们在输出序列中有着正确的相对次序,因为它们所在的桶是采用插入排序的。现假设它们落到不同的桶中,设分别为B[i']和B[j']。不失一般性,假设i' i'=floor(n*A[i])≥floor(n*A[j])=j' 得矛盾(因为i' 现在来分析算法的运行时间。除第5行外,所有各行在最坏情况的时间都是O(n)。第5行中检查所有桶的时间是O(n)。分析中唯一有趣的部分就在于第5行中插人排序所花的时间。为分析插人排序的时间代价,设ni为表示桶B[i]中元素个数的随机变量。因为插入排序以二次时间运行,故为排序桶B[i]中元素的期望时间为E[O(ni2)]=O(E[ni2]),对各个桶中的所有元素排序的总期望时间为:O(n) (1) 为了求这个和式,要确定每个随机变量ni的分布。我们共有n个元素,n个桶。某个元素落到桶B[i]的概率为l/n,因为每个桶对应于区间[0,1)的l/n。这种情况与投球的例子很类似:有n个球(元素)和n个盒子(桶),每次投球都是独立的,且以概率p=1/n落到任一桶中。这样,ni=k的概率就服从二项分布B(k;n,p),其期望值为E[ni]=np=1,方差V[ni]=np(1-p)=1-1/n。对任意随机变量X,有: (2) 将这个界用到(1)式上,得出桶排序中的插人排序的期望运行时间为O(n)。因而,整个桶排序的期望运行时间就是线性的。 16、一棵包含n个节点的树有几条边: A. n B. n-1 C. 不一定 17、在Pascal语言中,表达式35 div 3 mod 4 的值是________。 A.0B.2C.3D.6 18、在数据结构中,"树"结构下层结点出现三个以上的结点,这种结构称为________。 A.三层树B.三叉树C.多层树D.多叉树 19、在Pascal语言中,下列程序段所计算的公式是________。 程序段:S:=0 ;T:=1; For I:=1 to 10 do Begin T:=T*I;1 2 6 S:=S+T;1 3 end; A.S=1+2+3+4+……+10 B.S=1*2*3*4*……*10 C.S=1!+2!+3!+4!+ (10) D.S=1+2*3+3*4+4*5+……+10*11 20、以下说法正确的是()。 A.CPU与内存不交换信息B.CPU与内存直接交换信息 C.CPU与内存间接不交换信息D.CPU与内存部分交换信息 cpu是中央处理单元的英文缩写,又叫中央处理器。是电脑的核心部件,像人的大脑一样。它又包括算术处理单元、逻辑控制单元等,主要功能是计算和处理数据。 内存又叫存储器,是电脑的存储单元,CPU取数据以及对数据的处理结果都要存放在内存中。存储器又分只读存储器和随机存储器。只读存储器存放电脑出厂时的一些固定设置,如bios(基本的输入输出系统)设置,用户不可更改。随机存储器存放CPU需要的临时数据、经CPU处理后的结果数据,这些数据在断电后丢失,比如打字时要随时保存,就是防止断电后丢失数据,被保存的数据放在硬盘中,就不会丢失了。 纵观CPU和内存,两者在电脑中缺一不可,互相依存。两者性能也必须匹配,如果,cpu性能高,而内存性能低,或是内存性能高,而CPU性能低,都会影响电脑的整体性能。 二、阅读下列程序,写出程序运行结果(第1题5分,第2,3,4题各6分,共23分) program exp1; const n=5; var I,j,k:integer; r:array[0..10] of integer; begin for I:=1 to n do read(r[I]); r[1]=8, r[2]=4 r[3]=9, r[4]=3, r[5]=5 for I:=2 to n do begin k:=r[I];j:=I-1; while (k>r[j]) and (j>0) do begin r[j+1]:=r[j];j:=j-1;end; r[j+1]:=k; end; for I:=1 to n do write(r[I],??); writeln end. 键盘输入: 8 4 9 3 5 屏幕输出:98543 program exp2; var a,b,f:integer; function gd(m,n:integer):integer; begin if n=0 then gd:=m else gd:=gd(n,m mod n); end; begin readln(a,b); write(…(…,a,?,?,b,?)=?); f:=gd(a,b); writeln(f) end. 键盘输入: 172 16 屏幕输出:(172,16)=4 3、Program exp3(input,output); V AR I,J,S:INTEGER; B :ARRAY[0..5] OF INTEGER; BEGIN S:=1; FOR I:=1 TO 5 DO B[I]:=I; J:=1; WHILE J>0 DO BEGIN J:=5; WHILE (J>0) AND (B[J]=10+J-5) DO J:=J-1; IF J>0 THEN BEGIN S:=S+1; B[J]:=B[J]+1; FOR i:=J+1 TO 5 DO B[i]:=B[J]+i-J END; END; WRITELN('S=',S); END. S=252 4、program exp4(input,output); var m,n,g:integer; function gcd(m,n:integer):integer; begin if n=0 then gcd:=m else gcd:=gcd(n,m mod n) end; begin read(m,n); g:=gcd(m,n); writeln('m=',m,'n=',n,'gcd=',g) end. 输入:48 9 输出:m=48n=9gcd=3 三、问题解答(第1题每空4分,第2题8分) 1、数据结构中,下面是一个树结构图,这个树的"先序遍历"结果是abcde________,中序遍历结果是:______badce_______。 4.1树的概念 树的递归定义如下:(1)至少有一个结点(称为根)(2)其它是互不相交的子树 1.树的度——也即是宽度,简单地说,就是结点的分支数。以组成该树各结点中最大的度作为该树的度,如上图的树,其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。 2.树的深度——组成该树各结点的最大层次,如上图,其深度为4; 3.森林——指若干棵互不相交的树的集合,如上图,去掉根结点A,其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林; 4.有序树——指树中同层结点从左到右有次序排列,它们之间的次序不能互换,这样的树称为有序树,否则称为无序树。 5.树的表示 树的表示方法有许多,常用的方法是用括号:先将根结点放入一对圆括号中,然后把它的子树由左至右的顺序放入括号中,而对子树也采用同样的方法处理;同层子树与它的根结点用圆括号括起来,同层子树之间用逗号隔开,最后用闭括号括起来。如上图可写成如下形式: (A(B(E(K,L),F),C(G),D(H(M),I,J))) 4.2 二叉树 1.二叉树的基本形态: 二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态: (1)空二叉树——(a); (2)只有一个根结点的二叉树——(b); (3)右子树为空的二叉树——(c); (4)左子树为空的二叉树——(d); (5)完全二叉树——(e) 注意:尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形。 2.两个重要的概念: (1)完全二叉树——只有最下面的两层结点度小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树; (2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。 如下图: 完全二叉树 满二叉树 3.二叉树的性质 性质1二叉树的第i层上至多有2i-1个结点(i>=1) 性质2深度为h的二叉树至多有2h-1个结点,最少有h个结点; 性质3 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1; 推论:如果一棵m度树中有n1个度为1的结点,n2个度为2的结点,…….有n m个度为m的结点,则该树中叶结点的的个数=______________. 分析:令N为总结点数,B为树枝总数,点则有:N=B+1,因为N= n0+n1+n2+……+n m, B= n1+2n2+……+mn m,所以叶结n0=n2+2n3+……+(m-1)n m+1. 性质4具有n个(n>0)结点的完全二叉树的深度为[log2(n+1)]或[log2n]+1。 (5)有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系: 若I为结点编号则如果I<>1,则其父结点的编号为I/2; 如果2*I<=N,则其左儿子(即左子树的根结点)的编号为2*I;若2*I>N,则无左儿子; 如果2*I+1<=N,则其右儿子的结点编号为2*I+1;若2*I+1>N,则无右儿子。 4.二叉树的遍历运算(递归定义) (1)先序遍历 访问根;按先序遍历左子树;按先序遍历右子树 (2)中序遍历 按中序遍历左子树;访问根;按中序遍历右子树 (3)后序遍历 按后序遍历左子树;按后序遍历右子树;访问根 *规律:不同形态的二叉树数目恰好是前序序列均为1,2,3,…,n的二叉树所能得到的中序序列的数目,即是1/(n+1)C2n n。例如:按中序遍历二叉树所得的结果序列为ABC,试给出所有可能得到这一遍历的二叉树。 分析:n=3, 则1/(n+1)C2n n=1/(3+1)C63=5种。 4.3二叉树的应用 哈夫曼树与哈夫曼码 树的路径长度:一棵树的每一个叶结点到根结点的路径长度的和。 带权二叉树:给树叶结点赋上某个实数值(称叶结点的权)。 带权路径长度:各叶结点的路径长度与其权值的积的总和。 哈夫曼树(最优二叉树):带权路径长度最小的二叉树。 如何构建哈夫树:(思想是:权越大离跟越近) 2、给出一个后缀算术表达式为 24 8 +3 *4 10 7 -*/@ 写出对应的中缀算术表达式:______(24+8)*3/4*(10-7)_____________________________________ 24+8*3/4*10-7 为了不改变原来的运算次序,加上括号后为: [(24+8)*3]/[4*(10-7)] 后序遍历是先遍历左子树,后遍历右子树,最后才是根,所以,紧邻每个运算符号前的两个数字必为该运算符的左右操作数,也就是该根的左右子树+号前的24 8分别是它的左右子树,-号前的10 7分别是它的左右子树 所以,原表达式初步可变为: (24 8 +) 3 * 4 (10 7 -) * / 现在第一个*号前的操作数可以看出是(24 8 +)3 第二个*号前的操作数为4(10 7 -) 两个括号内的部分可以确定分别组成一棵子树,所以,进一步可变为: ( (24 8 +) 3 *) (4 (10 7 -) *) / 左子树右子树根 由此可确定该二叉树,然后中序遍历即可 四、完善程序(第一题每空3分,第二题每空2分,第三题每空4分,共32分) 1、连续整数平台问题 已知一个含有多个整数的数组,其中相同的元素集中在一起形成一个平台。以下程序用于对输入的数组求出其中最大平台长度。例如,中元素个数为20,它们依次为2 2 2 2 3 3 3 3 3 1 1 1 1 1 1 1 1 1 4 4 则它的最大平台长度为9。 const maxlength=100; var a:array[1..maxlength] of integer; i,maxi,n,s,t:integer; begin write('n=');readln(n); for i:=1 to n do read(a[i]); readln; maxi:=0; t:= [1] s:=1; for i:=2 to n do if a[i]=t then [2] else begin if s>maxi then maxi:=s; t:=a[i]; [3] [4] writeln('maxi=',maxi); end. (1) a[1] (2)s:=s+1 (3)s:=1 (4)if s>maxi then maxi:=s; 2、1000!尾0问题 以下程序用于统计1000!末尾有多少个0。其中1000!=1?2?3?…?1000。实际上我们只要统计1000!有多少个因子10。由于10=5?2,因而只需统计有多少个因子5和2。显然在1~1000的所有数中,5的因子个数比2的因子个数少。因此,只要统计1~1000的所有数中共有多少个因子5就行了。 var i,j,n:integer; begin n:=0; for i:=1 to 200 do begin j:=i*5; while [5] =0 do begin n:=n+1; j:= [6] end; end; writeln(n:4); End. (5)j mod 5 (6) j div 5 要考虑1000!后面有多少个0,我们可以这样想,0是由什么得来的呢?? 2*5=10,是的,我们可以由2*5得来0,好的,我们就来看,1000!的质因数分解中有多少个2,多少个5; 想一下,2的个数一定大于5个,所以,只要考虑5的个数就行了... 好的,我们这样想 1000以内有多少个能被5整除的数?? 1000/5=200 1000以内有多少个能被25整除的数? 1000/25=40 1000以内有多少个能被125整除的数? 1000/125=8 1000以内有多少个能被625整除的数? 1000/625=1 ............ 所以,1000!中,5的指数就是:200-40-8-1+2*(40-8-1)+3*(8-1)+4*1=200+40+8+1=249个 好的,我们现在不考虑1000,考虑其他的任何一个数n,那么这个数的阶乘中有多少个5呢? n/5+n/25+n/125+... 一直到n<5^m为止; 注意int/int==int(4/3==1) 先声明n,result(结果),输入n(这里n=1000) while (n!=0) { n=n/5; result +=n; } 输出n就行了.