计算机导论课后习题参考答案

第1章计算机概述

一、单项选择题

ABDBCCDBAD

二、简答题

1.根据计算机所采用的电子逻辑元件可将计算机的发展划分为4个发展阶段，每个阶

段所采用的元器件分别为：电子管，晶体管，中、小规模集成电路，大规模、超大规模集

成电路。

2.冯•诺依曼计算机主要由4部分组成：运算器、存储器、控制器、输入/输出设备。

3.衡量计算机性能的指标主要有5个，分别为：字长、主频、存储容量、运算速度和

存取周期。

4.计算机的特点：1）能自动连续、高速度地运算；2）运算速度快；3）运算精度高；

4）具有超常的记忆能力；5）具有可靠的逻辑判断能力。

按运算规模，计算机可分为巨型机、大型机、中型机、小型机、微型机和工作站。

第2章计算机中的数据

一、单项选择题

AABCB

二、计算题

1.(1)7(2)511(3)4076

2.(1)7660(2)2010(3)2650

3.(1)2510(2)62720(3)643613630

4.(1)0.1B(2)-101.01B(3)110011B

三、简答题

1.计算机采用二进制表示数据主要有以下4个原因：1）二进制物理上易于实现；2）

二进制运算法则简单；3）二进制编码机器可靠性高：4）二进制通用性和逻辑性强。

2.在计算机中，所有数值型数据都用二进制编码来表示，这串二进制编码称为该数据

的机器数，数据原来的表现形式称为“真值”。一个进制中数码的个数称为“基数”。

3.带符号整数常用的编码形式有3种，分别为原码、反码和补码。1）原码表示法为：

最高位是符号位（0表示正，1表示负），其余各位表示数的绝对值大小。2）反码表示法为：

最高位是符号位（0表示正，1表示负），正数的反码与原码相同，负数的反码是在其原码

的基础上，除符号位外各位求反。3）补码表示法为：最高位是符号位（0表示正，I表示

负），正数的补码与原码相同，负数的补码是在该数反码的最低位加1。

4.要表示文本，必须先对每个可能出现的字符进行表示。计算机最早用于处理英文，

使用ASCII码来表示字符；后来也用于处理中文和其它文字，为了统一，出现了Unicode

码。1）ASCII码用7位二进制数表示一个字符，共可表示128个字符。2）Unicode码用

32位二进制数表示一个字符，最多可表示232个符号，代码的不同部分用于表示世界上不

同语言的符号，还有部分用于表示图形和特殊符号。

第3章计算机系统组成

一、单项选择题

1>B2、A3、B4、A5、B6、D7、D8、B9、D10、C

11、C12、A13、B14、C15、A16、C17、D18、A19、B20、D

二、简答题

1.微型计算机的结构主要由硬件和软件两部分组成，硬件部分主要包括包括中央处理

器（CPU）、外部总线扩展电路（包括板卡）、只读存储器（ROM）、存储器（RAM）、外部存储器：

硬盘、光驱等、外部接口串口、USB口、并行口等，以及显示器、键盘鼠标等。软件部分

主要包括操作系统以及应用系统软件及驱动程序等。

2.计算机系统包括硬件系统和软件系统两部分，简称为硬件和软件。硬件（Hardware）

是组成计算机的各种物理设备，由五大功能部件组成，即运算器、控制器、存储器、输入

设备和输出设备。这五大部分相互配合，协同工作。软件（Software）是指在硬件系统上运

行的各类程序、数据及有关资料的总称，由系统软件和应用软件组成。硬件是软件建立和

依托的基础，软件是计算机的灵魂。没有软件系统的计算机我们称之为“裸机”。因此，硬

件和软件相互结合构成了一个完整的计算机系统，只有硬件和软件相结合才能充分发挥计

算机系统的功能。

3.中央处理单元简称CPU（CentralProcessingUnit）,它是计算机系统的核心，计

