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

一、应用题

1． 证明:具有n 个顶点和多于n －1条边的无向连通图G —定不是树。

【答案】证明:具有n 个顶点n －1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n －1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树。

2． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？

【答案】(1)动态存储分配伙伴系统的基本思想

在伙伴系统中，无论占用块或空闲块，其大小均为(k为大于等于0的正整数) 。若内存容量为，则空闲块大小只能是。由同一大块分裂而得的两个小块互称“伙伴空间”，

(

若)

或109如内存大小为2的块分裂成两个大小为2的块。只有两个“伙伴空间”才能合并成一个大空间。起始地址为P ，

大小为的内存块，其伙伴的起始地址为

:

(若

(2)和边界标识法的不同 ) 。

边界标识法在每块的首尾均有“占用”/ “空闲”标志，空闲块合并方便。伙伴系统算法简单、速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。

3． 设a ，b ，c ，d ，e 五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现:ac ，Bd ，aa ，be ，ab ，ad ，cd ，be ，ae ，ce 。要求用哈希(Hash)方法将它们存入具有10个位置的表中。

(1)将上述关键字(标识符) 构造一个哈希函数，使得发生冲突尽可能地少；

(2)线性探测再散列法解决冲突。写出上述各关键字在表中位置。

【答案】(1)构造的哈希函数为:哈希函数H(key)=(关键字各字符编码之和)MOD7。

(2)关键字在表中的位置如表所示:

表 关键字在表中的位置

4． 某博物馆最多可容纳500人同时参观, 有一个出入口, 该出入口一次仅允许个通过。参观者的活动描述如下:

Cobegin

参观者进程i :

{

进门;

参观;

出门;

}

coend

请添加必要的信号量和P 、V(或wait （ ）、signal （ ）) 操作, 以实现上述操作过程中的互斥与同步。要求写出完整的过程, 说明信号量含义并赋初值。

【答案】定义两个信号量

博物馆可以容纳的最多人数

用于出入口资源的控制

5． 三个进程PI 、P2, P3互斥使用一个包含N(N＞0) 个单元的缓冲区。P1每次用produce （ ）生成一个正整数并用put （ ）送入缓冲区某一空单元中; P2每次用getodd （ ）从该缓冲区中取出一个奇数并用countodd （ ）统计奇数个数；P3每次用geteven （ ）从该缓冲区中取出一个偶数并用counteven （ ）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

【答案】定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty 控制生产者与消费者之间的同步；mutex 控制进程间互斥使用缓冲区，程序如下:

（ ）

//并发进程

//生产者进程

//等待调度,

//生产者生产数

. //有无空何'

//能否进人缓冲区

//放置数字

//释放缓冲区

//是否偶数

//偶数信号量加

1

//否则奇数信号量加

1

//消费者进程

1

//有无奇数

//能否进入缓冲区

（ ） //取奇数

//释放缓冲区

//空间加

1

//计算奇数个数

•

//有无偶数

//能否进人缓冲区

//取偶数

//释放缓冲区

//空间加

1

（ ） //计算偶数个数

//并发结束

二、算法设计题

6． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。

【答案】算法如下:

//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个数，初始为

//p和q 分别是链表A 和B 的工作指针

//pre为A 中p 所指结点的前驱结点的指针