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

一、应用题

1． 画出对算术表达式

表所示。

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

求值时操作数栈和运算符栈的变化过程。 求值，过程如【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式

2． 给出模式串在KMP 算法中的next 和nextval 数组。

【答案】模式串的next 函数定义如下：

根据此定义，

可求解模式串的next 和nextval 值如下：

3． 一个长度为的升序序列S , 处在第「L/2」个位置的数为S 的中位数。例如，若序列Sl= （11，13, 15, 17，19），则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2= （2, 4, 6, 8, 20）, 则S1和S2的中位数是11。现有两个等长升序序列A 和B ，试设计一个时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。要求：

（1）给出算法的基本设计思想。

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

（3）说明你所设计算法的时间复杂度和空间复杂度。

【答案】（1）算法的基本设计思想：分别求两个升序序列A 和B 的中位数，设为a 和b 。 ① 若a=b，则a 或b 即为所求的中位数。

② 否则，若a

所在序列B 的较大一半。若a>b，中位数只能出现（b ，a ）范围内，舍弃b 所在序列B 的较小一半，同时舍弃a 所在序列A 的较大一半。

③在保留的两个升序序列中求出新的中位数a 和b ，重复上述过程，直到两个序列中只含一个元素时为止，则较小者即为所求的中位数。

（2）用C 语言算法描述如下：

//分别考虑奇数和偶数，保持两个子数组元素个数相等

//若元素个数为奇数个

//舍弃A 中间点以前部分且保留中间点

//舍弃B 中间点以后部分且保留中间点

}

//若元素个数为偶数个

//舍弃A 中间点及中间点以前部分

//舍弃B 中间点以后部分且保留中间点

//若元素个数为奇数个

//舍弃A 中间点以后部分且保留中间点

//舍弃B 中间点以前部分且保留中间点

//若元素个数为偶数个

//舍弃A 中间点以后部分且保留中间点

//舍弃B 中间点及中间点以前的部分

（3）说明算法的复杂性：算法的时间复杂度、空间复杂度分别是

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

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

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）