算机所发生的全部动作都是由CPU的控制。由三个组成部分：算术逻辑单元（ALU）、寄存

器、控制单元

（1）算术逻辑单元：算术逻辑单元（ALU）对数据进行逻辑、移位和算术运算；

（2）寄存器：寄存器是用来临时存放数据的高速独立的存储单元。主要有：数据寄存器、

指令寄存器、程序计数器；

（3）控制单元：控制单元是对计算机发布命令的“决策机构”，用来协调和指挥整个计算

机系统的操作，它是控制整个计算机有条不紊地自动执行程序的元件。

4.存储器（Memory）是计算机用来存放程序和数据的记忆装置。存储器按照用途可分

为主存储器（内存）和辅助存储器（外存）。

（1）主存储器（内存）是指主板上的存储部件，主要采用半导体器件和磁性材料，用

来存放当前正在执行的数据和程序，它可直接和运算器、控制器交换数据，具有容量小、

速度快等特点；

（2）辅助存储器（外存）是指磁性介质或光盘等，能长期保持信息，相对于内存，它

有容量大、速度相对慢等特点。

5.输入设备（inputdevice）是指向计算机输入数据和信息的设备。常见的输入设备

有键盘、鼠标、扫描仪等。

（1）键盘（keyboard）：键盘广泛应用于微型计算机和各种终端上，通过键盘想计算

机输入各种指令和数据，指挥计算机工作。按键盘的键数分，键盘可分为83键盘、101键

盘、104键盘、107键盘等；按键盘的形式分，可分为有线键盘、无线键盘、带托键盘和

USB键盘等。按工作原理分，可分为机械键盘、塑料薄膜式键盘、导电橡胶式键盘、无接

点静电电容键盘。按外形分，可分为标准键盘和人体工程学键盘等。

(2)鼠标(mouse)：鼠标是计算机显示系统纵横坐标定位的指示器，因形似老鼠而得名。

鼠标按其工作原理的不同分为机械鼠标和光电鼠标，机械鼠标主要由滚球、辐柱和光栅信

号传感器组成。当你拖动鼠标时，带动滚球转动，滚球又带动辑柱转动，装在辑柱端部的

光栅信号传感器采集光栅信号。传感器产生的光电脉冲信号反映出鼠标器在垂直和水平方

向的位移变化，再通过电脑程序的处理和转换来控制屏幕上光标箭头的移动。按照形式可

分为有线鼠标和无线鼠标等。

(3)扫描仪(scanner)：扫描仪是利用光电技术和数字处理技术，以扫描方式将图形

或图像信息转换为数字信号的装置•扫描仪对照片、文本页面、图纸、美术图画、照相底

片、菲林软片，甚至纺织品、标牌面板、印制板样品等三维对象都可作为扫描对象，提取

和将原始的线条、图形、文字、照片、平面实物转换成可以编辑及加入文件中的装置。常

用的扫描仪有台式、手持式和滚筒式三种。分辨率是扫描仪最主要的技术指标，它表示扫

描仪对图像细节上的表现能力，即决定了扫描仪所记录图像的细致度，其单位为PPI

(PixelsPerInch)。

输出设备(outputdevice)是指将计算机中的数据或信息输出给用户，是人与计算机

交互的一种部件。常见的输出设备有显示器、打印机、绘图仪、影像输出系统、语音输出

系统和磁记录设备等。

(1)显示器(display)：也称为监视器，属于计算机输出设备。显示器的主要性能指

标有像素、分辨率、屏幕尺寸、点间距、灰度级、对比度、帧频、行频和扫描方式等；

(2)打印机(printer):用于将计算机处理的结果打印在相关介质上。衡量打印机性

能的指标有3项：打印分辨率、打印速度和噪声。

6.计算机软件系统由系统软件和应用软件组成。操作系统是最基本的软件系统，是人

机交互的接口。应用软件是为某类应用需要或解决某些特定问题而设计开发的程序，主要

由通用软件和专门软件组成。

第4章操作系统

