08.已知在一个数组A[m+n]中依次存放着两个线性表(a1,a2,...,am)和(b1,b2,...,bn).编写一个函数,将数组中的两个顺序表的位置互换,即将(b1,b2,...,bn)放在(a1,a2,...,am)的前面
10.[2010统考真题]设将n(n>1)个整数存放到一维数组R中,设计一个在时间和空间两方面都尽可能高效的算法.将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据由(X0,X1,...,Xn-1)变换为(Xp,Xp+1,...,Xn-1,X0,X1,...,Xp-1).
11.[2011统考真题]一个长度为L(L>=1)的升序序列S,处在L/2上取整位置的数称为S的中位数.现给定两个等长的升序序列A和B,设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列整体的中位数.
12.[2013统考真题]已知一个整数序列A=(a0,a1,...,an-1),其中0<=ai<n(0<=i<n).若存在ap1=ap2=...=apm=x且m>n/2(0<=pk<n,1<=k<=m),则称x为A的主元素.例如A=(0,5,5,3,5,7,5,5),则5为主元素;又如:A=(0,5,5,3,5,1,5,7),则A没有主元素.设计高效的算法,找出主元素并输出,若没有则输出-1
14.[2022统考真题]定义三元组(a,b,c)的距离D=|a-b|+|b-c|+|c-a|.给定三个非空集合S1、S2和S3,按升序分别存储在3个数组中. 请设计一个尽可能高效的算法,计算并输出所有可能的三元组(a,b,c)(a∈S1,b∈S2,c∈S3)中的最小距离. 例如:S1={-1,0,9}, S2={-25,-10,10,11}, S3={2,9,17,30,41}的最小距离是2,对应的三元组是(9,10,9).
11. 设C={a1,b1,a2,b2,...,an,bn}为线性表,采用带头结点的单链表存放,设计一个算法,将其拆分为两个线性表,使得A={a1,a2,...,an},B={bn,...,b2,b1}
20.设头指针L的带头结点的非循环双向链表,其中每个节点除了前驱指针、数据和后继指针外,还有一个访问频度域freq.在链表被启用前,其值被初始化为0.每当链表中进行一次Locate(L,x)运算时,令元素值为x的结点中的freq域的值增1,并使此链表中结点保持按访问频度非增(递减)的顺序排列.同时最近访问的结点排在频度相同的结点前面,以使频繁访问的结点总是靠近表头.试编写符合上述要求的Locate(L,x)运算的算法,该运算为函数过程,返回找到结点的地址,类型为指针型.
23.[2012统考真题]假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,可以共享相同的后缀空间,例如:"loading"和"being"中"ing"是共享的.设str1和str2分别指向两个单词所在单链表的头结点,找出str1和str2所指向的.两个链表的共同后缀的起始位置.
25.[2019统考真题] 设线性表L=(a1,a2,a3...,an)采用带头结点的单链表保存,请设计一个空间复杂度为O(1)且时间上尽可能高效的算法,重新排列L中的各节点,得到线性表L'=(a1,an,a2,an-1,...)
07.[2019统考真题]请设计一个队列,要求满足:(1).初始化时队列为空;(2).入队时,允许增加队列占有的空间;(3).出队后,出对元素所占的空间可重复使用;(4).入队操作和出队操作的时间复杂度始终保持为O(1)
if n = 0:
Pn(x) = 1
if n = 1:
Pn(x) = 2x
if n > 1:
Pn(x) = 2xPn-1(x) - 2(n-1)Pn-2(x)