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

admin2010-05-13 79

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

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

答案4

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

互联网借助TCP／IP协议把许多同构或异构的计算机网络互相连接起来，实现了遍布全球的计算机的互连、互通和互操作，其中的IP协议起着关键性的作用。下面有关IP协议的叙述中，错误的是()。
在μC／OS-Ⅱ中，OSSched()函数是任务调度的前导函数，用于判断进行任务调度的条件是否满足。下列满足条件的变量值为()。
按照软硬件技术的复杂程度嵌入式系统分为低端系统、中端系统和高端系统三大类，下面有关低端系统的叙述中错误的是()。
嵌入式系统的存储器以半导体存储器为主。随着技术的不断发展，新型存储器不断出现，主要包括FRAM和MRAM，分别称为【59】存储器和【60】存储器。
对于嵌入式Linux而言，Bootloader完成的工作步骤不包括如下()项。
ARM中某部件能把系统中不同类型的存储器进行统一管理，通过地址映射需要运行在连续地址空间的软件可运行在不连续的物理存储器中，需要较大存储空间的软件可以在较小容量的物理存储器中运行，这就是所谓的【49】存储器技术，完成这一功能的部件用英文缩写为【50】。
关于ARM处理器的工作模式，以下说法错误的是()。
设R1中为一正整数，将其数值的一半存入R2的ARM指令正确的是()。
下面是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中的组成部分A是【41】接口；组成部分B是【42】接口。
设根结点的层次为0，则高度为k的二叉树的最大结点数为

随机试题

许多道教宫观以“太清宫”、“上清宫”命名，“太清”、“上清”分别指的是()。
A、右锁骨中线叩诊由清变浊B、左腋中线叩诊由清变浊C、右锁骨中线叩诊由浊变实D、右锁骨中线叩诊由鼓变浊E、右锁骨中线叩诊浊音消失肝上界（）
Thecombinedsalesofthe100largestforeigninvestingcompaniesintheU.S.increasedbya40%inthetwoyearsbetween1977
房地产价格在短期内通常有上下波动,易看出其变动规律和发展趋势。()
具有黏度低、抗渗性强、稳定性和耐久性好、低毒性等特性的浆液是()
甲、乙、丙三个单位拟组成联合体参加某泵站土建标投标，并授权甲单位作为该联合体的牵头人，并以牵头人的名义向招标代理机构提交投标保证金，那么该投标保证金对()有约束力。
假设2008年某公司的总利润为734．23万美元，2009年为947．93万美元，请问如果保持相同的增长率，预计2010年该公司的总利润应该为()万美元。
某公司分为6个部门，其中最大的部门有29台计算机，现申请了一个C类IP地址，要求每个部门在一个子网内，采用子网划分的方式来实现，则子网掩码应设为________。
Ididn’tgototheparty,butIdowishI______there.
WhatdidscientistslearnabouttheTrocto?

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

互联网借助TCP／IP协议把许多同构或异构的计算机网络互相连接起来，实现了遍布全球的计算机的互连、互通和互操作，其中的IP协议起着关键性的作用。下面有关IP协议的叙述中，错误的是()。

在μC／OS-Ⅱ中，OSSched()函数是任务调度的前导函数，用于判断进行任务调度的条件是否满足。下列满足条件的变量值为()。

按照软硬件技术的复杂程度嵌入式系统分为低端系统、中端系统和高端系统三大类，下面有关低端系统的叙述中错误的是()。

嵌入式系统的存储器以半导体存储器为主。随着技术的不断发展，新型存储器不断出现，主要包括FRAM和MRAM，分别称为【59】存储器和【60】存储器。

对于嵌入式Linux而言，Bootloader完成的工作步骤不包括如下()项。

关于ARM处理器的工作模式，以下说法错误的是()。

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

下面是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中的组成部分A是【41】接口；组成部分B是【42】接口。

设根结点的层次为0，则高度为k的二叉树的最大结点数为

许多道教宫观以“太清宫”、“上清宫”命名，“太清”、“上清”分别指的是()。

A、右锁骨中线叩诊由清变浊B、左腋中线叩诊由清变浊C、右锁骨中线叩诊由浊变实D、右锁骨中线叩诊由鼓变浊E、右锁骨中线叩诊浊音消失肝上界（）

Thecombinedsalesofthe100largestforeigninvestingcompaniesintheU.S.increasedbya40%inthetwoyearsbetween1977

房地产价格在短期内通常有上下波动,易看出其变动规律和发展趋势。()

具有黏度低、抗渗性强、稳定性和耐久性好、低毒性等特性的浆液是()

甲、乙、丙三个单位拟组成联合体参加某泵站土建标投标，并授权甲单位作为该联合体的牵头人，并以牵头人的名义向招标代理机构提交投标保证金，那么该投标保证金对()有约束力。

假设2008年某公司的总利润为734．23万美元，2009年为947．93万美元，请问如果保持相同的增长率，预计2010年该公司的总利润应该为()万美元。

某公司分为6个部门，其中最大的部门有29台计算机，现申请了一个C类IP地址，要求每个部门在一个子网内，采用子网划分的方式来实现，则子网掩码应设为________。

Ididn’tgototheparty,butIdowishI______there.

WhatdidscientistslearnabouttheTrocto?