c算法面试题及答案
一、单项选择题（每题2分，共20分）
1.以下哪种排序算法平均时间复杂度为O(nlogn)？
A.冒泡排序B.选择排序C.归并排序D.插入排序
2.在一个长度为n的数组中查找元素x，采用顺序查找的平均时间复杂度是？
A.O(1)B.O(n)C.O(logn)D.O(n^2)
3.栈的操作特性是？
A.先进先出B.先进后出C.随机进出D.以上都不对
4.深度优先搜索算法通常使用什么数据结构来辅助实现？
A.队列B.栈C.堆D.哈希表
5.对于一个有n个顶点的无向图，其邻接矩阵的大小是？
A.nB.n-1C.nnD.2n
6.以下哪种算法用于解决单源最短路径问题？
A.Prim算法B.Kruskal算法C.Dijkstra算法D.拓扑排序
7.快速排序在最坏情况下的时间复杂度是？
A.O(nlogn)B.O(n^2)C.O(n)D.O(1)
8.一棵完全二叉树有10个节点，其深度为（根节点深度为1）？
A.3B.4C.5D.6
9.哈希表中解决冲突的方法不包括以下哪种？
A.开放地址法B.链地址法C.二分查找法D.再哈希法
10.以下关于递归算法的说法，正确的是？
A.递归算法效率一定高于非递归算法
B.递归算法不需要栈空间
C.递归算法一定有终止条件
D.递归算法不能解决复杂问题
答案：1.C2.B3.B4.B5.C6.C7.B8.B9.C10.C
二、多项选择题（每题2分，共20分）
1.以下属于贪心算法应用的有？
A.哈夫曼编码B.背包问题（部分背包）C.最短路径问题D.活动安排问题
2.下列排序算法中，稳定的排序算法有？
A.冒泡排序B.选择排序C.归并排序D.插入排序
3.关于图的遍历，说法正确的是？
A.广度优先遍历使用队列辅助
B.深度优先遍历使用栈辅助
C.一个图的广度优先遍历序列是唯一的
D.一个图的深度优先遍历序列是唯一的
4.以下哪些数据结构可以用来实现优先队列？
A.堆B.栈C.队列D.二叉搜索树
5.下列关于算法复杂度的说法，正确的是？
A.时间复杂度衡量算法执行的时间长短
B.空间复杂度衡量算法执行过程中所需的额外空间
C.算法的时间复杂度和空间复杂度一定相互制约
D.渐近时间复杂度关注输入规模很大时算法的性能
6.对于二叉树，以下说法正确的是？
A.完全二叉树一定是满二叉树
B.满二叉树一定是完全二叉树
C.二叉树的遍历方式有前序、中序、后序和层序
D.二叉搜索树左子树节点值小于根节点值，右子树节点值大于根节点值
7.以下哪些算法可以用于图的最小生成树问题？
A.Prim算法B.Kruskal算法C.Dijkstra算法D.Floyd算法
8.字符串匹配算法包括？
A.暴力匹配算法B.KMP算法C.BM算法D.DFS算法
9.以下哪些操作可以在O(1)时间复杂度内完成（对于合适的数据结构）？
A.在哈希表中插入元素B.在栈中弹出元素
C.在队列中删除队首元素D.在有序数组中查找元素
10.关于递归和迭代，说法正确的是？
A.递归和迭代都可以解决循环问题
B.递归通常消耗更多栈空间
C.迭代效率一定比递归高
D.有些问题只能用递归解决，不能用迭代
答案：1.ABD2.ACD3.AB4.AD5.ABD6.BCD7.AB8.ABC9.ABC10.AB
三、判断题（每题2分，共20分）
1.二分查找只能用于有序数组。（）
2.拓扑排序适用于有向无环图。（）
3.堆排序是一种稳定的排序算法。（）
4.图的邻接表存储方式比邻接矩阵存储方式更节省空间。（）
5.递归算法的时间复杂度一定比迭代算法高。（）
6.哈希表的查找效率只与哈希函数有关，与冲突处理方式无关。（）
7.队列的插入操作在队尾进行，删除操作在队首进行。（）
8.一棵二叉树的前序遍历和中序遍历结果相同，则该二叉树一定是只有根节点。（）
9.动态规划算法通常需要保存子问题的解以避免重复计算。（）
10.快速排序的平均时间复杂度和最坏时间复杂度相同。（）
答案：1.√2.√3.×4.