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

admin2010-05-13 56

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

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

答案4

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

衡量实时操作系统性能的一个重要指标是从接收到可屏蔽中断请求信号到操作系统作出响应并转入中断服务程序所需要的最长时间，称为___________【61】时间。该时间包括两部分：一是___________【62】时间，是指系统因执行临界区代码等原因不允许响应中
数字音频的比特率(码率)指的是每秒钟的数据量，它与取样频率、量化位数、声道数目、使用的压缩编码方法等密切相关。假设数字音频的比特率为8kB／s，其取样频率是8kHz，单声道，未压缩，那么它的量化位数是()。
iOS的系统架构分为四个层次，从底层到高层依次是：核心操作系统层、核心服务层、媒体层和【69】层。所有iOS应用程序都由面向对象的程序设计语言【70】驱动。
在嵌入式系统（如数码相机）中，获取数字图像的过程大体分为四步，如下图所示，其中前3个步骤分别是()。
构建无线局域网的技术除了采用802．11(Wi－Fi)之外，另一种常用的是【45】_______技术，它是一种短距离、低速率、低成本的无线通信技术，其最高数据传输速率为1Mbps左右，传输距离大约在【46】_______m之内。
在μC／OS－Ⅱ操作系统下，处于运行态的任务不可能直接转入的状态是()。
下图是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中CPU中的组成部分A是【41】_______；组成部分B是【42】_______。
嵌入式Linux操作系统由用户进程、OS服务组件和Linux内核3个部分组成(如图)，下面选项中正确的是()。
设R1中为一正整数，将其数值的一半存入R2的ARM指令正确的是()。
汉字有多种不同的编码标准，下面关于不同编码标准之间关系的叙述中，错误的是()。

随机试题

《古诗十九首》
引起产后出血的原因哪种最多见
民法上的非票据关系包括()。
某点的绝对高程（海拔）是该点到（）的铅垂距离。
现行宪法规定，我国社会主义经济制度的基础是()。
计算机病毒是一种()。
给定纸盒的外表面，不能由它折叠而成的是：
该市职工工资最低的是()。从1975～2005年间，该市最高工资与最低工资的差距是()。
"Brand"isageneraltermwhichcoversnarrowertermssuchas"brandname","brandmark",and"trademark."Abrandnameisinte
A、Theroomisonfire.B、Themanisbotheredbythesmoke.C、Thereislittleair.D、Themanisnotpermittedintheroom.B逻辑推理题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

数字音频的比特率(码率)指的是每秒钟的数据量，它与取样频率、量化位数、声道数目、使用的压缩编码方法等密切相关。假设数字音频的比特率为8kB／s，其取样频率是8kHz，单声道，未压缩，那么它的量化位数是()。

iOS的系统架构分为四个层次，从底层到高层依次是：核心操作系统层、核心服务层、媒体层和【69】层。所有iOS应用程序都由面向对象的程序设计语言【70】驱动。

在嵌入式系统（如数码相机）中，获取数字图像的过程大体分为四步，如下图所示，其中前3个步骤分别是()。

构建无线局域网的技术除了采用802．11(Wi－Fi)之外，另一种常用的是【45】_技术，它是一种短距离、低速率、低成本的无线通信技术，其最高数据传输速率为1Mbps左右，传输距离大约在【46】_m之内。

在μC／OS－Ⅱ操作系统下，处于运行态的任务不可能直接转入的状态是()。

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

嵌入式Linux操作系统由用户进程、OS服务组件和Linux内核3个部分组成(如图)，下面选项中正确的是()。

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

汉字有多种不同的编码标准，下面关于不同编码标准之间关系的叙述中，错误的是()。

《古诗十九首》

引起产后出血的原因哪种最多见

民法上的非票据关系包括()。

某点的绝对高程（海拔）是该点到（）的铅垂距离。

现行宪法规定，我国社会主义经济制度的基础是()。

计算机病毒是一种()。

给定纸盒的外表面，不能由它折叠而成的是：

该市职工工资最低的是()。从1975～2005年间，该市最高工资与最低工资的差距是()。

"Brand"isageneraltermwhichcoversnarrowertermssuchas"brandname","brandmark",and"trademark."Abrandnameisinte

A、Theroomisonfire.B、Themanisbotheredbythesmoke.C、Thereislittleair.D、Themanisnotpermittedintheroom.B逻辑推理题

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

三级数据库技术

NCRE全国计算机三级

数字音频的比特率(码率)指的是每秒钟的数据量，它与取样频率、量化位数、声道数目、使用的压缩编码方法等密切相关。假设数字音频的比特率为8kB／s，其取样频率是8kHz，单声道，未压缩，那么它的量化位数是()。

iOS的系统架构分为四个层次，从底层到高层依次是：核心操作系统层、核心服务层、媒体层和【69】层。所有iOS应用程序都由面向对象的程序设计语言【70】驱动。

在嵌入式系统（如数码相机）中，获取数字图像的过程大体分为四步，如下图所示，其中前3个步骤分别是()。

构建无线局域网的技术除了采用802．11(Wi－Fi)之外，另一种常用的是【45】_______技术，它是一种短距离、低速率、低成本的无线通信技术，其最高数据传输速率为1Mbps左右，传输距离大约在【46】_______m之内。

在μC／OS－Ⅱ操作系统下，处于运行态的任务不可能直接转入的状态是()。

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

嵌入式Linux操作系统由用户进程、OS服务组件和Linux内核3个部分组成(如图)，下面选项中正确的是()。

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

汉字有多种不同的编码标准，下面关于不同编码标准之间关系的叙述中，错误的是()。

《古诗十九首》

引起产后出血的原因哪种最多见

民法上的非票据关系包括()。

某点的绝对高程（海拔）是该点到（）的铅垂距离。

现行宪法规定，我国社会主义经济制度的基础是()。

计算机病毒是一种()。

给定纸盒的外表面，不能由它折叠而成的是：

该市职工工资最低的是()。从1975～2005年间，该市最高工资与最低工资的差距是()。

"Brand"isageneraltermwhichcoversnarrowertermssuchas"brandname","brandmark",and"trademark."Abrandnameisinte

A、Theroomisonfire.B、Themanisbotheredbythesmoke.C、Thereislittleair.D、Themanisnotpermittedintheroom.B逻辑推理题

构建无线局域网的技术除了采用802．11(Wi－Fi)之外，另一种常用的是【45】_技术，它是一种短距离、低速率、低成本的无线通信技术，其最高数据传输速率为1Mbps左右，传输距离大约在【46】_m之内。

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