判断题：
1-1
N2logN和NlogN2具有相同的增长速度。 (2分)
1-2
对一棵平衡二叉树，所有非叶结点的平衡因子都是0，当且仅当该树是完全二叉树。(2分)
1-3
无向连通图所有顶点的度之和为偶数。 (2分)
1-4
对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。 (2分)
1-5
若用平方探测法解决冲突，则插入新元素时，若散列表容量为质数，插入就一定可以成功。 (2分)
选择题：
2-1
设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b、d、c、f、e、a、g，则栈S的容量至少是： (2分)
A、1
B、2
C、3
D、4
2-2
在下列所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是： (4分)
A、13、48
B、24、48
C、24、53
D、24、90
2-3
线性表、堆栈、队列的主要区别是什么？(2分)
A、线性表用指针，堆栈和队列用数组
B、堆栈和队列都是插入、删除受到约束的线性表
C、线性表和队列都可以用循环链表实现，但堆栈不能
D、堆栈和队列都不是线性结构，而线性表是
2-4
对N（N≥2） 个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是： (2分)
A、树中一定没有度为1的结点
B、树中两个权值最小的结点一定是兄弟结点
C、树中任一非叶结点的权值一定不小于下一层任一结点的权值
D、该树一定是一棵完全二叉树
2-5
在并查集问题中，已知集合元素0~8所以对应的父结点编号值分别是{ 1, -4, 1, 1, -3, 4, 4, 8, -2 }（注：?n表示树根且对应集合大小为n），那么将元素6和8所在的集合合并（要求必须将小集合并到大集合）后，该集合对应的树根和父结点编号值分别是多少？ (4分)
A、1和-6
B、4和-5
C、8和-5
D、8和-6
2-6
要判断一个整数N（>10） 是否素数，我们需要检查3到√N之间是否存在奇数可以整除N 。则这个算法的时间复杂度是：(2分)
A、O(N/2)
B、O(√NlogN)
C、O(√N)
D、O(0.5logN)
2-7
在一个有权无向图中，如果顶点b到顶点a的最短路径长度是10，顶点c与顶点b之间存在一条长度为3的边。那么下列说法中有几句是正确的？ (2分)
1.c与a的最短路径长度就是13
2.c与a的最短路径长度就是7
3.c与a的最短路径长度不超过13
4.c与a的最短路径不小于7
A、1句
B、2句
C、3句
D、4句
2-8
将MMM个元素存入用长度为SSS的数组表示的散列表，则该表的装填因子为： (2分)
A、S+M
B、M?S
C、M×S
D、M/S
2-9
给定输入序列 {4371, 1323, 6173, 4199, 4344, 9679, 1989} 以及散列函数 h(X)=X % 10 。如果用大小为10的散列表，并且用分离链接法解决冲突，则输入各项经散列后在表中的下标为：（-1表示相应的插入无法成功）(2分)
A、1, 3, 3, 9, 4, 9, 9
B、1, 3, 4, 9, 7, 5, -1
C、1, 3, 4, 9, 5, 0, 8
D、1, 3, 4, 9, 5, 0, 2
2-10
在拓扑排序算法中用堆栈和用队列产生的结果会不同吗？(2分)
A、是的肯定不同
B、肯定是相同的
C、有可能会不同
D、以上全不对
2-11
将 {28, 15, 42, 18, 22, 5, 40} 逐个按顺序插入到初始为空的最小堆（小根堆）中。则该树的前序遍历结果为：(4分)
A、5, 18, 15, 28, 22, 42, 40
B、5, 15, 18, 22, 28, 42, 40
C、5, 18, 28, 22, 15, 42, 40
D、5, 15, 28, 18, 22, 42, 40
2-12
将1~6这6个键值插到一棵初始为空的二叉搜索树中。如果插入完成后，搜索树结构如图所示，问：可能的插入序列是什么？ (2分)
A、1 2 3 4 5 6
B、4 1 2 3 5 6
C、4 1 3 2 6 5
D、4 1 3 2 5 6
2-13
给定一有向图的邻接表如下。从顶点V1出发按广度优先搜索法进行遍历，则得到的一种顶点序列为： (2分)
A、V1,V2,V3,V4,V5
B、V1,V2,V3,V5,V4
C、V1,V3,V2,V4,V5
D、V1,V4,V3,V5,V2
2-14
已知一个图的邻接矩阵如下，则从顶点V1出发按深度优先搜索法进行遍历，可能得到的一种顶点序列为： (2分)
A、V1,V2,V3,V4,V5,V6
B、V1,V2,V4,V5,V6,V3
C、V1,V3,V5,V2,V4,V6
D、V1,V3,V5,V6,V4,V2
2-15
给出关键字序列{ 4321, 56, 57, 46, 28, 7, 331, 33, 234, 63 }，下面哪个选择是按次位优先（LSD）链式基数排序进行了一趟分配和收集的结果？ (2分)
A、→331→4321→33→63→234→56→46→57→7→28
B、→4321→331→33→63→234→56→46→57→7→28
C、→56→28→4321→331→33→234→46→57→63→7
D、→57→46→28→7→33→234→63→56→4321→331
2-16
将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下：
第1趟排序后：2, 12, 16, 10, 5, 34, 88
第2趟排序后：2, 5, 10, 12, 16, 34, 88
则可能的排序算法是：(2分)
A、冒泡排序
B、快速排序
C、归并排序
D、插入排序
2-17
给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：(2分)
A、24
B、23
C、18
D、17
2-18
在利用堆栈将下列哪个中缀表达式转换为后缀表达式过程中，堆栈的操作系列为: push(′?′)、push(′(′)、push(′+′)、pop()、pop()、pop()、push(′?′)、pop()、push(′+′)、pop() (2分)
A、2*(3+4)*5+6
B、2*(3+4*5)+6
C、2*(3+4*5+6)
D、以上都是
2-19
采用线性探测冲突解决策略,hi(k)=(H(k)+i)mod11 ，将散列函数值分别等于2、2、3、3的四个对象a1、a2、a3、a4都插入一个大小为11的空散列表(哈希表)中。在不同的插入顺序中，哪句有关插入后散列表平均成功查找长度的判断是错的？ (4分)
A、按a1、a2、a3、a4顺序和按a1、a3、a4、a2顺序，平均成功查找长度一样;
B、按a1、a3、a2、a4顺序和按a3、a1、a2、a4顺序，平均成功查找长度一样;
C、按a1、a3、a2、a4顺序和按a4、a1、a2、a3顺序，平均成功查找长度一样;
D、按任何插入顺序，其平均成功查找长度都一样.
2-20
将10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7逐个按顺序插入到初始为空的最小堆中，然后连续执行两次删除最小元素操作（DeleteMin），再插入4，16，此后堆顶的元素是什么？ (2分)
A、