2.3.2 答案解析
一、单项选择题
1、A。主要考查顺序表的特点。顺序表中的元素是连续存储的，可以随机进行存取，但是插入和删除操作需要移动大量的元素。
2、C。主要考查顺序表删除操作的时间复杂度计算方法，见2.2.2小节。
3、C。主要考查顺序表插入操作的时间复杂度计算方法，插入操作的时间主要耗费在元素的移动过程中，其平均移动元素次数为n/2，故时间复杂度为O（n），见2.2.2小节。
4、A。主要考查顺序表和链表基本操作的主要特点，对于顺序表来说，由于其可随机存取的特点，按序号查找和存取操作的时间复杂度为O（1）；对于链表来说，其查找和存取操作必须从头指针开始顺序进行，故时间复杂度为O（n）。因此，这些操作（按序号查找和存取操作）采用顺序存储更节省时间。
5、B。主要考查线性表的顺序存储特点（逻辑上相邻，其物理地址也相邻）及地址的计算方法，第5个元素的地址Loc（a5）=Loc（a1）+（5-1）*m=100+4*2=108，故选择B。
6、B。
7、A。
8、B。在2.2.2小节中，在顺序表中插入新元素需要平均移动元素的次数为n/2，可得127/2=63.5，故选择B。
9、B。同第5题，Loc（a6）=Loc（a1）+（6-1）*2=90+10=100。
10、D。插入元素的位置分别是第1个位置、第2个位置、…、第n个位置，则需要移动元素的次数分别是n、n-1、…、1，移动元素的平均数＝移动元素的总次数／移动元素个数=（n+n-1+…+1）/n=（n+1）/2。
二、综合分析题
1、（1）L->list［k+1］；（2）L->length—或L->length=L->length-1。
2、在等概率的情况下，平均移动元素的个数为n/2。在概率为2（n-i）/（n*（n+1））的情况下，平均移动元素的个数为
。
三、算法设计题
1、主要考查顺序表的插入操作算法思想及其实现。为了使插入新元素x后顺序表仍然有序，就需要在插入前，将x与顺序表中的元素逐个比较，找到正确的位置，再将x存入到该位置。从后往前查找正确的插入位置，可在查找的同时将x插入到正确位置。
2、主要考查顺序表的基本操作。利用原顺序表A的空间，假设A的空间足够大，能容纳A和B中的元素。依次找出最大元素并将其存入到正确的位置上，这个位置是由A和B的长度决定的。分别从A的最后一个元素（令i=A->length）和B的第一个元素（令j=1）出发，依次取出相应的元素e1和e2并进行比较，若e1<=e2，表明e2为当前待比较元素集合中最大的元素，则将e2存入i+B.length-j位置上；若e1>e2，表明e1为当前待比较元素集合中最大的元素，则将e1存入i+B.length-j位置上。
3、分析：引入顺序表C，用于存储顺序表A和B中的元素。依次取出A和B中元素e1和e2，比较e1和e2，若e1<=e2，则将较小的一个即e1存入到C中，否则，将e2存入到C中。若A和B中有一个顺序表中的元素取出完毕，则将还未存取完毕的顺序表剩下的元素依次存入C中。最后修改C的表长为A和B的表长之和。
程序运行结果如图2-6所示。
图2-6 合并两个顺序表的程序运行结果
4、分析：其算法思想与第2题类似，为使合并后的顺序表呈递减排列，可分别从顺序表A和B的尾部出发，依次比较A和B中的元素，并将较大的一个存入到C中，以此类推，直至A和B中任何一个顺序表中的元素比较完毕，最后将剩下的元素直接存入到C中即可。若A和B中存在相同的元素，则只保留其中一个。
算法的执行时间主要耗费在扫描A和B中的元素，因此时间复杂度为O（n）。
说 明
该题考虑了若A和B中存在相同的元素，只保留其中一个，若不考虑元素值相同的情况，或打算保留相同的元素，则只需要删除掉扫描过程中else语句后面的代码段，同时将if条件改成e1<=e2即可。本算法未考虑A或B中原来的元素存在相同的情况，如果要求合并后的顺序表中不包含相同的元素，则需要在扫描A和B的过程中考虑是否C中已经存在了与A、B中相同的元素，如果存在相同的元素，就不能在继续进行插入，直接略过该元素即可。
5、分析：算法的策略是从前向后扫描顺序表L，依次取出每个元素作为候选主元素赋给mElem，然后确认mElem是否为主元素。为了确定mElem是否为主元素，需引入计数器count，当下一个元素与mElem相等时，count增加1，否则count减1；若count为0，则更换候选主元素重新计数，直至扫描完毕后；若count大于0，表示mElem为候选主元素。进一步扫描顺序表L，统计mElem在L中出现的次数count，若count>表长/2，则表示mElem为主元素，否则表明L中不存在主元素。算法可分为两步：（1）选取候选主元素：依次扫描L中的每个整数，将第一个遇到的整数保存到mElem中，记录出现次数count为1；若遇到的下一个整数仍等于mElem，则将count加1，否则count减1；当count减到0时，将遇到的下一个整数保存到mElem中，作为新的候选主元素，并重新计数令count为1，即从当前位置开始重复上述过程，直至扫描完L中的所有元素。（2）判断mElem是否为真正的主元素：再次扫描L，统计mElem中元素出现的次数，若大于L.length/2，则为主元素，否则L中不存在主元素。
程序运行结果如图2-7所示。
图2-7 程序运行结果
算法的时间复杂度为O（n），空间复杂度为O（1）。
说 明
该题主要考查是否顺序表中存在一个数出现的次数超过表的长度一半，只要存在元素相等，则将计数增1，否则减1；最后若计数大于0，则表明该元素可能出现次数超过表长的一半。在选择候选主元素过程中，出现不会超过表长一半的元素已经被新的候选元素替换。为了确定是否为主元素，只需要对该元素的出现次数从头到尾重新比较一遍即可。
6、C语言提供的整数范围为-231~231-1，超出这个范围的整数该如何表示呢？可以利用数组来存储，数组中的每一个元素存放一个数字，数组A和B分别存储两个整数，在将两个整数相加时，从低位到高位依次将对应位相加，如果和大于9，则将高位上加上进位1，并将和减去10后存储到当前位。
