数据结构串和数组习题
- 格式：pdf
- 大小：205.33 KB
- 文档页数：7
下载文档原格式
合集下载
数据结构课后习题(第4-5章)
【课后习题】第4章 串 第5章 数组和广义表网络工程2010级（ ）班 学号： 姓名：一、填空题（每空1分，共30分）1. 串有三种机内表示方法： 、 和 ，其中前两种属于顺序存储结构，第三种属于 。
2. 若n 为主串长度，m 为子串长度，则串的BF （朴素）匹配算法最坏的情况下需要比较字符的总次数为 ,T(n)= 。
3. 是任意串的子串；任意串S 都是S 本身的子串，除S 本身外，S 的其他子串称为S 的 。
4. 设数组a[1…50, 1…60]的基地址为1000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32,58]的存储地址为 。
5. 对于数组，比较适于采用 结构够进行存储。
6. 广义表的深度是指_______。
7. 将一个100100 A 的三对角矩阵，按行优先存入一维数组B[297]中，A 中元素66,66A 在B 数组中的位置k 为 。
注意：a i,j 的k 为 2(i-1)+j-1,(i=1时j=1,2;1<i<=n 时,j=i-1,i,i+1) 。
8. 称为空串； 称为空白串。
9. 求串T 在主串S 中首次出现的位置的操作是 ，其中 称为目标串， 称为模式。
10. 对称矩阵的下三角元素a[i,j]，存放在一维数组V 的元素V[k]中（下标都是从0开始），k 与i ，j 的关系是：k= 。
11. 在n 维数组中每个元素都受到 个条件的约束。
12. 同一数组中的各元素的长度 。
13. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。
14. 稀疏矩阵中有n 个非零元素，则其三元组有 行。
15.求下列广义表操作的结果：（1）GetHead【((a,b),(c,d))】=== ;（2）GetHead【GetTail【((a,b),(c,d))】】=== ;（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ;（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ;16.广义表E=(a,(b,E)),则E的长度= ，深度= ；二、判断题（如果正确，在下表对应位置打“√”，否则打“⨯”。
数据结构第四章串习题及答案
习题四串一、单项选择题1．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储2．串是一种特殊的线性表，其特殊性体现在（）。
A．可以顺序存储 B．数据元素是一个字符C．可以链接存储 D．数据元素可以是多个字符3．串的长度是指（）A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数4．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长5．若串S=“softwa re”,其子串的个数是（）。
A．8 B．37 C．36 D．9二、填空题1．含零个字符的串称为______串。
任何串中所含______的个数称为该串的长度。
2．空格串是指__ __，其长度等于__ __。
3．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。
一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。
4．INDEX（‘DATAST RUCTU RE’，‘STR’）=________。
5．模式串P=‘abaabc ac’的next函数值序列为________。
6．下列程序判断字符串s是否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回0；int f((1)__ ______){int i=0,j=0;while(s[j])(2)___ _____;for(j--; i<j && s[i]==s[j]; i++,j--);return((3)___ ____)}7．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。
第四章串和数组习题
第四章串和数组一．选择题1．串是一种特殊的线性表，其特殊性体现在（）A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符2．串的长度是（）A．串中不同字母的个数B．串中不同字符的个数C．串中所含字符的个数，且大于0 D．串中所含字符个数3．若串S=”software”，其子串数目是（）A．8 B．37 C．36 D．94．数组A[0..5，0..6]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素A[5][5]的地址为（）A．1175 B．1180 C．1205 D．12105．对矩阵压缩存储是为了（）A．方便运算B．节省存储空间C．方便存储D．提高运算速度6．一个n 阶对称矩阵，如果采用压缩存储方式，则容量为（）A．n2B．n2/2 C．n(n+1)/2 D．(n+1)2/27．对稀疏矩阵采用压缩存储，其缺点之一是（）A．无法判断矩阵有多少行多少列B．无法根据行列号查找某个矩阵元素C．无法根据行列号计算矩阵元素的存储地址D．使矩阵元素之间的逻辑关系更加复杂二．填空1．设串s1=”I am a student”，则串长为（）2．设有两个串p和q，其中q是p的子串，求子串q 在p中首次出现位置的算法称为（）3．一维数组的逻辑结构是（），存储结构是（）；对于二维或多维数组，分为按（）和（）两种不同的存储结构。
4．数组A[1..10,-2..6,2..8]以行优先顺序存储，设第一个元素的首地址为100，每个元素占3个单元的存储空间，则元素A[5][0][7]的存储地址为（）5．三维数组R[C1..D1,C2..D2,C3..D3]共含有（）个元素。
三、算法设计1．编写下列算法（假定下面所用的串均采用顺序存储方式，参数c、c1和c2均为字符型）：（1）将串S中所有其值为c1的字符换成c2的字符。
（2）将串S中所有字符逆序（3）从串S中删除其值等于c的所有字符（4）从串S中第index个字符起求出首次与字符串S1相同的子串的起始位置（5）从串S中删除重第i个字符起的j 个字符（6）从串S中删除所有与串S1相同的子串（允许调用第（4）题和第（5）题的算法）2．设计程序，计算串str中每一个字符出现的次数。
数据结构串和数组习题
C. 三元组和十字链表 D. 散列表和十字链表
4、一个非空广义表的表头（
）。
A. 不可能是子表
B. 只能是子表
C. 只能是原子
D. 可以是子表或原子
5、数组A[0..5,0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000
的内存单元中，则元素A[5][5]的地址是（ ）。
A. 1175
int i; for(i=0;i<s1->length&&i<s1->length;i++)
if(s->data[i]!=s2->data[i]) return s1->data[i]-s2->data[i];
return s1->length-s2->length; }
4、写出算法的功能。 int fun(sqstring *s,sqstring *t,int start){
A. 顺序的存储结构
B. 链式存储结构
C. 数 据 元 素 是
一个字符
D. 数据元素任意
4、设串长为 n，模式串长为 m，则 KMP 算法所需的附加空间为（ ）。
A. O(m)
B. O(n)
C. O(m*n)
D.
O(nlog2m)
5、空串和空格串（ ）。
A. 相同
B. 不相同
C. 可能相同
D. 无法确定
第四章 串
一、选择题
1、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（ ）。
A. 连接
B. 求子串
C. 模式匹配 D. 判断子串
2、已知串S=’aaab’，则next数组值为（ ）。
数据结构习题(顾为兵)第4章串和数组
22:04:25
I ‘ m⊔ a
⊔s t u d
e n t # #∧
串
第五章 串和数组(String and Array)
5.1
5.2 5.3
串的定义
串的表示与实现 模式匹配算法
5.4
数组
22:04:25Байду номын сангаас
串 模式匹配算法 朴素算法
5.3 朴素的模式匹配算法 Index( S, T, pos )
a a a b
0 1 2 3
长度＝m
设在第 i 个位置上匹配成功，共进行了i+m次比较；i的可 能取值范围是0..n-m, 故平均比较次数为：
E
n m i 0
C语言中, 用new申请，delete释放空间。
运行期间可以根据实际需要申请空间
22:04:25
串 串表示与实现 堆分配存储
基本运算举例：
void strcat（char *&T, char *s1, char *s2){ //将串s1和s2联结，结果存放入字符串T中 j=0; k=0; int len1=strlen(s1); len2=strlen(s2);
22:04:25
串 串表示与实现 定长顺序存储
5.2.1 定长顺序存储
用定长静态数组存储串：
#define maxsize 255 //串的最大长度
char char
s1[maxsize+1]; s2[100];
程序运行期间，数组的大小已经固定，不能变化
22:04:25
串 串表示与实现 定长顺序存储
22:04:25
//将S清为空串
// T=S1+S2
I ‘ m⊔ a
⊔s t u d
e n t # #∧
串
第五章 串和数组(String and Array)
5.1
5.2 5.3
串的定义
串的表示与实现 模式匹配算法
5.4
数组
22:04:25Байду номын сангаас
串 模式匹配算法 朴素算法
5.3 朴素的模式匹配算法 Index( S, T, pos )
a a a b
0 1 2 3
长度＝m
设在第 i 个位置上匹配成功，共进行了i+m次比较；i的可 能取值范围是0..n-m, 故平均比较次数为：
E
n m i 0
C语言中, 用new申请，delete释放空间。
运行期间可以根据实际需要申请空间
22:04:25
串 串表示与实现 堆分配存储
基本运算举例：
void strcat（char *&T, char *s1, char *s2){ //将串s1和s2联结，结果存放入字符串T中 j=0; k=0; int len1=strlen(s1); len2=strlen(s2);
22:04:25
串 串表示与实现 定长顺序存储
5.2.1 定长顺序存储
用定长静态数组存储串：
#define maxsize 255 //串的最大长度
char char
s1[maxsize+1]; s2[100];
程序运行期间，数组的大小已经固定，不能变化
22:04:25
串 串表示与实现 定长顺序存储
22:04:25
//将S清为空串
// T=S1+S2
串、数组、广义表习题
3、设有两个串p和q，求q在p中首次出现的位置的运算称作( ) Ｂ．模式匹配
4、一个nⅹn的对称矩阵，如果以行或列为主序放入内存， 则其容量为( )。 A、n*n B、n*n/2
C、(n+1)*n/2 D、(n+1)*(n+1)/2 5、对数组经常进行的两种基本操作是( ) 。 A、建立与删除 C、查找与修改 B、索引与修改 D、查找与索引
（3） Head（Tail（Head((a,b),(c,d))））== （4） Tail(Head(Tail((a,b),(c,d))))==
二、选择题
1、串是一种特殊的线性表，其特殊性体现在 （ ）。 A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、数据元素可以是多个字符 2、设串s1=‘ABCDEFG’,s2=‘PQRST’,函数con(x,y)返回x和y 串的连接串，subs（s,i,j）返回串s的从序号i的字符开始的j len(s) s 个字符组成的字串， len(s)返回串s的长度，则 con(subs(s1,2,len(s2)), subs(s1,len(s2),2))的结果串是（） A）BCDEF B）BCDEFG C）BCPQRST Ａ．连接 D）BCDEFEF Ｃ．求子串 Ｄ．求串长
6、二维数组A[10..20，5..10]采用行序为主序方式存储， 每个数据元素占4个存储单元，且A[10，5]的存储地址是 1000，则A[18，9]的地址是( )。 A、1208 B、1212 C、1368 D、1364
7、现有广义表Ls=(a,(a,b),d,e,((i,j,()),k)),则该广义表的长度 是( )。 A.4 B.5 C.8 D.9
8、现有广义表Ls=(a,(a,b),d,e,((i,j,()),k)),则该广义表的深度 是( )。 A.2 B.3 C.4 D.5
数据结构：习题2(栈.队列、串、数组)
第4章 串习题 2.编写算法，实现串的基本操作compare(S,T)，相等时返回1， 不等返回0。 compare(SString S,SString T) { int i; for(i=0;i<S.len;i++) if(S.ch[i]!=T.ch[i]) return 0; if(i=S.len&&S.len==T.len) return 1; else return 0; }
2 0 3
11
第5章 数组和广义表习题 3、设有一个上三角矩阵An×n，其上三角中的元素逐行存储， 请给出计算上三角矩阵中任意元素aij位置的公式。
数 据
α 11 α 12 α 13 ⋯ α 1 n c α 22 α 23 ⋯ α 2 n α 33 ⋯ α 3n c c
c c c
α nn
按行存储： aij=Loc(a11)+(i-1)*(2n-i+2)/2+j-i 按列存储： aij=Loc(a11)+(j-1)*j/2+i-1 12
号堆栈中弹出栈顶元素并送到x /* 从i 号堆栈中弹出栈顶元素并送到x中 */ int Pop(DqStack *S,StackElementType *x,int i) { switch(i) { case 0: if(S->top[0]==-1) return(FALSE); *x=S->Stack[S->top[0]]; S->top[0]--; break; case 1: if(S->top[1]==M) return(FALSE); *x=S->Stack[S->top[1]]; S->top[1]++; break; default: return(FALSE); } return(TRUE); }
《数据结构》第四章串习题
《数据结构》第四章串习题《数据结构》第四章串习题基本概念题：4-1 设S1 =“Data Structure Course”，S2 =“Structure”，S3 =“Base”，求：（1）Length(S1)；（2）Compare(S2, S3)；（3）Insert(S1, 5, S3)；（4）Delete(S1, 5, 9)；（5）SubString(S1, 5, 9, T)；（6）Search(S1, 0, S2)；（7）Replace(S1, 0, S2, S3)4-2 什么叫串？串和字符在存储方法上有什么不同？空串和空格串是否相同，为什么？4-3 串是由字符组成的，长度为1的串和字符是否相同。
为什么？4-4 串是不定长的，表示串的长度有几种方法？C语言中的串采用哪种方法？4-5 可以说串是数据类型固定为字符类型的线性表，但是串操作和线性表操作的主要不同之处在哪里？4-6 可以用几种存储方法存储串？4-7 分别写出串的静态数组存储结构和串的动态数组存储结构的结构体定义。
4-8 为什么动态数组结构下串的实现要增加撤消函数？复杂概念题：4-9 令t1=“aaab”, t2=“abcabaa”, t3=“abcaabbabcabaacba”，试分别求出他们的next[j]值。
4-10 简述模式匹配的Brute-Force算法思想。
简述模式匹配的KMP算法思想。
4-11 简述求子串的next[j]值的算法思想。
算法设计题：4-12 设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。
要求比较结果有等于和不等于两种情况。
4-13 设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。
要求比较结果有大于、等于和小于三种情况。
4-14 设串采用动态数组存储结构，编写函数实现两个串的比较Compare(S, T)。
要求比较结果有大于、等于和小于三种情况。
数据结构习题精编：串和数组
数据结构习题精编：串和数组一、选择题1．下面关于串的的叙述中，不正确的是A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．下面关于串的的叙述中，正确的是A．空串就是空白串B．串相等指的是串的长度相等C．串的长度必须大于零D．串是一种特殊的线性表3．字符串是一种特殊的线性表，它与一般线性表的区别是A．字符串是一种线性结构B．字符串可以进行复制操作C．字符串可以顺序存储也可以链式存储D．字符串由字符构成并且通常作为整体参与操作4．串s="Data Structure"中长度为3的子串的数目是A．9B．11C．12D．145．若串S="software"，则S的子串的数目是A．8 B．35 C．36 D．376．已知串S= "string"，T="this"，执行运算StrLength(StrCopy(S,T))的结果是A．2 B．4 C．6 D．107．若串S="SCIENCESTUDY"，则调用函数StrCopy(P,SubString(S,1,7))后得到A．P="STUDY" B．P="SCIENCE" C．S="STUDY" D．S="SCIENCE" 8．若字符串采用链式存储，每个字符占用一个字节，每个指针在占用四个字节，则该字符串的存储密度为A．20%B．25%C．50%D．75%9．为查找某一特定单词在文本中出现的位置，可应用的串运算是A．串联接B．求子串C．串比较D．子串定位10．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最好情况下字符的比较次数A．m B．n C．n-m D．n+m11．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最坏情况下字符的比较次数A．m B．n C．(n-m+1)*m D．n*m12．已知串S="aaab",其Next数组的元素值依次为A．0、1、2、3 B．1、1、2、3 C．1、2、1、1 D．1、2、3、1 13．串"ababaaababaa" 的next数组为A．011234223456 B．012121111212 C．0123012322345 D．012345678999 14．字符串"ababaabab" 的nextval 为A．(0,1,0,1,0,0,0,1,1) B．(0,1,0,1,0,1,0,1,1)C．(0,1,0,1,0,2,1,0,1) D．(0,1,0,1,0,4,1,0,1)15．二维数组A[10][20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[0][0]的存储地址为300，则A[8][10]的地址为A．660 B．732 C．980 D．113216．二维数组A[5][6]采用按列为主序的存储方式，每个元素占3个存储单元，若A[0][0]的存储地址是100，则A[4][3]的存储地址是A．157 B．166 C．169 D．18117．二维数组A按行优先顺序存储，其中每个元素占1个存储单元。
数据结构习题精编：串和数组
数据结构习题精编：串和数组一、选择题1．下面关于串的的叙述中，不正确的是A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．下面关于串的的叙述中，正确的是A．空串就是空白串B．串相等指的是串的长度相等C．串的长度必须大于零D．串是一种特殊的线性表3．字符串是一种特殊的线性表，它与一般线性表的区别是A．字符串是一种线性结构B．字符串可以进行复制操作C．字符串可以顺序存储也可以链式存储D．字符串由字符构成并且通常作为整体参与操作4．串s="Data Structure"中长度为3的子串的数目是A．9B．11C．12D．145．若串S="software"，则S的子串的数目是A．8 B．35 C．36 D．376．已知串S= "string"，T="this"，执行运算StrLength(StrCopy(S,T))的结果是A．2 B．4 C．6 D．107．若串S="SCIENCESTUDY"，则调用函数StrCopy(P,SubString(S,1,7))后得到A．P="STUDY" B．P="SCIENCE" C．S="STUDY" D．S="SCIENCE" 8．若字符串采用链式存储，每个字符占用一个字节，每个指针在占用四个字节，则该字符串的存储密度为A．20%B．25%C．50%D．75%9．为查找某一特定单词在文本中出现的位置，可应用的串运算是A．串联接B．求子串C．串比较D．子串定位10．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最好情况下字符的比较次数A．m B．n C．n-m D．n+m11．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最坏情况下字符的比较次数A．m B．n C．(n-m+1)*m D．n*m12．已知串S="aaab",其Next数组的元素值依次为A．0、1、2、3 B．1、1、2、3 C．1、2、1、1 D．1、2、3、1 13．串"ababaaababaa" 的next数组为A．011234223456 B．012121111212 C．0123012322345 D．012345678999 14．字符串"ababaabab" 的nextval 为A．(0,1,0,1,0,0,0,1,1) B．(0,1,0,1,0,1,0,1,1)C．(0,1,0,1,0,2,1,0,1) D．(0,1,0,1,0,4,1,0,1)15．二维数组A[10][20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[0][0]的存储地址为300，则A[8][10]的地址为A．660 B．732 C．980 D．113216．二维数组A[5][6]采用按列为主序的存储方式，每个元素占3个存储单元，若A[0][0]的存储地址是100，则A[4][3]的存储地址是A．157 B．166 C．169 D．18117．二维数组A按行优先顺序存储，其中每个元素占1个存储单元。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
int i=start-1,j=0; while(i<s->len&&j<t->len)
if(s->data[i]==t->data[j]){ i++;j++;
}else{ i=i-j+1;j=0;
} if(j>=t->len)
return i-t->len+1; else
return -1; }
第五章 数组和广义表
8 -3 - 7 -3
1 3 9 11
压缩存储到一维数组 F[m]中，则 m 为
int i; for(i=0;i<s1->length&&i<s1->length;i++)
if(s->data[i]!=s2->data[i]) return s1->data[i]-s2->data[i];
return s1->length-s2->length; }
4、写出算法的功能。 int fun(sqstring *s,sqstring *t,int start){
Loc(a[0][0])，求按列优先顺序存放的数组元素 a[j][j](0≤i≤m-1，0≤j≤n-1)的存
储地址
。
A．Loc(a[0][0]+[(i-1)*n+j-1]*d
B．Loc(a[0][0])+[i*n+j]*d
C．Loc(a[0][0]+[(j-1)*m+i]*d
D．Loc(a[0][0])+[j*m+i]*d
A. 顺序的存储结构
B. 链式存储结构
C. 数 据 元 素 是
一个字符
D. 数据元素任意
4、设串长为 n，模式串长为 m，则 KMP 算法所需的附加空间为（ ）。
A. O(m)
B. O(n)
C. O(m*n)
D.
O(nlog2m)
5、空串和空格串（ ）。
A. 相同
B. 不相同
C. 可能相同
D. 无法确定
零元素 a11，存于 F[0]中，则应存放到 F[K]中的非零元素 aij(1≤j≤n，1≤j≤i)的下
标 i，i 与 K 的对应关系是
。
A.(2n-j+1)j/2+I-j
B.(2n-j+2)(j-1)/2+i-j
C．(2n-i+1)i/2+j-I
D．(2n-i+2)i／2+j-i
7．设有 10 阶矩阵 A，其对角线以上的元素 aij(1≤j≤10，1<i<j)均取值为-3，其他矩阵元
A. ‘ijing’
B. ‘jing&’
C. ‘ingNa’
D. ‘ing&N’
二、判断题
（ ）1、造成简单模式匹配算法BF算法执行效率低的原因是有回溯存在。
（ ）2、KMP算法的最大特点是指示主串的指针不需要回溯。
（ ）3、完全二叉树某结点有右子树，则必然有左子树。
三、填空题
1、求子串在主串中首次出现的位置的运算称为
C. 三元组和十字链表
D. 散列和十字链表
15、假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的 4×5 的稀疏矩阵是（注：
矩阵的行列下标均从 1 开始）（ ）。
0 8 0 6 0
7 0 0 0 0
A.
0 5
0 0
0 4
0 0
00
0 8 0 6 0
7 0 0 0 3
B.
5 0
素为正整数，现将矩阵 A 压缩存放在一维数组 F[m]中，则 m 为
。
A．45
B．46
C．55
D.56
8．设广义表 L=(a，b，L)其深度是
。
A．3 B． C．2 D．都不对
9．广义表 B：(d)，则其表尾是
，表头是
。
A．d B．() C．(d) D．(())
10．下列广义表是线性表的有
。
A．Ls=(a，(b，c))
并把mu和nu的值进行互换，则完成了矩阵转置。 （ ）3、稀疏矩阵压缩存储后，必会失去随机存取功能。 （ ）4、广义表的长度是指广义表中括号嵌套的层数。 （ ）5、广义表是一种多层次的数据结构，其元素可以是单原子也可以是子表。 三、填空题
1、已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元
。
4．若 n 为主串长，m 为子串长，则用简单模式匹配算法最好情况下，需要比较字符总数
是
，最坏情况下，需要比较字符总数是
。
5．设二维数组 A[8][10]中，每个数组元素占 4 个存储单元，数组元素 a[2][2]按行优先顺
序存放的存储地址是 1000，则数组元素 a[0][0]的存储地址是
。
6．设有矩阵
第四章 串
一、选择题
1、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（ ）。
A. 连接
B. 求子串
C. 模式匹配 D. 判断子串
2、已知串S=’aaab’，则next数组值为（ ）。
A. 0123
B. 1123
C. 1231
D. 1211
3、串与普通的线性表相比较，它的特殊性体现在（ ）。
while(i<s->len&&j<t->len)
if(j==-1||s->data[i]==t->data[j]){
i++;j++;
}
else j=
;
if(j>=t->len)
return(
);
else
return(-1);
}
2、函数实现串的模式匹配算法，请在空格处将算法补充完整。
int index_bf(sqstring*s,sqstring *t,int start){
B．Ls=(a，Ls)
C．Ls=(a，b)
D．Ls=(a，(()))
11.一个非空广义表的表尾
。
A．只能是子表
B．不能是子表
C．只能是原子元素
D．可以是原子元素或子表
12．已知广义表 A=((a，(b，c))，(a，(b，c)，d))，则运算 head(head(tail(A)))的结果
是
。
A．a
的值是（ ）。
A. i(i-1)/2+j-1
B. i(i-1)/2+j
C. i(i+1)/2+j-1
D. i(i+1)/2+j
13、广义表A=((a),a)的表头是（
）。
A. a
B. (a)
C. b
D. ((a))
14、稀疏矩阵一般的压缩存储方法有两种，即（
）。
A. 二维数组和三维数组
B. 三元组和散列
int i=start-1,j=0;
while(i<s->len&&j<t->len)
if(s->data[i]==t->data[j]){
i++;j++;
}else{
i=
;j=0;
}
if(j>=t->len)
return
;
else
return -1;
}}/*listDelete*/
3、写出下面算法的功能。 int function(SqString *s1,SqString *s2){
一、选择题
1、设广义表L=((a，b，c))，则L的长度和深度分别为（
）。
A. 1和1
B. 1和3
C. 1和2
D. 2和3
2、广义表((a),a)的表尾是（ B ）。
A. a
B. (a)
C. ()
D. ((a))
3、稀疏矩阵的常见压缩存储方法有（ ）两种。
A. 二维数组和三维数组
B. 三元组和散列表
A. b,c
B. (b,c)
C. c
D. (c)
9、常对数组进行两种基本操作是（ ）。
A. 建立和删除
B. 索引和修改
C. 查找和修改
D. 查找与索引
10、对一些特殊矩阵采用压缩存储的目的主要是为了（
）。
A. 表达变得简单 C. 去掉矩阵中的多余元素
B. 对矩阵元素的存取变得简单 D. 减少不必要的存储空间的开销
0 0
4 0
0 0
0 0
0 8 0 6 0
0 0 0 0 3
C.
7 5
0 0
0 4
0 0
00
0 8 0 6 0
7 0 0 0 0
D.
5 0
0 0
4 0
0 0
03
16、以下有关广义表的表述中，正确的是（ ）。
A. 由 0 个或多个原子或子表构成的有限序列
B. 至少有一个元素是子表
素的存储地址是LOC(A[0][0])，则A[i][j]的地址是___
___。
2、广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是：
。
3、二维数组，可以按照
两种不同的存储方式。
4、稀疏矩阵的压缩存储方式有：
和
。
四、综合题
1、现有一个稀疏矩阵，请给出它的三元组表。
0 3 1 0 1 0 0 0 0 2 1 0 0 0 2 0
C. 三元组和十字链表 D. 散列表和十字链表
if(s->data[i]==t->data[j]){ i++;j++;
}else{ i=i-j+1;j=0;
} if(j>=t->len)
return i-t->len+1; else
return -1; }
第五章 数组和广义表
8 -3 - 7 -3
1 3 9 11
压缩存储到一维数组 F[m]中，则 m 为
int i; for(i=0;i<s1->length&&i<s1->length;i++)
if(s->data[i]!=s2->data[i]) return s1->data[i]-s2->data[i];
return s1->length-s2->length; }
4、写出算法的功能。 int fun(sqstring *s,sqstring *t,int start){
Loc(a[0][0])，求按列优先顺序存放的数组元素 a[j][j](0≤i≤m-1，0≤j≤n-1)的存
储地址
。
A．Loc(a[0][0]+[(i-1)*n+j-1]*d
B．Loc(a[0][0])+[i*n+j]*d
C．Loc(a[0][0]+[(j-1)*m+i]*d
D．Loc(a[0][0])+[j*m+i]*d
A. 顺序的存储结构
B. 链式存储结构
C. 数 据 元 素 是
一个字符
D. 数据元素任意
4、设串长为 n，模式串长为 m，则 KMP 算法所需的附加空间为（ ）。
A. O(m)
B. O(n)
C. O(m*n)
D.
O(nlog2m)
5、空串和空格串（ ）。
A. 相同
B. 不相同
C. 可能相同
D. 无法确定
零元素 a11，存于 F[0]中，则应存放到 F[K]中的非零元素 aij(1≤j≤n，1≤j≤i)的下
标 i，i 与 K 的对应关系是
。
A.(2n-j+1)j/2+I-j
B.(2n-j+2)(j-1)/2+i-j
C．(2n-i+1)i/2+j-I
D．(2n-i+2)i／2+j-i
7．设有 10 阶矩阵 A，其对角线以上的元素 aij(1≤j≤10，1<i<j)均取值为-3，其他矩阵元
A. ‘ijing’
B. ‘jing&’
C. ‘ingNa’
D. ‘ing&N’
二、判断题
（ ）1、造成简单模式匹配算法BF算法执行效率低的原因是有回溯存在。
（ ）2、KMP算法的最大特点是指示主串的指针不需要回溯。
（ ）3、完全二叉树某结点有右子树，则必然有左子树。
三、填空题
1、求子串在主串中首次出现的位置的运算称为
C. 三元组和十字链表
D. 散列和十字链表
15、假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的 4×5 的稀疏矩阵是（注：
矩阵的行列下标均从 1 开始）（ ）。
0 8 0 6 0
7 0 0 0 0
A.
0 5
0 0
0 4
0 0
00
0 8 0 6 0
7 0 0 0 3
B.
5 0
素为正整数，现将矩阵 A 压缩存放在一维数组 F[m]中，则 m 为
。
A．45
B．46
C．55
D.56
8．设广义表 L=(a，b，L)其深度是
。
A．3 B． C．2 D．都不对
9．广义表 B：(d)，则其表尾是
，表头是
。
A．d B．() C．(d) D．(())
10．下列广义表是线性表的有
。
A．Ls=(a，(b，c))
并把mu和nu的值进行互换，则完成了矩阵转置。 （ ）3、稀疏矩阵压缩存储后，必会失去随机存取功能。 （ ）4、广义表的长度是指广义表中括号嵌套的层数。 （ ）5、广义表是一种多层次的数据结构，其元素可以是单原子也可以是子表。 三、填空题
1、已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元
。
4．若 n 为主串长，m 为子串长，则用简单模式匹配算法最好情况下，需要比较字符总数
是
，最坏情况下，需要比较字符总数是
。
5．设二维数组 A[8][10]中，每个数组元素占 4 个存储单元，数组元素 a[2][2]按行优先顺
序存放的存储地址是 1000，则数组元素 a[0][0]的存储地址是
。
6．设有矩阵
第四章 串
一、选择题
1、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（ ）。
A. 连接
B. 求子串
C. 模式匹配 D. 判断子串
2、已知串S=’aaab’，则next数组值为（ ）。
A. 0123
B. 1123
C. 1231
D. 1211
3、串与普通的线性表相比较，它的特殊性体现在（ ）。
while(i<s->len&&j<t->len)
if(j==-1||s->data[i]==t->data[j]){
i++;j++;
}
else j=
;
if(j>=t->len)
return(
);
else
return(-1);
}
2、函数实现串的模式匹配算法，请在空格处将算法补充完整。
int index_bf(sqstring*s,sqstring *t,int start){
B．Ls=(a，Ls)
C．Ls=(a，b)
D．Ls=(a，(()))
11.一个非空广义表的表尾
。
A．只能是子表
B．不能是子表
C．只能是原子元素
D．可以是原子元素或子表
12．已知广义表 A=((a，(b，c))，(a，(b，c)，d))，则运算 head(head(tail(A)))的结果
是
。
A．a
的值是（ ）。
A. i(i-1)/2+j-1
B. i(i-1)/2+j
C. i(i+1)/2+j-1
D. i(i+1)/2+j
13、广义表A=((a),a)的表头是（
）。
A. a
B. (a)
C. b
D. ((a))
14、稀疏矩阵一般的压缩存储方法有两种，即（
）。
A. 二维数组和三维数组
B. 三元组和散列
int i=start-1,j=0;
while(i<s->len&&j<t->len)
if(s->data[i]==t->data[j]){
i++;j++;
}else{
i=
;j=0;
}
if(j>=t->len)
return
;
else
return -1;
}}/*listDelete*/
3、写出下面算法的功能。 int function(SqString *s1,SqString *s2){
一、选择题
1、设广义表L=((a，b，c))，则L的长度和深度分别为（
）。
A. 1和1
B. 1和3
C. 1和2
D. 2和3
2、广义表((a),a)的表尾是（ B ）。
A. a
B. (a)
C. ()
D. ((a))
3、稀疏矩阵的常见压缩存储方法有（ ）两种。
A. 二维数组和三维数组
B. 三元组和散列表
A. b,c
B. (b,c)
C. c
D. (c)
9、常对数组进行两种基本操作是（ ）。
A. 建立和删除
B. 索引和修改
C. 查找和修改
D. 查找与索引
10、对一些特殊矩阵采用压缩存储的目的主要是为了（
）。
A. 表达变得简单 C. 去掉矩阵中的多余元素
B. 对矩阵元素的存取变得简单 D. 减少不必要的存储空间的开销
0 0
4 0
0 0
0 0
0 8 0 6 0
0 0 0 0 3
C.
7 5
0 0
0 4
0 0
00
0 8 0 6 0
7 0 0 0 0
D.
5 0
0 0
4 0
0 0
03
16、以下有关广义表的表述中，正确的是（ ）。
A. 由 0 个或多个原子或子表构成的有限序列
B. 至少有一个元素是子表
素的存储地址是LOC(A[0][0])，则A[i][j]的地址是___
___。
2、广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是：
。
3、二维数组，可以按照
两种不同的存储方式。
4、稀疏矩阵的压缩存储方式有：
和
。
四、综合题
1、现有一个稀疏矩阵，请给出它的三元组表。
0 3 1 0 1 0 0 0 0 2 1 0 0 0 2 0
C. 三元组和十字链表 D. 散列表和十字链表