阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的-考网

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。

【说明】

模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1。

KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：

1．在串t和串s中，分别设比较的起始下标i=j=0。

2．如果串t和串s都还有字符，则循环执行下列操作：

（1）如果j=-l或者t[i]=s[j]，则将i和j分别加1，继续比较t和s的下一个字符；

（2）否则，将j向右滑动到next[j]的位置，即j =next[j]。

3．如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回-1。

其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。

【C代码】

（1）常量和变量说明

t，s：长度为lt和ls的字符串

next:next数组，长度为ls

（2）C程序

#include ＜stdio.h>#include＜stdlib.h>#include＜string.h>/*求next[]的值*/void get_next( int*next, char *s, int ls) { inti=0，j=-1; next[0]=-1;/*初始化next[0]*/ while(i＜ ls){/*还有字符*/ if(j==-1lls[i]==s[j]){/*匹配*/ j++; i++; if(s[i]==s[j]) next[i]= next[j]; else Next[i]= j; }else j = next[j]; }} int kmp( int*next, char *t ,char *s, int lt, int ls ) { Inti= 0,j =0 ; while(i ＜ lt && （1） ){ if(j==-1 || （2） ){ i++ ; j++ ; }else （3） ;}if (j >= ls)return （4） ;else return-1;}

【问题1】（8分）

根据题干说明，填充C代码中的空（1）～（4）.

【问题2】（2分）

根据题干说明和C代码，分析出kmp算法的时间复杂度为（5）（主串和子串的长度分别为It和Is，用O符号表示）。

【问题3】（5分）

根据C代码，字符串"BBABBCAC"的next数组元素值为（6）（直接写素值，之间用逗号隔开）。若主串为"AABBCBBABBCACCD"，子串为"BBABBCAC"，则函数Kmp的返回值是（7）。

查看答案纠错

答案：

本题解析：

【问题1】

（1）：j＜ls;

（2）：t[i]==s[j];

（3）：get_next(next, s, ls);

j=next[j];

（4）：i+1-ls;

【问题2】（2分）

（5）O(ls+lt)

【问题3】

（6）[-1, -1,1, -1, -1, 2, 0, 0]，

（7）6

包含此试题的试卷

2021年程序员模拟题1

你可能感兴趣的试题

问答题

【说明】利用ASP+access开发网站管理系统，设计以下两个网页Add_form.asp 和Add.asp，通过它们将网站信息添加到数据库test.mdb 中website表中。下图是Add_form.asp 浏览页面，在其上输入需要添加页面内容后，单击"确定"按钮，执行Add.asp 页面完成相应内容添加到数据库test.mdb 中。

中级网络工程师,章节练习,基础复习,中级网络工程师计算机

问题1：完成程序中空白处填空。

＜% Option Eplicit%>＜Html>＜head>＜title>添加记录示例＜/title>＜/head>(1)align="center">添加新网站＜/h2>＜center>＜table border="1" width="90%">＜form name ="form1"method="（2）"action=（3）">＜tr>＜td>网站名称＜/td>＜td>＜input type="（4）"name="name" size=20>＜/td>＜/tr>＜tr>＜td>网站地址＜/td>＜td>＜input type="text"name="URL" size=40>＜/td>＜/tr>＜tr>＜td>网站简介＜/td>＜td>（5） name ="into" row="2"cols="40"wrap="solf ">＜/textarea>＜/td>＜/tr>＜tr>＜td> ＜/td>＜td>＜input type=(6)" "value="确定">＜input type=(7)" "value="（8）"＜/td>＜/tr>＜/from>＜/table>＜/center>＜/body>＜/html>

添加数据记录执行程序add.asp:

＜% Otion Eplicit>＜% '如果上面信息已经填全了，就添加记录，否则给出错误提示信息Dim connSet conn=server.（9）("ADODB.Connection")conn.Open "Dbq="&Server,mappath("（10）")&";Driver={Microsoft Access Driver(*.mdb)};"Dim strSql,varName,varURL,varlntro,rs '定义变量VarName=Request.Form("（11）")VarURL=Request.Form(" URL")VarIntro =Request.Form("Intro")（12）="Insert into website (name,URL.intro,submit_date)Values( "&varName &","&_varURL&","& varIntro &",# "&Date（）&" # )" 'Date（）表示取服务器时间Set rs=conn.(13) (strSql)index.asp" '添加成功，则返回首页index.asp…response.（14） "请将所有信息填写完整"response. (15)"add_form.asp"%>

备选答案

(1).A.b3 B. h2 C.h3 D.空白

（2）A. get B. post C.put D.pull

(3）A.add.asp B.add C.add_form.asp D.continue

(4)A.submit B.option C.radio D.text

(5)A. textarea B.text C.select D.option

(6)A.submit B.reset C.radio D.text

(7)A.submit B.reset C.radio D.text

(8)A.submit B.确定 C.reset D.重写

(9)A.mappath B.cereateobject C.application D.server

(10)A.test B.test.mdb C.website D.website.table

(11)A.name B.text C.requesto D.response