西大 2001 年试题与分析参考答案.docx

西大2001年试题与分析参考答案

一、1．使用GOTO语句可以使流程在程序中转来转去，表面上看，比较灵活方便，但这恰恰是结构化

程序所忌讳的。因此，在设计程序时一般不轻易使用GOTO语句。结构化程序设计不是完全禁止使用

GOTO语句的，而只是有限制地使用GOTO语句，即只能在一个基本结构内使用，而不允许用GOTO语句

从一个基本结构转移到另一个基本结构。

．面向对象的程序设计优于传统的结构化程序设计，其优越性表现在它有希望解决软件工程的两个重

要问题——软件复杂性控制和软件生产效率的提高，另外还符合人类的思维习惯，能够自然地表现现实

世界实体和问题。它具有以下特点：

·数据的抽象性

·数据的隐藏性

·继承性

·多态性

·动态装订

封装是将方法和数据放在同一对象中，使得对数据的存取只能通过该对象本身的方法来进行，程序的其

它部分不能直接作用于此对象中的数据，对象间的交互只能通过消息来进行，因此，封装又称为数据隐

藏。

．函数的副作用是指函数具有采用别名和修改元的成分。

．数组可以看成是线性表在下述含义上的扩展：线性表中的数据元素本身也是一个数据结构。在n维

数组中的每个数据元素都受着n个关系的约束，在每个关系中，数据元素都有一个直接后继元素（除去

最后一个元素）和一个直接前驱元素（除去最前一个元素）。因此，这n个关系中的任一关系，就其单

个关系而言，仍是线性关系。串是取值范围受到限制的线性表，即只能取字符集合中的字符。因此，串

仍然是线性表。

二、1．C2．E、G

三、1．设度为0、1、2的结点个数及总结点个数分别为n0、n1、n2和n，则有

n0=50

n=n0+n1+n2

n-1=n1+2×n2

由以上三式可得n2=49

故有n-1=n1+2×49

n=n1+99

所以当n1=0时，n至少有99个结点。

．相关语句为：IFX^.Ltag=1

THENpost_order_prior:=X^.LcELSEBEGIN

IFX^.Rtag=0

THENpost_order_prior:=X^.RcELSEpost_order_prior:=X^.LcEND

．构造的Huffman树如图7.1所示。

图7.1huffman树

带权路径长度WPL=(5+6)×3+(7+8+9)×2=81.

．不能得到一个有序序列。堆的定义只规定了结点与其左右孩子结点间的大小关系，而同一层上的堂

兄结点间并无明确的大小关系，所以堆的层次遍历并不能得到一个有序序列。5．可以。参考西电99年软件专业试题。

6．可以。二叉树后序序列中的第一个结点即是左子树中最左下的结点，若最左

下的结点无左子树但有

右子树，那么后序序列第一个结点应是该右子树中最左下的结点。算法描述如下：FUNCTIONpostfirstnode(T:bitree):bitree;

BEGIN

P:=T;

IFTNILTHEN

WHILE(p^.lchildNIL)OR(p^.rchildNIL)DOBEGIN

WHILEp^.lchildNILDOp:=p^.lchild;

IFp^.rchildNILTHENP:=p^.rchild

END;

Postfirstnode:=pEND;

7

．运行结果为：

1

2

1

3

1

2

1

8

．二叉排序树如图

7.2所示。

图7.2二叉排序树

在等概率下查找成功的平均查找长度为

ASLsucc= (1+2×2+3+3+4+3+2×5+1×6)=

四、1．令Root指向根结点，hp指示有哪些信誉好的足球投注网站的结点，lc指示有哪些信誉好的足球投注网站过程中某一层中最后的一个结点。

当hp=lc时，说明此时有哪些信誉好的足球投注网站的结点正好是该层中的最后一个结点，则深度加1。结点按层从左到右入

队列。算法描述如下：

PROCEDUREDepthOfTree(root:pointer;VARdepth:integer);VARque:ARRAY[1..maxn]OFpointer;

he,tp,lc:integer;

BEGIN

depth:=0;

IFrootNILTHENBEGIN

hp:=0;

tp:=1;

lc:=1;

que[1]:=root;{指针结点进队列}REPEAT

hp:=(hpMODmaxn)+1;root:=que[hp];

IFroot^.lchildNILTHENBEGIN

tp:=(tpMODmaxn)+1;que[tp]:=root^.rchildEND;

IFr