内容发布更新时间 : 2024/5/18 13:23:38星期一 下面是文章的全部内容请认真阅读。

习题四 串

一、单项选择题

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=“software”,其子串的个数是（ ）。

A．8 B．37 C．36 D．9

二、填空题

1．含零个字符的串称为______串。任何串中所含______的个数称为该串的长度。

2．空格串是指__ __，其长度等于__ __。

3．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。

4．INDEX（‘DATASTRUCTURE’， ‘STR’）=________。

5．模式串P=‘abaabcac’的next函数值序列为________。

6．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f(\返回1，f(\返回0；

int f((1)__ ______) {int i=0,j=0;

while (s[j])(2)___ _____;

for(j--; i

7．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。

void maxcomstr(orderstring *s,*t; int index, length) {int i,j,k,length1,con; index=0;length=0;i=1;

14

while (i<=s.len) {j=1;

while(j<=t.len)

{ if (s[i]= =t[j])

{ k=1;length1=1;con=1;

while(con)

if (1) _ { length1=length1+1;k=k+1; }

else (2) __;

if (length1>length) { index=i; length=length1; } (3)__ __;

}

else (4) ___; }

(5) __ } }

三、应用题

1．描述以下概念的区别：空格串与空串。

2．设有 A=” ”,B=\，C=\，D=\试计算下列运算的结果(注:A+B是CONCAT（A,B）的简写,A=\的 \含有两个空格)。 (a) A+B (b) B+A (c) D+C+B

(d) SUBSTR(B,3,2) (e) SUBSTR(C,1,0) (f) LENGTH(A) (g) LENGTH(D) (h) INDEX(B,D) (i) INDEX(C,\(j) INSERT(D,2,C) (k) INSERT(B,1,A) (l) DELETE(B,2,2) (m) DELETE(B,2,0)

3．设主串S=‘xxyxxxyxxxxyxyx’，模式串T=‘xxyxy’。请问：如何用最少的比较次数找到T在S中出现的位置？相应的比较次数是多少？

4．给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。

5．已知：s ＝“（xyz）＋＊”，t ＝“（x＋z）＊y”。试利用联结、求子串和置换等基本运算，将 s 转化为 t 。

四、算法设计题

15

1．在顺序串上实现串的判等运算EQUAL(S,T)。

2．在链串上实现判等运算EQUAL(S,T)。

3．若S和T是用结点大小为1的单链表存储的两个串（S、T为头指针），设计一个算法将串S中首次与串T匹配的子串逆值。

4． 以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。（如果字符串的一个子串（其长度大于1）的各个字符均相同，则称之为等值子串。如果输入字符串S，以“！”作为结束标志。串S中不存在等值子串，则输出信息“无等值子串”，否则求出（输出）一个长度最大的等值子串。例如：若S=“abc123abc123!”，则输出“无等值子串”；若S=“abceebccadddddaaadd!”，则输出“ddddd”。）

5．写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。

16

习题五 数组和广义表

一、单项选择题

1．常对数组进行的两种基本操作是（ ）

A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引 2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定.

A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*k B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[i,j]=[(n+1)*i+j]*k

3．稀疏矩阵的压缩存储方法是只存储 ( )

A.非零元素 B. 三元祖（i,j, aij） C. aij D. i,j 4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

A. 1175 B. 1180 C. 1205 D. 1210 5. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ ）。

A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1 6. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。

A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next 7. 对稀疏矩阵进行压缩存储目的是（ ）。

A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度

8. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。

A. head(tail(LS)) B. tail(head(LS))

C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 9. 广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。

A. a B.（） C.（a,b,c,d） D.（b,c,d） 10. 设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。

A. 1和1 B. 1和3 C. 1和2 D. 2和3 11. 下面说法不正确的是( )。

A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构

二、填空题

1．通常采用___________存储结构来存放数组 。对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。

2. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第_ _行，第_ _列的元素。

17

3．设n行n列的下三角矩阵A已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j]对应的B中存储位置为_______。

4. 所谓稀疏矩阵指的是_ 。

5. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于____ 。为了区分原子和表，一般用 ____表示表，用 _____表示原子。一个表的长度是指 __，而表的深度是指__ __ 6．设广义表L=((),()), 则head(L)是 ；tail(L)是 ；L的长度是 ；深度是 __。

7．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在___________处用适当的句子用以填充。

Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b) { (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu; if(a.tu) { q=1;

for(col=1; ___________;col++) for(p=1;p<=a.tu;p++) if(___________==col)

{(*b).data[q].i=a.data[p].j; (*b).data[q].j=a.data[p].i; (*b).data[q].v=a.data[p].v; ___________; }

}

8. 完善下列程序。下面是一个将广义表逆置的过程。例如原来广义表为（（a,b）,c,（d,e）），经逆置后为：（（e,d）,c,（b,a））。

typedef struct glistnode {int tag;

struct glistnode *next; union{char data;

struct{struct glistnode *hp,*tp;}ptr; }val; }*glist,gnode; glist reverse(p) glist p;

{glist q,h,t,s; if(p==NULL) q=NULL; else

{if(1) { q=(glist)malloc(sizeof(gnode)); q->tag=0;

18