自测卷精选试题
设主串长为n，模式串长为m(m≤n)，则在匹配失败的情况下，朴素匹配算法进行的无效位移次数为(30)。
A．m
B．n-m
C．n-m+1
D．n
解析：本题考查字符串的匹配内容。字符串是由某字符集上的字符所组成的任何有限字符序列。字符串的匹配实际上就是在一个字符串中查找另一个字符串，如果查找到则说明匹配成功。在一个字符串中查找另一个字符串时，是从主串的第一个字符开始的，用其第一个字符与模式串中的第一个字符比较，看是否相等，如果不等则主串往后移动一位，如果查找不到，那么只需要把主串移动到n-m+1位置即可，因为后面就算再出现能查找到的情况那也没有模式串的长度了，肯定不能完全查找出模式串。那么在匹配过程中，进行的无效位移次数为n-m+1次。
●在字符串的模式匹配过程中，如果模式串的每个字符依次和主事中一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特—福斯模式匹配算法（朴素的或基本的模式匹配）中，若主串和模式串的长度分别为n和m（且n远大于m），且恰好在主串末尾的m个字符处匹配成功，则在上述的模式匹配过程中,字符的比较次数最多为(57)。
(57) A. n*m
B. (n-m+1)*m
C. (n-m-1)*m
D. (n-m)*n
求字符串T在字符串S中首次出现的位置的操作称为()。
A、串的模式匹配
B、求子串
C、求串的长度
D、串的连接
设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。
A、求子串
B、联接
C、模式匹配
D、求串长
设有两个串p和q，求q在p中首次出现位置的运算称为( )。
A．连接
B．模式匹配
C．求子串
D．求串长
解析： 字串的定位操作通常称为串的模式匹配，是各种串处理系统中最重要的操作之一。
李串是一种特殊的线性表，其特殊性体现在：可以顺序存储 数据元素是一个字符 可以链式存储 数据元素可以是多个字符2（ B ）
李设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作：连接 模式匹配 求子串 求串长（ D ）
李设串 s1=ABCDEFG，s2=PQRST ，函数 con(x,y)返回 x 和 y 串的连接串，subs(s, i, j)返回串 s 的从序号 i 开始的 j 个字符组成的子串，len(s)返回串 s 的长度，则 con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的结果串是：BCDEF BCDEFG BCPQRST BCDEFEF解：con(x,y)返回 x 和 y 串的连接串，即 con(x,y)ABCDEFGPQRST ；subs(s, i, j)返回串 s 的从序号 i 开始的 j 个字符组成的子串，则subs(s1, 2, len(s2)subs(s1, 2, 5)= BCDEF; subs(s1, len(s2), 2)subs(s1, 5, 2)= EF;所以 con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)con( BCDEF, EF)之连接，即 BCDEFEF（ A ）
01 年计算机系考研题 假设有 60 行 70 列的二维数组 a160, 170以列序为主序顺序存储，其基地址为 10000，每个元素占 2 个存储单元，那么第 32 行第 58 列的元素 a32,58的存储地址为 。 （无第 0 行第 0 列元素）16902 16904 14454 答案 A, B, C 均不对答：此题与填空题第 8 小题相似。 （57 列60 行31 行）2 字节10000=16902( B )
设矩阵 A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组 B 1, n(n-1)/2 中，对下三角部分中任一元素 ai,j(ij), 在一维数组 B 中下标 k 的值是：i(i-1)/2+j-1 i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j
设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为 ( )
A．m
B．n-m
C．n-m+1
D．n
求字符串T在字符串S中首次出现的位置称为(42)。
A．串的模式匹配
B．求子串
C．求串的长度
D．串的连接
对串s和串t，为串t在串s中定位的运算称为( )。
A．判等
B．模式匹配
C．求串长
D．求子串
解析：子串的定位操作称为串的模式匹配。
● 在字符串的模式匹配过程中，如果模式串的每个字符依次和主事中一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特—福斯模式匹配算法（朴素的或基本的模式匹配）中，若主串和模式串的长度分别为n和m（且n远大于m），且恰好在主串末尾的m个字符处匹配成功，则在上述的模式匹配过程中，字符的比较次数最多为（57）。 A.n*m B.（n-m+1）*m C.（n-m-1）*m D.（n-m）*n
试题57分析本题主要考查字符串的匹配。在本题的描述中，告诉我们是在主串末尾的m个字符处匹配成功，那么在这之前，从左到右依次匹配了n-m次，且都失败了，最坏的情况，就是每次匹配都是匹配到最后一个字符不符合，因此每次匹配的比较次数就是子串的长度，即m。而匹配成功时，一共也比较了m次。所以字符的比较次数最多为（n-m+1）*m次。参考答案（57）B
设有两个字符串p和q，求q在p中首次出现位置的运算称为（ ）。
A.连接
B.模式匹配
C.求子串
D.求串长
B。【解析】字串的定位操作通常称为串的模式匹配，是各种串处理系统中最重要的操作之一。