关键词不能为空

当前您在: 主页 > 英语 >

第 4 章数据结构习题题目及答案 串

作者:高考题库网
来源:https://www.bjmy2z.cn/gaokao
2021-01-26 08:53
tags:

-

2021年1月26日发(作者:policeofficer)
一、基础知识题

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

第 4 章数据结构习题题目及答案 串的相关文章