2.3　顺序表的典型试题精选与解析

2.3.1　典型试题

一、单项选择题

1、（哈尔滨工业大学考研试题）在n个结点的线性表的数组实现中，算法的时间复杂度是O（1）的操作是（　　）。

A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

B．在第i个结点后插入一个新结点（1≤i≤n）

C．删除第i个结点（1≤i≤n）

D．以上都不对

2、（华中科技大学考研试题）对于顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，则删除一个元素时平均要移动表中的（　　）个元素。

A．n/2

B．（n+1）/2

C．（n-1）/2

D．n

3、（北京航空航天大学考研试题）若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度（　　）。

A．O（log₂n）

B．O（1）

C．O（n）

D．O（n²）

4、若一个线性表中最常用的操作是存取第i个元素和查找第i个元素的前趋元素，则采用（　　）存储方式最节省时间。

A．顺序表

B．单链表

C．双链表

D．单循环链表

5、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（　　）。

A．110

B．108

C．100

D．120

6、在一个长度为n的顺序表（顺序表中元素的序号从1到n）中，在第i个元素之前插入一个新元素时，需向后移动（　　）个元素。

A．n-i

B．n-i+1

C．n-i-1

D．i

7、在一个长度为n的顺序表中删除第i个元素，需要向前移动（　　）个元素。

A．n-i

B．n-i+1

C．n-i-1

D．i+1

8、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（　　）。

A．8

B．63.5

C．63

D．7

9、一个顺序表的第1个元素的存储地址是90，每个元素的长度为2，则第6个元素的存储地址是（　　）。

A．98

B．100

C．102

D．106

10、顺序表中，插入一个元素所需移动的元素平均数是（　　）。

A．（n-1）/2

B．n

C．n+1

D．（n+1）/2

二、综合分析题

1、函数ListDelete实现删除顺序表中某一元素的算法，请在空格处将算法补充完整。

2、（西安电子科技大学考研试题）假设LS=（a₁，a₂，…，a_n）是一个线性表，若采用顺序存储结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是多少？若元素插在a_i与a_i+1之间（0≤i≤n-1）的概率为2（n-i）/（n*（n+1）），则插入一个元素需要平均移动元素的个数是多少？

三、算法设计题

1、设顺序表LA中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

2、已知有两个顺序表A和B，A中的元素按照递增排列，B中的元素按照递减排列。试编写一个算法，将A和B合并成一个顺序表，使其按照递增有序排列，要求不占用额外的存储单元。

3、顺序表A和顺序表B的元素都是非递减排列，利用线性表的基本运算，将它们合并成一个顺序表C，要求C也是非递减排列。例如，A=（6，11，11，23），B=（2，10，12，12，21），则C=（2，6，10，11，11，12，12，21，23）。

4、设A和B是两个顺序表，其元素非递减排列。编写一个算法，将A和B中元素合并组成一个新的从大到小的有序排列的顺序表C，并分析算法的时间复杂度。

5、（2013年全国统考试题）已知一个整数序列A=（a₀，a₁，…，a_n-1），其中0≤a_i＜n（0≤i＜n）。若存在a_p1=a_p2=…=a_pm=x且m＞n/2（0≤p_k＜n，1≤k≤m），则称x为A的主元素。例如A=（0，5，5，3，5，7，5，5），则5为主元素；又如A=（0，5，5，3，5，1，5，7），则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素，否则输出-1。要求：

（1）给出算法的基本设计思想。

（2）根据算法设计思想，采用C语言描述算法。

（3）说明算法的时间复杂度和空间复杂度。

6、试设计一种表示任意长的整数的数据结构，计算任意给定的两个整数之和的算法。