数据结构第四章考试题库含答案文档格式.docx
- 文档编号:7796545
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:88
- 大小:53.93KB
数据结构第四章考试题库含答案文档格式.docx
《数据结构第四章考试题库含答案文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构第四章考试题库含答案文档格式.docx(88页珍藏版)》请在冰点文库上搜索。
.1231
.1211
5
.串‘ababaaababaa
’的next
数组为(
【中山大学1999
一、7】
A.012345678999
.012121111212
.011234223456
.0123012322345
6
.字符串‘ababaabab
’的nextval
为(
A.(0,1,0,1,04,1,0,1)
.(0,1,0,1,0,2,1,0,1)
C.(0,1,0,1,0,0,0,1,1)
.(0,1,0,1,0,1,0,1,1)
一、1(2
7
.模式串t=‘abcaabbcabcaabdab
’,该模式串的next数组的值为(
),nextval
数组的值为
()。
A.01112211123456712B
.01112121123456112
C.01110013101100701D
.01112231123456712
E.01100111011001701F
.01102131011021701
1998
二、3(2
8
.若串S=’software
’,其子串的数目
是(
【西安电子
科技大学
2001
应用
一、2(2分)】
A.8B
.37
.36
.9
9
.设S为一个长度为
n的字符串,其
中的字符各不相同,则S中的互异的非平
凡子串(非
空且不同于S
本身)的个数为
【中科院计算所
1997
】
A.2n-1B
.n2
.(n2/2)+(n/2)D
.(n2/2)+(n/2)-1E.
(n2/2)-(n/2)-1F.
其他情况
10.串的长度是
指(
【北京工商大学
一、6(3
A.串中所含不同字母
的个数
.串中所含字符的个数
C.串中所含不同字符
.串中所含非空格字符
二、判断题
.KMP算法的特点是在模式匹
配时指示主
串的指针不会变小。
【北京邮电大学
2002
一、4(1分)】
.设模式串的长度为
m,目标串的
长度为n,当n≈m且处理只匹配一次
的模式时,朴素的匹配(即子串定
位函数)算法所
花的时间代
价可能会更为节省。
【长沙铁道学院
一、1(1
分)】
.串是一种数据对象
和操作都特殊的线性
表。
【大连海事大学20011
、L(1
二、填空题
.空格串是指
__
(1)__
,其长度等于___
(2)__
。
【西安电子科技
大学2001
软件一、4(2
.组成串的数据元素
只能是________。
【中山大学
(1
.一个字符串中
________
称为该串的子串
【华中理工大学
一、3(1
.INDEX(‘DATASTRUCTURE’,‘STR’)=________。
【福州大学1998
二、4(2
.设正文串长度为
n,模式串长度为m,则串匹配的KMP算法的时间复
杂度为________。
【重庆大学
一、4】
.模式串P=‘abaabcac’的next
函数值序列为
________。
【西安电子科技大学
2001软件
一、6(2分)】
.字符串’ababaaab’的nextval
函数值为________。
【北京邮电大
二、4
.设T和P是两个给定的串,在
T中寻找等于P的子串的过程称
为__
(1)__,又称P为__
(2)__
【西安电子科技
大学
1998二、5(16/6分)】
9.串是一种特殊的线
性表,其特殊性表现在__
(1)__
;
串的两种最基本
的存储方式
是__
(2)__、__(3)__
两个串相等的充
分必要条件
是__(4)__。
【中国矿业大学
2000一、3
(4分)】
10
.两个字符串
相等的充分
必要条件是_______。
【西安电子科技大学
1999软件
一、1(2分)】
11
.知U=‘xyxyxyxxyxy’;
t=‘xxy’;
ASSIGN(S,U);
ASSIGN(V,SUBSTR(S,INDEX(s,t),LEN(t)+1));
ASSIGN(m,‘ww’)
求REPLACE(S,V,m)=________。
【东北大学
1997一、1(5
12
.实现字符串
拷贝的函数
strcpy
为:
voidstrcpy(char*s,char*t)/*copyttos*/
{while(________)
}【浙江大学
一、5(3
13.下列程序判断字符串s是否对称,对称则返回1,否则返回0;
如
f("
abba"
返回
1,f("
abab"
0;
intf(
(1)________)
{inti=0,j=0;
while(s[j])
(2)________;
for(j--;
i<
j&
&
s[i]==s[j];
i++,j--);
return((3)_______)
}【浙江大学1999一、6(3分)】
14.下列算法实现求采用顺序结构存储的串s和串
程序(a)
t的一个最长公共子
串。
PROCEDUREmaxcomstr(VARs,t:
orderstring;
VARindex,length:
integer);
VARi,j,k,length1:
integer;
con:
boolean;
BEGIN
index:
=0;
length:
i:
=1;
WHILE(i<
=s.len)DO
[j:
WHILE(j<
=t.len)DO
[IF(s[i]=t[j])THEN
[k:
length1:
=true;
WHILEconDO
IF
(1)__THEN[length1:
=length1+1;
k:
=k+1;
]ELSE
IF(length1>
length)THEN[index:
=i;
length:
=length1;
]
(3)____;
(2)_;
]
ELSE(4)____;
(5)___;
END;
程序(b)
voidmaxcomstr(orderstring*s,*t;
intindex,length)
{inti,j,k,length1,con;
index=0;
length=0;
i=1;
while(i<
=s.len)
{j=1;
while(j<
=t.len)
{if(s[i]==t[j])
{k=1;
length1=1;
con=1;
while(con)
if
(1)_{length1=length1+1;
k=k+1;
}else
(2)__;
if(length1>
length){index=i;
length=length1;
}
}
else(4)___;
(5)__
}}【上海大学2000一、2(10
15.完善算法:
求KMP算法中next数组。
PROCget_next(t:
string,VARnext:
ARRAY[1..t.len]OFinteger);
j:
k:
=
(1)__;
next[1]:
WHILEj<
t.lenDO
IFk=0ORt.ch[j]=t.ch[k]THENBEGINj:
=j+1;
next[j]:
=k;
END
ELSEk:
=
(2)___;
【中山大学
16.下面函数
返回0。
1998index
四、用于求
1(4分)】
t是否为s的子串,若是返回
t第一次出现在
s中的序号(从
1开始计
),否则
例如:
s=
‘abcdefcdek
’,t=‘cde’,
则indse(s,t)=3,
index(s,
’aaa’)=0
已知
t,s
的串长分别
是mt,ms
FUNCindex(s,t,ms,mt);
i:
WHILE(i<
ms)AND(j<
mt)DO
IFs[i]=t[j]THEN[
(1)__;
(2)__]
ELSE[(3)___;
(4)_]
IFj>
mtTHENreturn(5)____;
ELSEreturn(6)__
ENDF;
【南京理工大学1999
17.阅读下列程序说明和
三、pascal
(6程序
把应填入其中的(
)处的字句
写在答题纸
上。
程序说明:
本程序用于判别输入的字符串是否为如下形式的字符串:
W&
M$其中,子字符串M是子字符串W的字符反向排列,在此假定
W与M的分隔符,字符$用作字符串的输入结束符。
例如,对输入字符串ab&
ba$、11&
12$、ab&
dd$、&
$,程序将分别
程序
W不含有字符&
和字符$,
输出Ok.(是),No.(不是
字符)。
用作
PROGRAMaccept(input,output);
CONSTmidch=’&
’;
endch=’$’;
VARan:
ch:
char;
PROCEDUREmatch(VARanswer:
boolean);
VARch1,ch2:
f:
read(ch1);
IFch1<
>
endch
THENIF
(1)__
THENBEGINmatch(f);
IFfTHENBEGINread(ch2);
answer:
=
(2)_ENDELSEanswer:
=false
ELSE(3)___
ELSE(4)___
writeln(
‘EnterString:
’);
match(an);
IFanTHENBEGIN
(5)__IF(6)_THENwriteln(
‘Ok.’)ELSEwriteln(‘No.’)
ELSE
‘No.’)
END.【上海海运学院
1998七(15分)】
18.试利用下列栈和串的基本操作完成下述填空
题。
initstack(s)
置s为空栈;
push(s,x)
元素x入栈;
pop(s)
出栈操作;
gettop(s)
返回栈顶元
素;
sempty(s)
判栈空函数
setnull(st)
置串st为空串;
length(st)
返回串st
的长度;
equal(s1,s2)
判串s1和s2是否相等的函数;
concat(s1,s2)
返回联接
s1和s2
之后的串;
sub(s,i,1)
返回s中第i个字符;
empty(st)
判串空函数
FUNCinvert(pre:
string;
VARexp:
string):
{若给定的表达式的前为空串,并返回“false
缀式pre”。
已知原表
正确,本过程求
达式中不包
得和它相应
含括弧,opset
的表达式exp
为运算符的集合
并返回“
true
”,否则
exp
VARs:
stack;
i,n:
succ:
char;
n:
=length(pre);
(1)__;
(2)__;
n)ANDsuccDO
BEGINch:
=sub(pre,i,l);
IF(3)_THEN(4)__
ELSEIF(5)__THEN(6)_
ELSEBEGIN
exp:
=concat((7)___,(8)____);
=concat((9)___,(10)___);
(11)__;
=i+1
IF(12)___THEN
BEGINexp:
=concat(exp,sub(pre,n,1));
invert:
=trueEND
ELSEBEGINsetnull(exp);
=falseEND
注意:
每个空格
只填一个语句。
【清华大学1996八】
四、应用题
.名词解释:
【大连海事1996
一、10(1
分)】【河海大学
二、5(3分)】
.描述以下概念的区
别:
空格串与空串。
【大连海事大学1996
三、2、
(1)(2分)】
S1和S2的长度分别为
m和n。
求这两个字符串
最大共同子
串算法的时间复杂度为T(m,n)。
估算最优的
T(m,n)
,并简要说
明理由。
【北京工业大学1996
一、5(6
.设主串
S=‘xxyxxxyxxxxyxyx
’,模式串
T=‘xxyxy’。
请问:
如何用
最少的比较次数找到
T在S中出现
的位置?
相应的
比较次数是多少?
【大连
海事大学2001四(8
分)
5.KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进?
【大连海事大学1996三、1((2
6.已知模式串
t=‘abcaabbabcab
’写出用
KMP法求得的每个字符对
应的next和nextval
函数值。
三(10
7.给出字符串‘abacabaaad’在KMP算法中的next
和nextval
数组。
【北京邮电大
学2000三、1(5分)】
8.令t=‘abcabaa’,求其next
函数值和
nextval
【北方交通大学1994
一
(6分)】
9.已知字符串‘cddcdececdea
’,计算每个字
符的next
函数的值。
【南京邮电大学2000
一2】
.试利用KMP算法和改进
算法分别求p1=‘abaabaa’和p2=‘aabbaab’的next
函数和nextval
函数。
【东南大学
一、6(8
.已知KMP串匹配算法
中子串为
babababaa,写出next
数组改进后的next
数组信息值(要
求写出数组下
标起点)。
【西南交通大学
2000二、2】
.求模式串
T=‘abcaabbac'
的失败函数
Next(j)
值。
【西安交通大
四、4(5
13
.字符串的模
式匹配
KMP算法中,失败函数(NEXT)是如何定义的
?
计算模式串p=‘aabaabaaabc’中各字
符的失败函数值
.【石油大学1998
一、2(10
分)】
14
.设字符串
S=‘aabaabaabaac'
,P=‘aabaac'
(1)给出S和P的next
值和nextval
值;
(2)若S作主串,P作模式串,试给出利用BF算法和KMP算法的匹配过程。
【北方交通大学
二(15
15
.设目标为
t=‘abcaabbabcabaacbacba
’,模式为p=‘abcabaa’
(1)计算模式p的naxtval
函数值;
(5分)
(2)不写出算法
只画出利用
KMP算法进行模式
匹配时每一
趟的匹配过
程。
(5分)
【清华大学
八(10分)】
16
.模式匹配算
法是在主串
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第四 考试 题库 答案
![提示](https://static.bingdoc.com/images/bang_tan.gif)