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

一、应用题

1． 为什么文件的倒排表比多重表组织方式节省空间？

【答案】倒排表有两项，一是次关键字值，二是具有相同次关键字值的物理记录号，这些记录号有序且顺序存储，不使用多重表中的指针链接，因而节省了空间。

2． 在改进了的（无回溯）字符串模式匹配中，要先求next 数组的值。下面是求nextval 值的算法。

{在模式P 中求nextval 数组的值

}

算法中第4行有【答案】第4行的

第六行中也有

两处比较语句相同。请分析说明此两处比较

语句的含义是什么? 分析此算法在最坏情况下的时间复杂度是多少？

语句是测试模式串的第J 个字符是否等于第K 个字符，如是，则

语句的意义是，当第J 个字符在模式匹配中失

指针J 和K 均増加1，继续比较。第6行的

配时，若第K 个字符和第J 个字符不等，则下个与主串匹配的字符是第K 个字符；否则，若第K 个字符和第J 个字符相等，则下个与主串匹配的字符是第K

个字符失配时的下一个（即

）。该算法在最坏情况下的时间复杂度

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

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

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

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

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

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

（2）

typedef struct BiNode

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

如果当前节点为空节点

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

WPL

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

4． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。

（1）试问这种二叉树的结点总数是多少？ （2）试证明

。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。

【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-l 。

（2）证明：当i=l时，成立。

设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1, 对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公，所以结果不变，这就证明当i=n时公式仍成立。证毕。 式中. 因为

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

（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。

, 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍

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

出栈主要语句

（2）

6． 三个进程P1、P2, P3互斥使用一个包含N P1每次用produce （N ＞0）个单元的缓冲区。（ ）生成一个正整数并用put （ ）送入缓冲区某一空单元中；P2每次用getodd （ ）从该缓冲区中取出一个奇数并用countodd （ ）统计奇数个数；P3每次用geteven （ ）从该缓冲区中取出一个偶数并用counteven （ ）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

【答案】定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty 控制生产者与消费者之间的同步；mutex 控制进程间互斥使用缓冲区，程序如下：