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

一、应用题

1． 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？

【答案】有两种方法，具体如下：

（1）对该算术表达式（二叉树> 进行后序遍历. 得到表达式的后序遍历序列，再按后缀表达式求值。

（2）递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符（+、一、*、/等） 进行求值。

2． KMP 算法（字符串匹配算法）较Brute （朴素的字符串匹配）算法有哪些改进？

【答案】朴素的模式匹配度达到

时间复杂度是

KMP 算法有一定改进，时间复杂

主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配

时，KMP 算法的优点更为突出。

3． 设哈希（Hash ）表的地址范围为0～17，哈希函数为：造出哈希表，试回答下列问题：

（1）画出哈希表示意图；

（2）若查找关键字63，需要依次与哪些关键字比较？ （3）若查找关键字60，需要依次与哪些关键字比较？

（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 【答案】（1）哈希表示意图如表所示：

表 哈希示意图

为关键字，用

线性探测再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）

（2）查找关键字63时，由于63比较。

（3）查找关键字60时，由于（4）

哈希地址12内为空，查找失败。 所以需要依次与31，46，47，32，17，

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

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

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

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

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

【答案】（1）第一层FOR 循环判断n ＋1次，往下执行n 次，第二层FOR 执行次数为（n ＋，第三层循环体受第一层循环和第二层循环的控制，其执行次数如（n －1）＋（n －2）＋... ＋1）表所示。

表 执行次数

执行次数为

（2）在n=5对，f （5）=55，执行过程中，输出结果为：

6． 假设Internet 的两个自治系统构成网络如题图所示，自治系统ASI 由路由器R1连接两个子网构成；自治系统AS2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、R1与R3的部分接口 IP 地址如题图所示。请回答下列问题。

题图网络拓扑结构

（1）假设路由表结构如下所示。请利用路由聚合技术，给出R2的路由表，要求包括到达题图中所有子网的路由，且路由表中的路由项尽可能少。