《2017年厦门大学自动化系845数据结构考研题库.doc》由会员分享，可在线阅读，更多相关《2017年厦门大学自动化系845数据结构考研题库.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年厦门大学自动化系845数据结构考研题库一、填空题1 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_，又称P 为_。【答案】模式匹配；模式串2 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_; 对于有向图来说等于该顶点的_。【答案】度；出度 3 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_条。【答案】m/2【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。4 对于给定的元素，可以构造出的逻辑结构有_，_，_，_四种。【答案】集合；线性结构；树形结构；图状结构（网状结构）5 设为哈夫曼树
2、的叶结点数日，则该哈夫曼树共有_个结点。【答案】 【解析】哈夫曼树只有度为0和2的节点。 6 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。 第 2 页，共 51 页 【答案】 7 【答案】5=_
3、8 抽象数据类型的定义仅取决于它的一组_，而与_无关, 即不论其内部结构如何变化，只要它的_不变，都不影响其外部使用。【答案】逻辑特性；在计算机内部如何表示和实现；数学特性 9 对n 个记录的表rl.n进行简单选择排序，所需进行的关键字间的比较次数为_。【答案】n （n-1）/2【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+.+l=n（n-l ）/2。10假定查找有序表【答案】37/12【解析】折半查找时每个的次数如表所示：表 平均查找次数为 11一个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度 12当线性表的元素总数基
4、本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。【答案】顺序【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。 中每个元素的概率相等，则进行折半查找时的平均查找长度为_二、选择题13下列关于UDP 协议的叙述中，正确的是（ ）I 提供无连接服务 II 提供复用/分用服务第 3 页，共 51 页 III 通过差错校验，保障可靠数据传输 A. 仅I B. 仅 I 、II C. 仅 II 、III D.I 、II
5、、III 【答案】B【解析】UDP 无连接创建，提供多路复用服务。虽然有差错检验，但是不能保证可靠数据传输，所以III 错误。 14ARP 协议的功能是（ ）。A. 根据IP 地址查询MAC 地址 B. 根据MAC 地址查询IP 地址 C. 根据域名查询IP 也址 D. 根据IP 地址查询域名 【答案】A 。【解析】ARP 协议是网络层协议，因此只能和传输层和数据链路层有关系，从这一点出发，域名是应用层的范畴，选项C 和D 是不正确的，根据MAC 地址查询IP 地址是RARP 协议的功能，因此进而得出正确答案是A 。 15棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有（ ）个结点。A.2hB.C.D. 【答案】B 【解析】此树满足哈夫曼树，除根节点外每层有两个节点。16内部异常（内中断）可分为故障（fault ）、陷讲（trap ）和终止（abort ）三类。下列有关内部异常的叙述中，错误的（ ）。A. 内部异常的产生与当前执行指令相关 B. 内部异常的检测由CPU 内部逻辑实现 C. 内部异常的响应发生在指令执行过程中D. 内部异常处理后返回到发生异常的指令继续执行 【答案】D【解析】内中断分为：由软中断指令启动的中断；在一定条件下由CPU 自身启动的中断。D 项错误，如突然掉电引发的内中断经处理后不会继续执行。 第 4 页，共 51 页一、填空题考研试题
