当前位置：问答库＞考研试题

一、应用题

1． 若森林共有n 个结点和b 条边（b

【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。

2． 请写出应填入下列叙述中（ ）内的正确答案。

某一工程作业的网络图如图1所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天

数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）

表示进行作业的路径。

完成此工程的关键路径是（A ）完成此工程所需的最少天数为（B ）天，此工程中具有最大充

，充裕天数是（D ）裕天数的事件是（C ）。关键路径上的事件的充裕天数是（E ）。

图1

【答案】A. 0-2-6-9-11; B. 20; C.事件顶点1、5和7各充裕两天；D. 4天；E. 0

3． 二叉树的带权路径长度（WPL ）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T ，采用二叉链表存储，节点结构为：

其中叶节点的weight 域保存该结点的非负权值。设root 为指向T 的根节点的指针，设计求T 的WPL 的算法。要求：

（1）给出算法的基本设计思想；

（2）使用C 或C++语言，给出二叉树结点的数据类型定义；

（3）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。

【答案】（1）算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参

加一即可。

（2）

typedef struct BiNode

（3）具体算法实现如下：

如果当前节点为空节点

//如果当前节点的左右孩子节点都为空，即当前节点为叶子节点，直接返回当前节点的

WPL

//如果当前节点不是叶子节点，则对当前节点的左右子树进行递归，返回左右子树WPL 之和

4． 证明：在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求毎步论断都指出根据。

【答案】前序遍历是“根左右”. 中序遍历是“左根右”. 后序遍历是“左右根”。若将“根”去掉，三祌遍历就剩“左右”。三种遍历中的差别耽足访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。

5． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。

【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O （n ）; 而在链式存储方式下，插入和删除时间复杂度都是0（1）。

6． 某计算机采用16位定长指令字格式，其CPU 中有一个标志寄存器，其中包含进位/借位标志CF 、零标志ZF 和符号标志NF 。假定为该机设计了条件转移指令，其格式如下：

其中，00000为操作码OP ; C、Z 和N 分别为CF 、ZF 和NF 的对应检测位，某测位为1时表示需检测对应标志，需检测的标志位中只要有一个为1就转移，否则就不转移，例如，

若

OFFSET 是相对偏移则需检测CF 和NF 的值，当CF=1或NF=1时发生转移；

量，用补码表示。转移执行时，转移目标地址为

为请回答下列问题。

（1）该计算机存储器按字节编址，还是按字编址？该条件转移指令向后（反向）最多可跳转

顺序执行时，下条指令地址

最多少条指令？

（2） 某条件转移指令的地址为200CH ，指令内容如下图所示，若该执行

时

则该指令执行后PC 的值是多少？若该指令执行时

则该指令执行后PC 的值又是多少？请给出计算过程。

（3）实现“无符号数比较小于等时转移”功能的指令中，C 、Z 和N 应各是什么？

（4）以下是该指令对应的数据通路示意图，要求给出中部件①〜③的名称或功能说明。

【答案】

（1）因为指令长度为16位且下条指令地址为

向后最多可跳转127条指令。

N=l, 故应根据ZF 和NF 的值来判断是否转移。（2）指令中C = 0, Z=l，当CF=0, ZF=0, NF=1

时需转移。已知指令中偏移量为1110 0011B=E3H, 符号扩展后为FFE3H , 左移一位（乘2）后为FFC6H , 故PC 的值（即转移目标地址）为

PC

的值为

（3）指令中的C 、Z 和N 应分别设置为

法器：地址相加。

7． 调用下列C 函数f （n ），回答下列问题：

（1）试指出f （n ）值的大小，并写出，f （n ）值的推导过程；

（2）假定n=5，试指出，f （5）值的大小和执行，f （5）时的输出结果。

C 函数：

故编址单位是字节。 题中给出偏移量OFFSET 为8位补码，其范围为-128〜127, 故相对当前指令进行条件跳转，时不转移。（4）部件①指令寄存器：用于存放当前指令；部件②移位寄存器：用于左移一位；部件③加