问题 单项选择题

设主串长为n,模式串长为m(m≤n),则在匹配失败的情况下,朴素匹配算法进行的无效位移次数为 (30)

A.m

B.n-m

C.n-m+1

D.n

答案

参考答案:C

解析:[分析]
本题考查字符串的匹配内容。
字符串是由某字符集上的字符所组成的任何有限字符序列。字符串的匹配实际上就是在一个字符串中查找另一个字符串,如果查找到则说明匹配成功。
在一个字符串中查找另一个字符串时,是从主串的第一个字符开始的,用其第一个字符与模式串中的第一个字符比较,看是否相等,如果不等则主串往后移动一位,如果查找不到,那么只需要把主串移动到n-m+1位置即可,因为后面就算再出现能查找到的情况那也没有模式串的长度了,肯定不能完全查找出模式串。那么在匹配过程中,进行的无效位移次数为n-m+1次。

多项选择题
阅读理解

London Thursday July 26(Reuters)--Ian Johnstone missed his girlfriend so much that he flew back to Britain from Australia to propose to her.The problem is that she flew in the opposite direction.

He and Amy Dolby even managed to miss each other when they sat in the same airport waiting-room in Singapore at the same time to wait for connecting flights.

Dolby,heartbroken when she arrived at Johnstone’s Sydney apartment to find he had flown to London,told the Times:“It was as though someone was playing a cruel joke on us.He is the most romantic person I have ever known.I think our problem is that we are both quite impulsive(冲动的)people.We are always trying to surprise each other.”

After an 11,000-mile flight across the globe,she was greeted by Johnstone’s astonished flatmate asking what she was doing there.

“The terrible truth dawned when I found that Lan’s rucksack and most of his clothes were missing.I sat on the end of his bed and cried my eyes out.And that really annoyed me,”she said.

Johnstone,a 27-year-old bricklayer,had taken a year off to travel round Australia.But he was missing Dolby,a 26-year-old secretary,so much he got a job on a Sydney building site and started saving for a surprise.

He then flew home to Britain and went to her apartment armed with an engagement ring,champagne and flowers.

“I really missed Amy and I’d been thinking about her all the time.I thought she was winding me up when she phoned me from Australia.”he said.

Johnstone then asked Dolby to marry him on the phone.“I didn’t know whether to laugh or cry but I accepted,”she said.

Dolby was given a short tour of Sydney by Johnstone’s friends and Johnstone had to stay in Britain for two weeks because he could not change his ticket.

小题1:According to the text,it seemed that       .

A.Johnstone and Dolby could have seen each other in the same airport waiting-room in Singapore

B.the couple pretended not to see each other in the same airport waiting-room in Singapore

C.the young lovestruck couple had both intended to propose to each other

D.Dolby stayed longer in Sydney than Johnstone stayed in Britain小题2:We can learn from the text that        .

A.Johnstone was not as impulsive as Dolby

B.Johnstone got a job in Sydney in order to start saving money for a surprise to Dolby

C.Dolby was heartbroken because someone was playing a cruel joke on her

D.Dolby was greeted by Johnstone’s flatmate at the airport小题3:When Johnstone asked her to marry him on the phone,Dolby didn’t know whether to laugh or cry because she had a mixed feeling of        .

A.excitement,anger and shyness

B.sadness,happiness and surprise

C.love,hatred and nevousness

D.cheer,regret and annoyance小题4:Which of the following shows the right order of what happened in the story?

a.Johnstone flew back to Britain to propose to his girlfriend,Amy Dolby.

b.Johnstone started working at a Sydney building site.

c.Johnstone went to Amy’s apartment in Britain with an engagement ring.

d.Johnstone proposed to Dolby over the phone.

e.They were waiting for their connecting flight in the airport in Singapore.

f.Dolby called Johnstone from Australia.

A.b—a—d—e—c—f

B.c—a—b—e—f—d

C.b—a—e—c—f—d

D.b—a—f—e—c—d