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

一、应用题

1． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。

【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O(n)；而在链式存储方式下，插入和删除时间复杂度都是O(1)。

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

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

3． 将关键字序列(7，8，30，11，18，9，14) 散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组. 散列函数是:H(key)＝(key×3)M0D7，处理冲突采用线性探测再散列法，要求装填(载）因子为.

(1)请画出所构造的散列表.

(2)分别计算等概率情况下查找成功和查找不成功的平均查找长度.

【答案】(1)

要求装填因子为

列函数值如下表:

采用线性探测法再散列法处理冲突，所构造的散列表为:

(2)查找成功时，在等概率情况下，查找表中每个元素的概率是相等的，因此是根据表中元素个数来计算平均查找长度，各关键字的比较次数如下表所示:

故查找成功的平均查找长度为(1+1+1+1+3+3+2)/7＝12/7.

在不成功的情况下，由于任意关键字key ，H(key)的值只能是0〜6之间，H(key)为0需要比较3次，H(key)为1需要比较2次，H(key)为2需要比较1次，H(key)为3需要比较2次，H(key)为4需要比较1次，H(key)为5需要比较5次，H(key)为6需要比较4次，共7种情况，如下表

，数组的长度应该为数组下标为0〜9. 各关键字的散

所示:

所以，在等概率下，查找失败的平均查找长度为:(3+2+1+2+1+5+4)/7＝18/7.

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

图 存储映像本意图

设str1和str2分别指向两个单词所在单链表的头结点, 链表结点结构为

所在结点的位置p) 。要求:

(1)给出算法的基本设计思想。

(2)根据设计思想, 采用C 或或JA V A 语言描述算法, 关键之处给出注释。

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

【答案】(1)算法的基本设计思想:

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

②将两个链表以表尾对齐:令指针p 、q 分别指向str1和str2的头结点, 若m>n, 则使p 指向链表中的第n+1个结点; 若m

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

(2)用C 语言算法描述如下:

n 分别为两个链表的长度。 。其中m 、, 请设计一个时间上尽可能高效的算法, 找出由str1和str2所指的两个链表共同后缀的起始位置(如图中字符i (3)参考答案的时间复杂度为:

或

5． 证明:置换选择排序法产生的初始归并段的长度至少为m(m是所用缓冲区的长度) 。

【答案】由置换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时(即初始归并段) ，缓冲区中m 个元素中除最小元素之外，其他m －1个元素均大于第一个选出的元素，即当以后读入元素均小于输出元素时，初始归并段中也至少能有原有的m 个元素。

6． 如果两个串含有相等的字符，能否说它们相等？

【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同(即两串串值相等) 。

7． 系统中有多个生产者进程和消费者进程, 共享用一个可以存1000个产品的缓冲区(初始为空) , 当缓冲区为未满时, 生产者进程可以放入一件其生产的产品, 否则等待; 当缓冲区为未空时, 消费者进程可以取走一件产品, 否则等待。要求一个消费者进程从缓冲区连续取出10件产品后, 其他消费者进程才可以取产品, 请用信号量P , V(wait, signed) 操作实现进程间的互斥和同步, 要求写出完整的过程; 并指出所用信号量的含义和初值

【答案】设置5个信号量

empty :表示缓冲区是否为空, 初值为1000

full :表示缓冲区是否为满, 初值为0

mutex1:生产者之间的互斥信号, 初值为1

mutex2:消费者之间的互斥信号, 初值为1

available :当前消费者能否访问缓冲区, 初值为1

定义变量in , out 分别为生产者和消费者进程所要使用的指针, 指向下一个可用的缓冲区单元, MaxNum=1000为缓冲区的大小, count 标志当前消费者已经取的产品的数量, 初值为0

生产者进程:

生产一个产品;

产品送入buffer(in);

消费者进程