法将A表和B表归并成一个按元素值递减有序(即非递增有序,允许值相同)排列的线性表 C,并要求利用原表(即A表和B表的)结点空间存放表C 5.设有线性表A=(a,a,,,,a)和B=(b,b,.,b).试写合并A、B为线性表C的算法, 使得: j(al, bl,,am, bm, bm+l, bn)= m<=n; (al, bl,an,bn, an+l, am)=m>n 假设A、B均以单链表为存储结构(并且m、n显示保存)。要求C也以单链表为存储结构并利 用单链表A、B的结点空间 6,设线性表存放在向量A[ arrslze]的前 plenum分量中,且递增有序。试写一算法,将X插 入到线性表的适当位置上,以保持线性表的有序性,并且分析算法的时间复杂性。 7.已知单链表L中的结点是按值非递减有序排列的,试写一算法将值为x的结点插入表L 中,使得L仍然有序。 8,试分别以顺序表和单链表作存储结构,各写一个实现线性表的就地(即使用尽可能少的附 加空间)逆置的算法,在原表的存储空间内将线性表(a1,a,,.,an)逆置为(an,,,a,a1) 9.假设分别以两个元素值递增有序的线性表A、B表示两个集合(即同一线性表中的元素各不 相同),现要求构成一个新的线性表C,C表示集合A与B的交,且C中元素也递增有序。试 分别以顺序表和单链表为存储结构,填写实现上述运算的算法。 0,已知A、B和C为三个元素值递增有序的线性表,现要求对表A作如下运算:删去那些 既在表B中出现又在表C中出现的元素。试分别以两种存储结构(一处种顺序结构,一种链式 的)编写实现上述运算的算法 1.假设在长度大于1的循环链表中,既无头结点也无头指针。s为指向链表中某个结点的 指针,试编写算法删除结点*s的前趋结点 12.已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写 算法,构造三个循环链表,使每个循环链表中只含同一类的字符,且利用原表中的结点空间 作为这三个表的结点空间(头结点可另辟空间)。 13.( Josephus环)任给正整数n、k,按下述方法可得排列1,2,……,n的一个置换:将数字 ,2,,..,n环形排列(如图算法设计题13.所示),按顺时针方向从1开始计数:计满 时输出该为之上的数字(并从环中删去该数字),然后从下一个数字开始继续计数,直到环中 所有数字均被输出为止。例如,n=10,k=3时,输出的置换是3,6,9,2,7,1,8,5,10, n-1 算法设计题13.图 4。试编写一算法,对输人的任意正整数n、k,输出相应的置换 4·在双链表上实现线性表的下列基本运算(a)初始化:(b)定位(c)插入(d)删除。 15·设有一双链表,每个结点中除有 prior、data和next三个域外,还有一个访问频度域 freq,在链表被起用之前,其值均初始化为零。每当在双链表上进行一次 LOCATEL,X)运算 时,令元素值为X的结点中freq域的值增1,并使此链表中结点保持按访问频度递减的顺序 排列,以便使频繁访问的结点总是靠近表头。试编写实现符合上述要求的 LOCATE运算的算法。 16·若X和Y是用结点大小为1单链表表示的串,设计一个算法找出X中第一个不在y中出10 法将 A 表和 B 表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表 C，并要求利用原表(即 A 表和 B 表的)结点空间存放表 C。 5．设有线性表 A=(a1,a2,.. .,am)和 B=(b1,b2,.. .,bn).试写合并 A、B 为线性表 C 的算法， 使得： C=    +  + = (a1,b1,...,an,bn,an 1,...,am) m n; (a1,b1,...,am,bm,bm 1,bn) m n; 当 当 假设 A、B 均以单链表为存储结构(并且 m、n 显示保存)。要求 C 也以单链表为存储结构并利 用单链表 A、B 的结点空间。 6，设线性表存放在向量 A[arrsize]的前 elenum 分量中，且递增有序。试写一算法，将 X 插 入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂性。 7．已知单链表 L 中的结点是按值非递减有序排列的，试写一算法将值为 x 的结点插入表 L 中，使得 L 仍然有序。 8，试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附 加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2,.. .,an)逆置为(an,.. .,a2,a1)。 9．假设分别以两个元素值递增有序的线性表 A、B 表示两个集合(即同一线性表中的元素各不 相同)，现要求构成一个新的线性表 C，C 表示集合 A 与 B 的交，且 C 中元素也递增有序。试 分别以顺序表和单链表为存储结构，填写实现上述运算的算法。 10，已知 A、B 和 C 为三个元素值递增有序的线性表，现要求对表 A 作如下运算： 删去那些 既在表 B 中出现又在表 C 中出现的元素。试分别以两种存储结构(一处种顺序结构，一种链式 的)编写实现上述运算的算法。 11．假设在长度大于 1 的循环链表中，既无头结点也无头指针。s 为指向链表中某个结点的 指针，试编写算法删除结点*s 的前趋结点。 12．已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写 算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间 作为这三个表的结点空间(头结点可另辟空间)。 13.(Josephus 环)任给正整数 n、k，按下述方法可得排列 1，2，……,n 的一个置换:将数字 1，2，.. .,n 环形排列(如图算法设计题 13.所示)，按顺时针方向从 1 开始 计数；计满 K 时输出该为之上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中 所有数字均被输出为止。例如，n=10,k=3 时，输出的置换是 3，6，9，2，7，1，8，5，10， 4。试编写一算法，对输人的任意正整数 n、k，输出相应的置换 14·在双链表上实现线性表的下列基本运算(a)初始化； (b)定位(c)插入(d)删除。 15·设有一双链表，每个结点中除有 prior、data 和 next 三个域外，还有一个访问频度域 freq，在链表被起用之前，其值均初始化为零。每当在双链表上进行一次 LOCATEL，X)运算 时，令元素值为 X 的结点中 freq 域的值增 1，并使此链表中结点保持按访问频度递减的顺序 排列，以便使频繁访问的结点总是靠近表头。试编写实现符合上述要求的 LOCATE 运算的算法。 16·若 X 和 Y 是用结点大小为 1 单链表表示的串，设计一个算法找出 X 中第一个不在 y 中出