1、下列叙述中，不正确的是 单选题 2分

2、下列关于栈中逻辑上相邻的两个数据元素的叙述中，正确的是 单选题 2分

3、对带头结点的单循环链表从头结点开始遍历（head为头指针，p=head->next）。若指针p指向当前被遍历结点，则判定遍历过程结束的条件是 单选题 2分

4、设栈的入栈序列为1，2，3，4，5，经过入、出栈操作后，可能得到的出栈序列是 单选题 2分

5、数组A[2][3]按行优先顺序存放，A的首地址为10。若A中每个元素占用一个存储单元，则元素A[1][2]的存储地址是 单选题 2分

6、广义表（（a，b），（c，d））的表尾是 单选题 2分

7、若完全二叉树T包含20个终端结点，则T的结点数最多是 单选题 2分

8、对下面的二叉树进行中序线索化后，结点f的右指针指向的结点是 单选题 2分

9、若图G是一个含有n个顶点的强连通有向图，则G的边数至少是 单选题 2分

10、若从顶点a开始对下图进行广度优先遍历，则不可能得到的遍历序列是 单选题 2分

11、下列排序算法中，稳定的是 单选题 2分

12、下列排序算法中，比较操作的次数与待排序序列初始排列状态无关的是 单选题 2分

13、若对二叉排序树进行遍历，则下列遍历方式中，其遍历结果为递增有序的是 单选题 2分

14、设一组记录的关键字为（12，22，10，20，88，27，54，11]，散列函数为H（key）=key%11，用拉链法解决冲突，则散列地址为0的链中结点数是 单选题 2分

15、在下面3阶B树中插入关键字65后，其根结点内的关键字是 单选题 2分

16、散列方法的基本思想是根据元素的关键字直接计算出该元素的（ ）。 填空题 2分

17、一个需要频繁增删的线性表宜选择（ ）存储结构。 填空题 2分

18、若中缀表达式为9+（6-2）*8，则相应的后缀表达式是（ ）。 填空题 2分

19、对任何一棵二叉树T，若其叶子结点数为no，度数为2的结点数为nz，则nz等，于（ ）。 填空题 2分

20、若某二叉树T的前序遍历序列是A，B，C，D，中序遍历序列是B，A，D，C，则T的后序遍历序列是（ ）。 填空题 2分

21、在给定n个叶子结点权值且不含度数为1的结点的所有二叉树中，其（ ）最小的二叉树称为哈夫曼树。 填空题 2分

22、用邻接表存储含n个顶点e条边的有向无环图G，对G进行拓扑排序，算法的时间复杂度为（ ）。 填空题 2分

23、连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的（ ）树。 填空题 2分

24、二分查找的速度快效率高，但是它要求表按关键字有序并且（ ）。 填空题 2分

25、除了问题的规模和分量个数之外，还有（ ）是影响基数排序时间复杂度的主要因素。 填空题 2分

26、对题26图所示的带权无向图G，试回答以下问题。（1）画出G的最小生成树；（2）若用克鲁斯卡尔（Kruskal）算法求最小生成树，请按被选中的次序写出最小生成树上各条边的顶点和权值。 简答题 5分

27、 简答题 5分

28、试回答下列关于拓扑排序算法的问题。 （1）算法中利用一个栈保存入度为0的顶点，其目的是什么？ （2）若在算法中将队列改为栈，相应地将入、出栈及判栈空操作改为入、出队列和判队列空操作，其他部分不变，是否依然能够得到拓扑排序的正确结果？ 简答题 5分

29、考虑用快速排序、堆排序和归并排序3种排序方法对数据序列进行排序，针对下列不同情况，宜分别选择哪种排序方法？ （1）使用尽量少的存储空间； （2）要求排序结果是稳定的； （3）快速找出数据序列中关键字值较大的若干项。 简答题 5分

30、 简答题 5分

31、 简答题 5分

32、 简答题 5分

33、 简答题 5分

34、 简答题 10分