2012 年 408 真题2012 年 408 数据结构 · 第 41 题选中文字高亮 · 下划线设有 6 个有序表 A、B、C、D、E、F,分别含有 10、35、40、50、60 和 200 个数据元素,各表中元素按升序排列。要求通过 5 次两两合并,将 5 个表最终合并成 1 个升序表,并在最坏情况下比较的总次数达到最小。请回答下列问题。 (1) 给出完整的合并过程,并求出最坏情况下比较的总次数。 (2) 根据你的合并过程,描述 N(N≥2) 个不等长升序表的合并策略,并说明理由。←上一题对同一待排序序列分别进行折半插入排序和直接插入排序,两者之间可能的不同之处是( )。下一题假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading" 和 “being” 的存储映像如下图所示。 设 str1 和 str2 分别指向两个单词所在单链表的头结点,链表结点结构为 | data | next |,请设计一个时间上尽可能高效的算法,找出由 str1 和 str2 所指向两个链表共同后缀的起始位置(如图中字符 i 所在的结点位置 p)。要求: 1)给出算法的基本设计思想。 2)根据设计思想,采用 C 或 C++ 或 Java 语言描述算法,关键之处给出注释。 3)说明你所设计算法的时间复杂度。→