数据结构与算法复习题（附答案）.docxVIP

数据结构与算法复习题（附答案）

一、选择题（每题2分，共40分）

1.下列关于时间复杂度的描述中，正确的是（）。

A.时间复杂度是指算法执行的绝对时间

B.同一个算法的时间复杂度与输入规模无关

C.算法的时间复杂度通常用大O符号表示最坏情况下的渐近复杂度

D.所有递归算法的时间复杂度都高于非递归算法

2.一个长度为n的顺序表，在第i个位置（1≤i≤n+1）插入元素的时间复杂度为（）。

A.O(1)B.O(n)C.O(logn)D.O(n2)

3.若一个栈的输入序列是1,2,3,4，输出序列不可能是（）。

A.4,3,2,1B.3,4,2,1C.2,4,1,3D.2,3,4,1

4.循环队列的队空条件是（）（假设队头指针为front，队尾指针为rear，队列容量为maxSize）。

A.front==rearB.(rear+1)%maxSize==front

C.rear==0D.front==(rear+1)%maxSize

5.对于一个具有n个节点的单链表，在已知节点p的前驱节点的情况下，删除p的时间复杂度是（）。

A.O(1)B.O(n)C.O(logn)D.O(n2)

6.一棵二叉树的中序遍历序列为DBEAFC，前序遍历序列为ABDECF，则后序遍历序列为（）。

A.DEBFCAB.DBEAFCC.DEBCFAD.DEBFAC

7.对于完全二叉树，若某节点无左孩子，则该节点一定（）。

A.是叶子节点B.有右孩子C.是根节点D.处于最后一层

8.对于有向图的邻接表存储，计算某个顶点的出度需要遍历（）。

A.该顶点的所有邻接节点B.所有顶点的邻接表中指向该顶点的节点

C.整个邻接表D.无法直接计算

9.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是（）。

A.快速排序B.堆排序C.冒泡排序D.插入排序

10.对序列{5,3,8,6,7,2,4,1}进行直接插入排序，第三趟（插入第4个元素）后序列为（）。

A.{3,5,8,6,7,2,4,1}B.{3,5,6,8,7,2,4,1}

C.{2,3,5,8,6,7,4,1}D.{3,5,8,7,6,2,4,1}

11.哈希表中解决冲突的方法不包括（）。

A.开放定址法B.链地址法C.再哈希法D.顺序查找法

12.若查找表的长度为n，采用二分查找的时间复杂度为（）。

A.O(n)B.O(n2)C.O(logn)D.O(nlogn)

13.以下关于图的遍历的描述中，错误的是（）。

A.深度优先有哪些信誉好的足球投注网站（DFS）使用栈实现

B.广度优先有哪些信誉好的足球投注网站（BFS）使用队列实现

C.无向图的DFS遍历结果唯一

D.有向图的BFS可能访问不到所有节点

14.一个带权无向图的最小生成树（MST）可能不唯一的条件是（）。

A.存在多条权值相同的边

B.图中存在环

C.图是连通的

D.所有边的权值互不相同

15.以下数据结构中，适合作为优先队列底层实现的是（）。

A.普通队列B.栈C.二叉堆D.链表

16.若一棵二叉树的先序遍历为ABDECFG，中序遍历为DBEAFGC，则该二叉树的叶子节点是（）。

A.D、E、F、GB.A、B、CC.D、E、GD.B、C、F

17.对序列{7,5,3,9,2,6,4,1}进行快速排序，以第一个元素为枢轴，一次划分后的结果是（）。

A.{1,5,3,2,4,6,7,9}B.{2,5,3,4,1,6,7,9}

C.{2,5,3,6,1,4,7,9}D.{1,2,3,4,5,6,7,9}

18.若要将一个栈的所有元素逆序，最少需要（）个辅助栈。

A.0B.1C.2D.3

19.一个n×n的对称矩阵采用压缩存储，仅存储下三角部分（含对角线），则需要存储的元素个数为（）。

A.n(n+1)/2B.n(n-1)/2C.n2D.n2/2

20.以下关于平衡二叉树（AVL树）的描述中，错误的是（）。

A.左右子树的高度差绝对值不超过1

B.插入操作可能引发多次旋转

C.查找、插入、删除的时间复杂度均为O(logn)

D.所