考试时长：120分钟

一 不定项选择题（共25题，每题4分，共100分，少选、错选、多选均不得分）

A．CFHGEBDA   B．CDFEGHBA   C．FGHCDEBA   D．CFHGEDBA

解析：由先序遍历序列和中序遍历序列可以唯一确定树的结构

    步骤： 由先序序列确定根节点；按根节点把中序序列分为两端，前面的是左子树，后面的是右子树；对左右子树重复前面的步骤 

    还原树形结构：

        根节点：A

                D          B

          C        E

                F      G

                            H   

    后续遍历序列：CFHGEDBA   

    答案选 D

2 下列哪两个数据结构，同时具有较高的查找和删除性能？（）

A．有序数组     B．有序链表      C．AVL树        D．Hash表

解析：几种常见的数据结构的操作性能对比如下图所示

    由上图可见，平衡二叉树的查找，插入和删除性能都是O(logN)，其中查找和删除性能较好；哈希表的查找、插入和删除性能都是O(1)，都是最好的。

    答案：CD    

3 下列排序算法中，哪些时间复杂度不会超过nlogn？（BC）

A．快速排序     B．堆排序        C．归并排序      D．冒泡排序

解析：几种常见的排序算法对比：