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

一、应用题

1． 设哈希（Hash ）表的地址范围为0～17，哈希函数为：

造出哈希表，试回答下列问题：

（1）画出哈希表示意图；

（2）若查找关键字63，需要依次与哪些关键字比较？

（3）若查找关键字60，需要依次与哪些关键字比较？

（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

【答案】（1）哈希表示意图如表所示：

表 哈希示意图

（2）查找关键字63时，由于

63比较。

（3）查找关键字60时，由于

（4） 哈希地址12内为空，查找失败。 所以需要依次与31，46，47，32，17，为关键字，用线性探测再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）

2． 文件存储结构的基本形式有哪些? 一个文件采用何种存储结构应考虑哪些因素？

【答案】文件的基本组织方式有顺序组织、索引组织、散列组织和链组织，常用的结构有顺序结构、索引结构、散列结构。

（1）顺序结构，相应文件为顺序文件，其记录按存入文件的先后次序顺序存放。顺序文传本质上就是顺序表。若逻辑上相邻的两个记录在存储位置上相邻，则为连续文件；若记录之间以指针相链接，则称为串联文件。顺序文件只能顺序存取，要更新某个记录，必须复制整个文件。顺序文件连续存取的速度快，主要适用于顺序存取，批量修改的情况。

（2）带索引的结构，相应文件为索引文件。索引文件包括索引表和数据表，索引表中的索引项包括数据表中数据的关键字和相应地址，索引表有序，其物理顺序体现了文件的逻辑次序，实现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能随机存取。

（3）散列结构，也称计算寻址结构，相应文件称为散列文件，其记录是根据关键字值经哈希函数计算确定其地址，存取速度快，不需索引，节省存储空间。不能顺序存取，只能随机存取。

文件采用何种存储结构应综合考虑各种因素，如：存储介质类型、记录的类型、大小和关键

字的数目以及对文件作何种操作。

3． 若森林共有n 个结点和b 条边（b

【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。

4． 假定有下列，矩阵（n 为奇数）

如果用一维数组B 按行主次序存储A 的非零元素，问：

（1）A 中非零元素的行下标与列下标的关系；

（2）给出A 中非零元素的下标

位在B 中的位置公式。

【答案】（1）主对角线上元素的坐标是i=j，副对角线上元素的坐标i 和j 有

所以A 中非零元素的行下标和列下标的关系是或 的关系，与B 中的下标R 的关系； 给出利用的下标定（3）假定矩阵中每个元素占一个存储单元且B 的起始地址为（2）非零元素分布在两条主、副对角线上，除对角线相交处一个元素（下称“中心元素”）外，其余每行都有两个元素。主对角线上的元素，在向量B 中存储的下标

是

副对角线上的元素，在中心元素前，在向量B

中存储的下标是

在中心元素后，其下标如下：

（3）在B 中的位置如下：

5． 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

（1）画出描述折半查找过程的判定树；

（2）若查找元素54，需依次与哪些元素比较？

（3）若查找元素90，需依次与哪些元素比较？

（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。

【答案】（1）判定树如图所示：

图 判定树

（2）若查找元素54，需依次和元素30、63、42、54比较，查找成功。

（3）若查找元素90，需依次和元素30、63、87、95比较，查找失败。

（4）

6． 三维数组

的存储首地址。

【答案】数组占的存储字节

数

的存储地

址 的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间? 如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素

7． 某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB , 主存（物理）地址空间大小为1MB , 页面大小为4KB ; Cache 采用直接映射方式，共8行；主存与Cache 之间交换的块大小为32B ，系 统运行到某一时刻时，页表的部分内容和Cache 的部分内容分别如题a 图、题b 所示：图中页框号及标记字段的内容为十六进制形式。

图

a

图b

请回答下列问题。

（1）虚拟地址共有几位，哪几位表示虚页号? 物理地址共有几位，哪几位表示页框号（物理