一、单项选择题

DAABAACBCC

二、简答题

1.操作系统是一个管理和控制计算机硬件与软件资源，合理组织计算机工作流程，控

制程序运行，并向用户提供良好工作环境和接口的系统软件。操作系统至少应当具有4种

管理功能：内存管理、进程管理、设备管理和文件管理。

2.操作系统是随着计算机硬件技术的不断发展和用户的使用要求的提高而从无到有

不断完善起来的，其主要类型及其特点如下：

(1)批处理操作系统：具有很高的资源利用率和系统吞吐量，但作业的平均周转时

间较长，也没有交互性。

(2)分时操作系统：具有多路性、独立性、及时性和交互性特征，而交互性是其最

重要的特征之一。

(3实时操作系统：实时操作系统通常是专用的，具有高及时性和高可靠性，但交互

性较弱。

(4)微机操作系统：是配置在微型计算机上的操作系统，可以是单任务或多任务，

也可以是单用户或多用户系统。

(5)网络操作系统：是配置在网络中的操作系统，用于管理网络通信和共享资源，

协调各计算机上任务的运行，并向用户提供统一的、有效方便的网络接口。

(6)分布式操作系统：是配置在分布式处理系统上的操作系统，其最基本的特征是

能实现处理上的分布，而处理分布的实质是资源、功能、任务和控制都是分布的。

3.死锁是指多个进程在执行过程中，因争夺资源而造成的一种互相等待的现象。若无

外力推动，它们都将无法执行下去。发生死锁需要4个必要条件：互斥、资源占有、抢先

和循环等待。

4.64M-16M=48M

第5章程序设计基础

一、单项选择题

1、D2、C3、A4、C5、D6、D7、B8、A9、C10、C11、D

二、简答题

1.计算机程序设计语言的分类：

(1)机器语言：由机器指令构成的语言称机器语言，即用二进制编码组成。

(如:01110101)

特点：①费时费事；

②难懂容易错；

③只能在一种型号计算机上运行；

④可以直接在计算机上运行。

(2)汇编语言：用容易记忆的符号来代替机器指令中操作码和地址码的一种语言。

(如：ADD代表“+”SUB代表MOV代表“传递”)

优点：①程序直观容易阅读；

②编程工作量相对小。

缺点：①只能在一种型号机器上运行；

②不能直接在计算机上运行。

(3)高级程序设计语言：高级程序设计语言是一种面向过程或者面向对象的语言，不面

向机器，用一些符号或者数字对求解的问题或者现实世界进行描述。

特点：①直观、易写、易读、工作量小；

②不依赖于具体的机器；

③便于程序交流；

④不可直接在计算机上运行，经编译程序编译成机器语言后方可运行。

2.算法(Algorithm)是对特定问题求解步骤准确而完整的描述，它的表现形式是计算

机指令的有序系列，执行这些指令就可解决特定问题。一个好的算法应当具有以下5个重

要特性。

(1)有限性：算法在执行有限步之后必须终止，且每一步都应在有限的时间内完成：

(2)确定性：算法的每一步必须要有确切的含义，不能存在二义性；

(3)可行性：算法的每一步都是可执行的，可以通过有限次操作来完成其功能；

(4)输入：一个算法具有0个或多个输入；

(5)输出：一个算法具有1个或多个输出。

3.常用算法的描述方法有：自然语言法、流程图法、N-S流程图法、伪代码法等。

(1)自然语言：就是采用人们日常使用的语言，来描述解决问题的方法和步骤；这种描

述方法通俗易懂，即使是不熟悉计算机语言的用户也很容易理解程序。

(2)流程图：流程图是以特定的图形符号加上说明来表示算法，通常是用一些图框来表

示各种操作。

(3)N-S图是在流程图的基础上完全去掉流程线，并将全部算法写在一个矩形框内，且

框内还可以包含其他框的表示形式。N-S图包括顺序、选择和循环3种基本结构，如下图

所示：

顺序结构选择结构

当条件为JI时

循环结构

(4)伪代码：伪代码是介于自然语言和计算机语言之间的文字和符号.伪代码通常采用

自然语言、数学公式和符号来描述算法的操作步骤，同时采用计算机高级语言的控制结构

来描述算法步骤的执行顺序。在程序开发期间，伪代码经常用于“规划”一个程序，然后

再转换成某种高级语言程序。

4.计算机技术所涉及的算法比较多，常用的算法有枚举法、递推法、递归法、贪心算

法、分治法、回溯法等.

(1)枚举法，或称为穷举法，其基本思路是：对于要解决的问题，列举出它所有可能的

情况，逐个判断哪些是符合问题所要求的条件，从而得到问题的解；

(2)递推法：是按照一定的规律来计算序列中的某个项，通常是通过计算前面的一些项

来得出序列中指定项的值；

(3)递归法：程序直接或间接自己调用自己的方法简称为递归，它通常是把一个大型的、

复杂的问题层层转化为一个个与原问题相似的、规模较小的问题来进行求解；

(4)贪心算法：贪心算法采用自顶向下，以迭代的方式做出相继的贪心选择，每做一次

贪心选择就将所求解问题简化为一个规模更小的子问题，通过每一步贪心选择，就可得到

问题的一个最优解。贪心算法的每一步都能获得局部最优解，但由此产生的全局解有时不

一定是最优解，所以贪婪法不能回溯。

(5)分治法：分治法是把一个复杂的问题分解成两个或更多个相同或相似的子问题，再

把子问题分解成更小的子问题，直到最后的子问题可以进行简单的直接求解，合并所有子

问题的解就可得到原问题的解。

(6)回溯法：回溯法的基本思想是，在包含问题所有解的解空间树中，按照深度优先搜

索的策略，从根结点出发深度搜索解空间树；当搜索到某一结点时，要先判断该结点是否

包含问题的解，如果包含就从该结点出发继续搜索下去，否则就逐层向其祖先结点回溯。

若用回溯法求问题的所有解，需要回溯到根，且根结点的所有可行的子树都要进行搜索后

才能结束；若使用回溯法求任一个解时，则只需搜索到问题的一个解就可以结束。

三、程序编程

1.#include"stdio.h"

voidmain()

(

intx,y,z,t;

scanf("%d%d%d”,&x,&y,&z);

if(x>y)

(

t=x;x=y;y=t;

}/*交换x,y的值*/

if(x>z)

(

t=Z；Z=X;x=t;

}/*交换X,z的值*/

if(y>z)

(

t=y;y=z;z=t;

}/*交换z,y的值*/

printf(""smalltobig:%d%d%d\n〃，x,y,z);

2.^include“stdio.h”

voidmain()

(

intn,i,j,k;

printf(〃请输入要打印的行数：〃)；

scanf(〃％d〃，&n);

for(i=0;i<n;i++)

(

for(j=0;j<n-i-l;j++)

(

printf(/z");

)

for(k=0;k<2*(i+1)T;k++)

(

printf(〃*〃);

printf(〃\n〃)；

)

3.#includez，stdio.h〃

voidmain()

{intx,y,z;

printf(〃%8s%8s%8s\n〃，〃Cock〃，"Hen","chicken");

for(x=0;x<=20;x++)

for(y=0;y<=33;y++)

{z=3*(100-5*x-3*y);

if(z>=0&&x+y+z==100)

printf("%8d%8d%8d\n”,x,y,z);

)

第6章数据结构*

一、单项选择题

DDCCABDCCB

二、填空题

1.线性结构非线性结构。2.一对一一对多多对多

3.前驱1后续14.前驱1后续可以任意多个

5.有限集合D上的关系有限集合6.有序序列。

7.开放定址法拉链法8.散结构表结构树结构图结构

9.m=2ee=m10.插入排序选择排序

三、上机编程题

1.(1)实现顺序表类的参考代码：

#include<iostream>

usingnamespacestd;

classSeqList1{

public:

SeqList1(intsz,intleng);//构造函数

voidResize(intnewSize);

intlength(){returnlen;}//表长度

voidGet();//输入线性表中的元素

voidGetOut();//输出线性表中的元素

intSearch(intx);//在表中顺序搜索x

intbinarySearch(intx);〃二分查找

intInsert(intx,inti);〃在索引i处插入x

intinsertx(intx);//有序插入

intRemove(inti);//删除第i个位置处的表项

private:

int*data;//表的存放数组

intmaxSize;//表的最大可容纳项数

intlen;〃表实际长度

)；

SeqListl::SeqListl(intsz,intleng){//构造函数

if(sz>0){

maxSize=sz;

len=leng;

data二newint[maxSize];

if(data==NULL){

cout<<〃存储分配错误！〃<<〃\n〃；

return;

}

)

)

voidSeqListl::Resize(intnewSize){

if(newSize<=0){

cerr<〈〃无效的数组大小〃<<endl;

return;}

if(newSize!=maxSize){

int*NewArray=newint[newSize];

if(NewArray==NULL){

cerr<<"存储分配错误〃<<endl;

return;}

intn=len+l;

int*srcptr=data;

int*destptr=NewArray;

while(n--)*destptr++=*srcptr++;

data=NewArray;

maxSize=newSize;

)

)

voidSeqListl::Get(){//输入线性表中的元素

for(inti=0;i<len;i++){

cout<〈〃线性表第〃+〃个元素是：〃；

cin>>data[i];

)

cout<<endl;

}

voidSeqListl::GetOut(){//输出线性表中的元素

cout<〈〃线性表元素：{〃；

for(inti=0;i<len;i++){

cout<<data[i]<<z，

)

cout<<"}"<<endl;

}

intSeqListl::Insert(intx,inti){

//在顺序表中索引为i的位置处插入项x

〃函数返回插入是否成功的信息

intj;

if(i<0I|i>len)return1;

//插入位置不合理，不能插入

if(len==maxSize)return2;

//无空闲可用存储单元，不能插入

for(j=len;j>i;j一)

data[j]=data[j-1];〃依次后移

data[i]=x;//插入

len++;//顺序表长度增1

return0;

)

intSeqListl::insertx(intx){//有序插入

if(len==maxSize)Resize(maxSize*2);

//无空闲可用存储单元，扩容2倍

inti;

for(i=len-l;x<data[i]&&i>=0;i--)

data[i+l]=data[i];//边查边移

data[i+l]=x;〃插入x

len++;//表长增1

return0;

)

intSeqListl::Remove(inti){

//删除第i个位置处的表项

intj;

if(i<0||i>len)return1;

//删除位置不合理，不能删除

for(j=i+l;j<len;j++)

data[j-l]=data[j];//依次前移

len--;//表长度减1

return0;

}

intSeqListl::Search(intx){

//搜索函数：在表中顺序搜索与给定值x匹配的表项

//找到则函数返回该元素在线性表中的索引

//否则函数返回7,表示搜索失败

for(inti=0;i<len;i++)

if(data[i]==x)returni;

return-1;

)

intSeqListl::binarySearch(intx){

intleft,right,mid;

left=0;right=len-l;//定左右边界指针

while(left<=right){〃当待查段不空时

mid=(left+right)/2;//计算中值地址mid

if(x==data[mid])return(mid);//返回x的地址mid

if(x<data[mid])right=mid-l;//准备查前半段

elseleft=mid+l;//准备查后半段

}

return-1;//未找到x,返回无效地址

}

intmain(){

SeqListls1(100,5);

s1.Get();

s1.GetOut();

cout<<“线性表长度：z,<<sl.length()<<endl;

cout<<〃请输入需要查找的元素：〃；

intx;

cin>>x;

inti=s1.Search(x);

if(i!=-l)cout<<〃元素〃<<x<<”为线性表中第〃<<i+l<<〃个元素”<<endl;

elsecout<<“查找元素不存在！"<<endl;

ints;

i=s1.binarySearch(x);

if(i!=-l)cout<<"元素〃<<x<<〃为线性表中第〃<<i+l<<〃个元素〃<<endl;

elsecout<〈〃查找元素不存在！"<<endl;

i=sl.insertx(x);

if(i!=-l)cout<<x<<〃已插入线性表〃<<endl;

cout<<”插入后线性表长度:,z<<sl.length()<<endl;

s1.GetOut();

intj=s1.Remove(i);

if(j!=-l)cout<<〃表头元素已从线性表中删除〃<<endl;

cout<<"删除后线性表长度:，z<<sl.length()<<endl;

s1.GetOut();

return0;

}

运行结果如下图所示：

D:\JMSOFT\CYuYan\bin\wwtemp.exea*・*[o|回

a

型

房

元B

二F12

m

二

泰

呆

r2元5

旨

二B

幺

型

呆

元

二F316

♦

二m

幺

型

球

p4元S18

L二

幺

为

球

元2

二is-52

L.F

!51618

唾线:l建l慧ll鬻r元素:

8

质△后续性表长度：6

缓性美元藁：〈258161822>

表头元素已从线性表中删除

秘除后续些表长度：5

线性表兀素：＜58161822>

Pressanykeytocontinue,

(2)实现链表类的参考代码:

#include<iostream.h>

typedefintElemType;

structNodeType{

ElemTypedata;

NodeType*next;

)；

classLinkList{

private:

NodeType*Head;

intlen;

public:

LinkList();//构造

"LinkList();//析构

voidcreate();//头插法建表

voidcreate2();//尾插法建表

intgetLen();〃获取长度

voidinsert();//插入

ElemTypedelet。；//删除

voidsearch();//查找

voiddisplay();

voidinverse();//逆转函数

)；

//创建空链表

LinkList::LinkList(){

Head二newNodeType;

Head->next二NULL;

Head->data=O;

len=0;

)

LinkList::"LinkList(){

NodeType*p=Head->next;

〃使指针P指向链表的第一个节点

while(p!=NULL){

Head->next=p->next;

//使头指针指向P的下一个节点

deletep;

p=Head->next;

//使P节点指向头指针向的那个节点

)

deleteHead;

〃最后将头节点也删除

len=0;

cout<〈〃已经删除链表!z，<<endl;

}

voidLinkList::display()(

NodeType*p;

p=Head->next;

cout<<〃链表的值为：〃；

while(p!=NULL){

cout<<p->data<<zz〃；

p=p->next;

)

cout<<endl;

)

voidLinkList::create(){//头插法创建链表

NodeType*s;

ElemTypex;

cout<〈〃请输入一组数据并且以0结束。〃<<endl;

cin>>x;//输入数据元素。

while(x!=0){

s二newNodeType;//动态的申请一个节点

s->data=x;//给节点的数据域赋值

s->next=Head->next;//使s指向第一个节点

Head->next=s;〃使头节点指向新申请的s节点

1en++;

cin>>x;

)

cout<<“链表建成!，，<<endl;

)

voidLinkList::create2(){//尾插法创建链表

NodeType*last,*p;

ElemTypex;

last=Head;

cout<〈〃请输入一组数据并且以0结束。z，<<endl;

cin>>x;//输入数据元素。

while(x!=0){

p=newNodeType;

p->data=x;

last->next=p;//插在表尾

last=p;//修改尾指针

len++;

cin>>x;//读入下一个元素

)

last->next=NULL;

cout<<〃链表建成！〃<<endl;

)

voidLinkList::insert(){

cout<〈〃要插入元素的位置：，，<<endl;

inti;

cin>>i;

cout<<“要插入的元素：，z<<endl;

ElemTypex;

cin>>x;

NodeType*p,*q,*s;〃定义结构体类型指针

intk=l;

p=Head;//让p指向Head节点

q=p->next;//让q指向第一个节点

while(k<i&&q!=NULL){

P二q；

q=q->next;

k++;

)

if(k==i){〃实现插入

s=newNodeType;

s->data=x;

p->next=s;

s->next=q;

len++;

cout<〈〃记录成功插入！"<<endl;

)

else

cout<〈〃插入记录失败！〃；

)

ElemTypeLinkList::delet(){

cout<<〃输入要删除的元素：，z<<endl;

intx;

cin>>x;

NodeType*p,*q;

ElemTypey;

intk=1;

p=Head;

q=p->next;

while(q!=NULL&&q->data!=x){

P=q；

q=q->next;

)

if(q!=NULL&&q->data==x){

y=q->data;

p->next=q->next;

deleteq;

len一;

cout<<”记录成功删除!”<<endl;

)

else{

cout<<，zx不存在，删除失败"<<endl;

y=0;

}

returny;

)

voidLinkList::search(){

cout<〈”输入要查找的元素："<<endl;

intx;

cin>>x;

NodeType*p=Head;

while(p!=NULL){

if(p->data==x){

cout<<”记录查找成功！〃<<endl;//找到x

return;

)

p=p->next;//暂时没找到，则继续向后找

)

cout<<〃记录不存在！〃<<endl;//查找不成功

)

voidLinkList::inverse(){//链表的逆置

NodeType*p,*q;

p=Head->next;//让p指向第一个元素

Head->next=NULL;//让Head的指针域为空

while(p!=NULL){

q=p->next;//让q指向第二个元素

p->next=Head->next;〃让p的指针域为空

Head->next=p;

p=q;

)

)

intLinkList::getLen(){

returnlen;

voidmain(){

LinkListh;

h.create2();

h.display();

h.search();

h.delet();

h.display();

h.insert();

h.display();

cout<<〃进行链表元素逆置〃〈〈endl;

h.inverse();

h.display();

}

运行结果如下图所示：

2.实现二叉树类。

4include〃stdio.h〃

^includeiostream.h〃

#defineN6

typedefstructBTreeNode{

intdata;

BTreeNode*lChiId,*rChiId;

}Bnode,*ptr;

classBTree{

public:

voidsetRoot(ptrr){root=r;}

ptrgetRoot(){returnroot;}

ptrcreateBTree();//二叉树的创建

ptrbuiIdtree(inta[],intb[],inti,intj,ints,intt);

voidpreOrder。；//前序遍历(递归)

voidinOrder。；//中序遍历(递归)

voidpostOrder();〃后序遍历(递归)

intBTreeSize();//求结点个数

intBTreeLeaves();//求叶子结点个数

intBTreeHeight();//求树高

protected:

voidinOrder(ptr)"/中序遍历

voidpreOrder(ptr);//前序遍历

voidpostOrder(ptr);//后序遍历

intBTreeSize(ptr);〃结点个数

intBTreeLeaves(ptr);//叶子结点

intBTreeHeight(ptr);//树高

private:

ptrroot;

}；

ptrBTree::createBTree(){

ptrp;

intx;

scanf("%d〃，&x);

if(x==0)returnNULL;

p=newBnode;

p->data=x;

p->lChild=createBTree();

p->rChild=createBTree();

returnp;

}

ptrBTree::buildtree(inta[],intb[],inti,intj,ints,intt){

intk;

ptrp;

if(i>j)returnNULL;//序列空，返回空指针

p=newBnode;//申请结点

p->data=a[i];//造根结点

k=s;

while((k<=t)&&(b[k]!=a[i]))k++;//找根

if(b[k]!=a[i]){

cout<<z，Errorz，<<endl;

returnNULL;//没找到，出错

)

p->lChild=buiIdtree(a,b,i+1,i+k-s,s,k-l);

p->rChild=buiIdtree(a,b,i+k-s+1,j,k+1,t);

returnp;//返回根结点