-
一、基础知识题
4.1
简述下列每对术语的区别:
空串和空格串;
串常量与串变量;主串和子串;串变量的名字和串变量的值;静态分 配的顺序串
与动态分配的顺序串。
【解答】
不含任何字符的串称 为空串,其长度为
0
。仅含有空格字符的串称为空格串,其长度为串
中空格字符的个数 。空格符可用来分割一般的字符,便于人们识别和阅读,但计算串长时应包括这些空格
符。空串在串处理 中可作为任意串的子串。
用引号(数据结构教学中通常用单引号,而
C
语言中用双引号)括起来的字符序列称为串常量,其
串值是常量。串值可以变化的量称为串 变量。
串中任意个连续的字符组成的子序列被称为该串的
子串
。包含子串的 串又被称为该子串的
主串
。子串
在主串中第一次出现时的第一个字符的位置称子串在主 串中的
位置
。
串变量与其它变量一样,要用名字引用其值,串变量的名字也是标识符,串变量的值可以修改。
串的存储也有静态存储和动态存储两种。静态存储指用一维数组,通常一个字符占用一个字节,需要静态定义串的长度,具有顺序存储结构的优缺点。若需要在程序执行过程中,动态地改变串的长度,则可以利用标准函数
malloc()
和
free()
动态地分配或释放存储 单元,提高存储资源的利用率。在
C
语言中,
动态分配和回收的存储单元都来自于一个 被称之为
“
堆
”
的自由存储区,故该方法可称为
堆分配存储
。类型
定义如下所示:
typedef struct
{
char
*str;
int
length;
}HString;
4.2
设有串
S=’good’
,
T=’I
︼
am
︼
a
︼
student’
,
R=’
!
’
,求:
(
1
)
StringConcat(T
,
R)
(
2
)
SubString(T
,
8
,
7
)
(
3
)
StringLength(T)
(
4
)
Index(T
,
’a’)
(
5
)
StringInsert( T
,
8
,
S)
(
6
)
Replace(T
,
SubString(T
,
8
,
7)
,
’teacher’)
【解答】
(1) StringConc at(T
,
R)=’I
︼
am
︼
a
︼
st udent
!
’
(2) SubString(T
,
8< br>,
7
)
=’student’
(3) StringLength(T)=14
(4) Index(T
,
’a’)=3
(5) StringInsert(T
,
8
,
S)=’I
︼
am
︼
a
︼
goodstude nt’
(6) Replace(T
,
SubString(T
,
8
,
7)
,
’teacher’)= ’I
︼
am
︼
a
︼
teacher’
4.3
若串
S
1
=‘ABCDEFG’
,
S
2
=‘9898’
,
S
3
=‘###’
,
S
4
=‘’
,执行
concat(replace( S
1
,
substr(S
1
,
length(S
2
)
,
length(S
3
))
,
S
3)
,
substr(S
4
,
index(S
2
,
‘8’)
,
length(S
2
)))
操作的结果是什么?
【解答】
concat(replace( S
1
,substr(S
1
,length(S
2
),le ngth(S
3
)),S
3
),substr(S
4
,index(S
2
,‘8’),length(S
2
)))
= concat(replace(S
1
,substr(S
1
,4,3),S
3
),substr(S
4
,2,4))
= concat(re place(S
1
,’DEF’,S
3
),’1234’)
= concat(‘ABC###G’,’1234’)
= ‘ABC###G1234’
4.4
设
S
为一个长 度为
n
的字符串,
其中的字符各不相同,
则
S
中的互异的非 平凡子串
(非空且不同
于
S
本身)的个数是多少?
【解答 】长度为
n
的字符串中互异的非平凡子串(非空且不同于
S
本身)的个数计算 如下:
长度为
1
的子串有
n
个,长度为
2
的子串有
n-1
个,长度为
3
的子串有
n-2
个,
……
,长度为
n-1
的子串有
2
个,长度为
n
的 子串有
1
个(按题意要求这个子串就是
S
本身,不能计算在总数内)。故子串
个数为
:(2+n)*(n-1)/2
4.5 KMP
算法< br>(
字符串匹配算法
)
较
Brute(
朴素的字符串匹配
)
算法有哪些改进
?
【解答】
KMP
算法的最大特点是主串指针 不回溯,在整个匹配过程中,对主串从头到尾扫描一遍,对
于处理存储在外存上的大文件是非常有效的。
虽然
Brute(
朴素的字符串匹配
)
算法的时间复杂度 是
O(n*m)
,但在一般情况下,其实际的执行时间
近似于
O(n+m)< br>,因此至今仍被采用。
KMP
算法仅当主串与模式间存在许多
“
部分匹 配
”
的情况下才显得
比
Brute(
朴素的字符串匹配
)< br>算法快得多。
4.6
求串
’ababaaababaa’
的
next
函数值。
【解答】
j
t
串
next[j]
4.7
模式串
t=’abcaabbcaa bdab’
,求模式串的
next
和
nextval
函数的值。
【解答】
j
t
串
next[j]
nextval[j]
1 2 3 4 5
6
7 8 9 10 11 12 13 14
a b c a a b b c a a b d a b
0 1 1 1 2 2 3 1 1 2 2 3 1 2
0 1 1 0 2 1 3 1 0 2 1 3 0 1
4.8
对
S=’aabcbabcaabcaaba’
,
T=’b ca’
,画出以
T
为模式串,
S
为目标串的匹配过程。
【解答】
↓
i=1
第一趟匹配:
a
a b c b a b c a a b c a a b a
b
↑
j=1
↓
i=2
第二趟匹配:
a b
a
b c a b c a c b a b
b
c
1 2 3 4 5
6
7 8 9 10
11 12
a b a b a a a b a b
a
a
0 1
1 2 3 4 2 2 3 4 5 6
↑
j=2
↓
i=3
第三趟匹配:
a b
a
b c a b c a c b a b
b
↑
j=1
↓
i=7
第四趟匹配:
a b a b c a b c a c b a b
b c a (
匹配成功
)
↑
j=4
4.9
选择题:下面关于串的的叙述中,哪一个是不正确的?
A
.串是字符的有限序列
B
.空串是由空格构成的串
C
.模式匹配是串的一种重要运算
D
.串既可以采用顺序存储,也可以采用链式存储
【解答】
B
4.10
选择题:串是一种特殊的线性表,下面哪个叙述体现了这种特殊性?
A
.数据元素是一个字符
B.
可以顺序存储
C.
数据元素可以是多个字符
D.
可以链接存储
【解答】
A
二、算法设计题
4.11
试写出用单链表表示的字符串结点类型的定义,
并依次实现它的计算串长度、
串赋值、
判断两串
相等、求子串、两串连接、求子串在串中位置的
6
个函数。要求每个字符串结点中只存放一个字符。
【算法
4.11
】
单链表结点的类型定义如下:
typedef
struct
Node
{char data;
struct
Node *next;
}LNode
,
*LinkedString
;
(1)
计算串长度
int
StringLength(LinkedString L)
{
∥求带头结点的用单链表表示的字符串的长度
p=L->next;
∥
p
指向串中第一个字符结点
j=0;
∥计数器初始化
while
(p)
{j++; p=p->next;}
∥计数器加
1
,指针后移
return
j;
}
(2)
串赋值
LinkedString StringAssign(LinkedString L)
{//
将字符串
L
的值赋给串
s
LNode *s,*p,*r;
s=(char *)malloc(sizeof(char));
s->next=null; //
头结点
r=s;
//r
记住尾结点
L=L->next;
//
串中第一字符
while
(L)
{p=(
char
*)malloc(sizeof(char));
p->data=L->data; //
赋值
p->next=r->next; //
插入链表中
r->next=p;
r=p;
//
指向新的尾结点
L=L->next;
}
return
s;
}
(3)
判断两串相等
int StringEqual(LinkedString s, LinkedString q)
{//
判断字符串的相等
LNode *p=s->next,*r=q->next;
while
(p && r)
if
(p->data==r->data)
{p=p->next; r=r->next;}
else return
0;
if
(!p && !r)
return
1;
else
return
0;
}
(4)
求子串
-
-
-
-
-
-
-
-
本文更新与2021-01-26 08:53,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/570978.html
-
上一篇:商务英语专业人才培养方案的调研分析报告
下一篇:C选择题填空题