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

一、应用题

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

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

2． 假设利用边界标识法，并以首次拟合策略分配，己知在某个时刻可利用空间表的状态如图所示（注：存储块头部

域的值和申请分配的存储量均包括头部和尾部的存储空间）请画出：

（1）当系统回收一个起始地址为559，大小为45的空闲块之后的链表状态；

（2）系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态。

【答案】（1）系统回收一个起始地址为559，大小为45的空闲块后，因右侧起始地址604为空闲块，应与之合并。合并后，成为起始地址为559，大小为167的空闲块。链表状态如图1所示：

图1

（2）系统在接受存储块大小为100的请求后，将大小为117的空闲块分出100给予用户。在回收一个起始地址为515，大小为44的空闲块之后，因左侧起始地址为462、大小为53和右侧起始地址为559、大小为167均为空闲块，应与之合并。合并后，起始地址为462、大小为264的空闲块。链表状态如图2所示：

图2

3． 用单链表保存m 个整数，节点的结构为（data , link ）, 且点而删除其余绝对值相等的节点。

例如若给定的单链表head 如下

删除节点后的head 为

要求

（1）给出算法的基本思想 （2）使用c 或

语言，给出单链表节点的数据类型定义。

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

（3）根据设计思想，采用c 或【答案】（1）算法思想：

定义一个大小为n 的布尔数组flag ，初始时所有的元素都赋值为false , 用来标识遍历过程中是否出现元素绝对值为flag 的节点。然后遍历链表，遍历过程中，每一个当前结点data 域的绝对值，则将flag 位置为真（true ）所对应的flag 位：若为真，则删除该结点；若为假（false ）。

（2）节点的数据结构定义如下：

（3）

全局数组标志节点的绝对值是否出现过

（n 为正整数）。现要求

设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节

（4）说明所涉及算法的时间复杂度和空间复杂度。

则删除该节点

如果此绝对值已经在节点值的绝对值中出现过

否则，将flag 中对应的位置置为true ，并将指针指向下一个元素

，申请大小（4）只遍历一次链表，所以时间复杂度为0 （m ） （m 为单链表中元素的个数）为n 的数组，所以空间复杂度为0 （n ） （n 为节点绝对值的最大值）。

4． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。

图1

【答案】森林转换为二叉树分以下三步：

（1）连线（将兄弟结点相连，各树的根看作兄弟）。

（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。 （3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。 所以由上面三棵树转换得到的二叉树如图2所示：