问答题 已知顺序表中有m个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m)。【清华大学1994八(15分)】
【正确答案】正确答案：顺序表无序，索引表有序。由顺序表中的关键字及其下标地址组成索引表中的一项。顺序表有m个记录，索引表应有m项。建立索引表宜采用“直接插入排序”，这样才能在顺序表有序时，算法复杂度达到最好O(m)。
【答案解析】