京东算法笔测试题及答案
姓名：__________班级：__________成绩：__________
1.以下哪种数据结构适合实现后进先出（LIFO）的操作？
A.队列B.栈C.链表D.树
答案：B
2.二叉树的前序遍历为ABC，中序遍历为BAC，后序遍历结果是？
A.BACB.BCAC.ACBD.CBA
答案：B
3.快速排序的平均时间复杂度是？
A.O(n)B.O(nlogn)C.O(n)D.O(nlogn)
答案：B
4.以下排序算法中不稳定的是？
A.冒泡排序B.归并排序C.插入排序D.快速排序
答案：D
5.以下操作时间复杂度为O(1)的是？
A.数组中间插入元素B.链表头部插入元素C.二叉搜索树查找D.堆删除堆顶
答案：B
6.3个红球和2个蓝球随机取两个，颜色相同的概率是？
A.1/5B.2/5C.3/5D.4/5
答案：B
7.用两个栈实现队列时，插入操作的时间复杂度是？
A.O(1)B.O(n)C.O(logn)D.O(n)
答案：A
8.队列的基本操作不包括？
A.入队B.出队C.取队尾D.判空
答案：C
9.完全二叉树第k层（根为第1层）最多有多少节点？
A.2^(k-1)B.2^k-1C.2^kD.2^(k+1)
答案：A
10.平衡二叉树（AVL树）的平衡因子是？
A.左子树高度减右子树高度B.右子树高度减左子树高度C.左子树节点数减右子树节点
数D.右子树节点数减左子树节点数
答案：A
11.以下排序算法空间复杂度为O(1)的是？
A.归并排序B.快速排序C.堆排序D.基数排序
答案：C
12.冒泡排序最好情况下（已排序）的时间复杂度是？
A.O(n)B.O(nlogn)C.O(n)D.O(1)
答案：A
13.二分查找要求数组必须？
A.有序B.无序C.元素唯一D.长度为奇数
答案：A
14.有序数组中查找第一个≥目标值的元素，二分查找的时间复杂度是？
A.O(n)B.O(logn)C.O(n)D.O(1)
答案：B
15.斐波那契数列第n项用动态规划求解的时间复杂度是？
A.O(n)B.O(n)C.O(logn)D.O(2^n)
答案：A
16.0-1背包问题中，状态dp[i][j]表示？
A.前i个物品容量j时的最大价值B.前i个物品价值j时的最小容量C.第i个物品容量j时
的最大价值D.第i个物品价值j时的最小容量
答案：A
17.5（101）^3（011）的结果是？
A.1B.2C.4D.6
答案：D
18.将整数x的最低位1变为0的操作是？
A.x(x-1)B.x|(x+1)C.x^(x-1)D.x-(x-x)
答案：A
19.求解单源最短路径的算法是？
A.KruskalB.PrimC.DijkstraD.Floyd-Warshall
答案：C
20.拓扑排序适用于？
A.无向图B.有向无环图C.有向有环图D.带权图
答案：B
21.双重循环（外层n次，内层i次）的时间复杂度是？
A.O(n)B.O(n)C.O(nlogn)D.O(1)
答案：B
22.递归斐波那契函数f(n)=f(n-1)+f(n-2)的时间复杂度是？
A.O(n)B.O(n)C.O(2^n)D.O(logn)
答案：C
23.数组和链表的主要区别是？
A.数组支持随机访问，链表不支持B.链表支持随机访问，数组不支持C.数组插入删除
更快D.链表内存连续
答案：A
24.查找数组重复元素最坏时间复杂度最低的是？
A.暴力法B.哈希表C.排序后遍历D.二分查找