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

一、填空题

1． 设有个结点的完全二叉树顺序存放在向量

【答案】

中，其下标值最大的分支结点为_____。

【解析】最大的分支结点是最后一个叶子结点的父结点。

2． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。

【答案】稳定

3． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。

【答案】

【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：

根据上述公式起始地址就为488。

4． 一个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】

完全二叉树的高度

5． 栈是_____的线性表，其运算遵循_____的原则。

；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）

6． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。

【答案】m/2

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。

7． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。

【答案】关键字；记录号；记录号；顺序；直接

8． VSAM 系统是由_____、_____、_____构成的。

【答案】索引集；顺序集；数据集

9． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；

首

先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。

【答案】

10．完善算法：求KMP 算法.next 数组。

END ； 【答案】

11．对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。

【答案】集合；线性结构；树形结构；图状结构（网状结构）

12．索引顺序文件既可以顺序存取，也可以_____存取。

【答案】随机

二、选择题

13．假定用若干个2Kx4位的芯片组成一个8Kx8位的存储器，则地址0B1FH 所在芯片的最小地址是（ ）。

A.0000H B.0600H C.0700H D.0800H 【答案】D

【解析】由若干芯片构成存储器，采用字和位同时扩展方法。8片2Kx4位的芯片分成4组，每组2个芯片，各组芯片的地址分配分别为：第1组，0000H 〜07FFH ; 第2组，0800H 〜0FFFH ; 第3组，1000H 〜17FFH ; 第4组，1800H 〜1FFFH 。地址0BIFH 处于第2组内，其芯片的最小地址为0800H 。

14．如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（ ）。

A.1条，1条 B.1条，多条 C. 多条，1条 D. 多条，多条 【答案】A

【解析】所谓递归查询方式就是：如果主机所询问的本地域名服务器不知道被查询域名的IP 地址，那么本地域名服务器就以DNS 客户的身份向其他服务器继续发出查询请求报文，而不是让该主机自行下一步的查询。所以主机只需向本地域名服务器发送一条域名请求，采用递归查询方法，本地域名服务器也只需向上一级的根域名服务器发送一条域名请求，然后依次递归。正确选项为A 。

15．已知字符串S 为“abaabaabacacaabaabcc ”，模式串t 为“abaabc ”，采用KMP 算法进行匹配，第一次出现“失配” （

A.i=l，j=0 B.i=5，j=0 C.i=5，j=2 D.i=6，j=2

【答案】C

【解析】模式匹配（KMP ）算法对普通的暴力匹配的改进在于：每当匹配过程中匹配失败时，主串（本题为S ）的指针（i ）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t ）向右“滑动”尽可能远的一段距离后，继续进行比较。模式串“滑动”的距离是由模式串（t ）本身决定的，即t 的子串

中前缀串和后缀串相等的最长长度。本题中第一次失配i=5, 字串为

，i=j = 5，则下次开始匹配时，i 和j 的值分别是（ ））。