数据结构(字符串)练习题与答案

1、下面关于串的叙述中，正确的是（ ）。 A.串是一种特殊的线性表 B.串中元素只能是字母 C.空串就是空白串 D.串的长度必须大于零 正确答案：A

解析： 串是一种特殊的线性表，其元素为单个字符，长度可以为0。

2、两个字符串相等的条件是（ ）。 A.串的长度相等 B.含有相同的字符集 C.都是非空串

D.两个串的长度相等且对应位置的字符相同 正确答案：D

3、若串str=“Software”，其子串的个数是（ ）。 A.8 B.9 C.36 D.37 正确答案：D

解析： 该串中所有字符不相同，长度为0的子串1个，长度为1的子串8个，长度为2的子串7个，…，长度为7的子串2个，长度为8的子串1个，总计子串数=1+8+7+…+2+1=1+8×9/2=37。 4、一个链串的节点类型定义为 #define NodeSize 6

typedef struct node { char data[NodeSize]; struct node *next; } LinkStrNode;

如果每个字符占1个字节，指针占2个字节，该链串的存储密度为（ ）。 A.1/3 B.1/2 C.2/3 D.3/4 正确答案：D

解析： 链串节点大小指每个节点存放的字符个数，本题节点大小为6，存储密度=(6*1)/(6*1+2)=3/4。

5、串采用节点大小为1的链表作为其存储结构，是指（ ）。 A.链表的长度为1 B.链表中只存放一个字符

C.链表中每个节点的数据域中只存放一个字符 D.以上都不对 正确答案：C

解析： C、链串节点大小指每个节点存放的字符个数。

6、对于一个链串s，查找第一个字符值为x的算法的时间复杂度为（ ）。 A.O(1) B.O(n)

C. O(n2) D.以上都不对 正确答案：B

解析：在链串查找第一个字符值为x的算法的时间复杂度为O(n)。 7、设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（ ）。 A.求子串 B.串联接 C.模式匹配 D.求串长 正确答案：C

解析：模式匹配算法就是找子串在主串中的位置。

8、在串的简单模式匹配中，当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是（ ）。 A.i++ B.i=j+1 C.i=i-j+1 D.i=j-i+1 正确答案：C

解析： C、在串的简单模式匹配中，当两字符比较不等时，目标串位i回溯到原来位置的下一个位置，即i=i-j+1。

9、在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是（ ）。 A.i=next[j]

B.i不变 C..j不变 D.j=next[j] 正确答案：B

解析： 在KMP模式匹配中，当两字符比较不等时，目标串位i不回溯，仍停留在原来的位置。

10、在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位j与目标串位i比较时，两字符不相等，则j的位移方式是（ ）。 A.i=next[j] B.i不变 C.j不变 D.j=next[j] 正确答案：D

解析：在KMP模式匹配中，当两字符比较不等时，目标串位i不改变，将其位置字符与模式串中next[j]位置的字符比较，即j=next[j]。