数据结构题目收录（三）

1、求出下列算法的时间复杂度。

i=1;k=0;
while(i<n-1){
	k=k+10*i;
	i++;
}
1
2
3
4
5

解析

基本语句k=k+10*i宫执行了n-2次，所以T(n)=O(n)。

2、求出下列算法的时间复杂度。

for(i=0;i<n;i++)
	for(j=0;j<m;j++)
		a[i][j]=0;
1
2
3

解析

内循环执行m次，外循环执行n次，根据乘法原理，共执行了$m\times n$次，故T(m,n)=O(m$\times$n) 。

3、一个顺序表所占用的存储空间大小与（）无关。

• A：表的长度
• B：元素的存放顺序
• C：元素的类型
• D：元素中各字段的类型

解析

顺序表所占的存储空间 = 表长 x sizeof(元素的类型)，元素的类型显然会影响存储空间的大小。对于同一元素类型的顺序表，表越长，所占存储空间就越大。

答案：B

4、设线性表有n个元素，严格来说，以下操作中，（）在顺序表上实现要比在链表上实现的效率高。

Ⅰ. 输出第i（1$\le$i$\le$n）个元素值
Ⅱ. 交换第3个元素与第4个元素的值
Ⅲ. 顺序输出这n个元素的值

• A：Ⅰ
• B：Ⅰ、Ⅲ
• C：Ⅰ、Ⅱ
• D：Ⅱ、Ⅲ

解析

对于Ⅱ，顺序表仅需3次交换操作；链表则需要分别找到两个结点前驱，第4个结点断链后再插入到第2个结点后，效率低。对于Ⅲ，需依次顺序访问每个元素，时间复杂度相同。

答案：C

5、若线性表中总的元素个数基本稳定，但经常要在表头删除元素，在表尾插入元素，那么最好采用____来实现该线性表。

• A：带头指针的单链表
• B：双向循环链表
• C：循环顺序队列
• D：顺序表

解析

由于规定了插入运算是在表尾插入一个新元素，删除运算是指删除表头第一个元素。如果使用仅有头指针的单项循环链表，每次插入结点都要遍历整个链表找到链尾，才能进行插入。如果采用顺序存储，每次删除表头元素时，都要移动n-1个元素。如果使用双向循环链表在寻找头、尾结点时也有可能要O(n)，不符合题意“总的元素个数稳定”、“仅需在表头和表尾操作”的要求。而循环顺序队列进行表头删除和表尾插入的操作，只需要移动尾指针就可以了，删除结点时，只需移动头指针就可以了。

答案：C

6、给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（）。

• A：O(1)
• B：O(n)
• C：O($n^2$)
• D：O($n{\log }_{2}n$)

解析

若先建立链表。然后依次插入建立有序表。则每插入一个元素就需要遍历链表寻找插入位置，即直接插入排序，时间复杂度为O($n^2$)。
若先将数组排好序，然后建立链表，建立链表的时间复杂度为O(n)，数组排序的最好时间复杂度为O($n{\log }_{2}n$)，总时间复杂度为O($n{\log }_{2}n$)。

答案：D

7、在长度为n的有序单链表中插入一个新结点，并仍然保持有序的时间复杂度是（）。

• A：O(1)
• B：O(n)
• C：O($n^2$)
• D：O($n{\log }_{2}n$)

解析

设单链表递增有序，首先要在单链表中找到第一个大于x的结点的直接前驱p，在p之后插入该结点。查找的时间复杂度为O(n)，插入的时间复杂度为O(1)，总时间复杂度为O(n)。

答案：B

8、一个链表最常用的操作是在末尾插入结点和删除结点，则选用（）最节省时间。

• A：带头结点的双循环链表
• B：单循环链表
• C：带尾指针的单循环链表
• D：单链表

解析

在链表的末尾插入和删除一个结点时，需要修改其相邻结点的指针域。而寻找尾结点及尾结点的前驱结点时，只有带头结点的双循环列表所需要的时间最少。

答案：A

9、设对n(n>1)个元素的线性表的运算只有4种：删除第一个元素；删除最后一个元素；在第一个元素之前插入新元素；在最后一个元素之后插入新元素，则最好使用（）。

• A：只有尾结点指针没有头结点指针的循环单链表
• B：只有尾结点指针没有头结点指针的非循环双链表
• C：只有头结点指针没有尾结点指针的循环双链表
• D：既有头结点指针又有尾结点指针的循环单链表

解析

对于A，删除尾结点*p时，需要找到*p的前一个结点，时间复杂度为O(n)。
对于B，删除首结点*p时，需要找到*p结点，这里没有直接给出头结点指针，而通过尾结点的prior指针找到*p结点的时间复杂度为O(n)。
对于D，删除尾结点*p时，需要找到*p的前一个结点，时间复杂度为O(n)。
对于C，执行这4种算法的时间复杂度均为O(1)。

答案：C

10、一个链表最常用的操作是在最后一个元素后插入一个元素和删除第一个元素，则选用（）。

• A：不带头结点的单循环链表
• B：双链表
• C：不带头结点且有尾指针的单循环链表
• D：单链表

解析

对于A，在最后一个元素之后插入元素的情况与普通单链表相同，时间复杂度为O(n)；而删除表中第一个元素时，为保持单循环链表的性质（尾结点的指针指向第一个结点），需要先遍历整个链表找到尾结点，再做删除操作，时间复杂度为O(n)。
对于B，双链表的情况与单链表的相同，一个是O(n)，一个是O(1)。
对于C，与A的分析对比，有尾结点的指针，省去了遍历链表的过程，因此时间复杂度均为O(1)。
对于D，要在最后一个元素之后插入一个元素，需要遍历整个链表才能找到插入位置，时间复杂度为O(n)；删除第一个元素的时间复杂度为O(1)。

答案：C

学海无涯苦做舟