若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是( )。

admin2010-05-13 43

问题若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是( )。

选项 A、O(1)
B、O(n)
C、O(n²)
D、0(n3)

答案4

解析在主串中可能存在多个模式串“部分匹配”的子串，因而引起数次回溯，若除了最后一次匹配，其他比较每次都需要回溯，则循环次数的数量级为n²。

转载请注明原文地址:https://kaotiyun.com/show/USSZ777K

本试题收录于：三级数据库技术题库NCRE全国计算机三级分类

三级数据库技术

NCRE全国计算机三级

相关试题推荐

下图为基于ARM处理器的嵌入式系统的键盘接口。下面关于该键盘接口的叙述中，错误的是()。
下面与AMBA（AdvancedMicrocontrollerBusArchitecture）有关的叙述中，错误的是()。
以下关于嵌入式系统软件与通用计算机系统软件的异同的陈述中，错误的是()。
相对于其它处理器，ARM处理器主要技术特征，以下说法错误的是()。
数字图像的像素深度指每个像素用多少个二进位来表示。它决定了图像中可能出现的不同颜色（或不同亮度）的最大数目。像素深度是8位的灰度图像，其不同的亮度等级总数为【43】种。最多可以有大约1600万种颜色的图像称为真彩色图像，真彩色图像的像素深度为【44】位。
数据库管理系统、图形用户界面、互联网浏览器、媒体播放器等软件，如果运行在嵌入式系统上，往往具有内部结构精简，【69】轻量化，占用存储资源【70】的特点。
设R1中为一正整数，将其数值的一半存入R2的ARM指令正确的是()。
设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为
信息认证是信息安全的一个重要方面，下列有关信息安全认证技术的描述正确的是________。Ⅰ．数字签名技术Ⅱ．身份识别技术Ⅲ．信息加密技术Ⅳ．信息的完整性验证技术
下列（）不属于数字签名算法应该满足的条件。

随机试题

4C中除了客户、成本、方便，还有()
胫前胫后肌麻痹腓总神经麻痹
A．病理性的混合性呼吸音B．湿啰音C．拍水音D．捻发音E．胸膜摩擦音气胸并发渗出性胸膜炎
中医药技术专长继承人应具备的条件是
刘稳与刘永系父子关系，刘稳在农村，年老多病，刘永外出做生意，收入颇丰，遂在县城买房定居，但刘永长期不给其父赡养费导致刘稳生活困难。2002年，刘稳就此诉至人民法院，人民法院判决刘永每月给付刘稳生活费1000元，刘稳、刘永均服判。到20(18年，刘稳因身体不
某扩建工程的边柱紧邻既有地下结构，抗震设防烈度8度，设计基本地震加速度值为0．3g，设计地震分组第一组，基础采用直径800mm泥浆护壁旋挖成孔灌注桩，图12—14(Z)为某边柱等边三桩承台基础图，柱截面尺寸为500mm×1000mm，基础及其以上土体的加权
某项工作最迟开始时间为第9天，最早完成时间为第8天，持续时问为2天，在不影响总工期前提下，该项工作可以利用的机动时间为()天。
某公司是一家从事特种牛肉进口与销售的公司，公司员工都是这几年毕业的学国际贸易和外语专业的大学生。该公司近来发现国内客户的要求越来越多，也越来越细，如果不了解这些客户的生产运营过程，不熟悉国家关于肉类食品生产加工的具体规定，就无法满足客户的需要。现有员工的人
市场中介组织在为市场主体及其交易活动提供服务的同时，还()。
Naturally,inagroupofanimalsasdiverseasthesnakes,andwithsomanyvariedenemies,therearenumerousdefensivereactio

最新回复(0)

若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是( )。

三级数据库技术

NCRE全国计算机三级

下图为基于ARM处理器的嵌入式系统的键盘接口。下面关于该键盘接口的叙述中，错误的是()。

下面与AMBA（AdvancedMicrocontrollerBusArchitecture）有关的叙述中，错误的是()。

以下关于嵌入式系统软件与通用计算机系统软件的异同的陈述中，错误的是()。

相对于其它处理器，ARM处理器主要技术特征，以下说法错误的是()。

数据库管理系统、图形用户界面、互联网浏览器、媒体播放器等软件，如果运行在嵌入式系统上，往往具有内部结构精简，【69】轻量化，占用存储资源【70】的特点。

设R1中为一正整数，将其数值的一半存入R2的ARM指令正确的是()。

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为

信息认证是信息安全的一个重要方面，下列有关信息安全认证技术的描述正确的是________。Ⅰ．数字签名技术Ⅱ．身份识别技术Ⅲ．信息加密技术Ⅳ．信息的完整性验证技术

下列（）不属于数字签名算法应该满足的条件。

4C中除了客户、成本、方便，还有()

胫前胫后肌麻痹腓总神经麻痹

A．病理性的混合性呼吸音B．湿啰音C．拍水音D．捻发音E．胸膜摩擦音气胸并发渗出性胸膜炎

中医药技术专长继承人应具备的条件是

某项工作最迟开始时间为第9天，最早完成时间为第8天，持续时问为2天，在不影响总工期前提下，该项工作可以利用的机动时间为()天。

市场中介组织在为市场主体及其交易活动提供服务的同时，还()。

Naturally,inagroupofanimalsasdiverseasthesnakes,andwithsomanyvariedenemies,therearenumerousdefensivereactio