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

一、应用题

1． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m , 模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式

给出它的next 函数值及next 函数的修正值nextval 之值。

【答案】KMP 算法的时间复杂性是

01102201320。

2． 一个长度为p 的next 和nextval 值分别为01112212321和请的升序序列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）说明算法的复杂性：算法的时间复杂度、空间复杂度分别是

3． 假定在一个8位字长的计算机中运行下列C 程序段：

若编译器编译时将8个8位寄存器R1〜R8分别分配给变量

回答下列问题。（提示：带符号整数用补码表示）

（1）执行上述程序段后，寄存器Rl 、R5和R6的内容分别是什么？（用十六进制表示） （2）执行上述程序段后，变量m 和kl 的值分别是多少？（用十进制表示）

（3）上述程序段涉及带符号整数加/减、无符号整数加/减运算，这四种运算能否利用同一个加法器及辅助电路实现? 简述理由。

（4）计算机内部如何判断带符号整数加/减运算的结果是否发生溢出? 上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？

【答案】（1）无符号整数运算，（Rl ） =x=134=10000110B=86H、（R5）

请

=x-y=246=10010000B=90H、（R6）=x+y=01111100B=7CH。

（2） m 的机器数与x 的机器数相同为86H=1000 0110B，解释为带符号整数（用补码表示）时，其值为-111 1010B= -112; 同理kl=（m-n ）=（x-y ）=90H=1001 0000B，解释为带符号整数（用补码表示）时，其值为-111 1010B=-112；

（3）四种运算可以利用同一个加法器及辅助电路实现，n 位加法器实现的是模2n 无符号整数加法运算。对于无符号整数a 和b , a+b可以直接用加法器实现，而实现；对于带符号整数用补码表示，补码加减运算公式为

：

，所以四种运算都可在n 位加法器

中实现。

（4）判断溢出的方法有3种：一位符号位、进位位和双符号位。上述程序段中只有

语句会发 生溢出，因为2个带符号整数均为负数，它们相加之后，结果小于8位二进制所能表示的最小负数。

4． 请回答下列关于图（Graph ）的一些问题：

（1）有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？

（2）表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？

（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？

【答案】⑴最多有n （n-l ）条边；最少有n 条边。

（2） 有有个矩阵元素；不一定是稀疏矩阵（稀疏矩阵的定义是非零元素个数远小于该矩阵元素个数，且分 布无规律）。

（3）使用深度优先遍历，按退出DFS 过程的先后顺序记录下的顶点是逆向拓扑有序序列。如果在执行DFS （V ） 未退出前，出现顶点u 到v 的回边，则说明存在包含顶点v 和顶点u 的环。

5． 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：

①该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点； ②选择离最近且尚未在最短路径中的顶点V ，加入到最短路径中，修改当前顶点

请证明之；否则请举例说明。

【答案】题目中方法不一定能（或不能）求得最短路径。举例说明：

图（a ）

③重复步骤②，直到是目标顶点时为止。请问上述方法能否求得最短路径? 若该方法可行，