已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”。采用KMP算法进行匹配，第一次出现“失配”(s[i]≠t[j])时，i=j=5，则下次开始匹配时，i和j的值分别是()。A.i=1,j=0B.i=5,j=0C.i=5,j=2D.i=6,j=2

给定下面的代码： int i=1,j=10; do { if(i++＞--j) continue; }while(i＜5) 执行完之后，i与j的值分别是多少? ( )

A．i=6,j=5

B．i=5,j=5

C．i=6,j=4

D．i=5,j=6

阅读下列函数说明和C代码，将应填入(n)处的字句写在对应栏内。

【说明】

函数QuickSort是在一维数组A[n]上进行快速排序的递归算法。

【函数】

void QuickSort( int A[ ],int s,int t)

{ int i=s,j=t+1,temp;

int x=A[s];

do{

do i ++ ;while (1);

do j -- ;while(A[j]＞x);

if(i＜j){temp=A[i];(2);(3);}

}while(i＜j);

A[a] =A[j];A[j] =x;

if(s＜i-1) (4);

if(j+1＜t) (5);

}

A.i=1，j=2

B.i=1，j=1

C.i=42，j=2

D.i=42，j=1

E.Compilationfails.

有以下程序 #include ＜stdio.h＞ #include ＜string.h＞ void fun(char s[][10],int n) { char t; int i j; for (i=0; i＜n-1; i++) for 0--i+l; j＜n; j++) /*比较字符串的首字符大小，并交换字符串的首字符*/ if(s[i][0] ＞ s[j][0]) { t = s[i][0]; s[i][0] = s[j][0]; s[j][0] = t;} } main() { char ss[5][10]= {"bcc", "bbcc", "xy", "aaaacc", "aabcc" }; fun(ss, 5); printf("%s,%s\n", ss[0],ss[4]); } 程序的运行结果是

A．xy, aaaacc

B．aaaacc,xy

C．xcc,aabcc

D．acc,xabcc

阅读以下程序：

include＜iostream.h＞

void main()

{

static int a[][3]={9,7,5,3，1，2，4，6，8}；

int i,j,s1=0，s2=0；

for(i=0；i＜3；i++)

for(j=0;j＜3;j++)

{

if(i==j)s1=sl+a[i][j]；

if(i+j==2)s2=s2+a[i][j]；

}

cout＜＜s1＜＜"，"＜＜s2＜＜endl;

}

则该程序的输出结果为【 】。

有以下程序： struct S{int n;int a[20];}； void f(struct S*P) { int i,j,t； for(i=0;i＜P-＞n-1;i++) for(j=j+1;j＜P-＞n-1;j++) if(p-＞a[i]＞p-＞a[j]) {t=P-＞a[i];p-＞a[i]=P-＞a[j];p-＞a[j]=t} } main() {int i；struct S s{10,{2,3,1,6,8,7,5,4,10,9}}； f(＆s)； for(i=0;i＜s.n;i++)printf("%d",s.a[i]);} 程序运行后的输出结果是( )。

A．3

B．4

C．5

D．6

有以下程序 #include ＜stdio．h＞ #include ＜string．h＞ void fun(char，*s[]，int n) { char *t; int i，j； for(i=0；i＜n-1；i++) for(j=i+1；j＜n；j++) if(strlen(s[i])＞strlen(s[j])) {t=s[i]；s[i]：s[j]；s[j]=t；} } main() { char *ss[]={"bcc"，"bbcc"，"xy"，"aaaacc"，"aabcc"}； fun(ss，5)； printf("%s，%s\n"，ss[0]，ss[4])； } 程序的运行结果是

A．xy，aaaacc

B．aaaacc，xy

C．bcc，aabcc

D．aabcc，bcc

有以下程序

#include <stdio.h>

#include <string.h>

void fun（char s[][10],int n）

{char t; int i,j;

for（i=0;i<n-1;i++）

for（j=i+1;j<n;j++）

/*比较字符串的首字符大小 ，并交换字符串的首字符*/

if（s[i][0]<s[j][0]） {t=s[i][0];s[i][0]=s[j][0];s[j][0]=t;}

}

