线性表算法试题 数据结构

数据结构复习题：线性表

算法分析题

1、己知一个顺序表L,其中的元素按值非递减有序排列,设计一个算法插入一个元素x后保持该顺序表仍按递减有序排列。要求算法的空间复杂度为O(1)。

2、设计一个算法从顺序表L中删除所有值为X的元素。要求算法的空间复杂度为O(1)。 3、从顺序表L中删除重复的元素,并使剩余元素间的相应次序保持不变.要求本算法的空间复杂记度为O(1)。

4、有一个单链表(不同结点的数据域值可能相同),其头指针为head,设计一个算法计算数据域为x的结点个数。

5、己知线性表元素递增有序,并以带头结点的单链表作存储结构,设计一个高效算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素)。并分析所写算法的时间复杂度。

6、设计一个在带头结点的单链表中删除一个最小值结点的高效算法。 7、有一个不带头结点的单链表L(至少有1人结点),其头指针为head,设计一个算法将L逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等。 8、用单链表表示集合,设计一个算法求两个集合的差。要求不破坏原有的结点。

9、用单链表表示集合,设计一个算法求两个集合的并。要求不破坏原有的结点。

10、设计一个算法,将一个头结点指针为a的单链表A分解成两个单链表A和B,其头结点指针分别为a和b,使得A链表中含有原链表A中序号为奇数的元素,而B链表中含有原链表A中序号为倒数的元素,且保持原来的相对顺序。

11、有一个单链表,其结点的元素值以递增有序排列,设计一个算法删除该单链表中多余的元素值相同的结点。

12、己知两个存放整数的有序单链表(己按整数从小至大的顺序排序),指针L1和L2分别指向这两个单链表的头结点。设计一个算法,将L1和L2合并成一个单链表,且新的链表仍按整数由小到大的顺序排列,新的单链表的结点由L1和L2的结点构成。要求合并后的单链表利用原来单链表的存储空间。

13、设计一个算法,将线性表lb连接到la之后,要求其时间复杂度为O(1),占用的辅助空间尽量小。描述所用的结构。

14、设指针p指向双链表中的结点X,指针f指向将要插入的新结点Y,Y要插入在结点X之后,写出指针需要修改的有关步骤。

15、有一个循环双链表,每个结点由两个指针(prior和next)以及关键字(data)构成,p指向其中某一结点,设计一个算法从该循环双链表中删除p所指的结点。

16、设有一个循环双链表,其中有一结点的指针为p,设计一个算法将p与其后续结点进行交换。

19、设A和B是两个单链表(带头结点)，其表中元素递增有序。设计一个算法将A和B归并成一个按元素值递增有序的单链表C，要求辅助空晨为O(1)，并分析算法的时间复杂度。