数据结构考研分类复习真题 第二章 线性表[28]

五算法设计题

假设有两个按元素值递增次序排列的线性表均以单链表形式存储请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表并要求利用原来两个单链表的结点存放归并后的单链表【北京大学 三 （分）】

类似本题的另外叙述有

（）设有两个无头结点的单链表头指针分别为hahb链中有数据域data链域next两链表的数据都按递增序存放现要求将hb表归到ha表中且归并后ha仍递增序归并中ha表中已有的数据若hb中也有则hb中的数据不归并到ha中hb的链表在算法中不允许破坏【南京理工大学 四（分）】

PROCEDURE merge(hahb);

（）已知头指针分别为la和lb 的带头结点的单链表中结点按元素值非递减有序排列写出将la 和 lb两链表归并成一个结点按元素值非递减有序排列的单链表（其头指针为 lc）并计算算法的时间复杂度【燕山大学 五 （分）】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []