1、将一棵二叉树的根节点放入队列，然后非递归的执行如下操作：将出队节点的所有子节点入队。以上操作可以实现哪种遍历( )
A、前序遍历 B、中序遍历 C、后续遍历 D、层序编历
答案：D；
二叉树的遍历：
①前序遍历：根、左、右
②中序遍历：左、跟、右
③后序遍历：左、右、跟
④层序遍历：从上到下，从左到右，必须配合队列（先入先出）完成
前中后序遍历取决于根的遍历顺序，左右子树的遍历顺序不会改变
注意：可以根据 前序+中序 或者 后序+中序 就可以还原一棵树，但是只有一个遍历或者 前序+后序 是无法还原的。
2、现有一个包含m个节点的三叉树，即每个节点都有三个指向孩子结点的指针，请问:在这3m个指针中有（）个空指针。
A、2m B、2m-1 C、2m+1 D、3m
答案：B
除了根节点以外，都有且只有一个指针指向该节点，所以m个节点中有m-1个非空指针，其 余皆为空指针，所以答案为3m-(m-1)=2m+1。
3、将一颗有100个结点的完全二叉树从根这一层开始，进行广度遍历编号(从1开始编号)，那么编号最小的叶节点的编号是（）
A、49 B、50 C、51 D、52
答案：C
叶子节点的度为0，在一颗完全二叉树中，度为0的节点数=度为2的节点数+1，度为1的节点数只能是0或者1，当度为1的节点数为1时，度为0的节点数为：m+（m+1）+1=100→m=49，即第51个是第一个叶子节点。
4、二叉查找树的查找效率与二叉树的树型有关, 在（）时其查找效率最低。
A、结点太多 B、完全二叉树 C、呈单枝树 D、结点太复杂
答案：C；
二叉树变成单支树则退化成链表，链表增删快/查找慢，所以单支树是二叉树查找最慢情况
5、执行（）操作时，需要使用队列作为辅助存储空间。
A、查找哈希（hash）表
B、广度优先搜索图
C、先序（根）遍历二叉树
D、深度优先搜索图
答案：B；
图的拓扑排序、深度优先、关键路径算法需要 栈 的辅助
树的层次遍历、图的广度优先需要 队列 的辅助
图的遍历方式：
深度优先遍历(DFS)：（借助递归）
从某个顶点出发，一直往下一个顶点遍历，直到没有下一个顶点为止，再返回上一个顶点的其他路径继续进行深度优先，直到该出发顶点的所有深度优先遍历结束，同样的操作对每个顶点都进行一次
广度优先遍历(BFS)：（借助队列）
从某个顶点出发，把所有的下一层顶点都依次遍历，结束后再对该层每个顶点广度优先遍历，直到该出发顶点的广度优先遍历结束，同样的操作对每个顶点都进行一次（类似层次遍历）
DFS\BFS过程中会有顶点被重复遍历，需要记录是否被遍历过的标志位，防止结果重复
DFS\BFS 遍历结果不唯一，与顶点顺序有关
6、已知数据表A中每个元素距其最终位置不远，为了节省时间，应该采取的算法是()
A、选择排序 B、插入排序 C、堆排序 D、快速排序
答案：B
每个元素距其最终位置不远，直接插入排序不需要移动太多元素，适用于这种情况，效率高
7、求 2n 个数中的最大值和最小值，最少的比较次数是？
A、4n/3 B、2n2 C、3n2 D、3n/2
答案：C
①.将2n个两两比较n次将数字分为两组:含有最大值的较大值一组与含有最小值的较小值一组
②.在较大值组中进行n-1次比较得出最大值
③.在较小值组中进行n-1次比较得出最小值
总共 n + n-1 + n-1 = 3n-2
②.在较大值组中进行n-1次比较得出最大值
③.在较小值组中进行n-1次比较得出最小值
总共 n + n-1 + n-1 = 3n-2