耿国华 - 数据结构 - C语言的描述 - 课后大部分习题答案[1]

直到队列成为空队列为止,则是否可能得到输出序列:

(1) A、C、E、C、C (2) A、C、E (3) A、C、E、C、C、C (4 ) A、C、E、C [提示]:

A、B、C、D、E (输出队首元素A )

A、B、C、D、E、A (把队首元素A 插入到队尾) B、C、D、E、A (删除队首元素A ) C、D、E、A (再次删除队首元素B) C、D、E、A (输出队首元素C)

C、D、E、A、C (把队首元素C 插入到队尾) D、E、A、C (删除队首元素C) E、A、C (再次删除队首元素D )

3. 给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满? 4. 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,画出对下列算术表达式求值时操作数栈和运算符栈的变化过程: A -B *C/D+E↑F

5. 试写一个算法,判断依次读入的一个以@为结束符的字母序列,是否为形如‘序列1&序列2’模式的字符序列。其中序列1 和序列2 中都不含字符’&’,且序列2 是序列 1的逆序列。例如,‘a+b&b+a’是属该模式的字符序列,而‘1+ 3& 3-1’则不是。 [提示]:

(1) 边读边入栈,直到&

(2 ) 边读边出栈边比较,直到??

6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法,将一个通常书写形式(中缀)且书写正确的表达式转换为逆波兰式(后缀)。 [提示]: 例:

中缀表达式:a+b 后缀表达式: ab+

中缀表达式:a+b×c 后缀表达式: abc×+ 中缀表达式:a+b×c-d 后缀表达式: abc×+d- 中缀表达式:a+b×c-d/e 后缀表达式: abc×+de/- 中缀表达式:a+b×(c-d)-e/f 后缀表达式: abcd-×+ef/- ? 后缀表达式的计算过程:(简便) 顺序扫描表达式,

(1) 如果是操作数,直接入栈;

(2 ) 如果是操作符op,则连续退栈两次,得操作数X, Y,计算X op Y,并将结果入栈。

? 如何将中缀表达式转换为后缀表达式? 顺序扫描中缀表达式,

(1)如果是操作数,直接输出;

(2 )如果是操作符op ,则与栈顶操作符op 比较: 如果op > op ,则op 入栈; 如果op = op ,则脱括号; 如果op < op ,则输出op ;

7. 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设

头指针),试编写相应的队列初始化、入队列和出队列的算法。 [提示]: 参P.56 P.70 先画图. typedef LinkList CLQueue; int InitQueue(CLQueue * Q)

int EnterQueue(CLQueue Q, QueueElementType x) int DeleteQueue(CLQueue Q, QueueElementType *x)

8. 要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag ,以tag 为0 或 1来区分头尾指针相同时的队列状态的空与满,请编写与此结构相应的入队与出队算法。 [提示]:

初始状态:front==0, rear==0, tag==0 队空条件:front==rear, tag==0 队满条件:front==rear, tag==1

其它状态:front !=rear, tag==0 (或1、2 ) 入队操作: ?

?(入队)

if (front==rear) tag=1;(或直接tag=1 ) 出队操作: ?

?(出队) tag=0;

[问题]:如何明确区分队空、队满、非空非满三种情况?

9. 简述以下算法的功能(其中栈和队列的元素类型均为int): (1)void proc_1(Stack S) { int i, n, A[255]; n=0;

while(!EmptyStack(S))

{n++; Pop(&S, &A[n]);} for(i=1; i<=n; i++) Push(&S, A[i]); }

将栈 S 逆序。

(2 )void proc_2(Stack S, int e) { Stack T; int d; InitStack(&T);

while(!EmptyStack(S)) { Pop(&S, &d);

if (d!=e) Push( &T, d); }

while(!EmptyStack(T)) { Pop(&T, &d); Push( &S, d); } }

删除栈 S 中所有等于e 的元素。 (3)void proc_3(Queue *Q) { Stack S; int d; InitStack(&S);

while(!EmptyQueue(*Q)) {

DeleteQueue(Q, &d); Push( &S, d); }

while(!EmptyStack(S)) { Pop(&S, &d); EnterQueue(Q,d) } }

