数据结构 1-5章习题.ppt

习题 Chap. 2 1.试写出在顺序存储结构下逆转线性表的算法，要求使用最小的附加空间。 2.从顺序存储结构的线性表a中删除第i个元素起的k个元素。 3.已知线性表中的元素非递减有序排列，并以带头结点的单链表作存储结构。试写一高效的算法，删除表中所有值相同的多余元素。 Chap. 2 4.试写倒排线性单链表的算法。 5.设对循环链表，实现如下算法： (1)合并两个表； (2)表格表的交运算； (3)删去第i个结点的前驱结点； (4)把第i个结点向前移动n个位置； 6.设L为顺序存储结构线形表，删去其中的所有零元素。 Chap. 3 1.写出如下中缀表达式的后缀形式： (1)A*B*C； (2)-A+B-C+D； (3)(A+B)*D+E/(F+A*D)+C； 2.设用循环链表表示队列，给出进队、出对、判断对空的算法。 3.编写一个用两个栈实现队列的算法。 4.编写一个判断表达式中“（）”、“[]”是否配对的算法。 Chap. 4 1.编写算法replace(string S, string t, string v)，将字符串S中的所有子串t用字符串v替换。 2.编写一算法计算模式串t在串S中出现的频率。 Chap. 5 1.试将稀疏矩阵A的非零元素表示成三元组的形式和十字链表的形式： A= 2.试编写一个以三元组形式输出十字链表表示的稀疏矩阵中非零元素的算法。 3.分别实现以三元组存储、十字链表存储稀疏矩阵的加法操作A=A+B的算法，并分析各自的时间复杂性。 Chap. 5 4.设GetHead为CAR，GetTail为CDR，求下列广义表的运算结果： (1)CAR((x, y, z)) (2)CDR((x, y, z)) (3)CAR(((a, b), (x, y))) (4)CDR(((a, b), (x, y))) (5)CAR(CDR(((a, b), (x, y)))) (6)CDR(CDR(((a, b), (x, y)))) (7)CAR(CDR(CDR(((a, b), (x, y))))) Chap. 5 5.设广义表 A=((a,b),(a,(b,(c))),d,((a,c),d)) 求表头、表尾。并画出类似于图5.9的结构示意图。 * * * * * *