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

一、应用题

1． 用一个数组S （设大小为MAX ）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的，其中i 为0或1，用判断条件，并用C 语言或PASCAL 语言设计公用的入栈操作push （i ，x ）于表示栈号，x 为入栈值。

，栈底设在数组的两端，两栈顶相邻时为栈满。设【答案】两栈共享一向量空间（一维数组）

共享数组为S[MAX]，则一个栈顶指针为一1，另一个栈顶指针为MAX 时，栈为空。用C 语言写的入栈操作push （i ，x ）如下：

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

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

}

算法中第4行有

第六行中也有

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

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

【答案】第4行的

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

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

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

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

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

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

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

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

（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

4． 已知一棵二叉树的后序遍历序列为EICBGAHDF , 同时知道该二叉树的中序遍历序列为CEIFGBADH ， 试画出该二叉树。

【答案】该二叉树如图所示：

图

5． 主机H 通过快速以太网连接Internet , IP地址为

题 a 表

服务器S 的IP 地址为211.68.71.80。

H 与S 使用TCP 通信时，在H 上捕获的其中5个IP 分组如题a 表所示。

请回答下列问题。

（1）题a 表中的IP 分组中，哪几个是由H 发送的? 哪几个完成了TCP 连接建立过程? 哪几个在通过快速以太网传输时进行了填充？

（2）根据题a 表中的IP 分组，分析S 已经收到的应用层数据字节数是多少？

（3）若题a 表中的某个IP 分组在S 发出时的前40字节如题b 表所列，则该IP 分组到达H 时经过了多少个路由器？

题 b 表

注：IP 分组头和TCP 段头结构分别如题a 图、题b 图所示：