内容发布更新时间 : 2024/12/31 20:21:04星期一 下面是文章的全部内容请认真阅读。
直到队列成为空队列为止，则是否可能得到输出序列：
（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 ＊Ｃ／Ｄ＋Ｅ↑Ｆ
5. 试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1&序列2’模式的字符序列。其中序列1 和序列2 中都不含字符’&’，且序列2 是序列 1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+ ３& ３－１’则不是。 [提示]：
（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) 第六章