求解两个长度为n的序列X和Y的一个最长公共子序列（如序列ABCBDAB和BDCABA的一个最长公..

2017年下半年上午试卷综合知识

第 5 题


关键词	时间复杂度
章/节	嵌入式系统程序设计

求解两个长度为n的序列X和Y的一个最长公共子序列（如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为（5)。经分析发现该问题具有最优子结构，可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为

，如下式所示。

A. O（n²）

B. O（n²1gn）

C. O（n³）

D. O（n2ⁿ）

相关试题嵌入式系统程序设计

第47题

2018年下半年

中断响应是一个软硬件结合处理系统例外事件的机制。中断发生时，操作系统通过检査（47)来判断中断原因。

第54题

2013年下半年

如果在一个单处理器的系统中有n个进程，则就绪队列中进程的个数最多为（54）。

第47题

2025年上半年

在进行DSP的软件设计时，可以用汇编语言或者C语言进行设计，最终是生成可执行文件，通过下载线缆下载到DSP上运行、调试。下列对DSP软件的开发、编译、调试过程描..

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5