实训习题

1.试以单链表作为存储结构，实现将线性表(a0,a1,…,an-1)就地逆置的操作。

2.设ha和hb是两个单链表，其表中元素递增有序。现将ha和hb合并成一个按元素值递减有序的单链表hc，并要求辅助空间为O(1)。

3.建立一个双链表，从链首开始，顺序显示链表中的所有结点的数据，然后从链尾开始，反序显示链表中所有结点的数据，最后将一个新结点插入到链表的表尾。

4.有两个顺序表la和lb，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表lc，要求lc也是非递减有序排列，如la=(2,2,3)，lb=(1,3,3,4)，则lc=(1,2,2,3,3,3,4)。

5.将若干城市的信息存入一个带头结点的单链表中，结点中的城市信息包括城市名和城市的位置坐标。要求：

（1）给定一个城市名，返回其位置坐标；

（2）给定一个位置坐标p和一个距离d，返回所有与p的距离小于d的城市。

6.约瑟夫环问题的描述是任给正整数n与k，按下述方法可得排列1,2,…,n的一个置换。将数字1,2,…,n环形排列，按顺时针方向从1开始计数，计满k时输出该位置上的数字（并从环中删去该数字），然后从下一个数字开始继续从1计数，直到环中所有数字均被输出为止。例如，当n=10，k=3时，输出的置换是3,6,9,2,7,18,5,10,4。试设计一个程序，对输入的任意正整数n与k，输出相应的置换（分别用顺序表和链表实现）。