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

一、算法设计题

1． 设A 和B 均为下三角矩阵，每一个都有n 行n 列。因此在下三角区域中各有n(n＋l)/2个无素。另设有一个二维数组C ，它有n 行n ＋1列。试设计一个方案，将两个矩阵A 和B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素矩阵元素

在C 中的存放位置下标的公式。

//本算法将n 阶方阵的下三角矩阵A 和B 置于C 中，矩阵B 要逆置

//算法结束

2． 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为:

{二叉树根结点的指针}

【答案】算法如下:

生成三叉链表的二叉树(题目给出PASCAL 定义，下面用类C 语言书写

)

是二叉树结点指针的一维数组，容量足够大

一维数组最后元素的下标

元素或虚结点

第 2 页，共 35 页

和B 的

【答案】算法如下:

根结点

双亲结点和子女结点用指针链上

结束

3． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为

。

【答案】算法如下:

用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值

n 为偶数时

r 最小值

("最大值) ；

4． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为；

。其中，data 存放结点的值；lc 、rc 为指向左、

右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。

【答案】算法如下:

先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在

设P 指向二叉树的根结点

结束

在中序线索二叉树T 中,, 求给定值为x 的结点的

后继结点

第 3 页，共 35 页

首先在T 树上査找给定值为x 的结点，由p 指向

' 若P 的右标志为1, 则P 的rc 指针指向其后继

结点P 的右子树中最左边的结点是结点P 的中序后继

结库

5． 设要求按

.

是一个记录构成的数组，

是一个整数数组，其值介于1〜100之间，现

的内容调整A 中记录的次序，比如当B[l]＝ll 时，则要求将A[l]的内容调整到A[ll]

中去。规定可使用的附加空间为O(1)。

【答案】算法如下:

//A是100个记录的数组，B 是整型数组，本算法利用数组B 对A 进行计数排序

//若B[i]＝i 则A[i]正好在自己的位置上，则不需要调整

//B[j]和B[k]交换

//r0是数组A 的元素类型，A[j]和A[k]

交换

//完成了一个小循环，第i 个已经安排好

//算法结束

二、应用题

6． 文件F 由200条记录组成, 记录从1开始编号, 用户打开文件后, 欲将内存中的一条记录插入文件F 中, 作为其第30条记录, 请回答下列问题, 并说明理由。

(1)若文件系统为顺序分配方式, 每个存储块存放一条记录, 文件F 的存储区域前后均有足够空闲的存储空间, 则要完成上述操作最少要访问多少存储块？F 的文件控制区内容会有哪些改变？

(2)若文件系统为链接分配方式, 每个存储块存放的一条记录和一个链接指针, 则要完成上述操作最少要访问多少存储块？若每个存储块大小为1KB , 其中4个字节存放指针, 则该系统支撑文件的最大长度是多少？

【答案】(1)因为要最少访问, 所以选择将前29块前移一个存储块单元, 然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出, 再访问目标存储块将数据写入,

所以最少需要访问

块存储块

F 的文件区的文件长度加1, 起始块号减1

(2)采用链接方式则需要顺序访问前29块存储块, 然后将新纪录的存储块插入链中即可, 把新

第 4 页，共 35 页