[数据结构]串、数组 C++编程作业

1 .?关于串的叙述，正确的是（ ）。

A.串是含有一个或多个字符的有穷序列

B.空串是只含有空格字符的串

C.空串是含有零个字符或含有空格字符的串

D.串是含有零个或多个字符的有穷序列

?解析

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

2 .?下面关于串的叙述中，正确的是（ ）。

A.串是一种特殊的线性表

B.串中元素只能是字母

C.空串就是空白串

D.串的长度必须大于零

?解析

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

3 .?关于串的的叙述，不正确的是（ ）。

A.串是字符的有限序列

B.空串是由空格构成的串

C.替换是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

?解析

空串中不含任何字符，包括空格。

4 .?两个字符串相等的条件是（ ）。

A.串的长度相等

B.含有相同的字符集

C.都是非空串

D.串的长度相等且对应的字符相同

5 .?串的长度是指（ ）。

A.串中所含不同字母的个数

B.串中所含字符的个数

C.串中所含不同字符的个数

D.串中所含非空格字符的个数

6 .?串是一种特殊的线性表，其特殊性体现在 （ ）。

A.可以顺序存储

B.数据元素是单个字符

C.可以链接存储

D.数据元素可以是多个字符

?解析

串中每个元素是单个字符。

7 .?若串str=“Software”，其子串的数目是（ ）。

A.8

B.9

C.36

D.37

?解析

该串中所有字符不相同，长度为0的子串1个，长度为1的子串8个，长度为2的子串7个，…，长度为7的子串2个，长度为8的子串1个，总计子串数=1+8+7+…+2+1=1+8×9/2=37。

8 .?若串s为一个长度为n的串，其中各字符不相同，则s中真子串的数目是（ ）。

A.n(n-1)/2

B.n(n+1)/2

C.n(n+1)/2+1

D.n(n-1)/2+1

?回答错误

解析

该串中所有字符不相同，长度为1的子串n个，长度为2的子串n-1个，…，长度为n-1的子串2个，长度为0的子串1个，总计真子串数=n+(n-1)+…+2+1=n(n+1)/2。

9 .?串采用结点大小为1的链表作为其存储结构，是指 （ ）。

A.链表的长度为1

B.链表中只存放一个字符

C.链表中每个结点的数据域中只存放一个字符

D.以上都不对

?解析

链串结点大小指每个结点存放的字符个数。

10 .?.对于一个链串s，查找第一个元素值为x的算法的时间复杂度为 （ ）。

A.O(1)

B.O(n)

C.O(n2)

D.以上都不对

?解析

在链串查找第一个元素值为x的算法的时间复杂度为O(n)。

11 .?下面关于串的的叙述中，哪一个是不正确的？（ ）

A.串是字符的有限序列

B.空串是由空格构成的串

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

12 .?若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2))) 其结果为（ ）

A.ABC###G0123

B.ABCD###2345

C.ABC###G2345

D.ABC###2345

E.ABC###G1234

F.ABCD###1234

G.ABC###01234

13 .?设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）

A.求子串

B.联接

C.匹配

D.求串长

14 .?若串S=’software’,其子串的数目是（ ）。

A.8

B.37

C.36

D.9

15 .?设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ ）。

A.2n-1

B.n2

C.(n2/2)+(n/2)

D.(n2/2)+(n/2)-1

E.(n2/2)-(n/2)-1

F.其他情况

16 .?串的长度是指（ ）

A.串中所含不同字母的个数

B.串中所含字符的个数

C.串中所含不同字符的个数

D.串中所含非空格字符的个数

17 .?设模式t=”abcabc”，则该模式的next值为（ ）。

A.{-1，0，0，1，2，3}

B.{-1，0，0，0，1，2}

C.{-1，0，0，1，1，2}

D.{-1，0，0，0，2，3}

?解析

j=0，next[0]=-1

j=1，next[1]=0

j=2:

k=1，t0≠t1，故next[2]=0

j=3:

k=1，t0≠t2

k=2，t0t1≠t1t2，故next[3]=0

j=4:

k=1: t0=t3

k=2: t0t1≠t2t3

k=3: t0t1t2≠t1t2t3，故next[4]=1

