2017年宁夏医科大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？
【答案】（1）最高位优先（MSD ）法 先对最高位关键字进行排序，将序列分成若干子序列，
每个子序列中的记录都具有相同的值，然后，分别就每个子序列对关键字
列。
（2）最低位优先
先对最低位关键字
位关键字
序列参加排序，
但对法 进行排序，然后对高一级关键字进行排序，依次重复，直至对最高进行排序，按值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。
2． 主机H 通过快速以太网连接Internet , IP地址为服务器S 的IP 地址为211.68.71.80。H 与S 使用TCP 通信时，在H 上捕获的其中5个IP 分组如题a 表所示。
题 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 ）
，seq=846b41c5H, 2题a 表中1号分组封装的TCP 段的FLAG 为02H （即SYN=1，ACK=0）
，seq=e059 9feffl，ack=846b41c6H，号分组封装的TCP 段的 FLAG 为12H （即 SY=1, ACK=1）
3号分组封装的TCP 段的FLAG 为10H （即 ACK=1）seq=846b41c6H, ack=e059 9ff0H，，所以 1、2、3号分组完成了 TCP 连接建立过程。
5号分组的总长度为40由于快速以太网数据帧有效载荷的最小长度为46字节，表中3、（28H ）
字节，小于46字节，其余分组总长度均大于46字节，所以3、5号分组在通过快速以太网传输时进行了填充。
（2）由3号分组封装的TCP 段可知，发送应用层数据初始序号为846b 41c6H, 由5号分组封装的TCP 段可知，ack 为846b 所以5号已经收到的应用层数据的字节数
为
（3）由于S 发出的IP 分组的标识=6811H，所以该分组所对应的是题47-a 表中的5号分组。S 发出的IP 分组的TTL=40H=64, 5号分组的TTL=31H=49, 64-49=15。所以，可以推断该IP 分组到达H 时经过了15个路由器。
3． 数据类型和抽象数据类型是如何定义的? 二者有何相同和不同之处? 抽象数据类型的主要特点是什么? 使用抽象数据类型的主要好处是什么？
【答案】（1）数据类型的定义
数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如c 语言中的整
，其操作有加、减、乘、除、型、实型、字符型等。整型值的范围（对具体机器都应有整数范围）
求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。
（2）抽象数据类型的定义
“抽象数据类型（ADT ）”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部
如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。
（3）两者的不同
抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。
（4）抽象数据类型的主要特点
，而是向“科学”迈进了一步。 抽象数据类型的出现使程序设计不再是“艺术”
（5）使用抽象数据类型的好处
使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明（提
，而不必了解实现细节。 供接口）
4． 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，则它的中序前驱结点没有右孩子。
【答案】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点：叶结点或仅有右子树的结点；而其中序前驱是其左子树上按中序遍历的最后个结点：叶结点或仅有左子树的结点。命题得证。
5． 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？
【答案】有两种方法，具体如下：
（1）对该算术表达式（二叉树> 进行后序遍历. 得到表达式的后序遍历序列，再按后缀表达式求值。
（2）递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符（+、
一、*、/等） 进行求值。
6． 在一棵表示有序集S 的二叉搜索树（binary search tree ）中，任意一条从根到叶结点的路径将S 分为3部分：在该路径左边结点中的元素组成的集合S1:在该路径上的结点中的元素组成的集合S2:在该路径右边结点中的元素组成的集合S3; S=S1US2US3, 若对于任意的
是否总有a ≤b ≤c? 为什么？
【答案】该结论不成立。例如，本题中对于任一
f 的左子树上。对于从a 到根结点路径上的所有，可在S2中找到a 的最近祖先f 。a 在，有可能f 在b 的右子树上，因而a 也就在b 的右子树上，这时a>b，因此a
相关内容
相关标签