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

一、应用题

1． 外排序中为何采用k 一路么？

【答案】外排序用路归并

是因为k 越小，归并趟数越多，读写外存次数越多，时间效

率越低，故一般应大于最少的2-路归并。若将k-路归并的败者树思想单纯用于内排序，因其由胜者树改进而来，且辅助空间大，完全可由堆排序取代，故将其用于内排序效率并不高。

2． 组织待检索文件的倒排表的优点是什么？

【答案】倒排表作为索引的优点是索引记录快，因为从次关键字值直接找到各相关记录的物理记录号，倒排因此而得名（因通常的查询是从关键字查到记录）。在插入和删除记录时，倒排表随之修改，倒排表中具有相同次关键字的记录号是有序的。

3． 在某程序中，有两个栈共享一个一维数组空间的栈底。

（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2, 试分别写出栈满、栈空的条件。 【答案】（1）入栈主要语句

出栈主要语句

合并而不用2—路合并? 这种技术用于内排序有意义吗? 为什

分别是两个栈

（2）

4． 画出对算术表达式表所示。

表 操作数栈和运算符找的变化过程

求值时操作数栈和运算符栈的变化过程。

求值，过程如

【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式

5． 设目标为

模式为

（1）计算模式p 的nextval 函数值；

（2）不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。 【答案】（1）P 的nextval 函数值为0110132（P 的next 函数值为0111232）。 （2）利用KMP （改进的nextval ）算法，每趟匹配过程如下： 第一趟匹配：abcab （i=5, j=5） 第二趟匹配：abc （i=7，j=3） 第三趟匹配：a （i=7，j=l） 第四趟匹配：

（成功）abcabaa （i=15，j=8）

6． 线性表有两种存储结构：一是顺序表，二是链表。试问：

（1）如果有，2个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构? 为什么？

（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中

的元素，那么应采用哪种存储结构? 为什么？

【答案】（1）应选择链式存储结构。因为它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O （1）。

（2）应选择顺序存储结构。因为顺序表可以随机存取，时间复杂度为O （1）。

7． 设散列表为数分别为

：

注：％是求余数运算中，函数码序列为

（2）计算搜索成功的平均搜索长度

表示颠倒十进制数x 的各位，如

即表的大小为

其

等。若插入的关键

，现采用双散列法解决冲突。散列函数和再哈希函

（1）试画出插入这8个关键码后的哈希表；

【答案】（1）插入这8个关键码后的哈希表如表所示：

表 插入关键字后的哈希表

（2）

8． 某计算机的CPU 主频为500MHz ，CPI 为5（即执行每条指令平均需要5个时钟周期）。假定某外设的数据传输率为0.5MB/S，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。

（1）在中断方式下，CPU 用于该外设I/O的时间占整个CPU 时间的百分比是多少？ （2）当该外设的数据传输率达到5MB/s时，改用DMA 方式传送数据。假定每次DMA 传送块大小为5000B , 且DMA 预处理和后处理的总开销为500个时钟周期，则CPU 用于该外设I/0时间占整个CTU 时间的百分比是多少？（假设DMA 与CPU 之间没有访存冲突）

【答案】（1）已知主频为500MHz ，则时钟周期=l÷500MHz=2ns，因为CPI=5, 所以每条指令，数据传输率为0.5MB/S, 所以传送时间平均5×2=10ns。又已知每中断一次传送32位（4个字节）=4÷0.5MB/s=

CPU 用于该外设I/0共需20条指令（中断服务程序包括18条指令+其他开销折

，花费时间=20×l0=200ns。CPU 用于该外设I/0的时间占整个CPU 时间的百分比合2条指令）

=200/8000×100%=0.025×100%=2.5%。

（2）改用DMA 方式传送数据，数据传输率为5MB/S，传送5000B 的时间=5000B÷5MB/s=lms。预处理和后处理的总开销时间=500×2ns=

CPU 用于该外设I/0时间占整个CPU 时间的百分比=

预处理和后处理的总开销时间÷传送数据的时间=l/1000×l00%=0.001×100%=0.1%。