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

一、应用题

1． 假定有下列，

矩阵（n 为奇数）

如果用一维数组B 按行主次序存储A 的非零元素，问： （1）A 中非零元素的行下标与列下标的关系； （2）给出A 中非零元素的下标位在B 中的位置公式。

【答案】（1）主对角线上元素的坐标是i=j，副对角线上元素的坐标i 和j 有所以A 中非零元素的行下标和列下标的关系是

或

的关系，

与B 中的下标R 的关系；

给出利用的下标

定

（3）假定矩阵中每个元素占一个存储单元且B 的起始地址为

（2）非零元素分布在两条主、副对角线上，除对角线相交处一个元素（下称“中心元素”）外，其余每行都有两个元素。主对角线上的元素，在向量B 中存储的下标

是

副对角线上的元素，在中心元素前，在向量B

中存储的下标是

在中心元素后，其下标如下：

（3）在B 中的位置如下：

2． 设将n （n ＞l ）个整数存放到一维数组R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P （0＜P ＜n ）个位置，即将R 中的数据由

变换为

（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或

或JA V A 语言描述算法，关键之处给出注释。

原地逆置，得到

（3）说明你所设计算法的时间复杂度和空间复杂度。 【答案】（1）算法的基本设计思想：先将n

个数据由

第 2 页，共 37 页

要求：

然后再将数组R 中的前

，

（2）用C 语言算法描述如下：

个数和后P 个数分别原地逆置，

最终得到结果

（3）说明算法的复杂性：上述算法中3个Reverse 函数的的时间复杂度分别

为

为O

故算法的时间复杂度为

，算法的空间复杂度为0（1）。

3． 证明任一结点个数为n 的二叉树的高度至少为0 （logn ）。

【答案】最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n 个结点的二叉树的最低高度是h ，则n 应满足虑h 是整数. 则有即任一结点个数为n 的二叉树的高度至少为

4． 在某程序中，有两个栈共享一个一维数组空间的栈底。

（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2, 试分别写出栈满、栈空的条件。 【答案】（1）入栈主要语句

出栈主要语句

。解此不等式，并考

分别是两个栈

（2）

第 3 页，共 37 页

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

某一工程作业的网络图如图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

6． 索引顺序存取方法（ISAM ）中，主文件已按关键字排序，为何还需要主关键字索引？

【答案】ISAM 是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是以盘组、柱面和磁道（盘面）三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道（盘面）三级索引。在ISAM 文件上检索记录时，先从主索引（柱面索引的索引）找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止；反之，若找遍该磁道而未找到所查记录，则文件中无此记录。

7． 已知n 阶下三角矩阵A （即当时，有

，按照压缩存储的思想，可以将其主对角线以）

下所有元素（包括主对角线上元素）依次存放于一维数组B 中，请写出从第一列开始采用列序为主序分配方式时在B 中确定元素的存放位置的公式。

【答案】2

阶下三角矩阵元素第1列到第

列是梯形，元素数为

第1列有n 个元素，第j 列有而在第j 列上的位置是为

8． 对于后序线索二叉树，怎样査找任意结点的直接后继? 对于中序线索二叉树，怎样査找任意结点的直接前驱？

【答案】（1）后序线索树中结点的后继的方法如下：根结点无后继：当结点的rtag=1时，其右线索指向后继；当结点的rtag=0且是其双亲的右孩子，或是双亲的左孩于且双亲无右孩时，其双亲是该结点的后继；当结点是其双亲的左孩子且双亲有右孩子时，其双亲结点右子树种最左下

第 4 页，共 37 页

个元素，所以n

阶下三角矩阵A 按列存储，其元素在一维数组B 中的存储位置k 与i 和j 的关系为：