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()
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]。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。