【练习题】一.线性表

 

1.将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表《存储空间，不另外占用其他的存储空间。表中不允许有重复的数据。

2.将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。

3.已知两个链表4 和 B分别表示两个集合，其元素递增排列。请设计一个算法，用于求出A与 B 的交集，并存放在 A 链表中。

4.已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计算法求出两个集合和 B 的差集( 即仅由在 4 中出现而不在 B 中出现的元素所构成的集合 )，并以同样的形式存储同时返回该集合的元素个数。

5.设计算法将一个带头结点的单链表 A 分解为两个具有相同结构的链表 B 和 C，其中 B表的结点为 A 表中值小于零的结点,而 C表的结点为 A 表中值大于零的结点(链表A 中的元素为非零整数，要求 B、C 表利用 A 表的结点 )。

6.设计一个算法，通过一趟遍历确定长度为n的单链表中值最大的结点，返回该结点的数据
域。

7.设计一个算法，将链表中所有结点的链接方向“原地”逆转，即要求仅利用原表的存储空间，换句话说，要求算法的空间复杂度为 O(1)。

8.设计一个算法，删除递增有序链表中值大于 mink 且小于 maxk (mink 和 maxk 是给定的两个参数，其值可以和表中的元素相同，也可以不同)的所有元素。

9.已知p 指向双向循环链表中的一个结点，其结点结构为 data、prior、next 三个域，写出算法 Exchange(p)，交换p 所指向的结点及其前驱结点的顺序。

10.已知长度为 n的线性表 A 采用顺序存储结构，请写一个时间复杂度为 O(m)、空间复杂度为 O(1)的算法，该算法可删除线性表中所有值为 item 的数据元素。

11.[2009 年第 42 题]已知一个带有表头结点的单链表，结点结构为( data，link )，假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点 (k 为正整数 )。若查找成功，算法输出该结点的 data 域的值，并返回 1;
否则，只返回 0。要求:
(1) 描述算法的基本设计思想;

(2) 描述算法的详细实现步骤;

(3)根据设计思想和实现步骤，采用程序设计语言描述算法( 使用 C、C++或 Java 语言实现 ),关键之处请给出简要注释。
12.[2010 年第 42 题] 设将 n (n>1)个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将 R 中保存的序列循环左移 p( 0 (1) 给出算法的基本设计思想;
(2 )根据设计思想，采用 C或 C++或 Java 语言描述算法，关键之处给出注释;
(3)说明你所设计算法的时间复杂度和空间复杂度。13.[2011 年第 42 题]一个长度为L(L≥1)的升序序列 S，处在第[L/2]个位置的数称为 S的中位数。例如，若序列 SI=(11，13，15，17，19)，则 S1 的中位数是 15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 S2=(2，4，6，8，20)，则 S1 和 2 的中位数是11。现有两个等长升序序列 A和 B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。
要求:
( 1) 给出算法的基本设计思想;
(2)根据设计思想，采用 C或 C++或 Java 语言描述算法，关键之处给出注释;
(3)说明你所设计算法的时间复杂度和空间复杂度。

14.[2012 年第 42 题] 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时,则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如图 2.2 所示。

图 2.2 共享相同后缀存储空间两个单词链表
设.str1 和str2 分别指向两个单词所在单链表的头结点，链表结点结构为 ( data，next)，请设计一个时间上尽可能高效的算法，找出由str1 和str2 所指的两个链表共同后缀的起始位置( 如图中字符i所在结点的位置p)。要求:
( 1) 给出算法的基本设计思想;
(2)根据设计思想，采用 C或 C++或 Java 语言描述算法，关键之处给出注释;
(3)说明你所设计算法的时间复杂度。

15.[2013 年第41题]已知一个整数序列 A-(ao,ai,·.，ani)，其中0≤aKn(0≤in/2(0≤p;Sn，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 中没有主元素。假设 A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 A的主元素。若存在主元素，则输出该元素;否则输出-1。要求:
(1) 给出算法的基本设计思想;
(2)根据设计思想，采用 C 或 C++或 Java 语言描述算法，关键之处给出注释(3)说明你所设计算法的时间复杂度和空间复杂度
16.[2015 年第 41 题]用单链表保存m个整数，结点的结构为 (data，link)，且data|≤n(为正整数 )。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的点，仅保留第一次出现的结点而删除其余绝对值相等的结点。

例如，若给定的单链表 head 如2.3(a)所示，则删除结点后的 head 如图 2.3(b)所示。

图 2.3整数链表的存储结构
要求:
(1)给出算法的基本设计思想;
(2)使用 C 或 C++语言，给出单链表结点的数据类型定义;
(3) 根据设计思想，采用 C或 C++语言描述算法，关键之处给出注释;

(4) 说明你所设计算法的时间复杂度和空间复杂度。

17.[2016 年第 43 题]已知由 n(n=2)个正整数构成的集合 A={a}(0≤k (1) 给出算法的基本设计思想;
(2) 根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释(3 ) 说明你所设计算法的平均时间复杂度和空间复杂度。