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

图（编者略）中带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合两表中的元素皆为递增有序请写一算法求A和B的并集AUB要求该并集中的元素仍保持递增有序且要利用A和B的原有结点空间【北京邮电大学 二 （分）】

类似本题的另外叙述有

() 已知递增有序的两个单链表AB分别存储了一个集合设计算法实现求两个集合的并集的运算A:=A∪B【合肥工业大学 五（分）】

（）已知两个链表A和B分别表示两个集合其元素递增排列编一函数求A与B的交集并存放于A链表中【南京航空航天大学 六（分）】

（）设有两个从小到大排序的带头结点的有序链表试编写求这两个链表交运算的算法（即L∩L）要求结果链表仍是从小到大排序但无重复元素【南京航空航天大学 十一（分）】

（）己知两个线性表A B均以带头结点的单链表作存储结构且表中元素按值递增有序排列设计算法求出A与B的交集C要求C另开辟存储空间要求C同样以元素值的递增序的单链表形式存贮【西北大学 五 ( 分)】

（）已知递增有序的单链表AB和C分别存储了一个集合设计算法实现A=A∪（B∩C）并使求解结构A仍保持递增要求算法的时间复杂度为O(|A|+|B|+|C|)其中|A|为集合A的元素个数【合肥工业大学 五（分）】

知LL分别为两循环单链表的头结点指针mn分别为LL表中数据结点个数要求设计一算法用最快速度将两表合并成一个带头结点的循环单链表【东北大学 二 (分)】

类似本题的另外叙述有

（）试用类Pascal语言编写过程PROC join（VAR lalink lblink） 实现连接线性表la和lb(lb在后)的算法要求其时间复杂度为（） 占用辅助空间尽量小描述所用结构【北京工业大学 一 (分)】

（）设有两个链表ha为单向链表hb为单向循环链表编写算法将两个链表合并成一个单向链表要求算法所需时间与链表长度无关【南京航空航天大学 四（分）】

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