中数据元素非递减有序排列。 2.8将2.7题中L的存储结构改为单链表，写出相应的实现算法。 2.9设有两个非递减有序的单链表A和B。请写出算法，将A和B“就地”归并 成一个按元素值非递增有序的单链表C。 2.10设有一个长度大于1的单向循环链表，表中既无头结点，也无头指针，s 为指向表中某个结点的指针，如图2-1所示。试编写一个算法，别除链表中指针 s所指结点的直接前驱。 待删结点3个 图2-1 2.11已知线性表用带头结点的单链表表示，表中结点由三类字符组成：字母、 数字和其他字符。试编写算法，将该线性链表分割成三个循环单链表，每个循环 单链表中均只含有一类字符。 2.12已知线性表用顺序存储结构表示，表中数据元素为个正整数。试写一算 法，分离该表中的奇数和偶数，使得所有奇数集中放在左侧，偶数集中放在右侧。 要求：(1)不借助辅助数组：(2)时间复杂度为0()。 2.13设以带头结点的双向循环链表表示的线性表L=(a,a,a,,a。试写 时间复杂度为0(m)的算法，将L改造为L=(a,as,,a,,a4,a)。 第四章栈和队列 思考题： 3.1简述栈和线性表的差别。 3.2如果进栈序列为A、B、C、D,写出所有可能的出栈序列。 3.3简述栈和队列的相同点和差异。 第3页中数据元素非递减有序排列。 2.8 将 2.7 题中 L 的存储结构改为单链表，写出相应的实现算法。 2.9 设有两个非递减有序的单链表 A 和 B。请写出算法，将A和B“就地”归并 成一个按元素值非递增有序的单链表 C。 2.10 设有一个长度大于 1 的单向循环链表，表中既无头结点，也无头指针，s 为指向表中某个结点的指针,如图 2-1 所示。试编写一个算法，删除链表中指针 s 所指结点的直接前驱。 待删结点 s 图 2-1 2.11 已知线性表用带头结点的单链表表示，表中结点由三类字符组成：字母、 数字和其他字符。试编写算法，将该线性链表分割成三个循环单链表，每个循环 单链表中均只含有一类字符。 2.12 已知线性表用顺序存储结构表示，表中数据元素为 n 个正整数。试写一算 法，分离该表中的奇数和偶数，使得所有奇数集中放在左侧，偶数集中放在右侧。 要求：(1)不借助辅助数组;(2)时间复杂度为 O(n)。 2.13 设以带头结点的双向循环链表表示的线性表L=(a1,a2,a3,...,an)。试写一 时间复杂度为O(n)的算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。 第四章 栈和队列 思考题： 3.1 简述栈和线性表的差别。 3.2 如果进栈序列为 A、B、C、D，写出所有可能的出栈序列。 3.3 简述栈和队列的相同点和差异。 第 3 页