main（）

{char ss[5][10]={“bcc”,”bbcc”,”xy”,”aaaacc”,”aabcc”};

fun（ss,5）; printf（“%s,%s\n”,ss[0],ss[4]）;

}

程序的运行结果是（ ）。

A．xy,aaaacc

B．aaaacc,xy

C．xcc,aabcc

D．acc,xabcc

在执行完此程序段后，i，j值为 int i=1，j=10； do{ if(++i＞j--)continue； }while(i＜5)；

A．i=6 and j=5

B．i=5 and j=5

C．i=6 and j=4

D．i=5 and j=6

执行下面的程序段后i和j的结果为 int i=1,j=10； do { if(i++＞--j)continue； } while(i＜5);

A．i=6,j=5

B．i=5,j=5

C．i=6,j=4

D．i=5,j=6

A.i=1，j=0

B.i=1，j=4

C.i=3，j=4

D.i=3，j=0

E.Compilationfails.

有以下程序 main() {int a[4][4]={{1，4，3，2}，{8，6，5，7}，{3，7，2，5}，{4，8，6，1}}，i，j，k，t； for(i=0；i＜4；i++) for(j=0；j＜3；j++) for(k=j+1；k＜4；k++) if(a[j][i]＞a[k][i]){t=a[j][i]；a[j][i]=a[k][i]；a[k][i]=t；}/*按列排序*/ for(i=0；i＜4；i++)printf("%d，"，a[i][i])；

A．1，6，5，7，

B．8，7，3，1，

C．4，7，5，2，

D．1，6，2，1，

有以下程序 #include<stdio．h> #include<string．h> void fun(char s[][10]，int n) { char t；int i，j； for(i=0；i<n-1；j++) for(j=i+1，j<n；j++) ／*比较字符串的首字符大小，并交换字符串的首字符*／ if(s[0])>s[i][c]{t=s[i][o]；s[i][o]=s[j][o]；s [j][0]=t；} } main { char ss[5][10]="bcc"，"bbcc"，"xy"，"aaaacc"，" aabcc"} fun(ss，5)；printf("％s，％s"，ss[0]，ss[4])； } 程序运行结果是( )。

A.xy，aaaacc

B.aaaacc，xy

C.xcc，aabcc

D.acc，xabcc

在执行完此程序段后，i，j值为 int i=1-10； do{ if(++i＞j--)continue； } while(i＜5);

A．i=6 and j=5

B．i=5 and j=5

C．i=6 and j=4

D．i=5 and j=6

试题四（共15分）

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

【说明】

模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。

如果匹配成功，返回s在t中的位置，否则返回-1 。

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

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

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：长度为悯铂Is的字符串

next:next数组，长度为Is

（2）C程序

include <stdio．h>

nclude <stdliB．h>

include <string．h>

／*求next【】的值*/

void get_next（ int *next, char *s, int Is） {

int i=0，j=-1；

next[0]=-1；/*初始化next[0]*／

while（i< ils）{/*还有字符*／

if（j=-1l ls[i]=s[j]）{／*匹配*／

j++；

i++；

if（ s[i]一s[jl）

next [i]- next[j];

else

Next[i]=j；

}

else

J= next[j]；

}

}

int kmp（ int *next, char *t ,char *s, int.lt, int Is ）

{

inti= 0,j =0 ;

while （i<lt && （ 1 ） {

if（ j=-1 II 2_） {

i++ ;

j ++ ;

} else

（3） :

}

if （j>= ls）

Retum （4）

else .

retum-1；

【问题1】（8分）

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

【问题2】（2分）

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

【问题3】（5分）

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

main( )

{ int a[6]＝{10,20,30,40,50,60},i;

invert(a,0,5);

for(i=0;i<6;i++) printf(“%d,”,a[i]);

printf(“\n”);

}

invert(int s[ ],int i,int j)

{ int t;

if(i<J)

{ invert(s,i+1j-1);

t=s[i];s[i]=s[j];s[j]=t;

}

}