严蔚敏版数据结构习题及参考答案1

（2）删除（即出队）算法： delete(LinkList *rear)

{ //设循环链队列的队尾指针为rear

if (rear= =NULL) //空队

printf(\

if(rear->next= =rear) //队中只有一个结点 rear=NULL; else

rear->next=rear->next->next; //rear->next指向的结点为循环链队列的队头结点

}

8．只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：

int InsertDecreaseList( SqList *L, elemtype x ) { int i;

if ( (*L).len>= maxlen) { printf(“overflow\ return(0); }

for ( i=(*L).len ; i>0 && (*L).elem[ i-1 ] < x ; i--)

(*L).elem[ i ]=(*L).elem[ i-1 ] ; // 比较并移动元素 (*L).elem[ i ] =x; (*L).len++;

return(1);

}

习题3

一、单项选择题

1. 空串与空格字符组成的串的区别在于（ ）。

A.没有区别 C.两串的长度相等

B.两串的长度不相等

D.两串包含的字符不相同

2. 一个子串在包含它的主串中的位置是指（ ）。

A.子串的最后那个字符在主串中的位置

B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置 D.子串的第一个字符在主串中首次出现的位置

3. 下面的说法中，只有（ ）是正确的。

A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数

C.若T包含在S中，则T一定是S的一个子串 D.一个字符串不能说是其自身的一个子串

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

A.两串的长度相等 B.两串包含的字符相同

C.两串的长度相等，并且两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同

5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ ）。

A. “ijing” C. “ingNa”

（S，T）=（ ）。

A.2 B.3 C.4 D.5

7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。

A. “Nanjing＆Shanghai” C. “ShanghaiNanjing”

B. “Nanjing＆Nanjing” D. “Shanghai＆Nanjing”

B. “jing＆” D. “ing＆N”

6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX

8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（ ）。

A.i＞0 B. i≤n C.1≤i≤n D.1≤i≤n+1

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

A.链表的长度为1 B.链表中只存放1个字符

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

二、填空题

1. 计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。

2. 两个字符串相等的充要条件是_____________________和___________________。

3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。

4. 串是指___________________。

5. 空串是指___________________，空格串是指___________________。 三、算法设计题

1. 设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，m

2. 设s和t是表示成单链表的两个串，试编写一个找出s中第1个不在t中出现的字符（假定每个结点只存放1个字符）的算法。

习题3参考答案

一、单项选择题

1．B 2．D 3．C 4．D 5．B 6．C 7．D 8．C 9．D 二、填空题

1. 固定长度，设置长度指针

2. 两个串的长度相等，对应位置的字符相等 3. “BCDEDE”

4. 含n个字符的有限序列 （n≥0）

5. 不含任何字符的串，仅含空格字符的字符串 三、算法设计题 1．算法描述为：

int delete(r,s,t,m) //从串的第m个字符以后删除长度为t的子串 char r[ ]; int s,t,m; { int i,j;

for(i=1;i<=m;i++)

r[s+i]=r[i];

for(j=m+t-i;j<=s;j++)

r[s-t+j]=r[j]; return (1);

} //delete 2．算法思想为：

（1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较；

（2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较； （3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。

设单链表类型为LinkList；注意，此时类型 LinkList中的data成分为字符类型。 LinkString find(s,t) LinkString *s, *t; { LinkString *ps, *pt; ps=s;

while(ps!=NULL) { pt=t;

while((pt!=NULL)&&(ps->data!=pt->data)) pt=pt->next; if(pt= =NULL)

ps=NULL;

else

{ ps=ps->next;

s=ps;

}

} return s;

} //find

习题4

一、单项选择题

1. 设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（ ）。

A.p +[i*n+j-1]*k

B.p+[(i-1)*n+j-1]*k D.p+[j*n+i-1]*k

C.524

D.518

C.p+[(j-1)*n+i-1]*k A.520

B.522

2. 已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（ ）。 3. 若数组A[0…m][0…n]按列优先顺序存储，则aij地址为（ ）。 A.LOC(a00)+[j*m+i] C.LOC(a00)+[(j-1)*n+i-1] （设每个元素占d个字节）

B. LOC(a00)+[j*n+i] D. LOC(a00)+[(j-1)*m+i-1]

4. 若下三角矩阵An×n，按列顺序压缩存储在数组Sa[0…(n+1)n/2]中，则非零元素aij的地址为（ ）。

(j?2)(j?1)+i-1]*d

2(j?2)(j?1)B. [(j-1)*n-+i]*d

2(j?2)(j?1)C．[(j-1)*n-+i+1]*d

2(j?2)(j?1)D．[(j-1)*n-+i-2]*d

2A. [(j-1)*n-5. 设有广义表D=(a,b,D)，其长度为（ ），深度为（ ）。 A.无穷大 A.a A.x

B.3

C.2 C.空表

D.5 D.(a)

6. 广义表A=（a），则表尾为（ ）。

B.(( ))

7. 广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（ ）。

B.(a,B) C.(x,(a,B)) D.A

B.A=(s,(a,B))

D.D=((a,B),(c,(a,B),D)

8. 下列广义表用图来表示时，分支结点最多的是（ ）。 A.L=((x,(a,B)),(x,(a,B),y)) C.B=((x,(a,B),y))