将队列 Q 逆序。

第四章

1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。给出下列操作的结果: StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); [参考答案]

StrLength(s)=14; sub1= ’I AM A_’; sub2= ’_’; StrIndex(s,’A’,4)=6; StrReplace(s,’STUDENT’,q)= ’I AM A WORKER’;

StrCat(StrCat(sub1,t), StrCat(sub2,q))= ’I AM A GOOD WORKER’; 2. 编写算法,实现串的基本操作 StrReplace(S,T,V)。

3. 假设以块链结构表示串,块的大小为 1,且附设头结点。 试编写算法,实现串的下列基本操作:

StrAsign(S,chars) ; StrCopy(S,T) ; StrCompare(S,T) ; StrLength(S) ; StrCat(S,T) ;

SubString(Sub,S,pos,len)。 [说明]:用单链表实现。

4.叙述以下每对术语的区别:空串和空格串;串变量和串常量;主串和子串;串变量的名字和串变量的值。

5.已知:S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作,将 S 转换为T.

6.S 和T 是用结点大小为 1 的单链表存储的两个串,设计一个算法将串S 中首次与T匹配的子串逆置。

7.S 是用结点大小为4 的单链表存储的串,分别编写算法在第k 个字符后插入串T,及从第k 个字符删除len 个字符。 以下算法用定长顺序串: 8.写下列算法:

(1) 将顺序串r 中所有值为ch1 的字符换成ch2 的字符。 (2 )将顺序串r 中所有字符按照相反的次序仍存放在r 中。 (3) 从顺序串r 中删除其值等于ch 的所有字符。

(4 ) 从顺序串r1 中第index个字符起求出首次与串r2 相同的子串的起始位置。 (5) 从顺序串r 中删除所有与串r1 相同的子串。

9.写一个函数将顺序串s1 中的第i 个字符到第j 个字符之间的字符用 s2 串替换。 [提示]:(1)用静态顺序串 (2 )先移位,后复制 10. 写算法,实现顺序串的基本操作 StrCompare(s,t)。 11. 写算法,实现顺序串的基本操作 StrReplace(&s,t,v)。 [提示]:

(1) 被替换子串定位(相当于第9 题中i)

(2 ) 被替换子串后面的字符左移或右移(为替换子串准备房间) (3) 替换子串入住(复制) (4 ) 重复上述,直到??

第五章

1.假设有 6 行 8 列的二维数组A,每个元素占用6 个字节,存储器按字节编址。已知A 的基地址为 1000,计算:

(1) 数组A 共占用多少字节; (288 ) (2 ) 数组A 的最后一个元素的地址; (1282) (3) 按行存储时,元素A36 的地址; (1126) (4 ) 按列存储时,元素A36 的地址; (1192) [注意]:本章自定义数组的下标从1 开始。

2. 设有三对角矩阵(a),将其三条对角线上的元素逐行地存于数组B(1:3n-2)中,使得 ij n×n B[k]= aij ,求:

(1) 用i,j 表示k 的下标变换公式; (2 ) 用k 表示i,j 的下标变换公式。 i = k/3 + 1, j = k%3 + i - 1 = k%3 + k/3 或:

i = k/3 + 1, j = k - 2 ×( k/3 )

2.假设稀疏矩阵 A 和 B 均以三元组表作为存储结构。试写出矩阵相加的算法,另设三元

组表C 存放结果矩阵。

[提示]:参考P.28 例、P.47 例。

4.在稀疏矩阵的快速转置算法5.2 中,将计算position[col]的方法稍加改动,使算法 只占用一个辅助向量空间。

5.写一个在十字链表中删除非零元素aij 的算法。 [提示]:“删除”两次,释放一次。

6.画出下面广义表的两种存储结构图示: ((((a), b)), ((( ), d), (e, f))) 7.求下列广义表运算的结果: (1) HEAD[((a,b),(c,d))]; (2 ) TAIL[((a,b),(c,d))];

(3) TAIL[HEAD[((a,b),(c,d))]];

(4 ) HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b (5) TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d) 第六章

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4