数据结构:笔记-时间复杂度_计算算法的时间复杂度是属于一种

1、顺序表含有127个元素,向其插入一个新元素并保持原来顺序不变,平均要移动____个元素()
正确答案: A 你的答案: A (正确)
63.5
8
32
7

2、哈夫曼树、平衡二叉树都是数据的逻辑结构()
正确答案: A 你的答案: B (错误)
对
错
解析：线性表，树，图 这些都是对数据逻辑结构的描述。
数据的存储结构只有顺序结构和链式结构（不一定是单链

3、有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是（）
正确答案: A 你的答案: A (正确)
访问第i个节点（1≤i≤n）
在第i个节点后插入一个新节点（1≤i≤n）
删除第i个节点（1≤i≤n）
将n个节点从小到大排序）

4、计算算法的时间复杂度是属于一种()
正确答案: B 你的答案: D (错误)
事前统计的方法
事前分析估算的方法
事后统计的方法
事后分析估算的方法

5、题目来源于王道论坛
下列程序段的时间复杂度是 。
count=0;
for(k=1;k<=n;k*=2)
for(j=1;j<=n;j++)
count++;

正确答案: C 你的答案: D (错误)
O(log2n)
O(n)
O(nlog2n)
O(n2)

6、数据结构的抽象操作的定义与具体实现有关()
正确答案: B 你的答案: A (错误)
对
错

解析：抽象数据类型独立于具体实现。

7、下列叙述中正确的是（ ）
正确答案: C 你的答案: B (错误)
算法的时间复杂度与算法程序中的语句条数成正比
算法的时间复杂度与计算机的运行速度有关
算法的时间复杂度与运行算法时特定的输入有关
算法的时间复杂度与算法程序编制者的水平有关

8、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（ ）
正确答案: A 你的答案: B (错误)
正确
错误

9、区分一个算法时，主要看它具有()等特点
正确答案: A C 你的答案: A C D (错误)
可行性
至少有一个输入量
确定性
健壮性

10、程序段
for(i=n-l;i>l;i–)
for(j=l;j<i;j++)
if(A[j]>A[j+1])
A[j]与A[j+1]对换;
其中n为正整数，则最后一行的语句频度在最坏情况下是（）
正确答案: B 你的答案: D (错误)
O(n)
O(n²)
O(n×log₂n)
不直接依赖于n

11、在顺序存储结构中,有时也存储数据结构中元素之间的关系()
正确答案: B 你的答案: B (正确)
对
错
解析：在顺序存储中只存储数据，不存储元素之间的关系，只有链式存储才存储元素之间的关系、

12、
最大堆中插入一条数据的时间复杂度是（）
正确答案: C 你的答案: A (错误)
O(n)
O(1)
O(log(n))
O(n ^ 2)

13、个优化的程序可以生成一n个元素集合的所有子集，那么该程序的时间复杂度是
正确答案: B
O(n!)
O(2的n次方)
O(n的2次方）
O(n log n)

14、对于n个元素，下列哪种操作时间复杂度不是O(nlogn)（）

正确答案: C 你的答案: D (错误)
凸包计算
LC搜索
有序序列数字查找
基于比较的排序

15、对于一个含n个元素的无序数组，构建一个大顶堆（Max-Heap），该操作的时间复杂度是Θ(____)

正确答案: A 你的答案: D (错误)
O(n)
O(n²)
O(log n)
O(nlog n)

16、求 2n 个数中的最大值和最小值，最少的比较次数是？
正确答案: C 你的答案: B (错误)
4n/3
2n-2
3n-2
3n/2

解析：最少的比较次数：就是最大的数和最小的数比较用掉一次比较；然后身剩下的2（n-1）个数字，每两个比较一次，比较n-1次；然后大的数和最大值比较，小的值和最小的值比较，进行2（n-1）比较，总的需要进行3(n-1)+1次比较，也就是3n-2。

17、以下哪些算法的平均时间复杂度是O(n*log n)（）
正确答案: B C D 你的答案: B D (错误)
冒泡排序
快速排序
希尔排序
堆排序