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

一、应用题

1． 下列广义表，可以唯一对应一棵二叉树的有？并归纳出唯一对应的条件。

【答案】唯一对应一棵二叉树的有（2）、（3）和（5）。唯一对应的条件：空表、只有一个元素的表、每个子表个数是零或是2的表。

2． 为什么在倒排文件组织中，实际记录中的关键字域可删除以节约空间? 而在多重表结构中这样做为什么要牺牲性能？

【答案】因倒排文件组织中，倒排表有关键字值及同一关键字值的记录的所有物理记录号，可方便地查询具有同一关键字值的所有记录；而多重表文件中次关键字索引结构不同，删除关键字域后查询性能受到影响。

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

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

出栈主要语句

分别是两个栈

（2）

4． 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading ”和“being ”的存储映像如图所示。

图 存储映像7K 意图

设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为符i 所在结点的位置p ）。要求：

（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或【答案】

（1）算法的基本设计思想：

①分别求出strl 和str2所指的两个链表的长度m 和n ;

②将两个链表以表尾对齐：令指针p 、q 分别指向strl 和str2的头结点，若表中的第

个结点；若

则使q 指向链表中的第

表尾的长度相等。

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

（3）说明你所设计算法的时间复杂度。

请设计一

个时间上尽可能高效的算法，找出由strl 和str2所指的两个链表共同后缀的起始位置（如图中字

则使p 指向链

个结点，即使指针p 和q 所指的结点到

③反复将指针p 和q 同步向后移动，并判断它们是否指向同一结点。若p 和q 指向同一结点，则该点即为所 求的共同后缀的起始位置。

（2）用C 语言算法描述如下：

两个指针同步向后移动

（3）参考答案的时间复杂度为：

或

其中m 、n 分别为两个链表的

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

题 a 表

返回共同C 缀的起始点

服务器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 图所示：

题a 图IP 分组头结构

题b 图TCP 段头结构

【答案】（1）由于题a 表中1、3、4号分组的源IP 地址（第13〜16字节）均为192.168.0.8 ，所 以1、3、4号分组是由H 发送的。 （coa80008H ）