设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。

单项选择题设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。

A.O（m）
B.O（n）
C.O（m*n）
D.O（nlog₂m）

点击查看答案&解析

您可能感兴趣的试卷

你可能感兴趣的试题

1.单项选择题串与普通的线性表相比较，它的特殊性体现在（）。

A.顺序的存储结构
B.链式存储结构
C.数据元素是一个字符
D.数据元素任意

点击查看答案

2.单项选择题已知串S=’aaab’，则next数组值为（）。

A.0123
B.1123
C.1231
D.1211

点击查看答案

3.单项选择题设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（）。

A.连接
B.求子串
C.模式匹配
D.判断子串

点击查看答案

4.填空题对于一个栈，给出输入项A,B,C,D，如果输入项序列为A,B,C,D，试给出全部可能的输出序列。

参考答案：出栈的可能序列： ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BC...

点击查看完整答案

5.填空题已知Q是一个非空队列，S是一个空栈。编写算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q的所有元素逆置。栈的ADT函数有：voidmakeEmpty（SqStacks）；置空栈voidpush（SqStacks，ElemTypee）；元素e入栈ElemTypepop（SqStacks）；出栈，返回栈顶元素intisEmpty（SqStacks）；判断栈空队列的ADT函数有：voidenQueue（Queueq，ElemTypee）；元素e入队ElemTypedeQueue（Queueq）；出队，返回队头元素intisEmpty（Queueq）；判断队空

参考答案：void QueueInvent(Queue q) { ElemType x; makeEmpty(SqSt...

点击查看完整答案

6.填空题阅读算法f2，并回答下列问题：（1）设队列Q=（1，3，5，2，4，6）。写出执行算法f2后的队列Q；（2）简述算法f2的功能。voidf2（Queue*Q）{DataTypee；if（!QueueEmpty（Q））{e=DeQueue（Q）；f2（Q）；EnQueue（Q，e）；}}

参考答案：（1）6,4,2,5,3,1 （2）将队列倒置

7.填空题已知栈的基本操作函数：intInitStack（SqStack*S）；//构造空栈intStackEmpty（SqStack*S）；//判断栈空intPush（SqStack*S，ElemTypee）；//入栈intPop（SqStack*S，ElemType*e）；//出栈函数conversion实现十进制数转换为八进制数，请将函数补充完整。voidconversion（）{InitStack（S）；scanf（“%d”，&N）；while（N）{（1）；N=N/8；}while（（2））{Pop（S，&e）；printf（“%d”，e）；}}//conversion

参考答案：（1）Push(S,N%8) （2）!StackEmpty(S)

8.判断题以链表作为栈的存储结构，出栈操作必须判别栈空的情况。

参考答案：对

9.判断题在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取结构。

参考答案：错

10.判断题栈和队列都是受限的线性结构。

参考答案：对