j=5:

k=1: t0≠t4

k=2: t0t1=t3t4

k=3: t0t1t2≠t2t3t4

k=4: t0t1t2t3≠t1t2t3t4，故next[5]=2

18 .?将数组称为随机存取结构是因为（ ）。

A.数组元素是随机的

B.对数组任一元素的存取时间是相等的

C.随时可以对数组进行访问

D.数组的存储结构是不定的

19 .?数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（ ）。

A.SA+141

B.SA+180

C.SA+222

D.SA+225

20 .?多维数组之所以有行优先顺序和列优先顺序两种存储方式，原因是（ ）。

A.数组的元素在行和列两个关系中

B.数组的元素必须从左到右顺序排列

C.数组的元素之间存在顺序关系

D.数组是多维结构，内存是一维结构

21 .?下面说法中，不正确的是（ ）。

A.对称矩阵只需存储包括主对角线在内的上（或下）三角的元素即可

B.对角矩阵只需存放非零元素即可

C.稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储

D.稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储

22 .?下面（ ）不属于特殊矩阵。

A.对角矩阵

B.三角矩阵

C.稀疏矩阵

D.对称矩阵

23 .?对特殊矩阵采用压缩存储的目的主要是为了（ ）。

A.表达变得简单

B.对矩阵元素的存取变得简单

C.去掉矩阵中的多余元素

D.减少不必要的存储空间

24 .?稀疏矩阵的常见压缩存储方法有（ ）两种。

A.二维数组和三维数组

B.三元组和散列表

C.三元组和十字链表

D.散列表和十字链表

25 .?一个非空广义表的表头（ ）。

A.不可能是子表

B.只能是子表

C.只能是原子

D.可以是原子或子表

26 .?关于广义表，下列说法不正确的是（ ）。

A.广义表的表尾总是一个广义表

B.广义表的表头总是一个广义表

C.广义表难以用顺序存储结构表示

D.广义表可以是一个多层次的结构

27 .?广义表G＝(a, b, (c, d, (e, f))，G) 的长度是（ ）。

A.8

B.4

C.7

D.3

28 .?设广义表L＝((a, b, c))，则L的长度和深度分别是（ ）。

A.1和1

B.1和3

C.1和2

D.2和3

29 .?以下论断正确的是（ ）。

A.""是空串，" "空格串

B."BEIJING"是"BEI JING"的子串

C."something"<"Something"

D."BIT"="BITE"

30 .?某串的长度小于一个常数，则采用（ ）存储方式最节省空间。

A.链式

B.顺序

C.堆结构

D.无法确定

31 .?若串S="SOFTWARE"，其子串的数目最多是（ ）。

A.35

B.36

C.37

D.38

32 .?已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存放，数组元素a[3][5]的存储地址是1000，则a[0][0]的存储地址是（ ）。

A.872

B.860

C.868

D.864

33 .?广义表是线性表的推广，它们之间的区别在于（ ）。

A.能否使用子表

B.能否使用原子项

C.是否能为空

D.表的长度

34 .?下列广义表属于线性表的是（ ）。

A.E=(a, E)

B.E=(a, b, c)

C.E=(a, (b, c))

D.E=(a, L)；L=()

35 .?广义表((a, b), c, d)的表尾是（ ）。

A.a

B.d

C.(a, b

D.(c, d)

36 .?广义表A=((x, (a, b)), (x, (a, b), y))，则运算head(head(tail(A)))为（ ）。

A.x

B.（a，b

C.(x,(a, b))

D.A

37 .?回文字符串

输入一个字符串，判断该串是否是回文字符串(即从头到尾读跟从尾到头读是一致的)。

是则输出“yes”

否则输出"no"

例如：输入 aabbcc,输出 no

输入 abcba,输出 yes

输入 abccba,输出 yes

?答案

#include <iostream>using?namespace?std;

bool?huiwen(string str){

????int?len=str.length();



????for(int?i=0;i<len/2;i++){

????????if(str.at(i)!=str.at(len-1-i))

????????????return?false;

????}

????return?true;

}int?main(){



????string str;

????cin>>str;

????cout<<(huiwen(str)?"yes":"no");

????return?0;

}