1. KMP算法的设计思想是什么？它有什么优点？

答：其设计思想是，利用已经部分匹配的结果来加快模式串的滑动速度。

主要优点有二：一是在模式与主串已经部分匹配的情况下，可以大大加快匹配速度；二是主串指针不回溯，可以使外设文件边读入边匹配。

2.已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？ 解：

按行存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (i-1)*m+(j-1) ] * K 按列存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (j-1)*m+(i-1) ] * K

3.递归算法比非递归算法花费更多的时间，对吗？为什么？

答：不一定。时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已。

四、计算题（每题5分，共20分）

1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’, 求Replace(s,’STUDENT’,q) 和 Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))。

解：① Replace(s,’STUDENT’,q)＝’I AM A WORKER’ ② 因为 SubString(s,6,2)＝‘A ’；SubString(s,7,8)＝‘ STUDENT’ Concat(t,SubString(s,7,8))＝’GOOD STUDENT’

所以Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))＝‘A GOOD STUDENT’

2. 已知主串s=’ADBADABBAABADABBADADA’,模式串pat=’ADABBADADA’。写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。

解：nextval函数值为0 1 0 2 1 0 1 0 4 0 在第12个字符处发现匹配！ s=’ADBADABBAABADABBADADA’ pat=’ADABBADADA’

3. （P60 4-18）用三元组表表示下列稀疏矩阵：

00000000

00000000

03000800

00000000(1)

00060000

00000000 00000005

20000000

00000 2

000090

0 00000

(2)

005000

000000

0 00003

解：参见填空题4. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。 所以（1）可列表为： （2）可列表为：

4. （P60 4-19）下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。

6 1 2 (1)3 4 5 6

46

455

22 111

112

249

13 (2) 328

44

356

36

437

116

解：（1）为6×4矩阵，非零元素有6个。 （2）为4×5矩阵，非零元素有5个

五、算法设计题（每题10分，共30分）

1. 编写一个实现串的置换操作Replace(&S, T, V)的算法。 解：

int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为 V,并返回置换次数

{

for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围

if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串 { //分别把

T的前面和后面部分保存为head和tail StrAssign(head,SubString(S,1,i-1));

StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1)); StrAssign(S,Concat(head,V));

StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串 i+=Strlen(V); //当前指针跳到插入串以后

n++; n++; }//if return n;

}//Replace

分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下, 会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?

2. 写出将字符串反序的递归或递推算法，例如字符串为“abcsxw”，反序为“wxscba”编写对串求逆的递

推算法) 请注意递归和递推的区别！递推是由“小”到“大”递进； 递归是由“大”到“小”嵌套。 算法思路：

① 假定用单链表结构存储字符串；

if没有到尾部字符就不停调用自身函数，直至到达末尾，再从尾部返回并打印字符； 否则就打印当前字符并返回。

Invert(stringlistnode *p){ if(!p)return(0);

else Invert(p->next);

printf(“%c”, p->data) }

如果当前串长为0,则return(-1) 否则开始递归：

if 串没有到末尾，则P=P->next; 再调用invert(s); else printf(p->data); return

void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r {

StrAssign(r,''); //初始化r为空串 for(i=Strlen(s);i;i--) {

StrAssign(c,SubString(s,i,1));

StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中 /这是递推算法。 }

}//String_Reverse

3. 试设计一个算法，将数组An 中的元素A[0]至A[n-1]循环右移k位，并要求只用一个元素大小的附加

存储，元素移动或交换次数为O(n) 解：

分析:要把A的元素循环右移k位,则A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[ 0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求 …… 此处隐藏：1148字，全部文档内容请下载后查看。喜欢就下载吧 ……