前言
纯题目链接：55道数据结构复习题
这里有题目有答案。只想看题目的，文章开头有链接.
选择题
- 给定一个整数sum，从有N个有序元素的数组中寻找元素a，b，使得a+b的结果最接近sum，最快的平均时间复杂度是（ ）
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn)
答案：A
解析：
此题目中，数组元素有序，所以a,b两个数可以分别从开始和结尾处开始搜，根据首尾元素的和是否大于sum,决定搜索的移动，整个数组被搜索一遍，就可以得到结果，所以最好时间复杂度为n
-
分析以下函数的空间复杂度
public static int[][] get2Array(int n){ int[][] array = new int[n][]; for(int i = 0; i < n; i++) { array[i] = new int[n-i]; n--; } return array; }A.O(1)
B.O(N)
C.O(N^2)
D.O(logN)
解析：
该函数的作用是创建一个倒三角的二维数组：
第0行n个int的空间
第1行n-1个int的空间
第2行n-2个int的空间
…
第n-1行1个元素的空间
空间总的个数为：1+2+3+…+N-1 + N + N = (1+N)*N/2 + N = N^2/2 + 3N/2
采用大O渐进发表示就是：O(N^2)
故选择C -
下列判断带头结点双向循环链表为空的语句中，正确的是（ ）
A.head == null;
B.head.next == null;
C.head.next == head;
D.head != null;
带头结点双向循环链表为空的图解：
即：head.prev == head 或者 head.next == head;
故应该选择C -
下列数据结构中，不属于线性表的是（ ）
A.循环队列
B.链表
C.动态顺序表
D.二叉树
答案：D
解析：二叉树属于树形结构，不是线性的，队列，链表，顺序表都属于线性表 -
关于链表和顺序表间的区别，叙述错误的是（ ）
A.链表和顺序表都属于线性表
B.链表不能随机访问其中的某个元素，顺序表可以
C.链表能做的事，顺序表都可以完成，只是操作方法不同，效率不同
D.链表在进行插入和删除的时候，速度总是比顺序表快
答案：D
解析：链表的插入和删除不是所有情况下都比顺序表快，比如尾插尾删，顺序表的时间复杂度为O（1），并且如果是单链表，如果要在中间某个节点的前面插入/删除一个节点，则需要遍历。所以时间的快慢要分情况看待。 -
链栈与顺序栈相比，比较明显的优点是（ ）
A.插入操作更加方便
B.删除操作更加方便
C.入栈时不需要扩容
解析：
A错误，如果是链栈，一般需要进行头插或者头删操作，而顺序栈一般进行尾插和尾删操作，链表的操作比顺序表复杂，因此使用顺序结构实现栈更简单
B错误，原因参考A
C正确，链式结构实现栈时，每次入栈相当于链表中头插一个节点，没有扩容一说 -
现有一循环队列，其队头为front，队尾为rear(rear指向队尾数据的下一个位置)，循环队列长度为N,最多存储N-1个数据。其队内有效长度为（ ）
A.(rear - front + N) % N + 1
B.(rear - front + N) % N
C.(rear - front) % (N + 1)
D.(rear - front + N) % (N - 1)
答案：B
解析：
有效长度一般是rear-front, 但是循环队列中rear有可能小于front，减完之后可能是负数，所以需要+N，此时结果刚好是队列中有效元素个数，但如果rear大于front，减完之后就是有效元素个数了，再加N后有效长度会超过N，故需要%N。 -
下列关于用栈实现队列的说法中错误的是（ ）
A.用栈模拟实现队列可以使用两个栈，一个栈模拟入队列，一个栈模拟出队列
B.每次出队列时，都需要将一个栈中的全部元素导入到另一个栈中，然后出栈即可
C.入队列时，将元素直接往模拟入队列的栈中存放即可
D.入队列操作时间复杂度为O(1)
答案：B
选项B中，一个栈模拟入队列，一个栈模拟出队列，出队列时直接弹出模拟出队列栈的栈顶元素，当该栈为空时，将模拟入队列栈中所有元素导入即可，不是每次都需要导入元素，故错误
选项A中，栈和队列的特性是相反的，一个栈实现不了队列
选项C中，一个栈模拟入队列，一个栈模拟出队列，入队列时，将元素直接往模拟入队列的栈中存放
选项D中，入队列就是将元素放到栈中，因此时间复杂度就是O(1) -
将一颗有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根节点编号为 1 ，则编号为 98 的节点的父节点编号为（ ）
A.47
B.48
C.49
D.50
答案：C -
将一棵二叉树的根结点放入队列，然后递归的执行如下操作，将出队结点所有子结点先左后右式的加入队。以上操作可以实现哪种遍历？
A.前序遍历
B.中序遍历
C.后序遍历
D.层序遍历
解析：
根据题目的描述，显然是层序遍历
故选择D -
如果一颗二叉树的前序遍历的结果是ABCD，则满足条件的不同的二叉树有（ ）种
A.13
B.14
C.15
D.16
答案：B
解析：
首先这棵二叉树的高度一定在3~4层之间:
三层：
A(B(C,D),()), A((),B(C,D)), A(B(C,()),D), A(B((),C),D),
A(B,C(D,())), A(B,C((),D))
四层：
如果为四层，就是单边树，每一层只有一个节点，除过根节点，其他节点都有两种选择，在上层节点的左边还是右边，所以222共8种
总共为14种。 -
二叉树的( )遍历相当于广度优先遍历，( )遍历相当于深度优先遍历
A.前序 中序
B.中序 前序
C.层序 后序
D.层序 前序
答案：D
解析：
广度优先需要把下一步所有可能的位置全部遍历完，才会进行更深层次的遍历，层序遍历就是一种广度优先遍历。
深度优先是先遍历完一条完整的路径（从根到叶子的完整路径），才会向上层折返，再去遍历下一个路径，前序遍历就是一种深度优先遍历。 -
多选：下面关于栈和队列的说法中错误的是（ ）
A.队列和栈通常都使用链表实现
B.队列和栈都只能从两端插入、删除数据
C.队列和栈都不支持随机访问和随机插入
D.队列是“先入先出”，栈是“先入后出”
解析：
A错误：栈是尾部插入和删除，一般使用顺序表实现，队列是头部删除尾部插入，一般使用链表实现
B错误：栈是后进先出，尾部插入和删除；队列是先进先出，尾部插入头部删除
C正确：栈只能访问栈顶元素，不支持随机访问，队列也不支持
D正确：栈和队列的特性
故错误的是A和B -
下列关于顺序结构实现循环队列的说法，正确的是（ ）
A.循环队列的长度通常都不固定
B.直接用队头和队尾在同一个位置可以判断循环队列是否为满
C.通过设置计数的方式可以判断队列空或者满
D.循环队列是一种非线性数据结构
解析：
队列适合使用链表实现，使用顺序结构(即固定的连续空间)实现时会出现假溢出的问题，因此大佬们设计出了循环队列，循环队列就是为了解决顺序结构实现队列假溢出问题的
A错误：循环队列的长度都是固定的
B错误：队头和队尾在同一个位置时 队列可能是空的，也可能是满的，因此无法判断
C正确：设置计数即添加一个字段来记录队列中有效元素的个数，如果队列中有效元素个数等于空间总大小时队列满，如果队列中有效元素个数为0时队列空
D错误：循环队列也是队列的一种，是一种特殊的线性数据结构
故选择C -
一颗完全二叉树有1001个结点，其叶子结点的个数是（ ）
A.251
B.500
C.501
D.不能确定
答案：C
解析：
该题需要用到二叉树性质：在任意二叉树中，度为0的节点都比度为2的节点多1个，即 n0 = n2 + 1
另外，在完全二叉树中，如果节点总个数为奇数，则没有度为1的节点，如果节点总个数为偶数，只有一个度为1的节点
因此：n0 + n1 + n2 = 1001 节点总数为奇数，没有度为1的节点
n0 + 0 + n2 = 2*n0-1 = 1001 n0 = 501 -
下列关于二叉树的叙述错误的是（ ）
A.二叉树指的是深度为 2 的树
B.一个 n 个结点的二叉树将拥有 n-1 条边
C.一颗深度为 h 的满二叉树拥有 2^h-1 个结点（根结点深度为1）
D.二叉树有二叉链和三叉链两种表示方式
答案：A
解析：
A错误: 二叉树指最大孩子个数为2，即树的度为二的树。深度描述的为树的层数。
B正确: 对于任意的树都满足：边的条数比节点个数少1，因为每个节点都有双亲，但是根节点没有
C正确: 正确，参加二叉树性质
D正确: 二叉链一般指孩子表示法，三叉连指孩子双亲表示法，这两种方式是二叉树最常见的表示方式，虽然还有孩子兄弟表示法，该中表示方式本质也是二叉链 -
在一颗度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，则叶子结点有（ ）个
A.4
B.5
C.6
D.7
答案：C
解析：
设度为i的节点个数为ni, 该树总共有n个节点,则n=n0+n1+n2+n3.
有n个节点的树的总边数为n-1条.
根据度的定义,总边数与度之间的关系为：n-1=0n0+1n1+2n2+3n3.
联立两个方程求解,可以得到n0 = n2 + 2n3 + 1, n0=6 -
设根结点的深度为1，则一个拥有n个结点的二叉树的深度一定在（ ）区间内
A.[log(n + 1)，n]
B.[logn，n]
C.[log(n + 1)，n - 1]
D.[log(n + 1)，n + 1]
答案：A
解析：
最大深度： 即每次只有一个节点，次数二叉树的高度为n，为最高的高度
最小深度： 此树为完全二叉树， 如果是完全二叉树
根据二叉树性质，完全二叉树的高低为 h = log(n+1)向上取整
故选择A -
一颗拥有1000个结点的树度为4，则它的最小深度是（ ）
A.5
B.6
C.7
D.8
答案：B
解析：
如果这棵树每一层都是满的，则它的深度最小，假设它为一个四叉树，高度为h，则这个数的节点个数为(4^h - 1) / 3，当h = 5, 最大节点数为341， 当h = 6, 最大节点数为1365，所以最小深度应该为6。 -
已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（ ）
A.ABDGHJKCEFILM
B.ABDGJHKCEILMF
C.ABDHKGJCEILMF
D.ABDGJHKCEIMLF
答案：B
解析：
由后序遍历确定子树的根，后序遍历从后向前看，最后一个元素为根，和前序遍历刚好相反，从后向前看后序遍历，应该是根，右，左，根据中序遍历确定子树的左右区间
故：根为: A
A的左子树：JGDHKB A的右子树：ELIMCF
A的左子树的根：B A的右子树的根：C
B的左子树：JGDHK B的右子树：空 C的左子树：ELIM C的右子树：F
B的左子树的根：D C的左子树根：E
D的左子树的根：G D的右子树的根：H E的右子树的根:I
故树的结构为：
故前序遍历：
A B D G J H K C E I L M F -
一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
A.所有的结点均无左孩子
B.所有的结点均无右孩子
C.只有一个叶子结点
D.至多只有一个结点
答案：C
解析：
前序遍历：根 左 右
后序遍历：左 右 根
从二叉树 前序 和 后序遍历结果规则中可以看出，如果树中每个节点只有一个孩子时，遍历结果肯定是反的
比如下面这前序和中序序列所构成的树的结构:
12345
54321
故每个节点只有一个孩子，即只有一个叶子节点 -
在一颗完全二叉树中，某一个结点没有其左孩子，则该结点一定（ ）
A.是根结点
B.是叶结点
C.是分支结点
D.在倒数第二层
答案：B
解析：
完全二叉树中如果一个节点没有左孩子，则一定没有右孩子，必定为一个叶子节点，最后一层一定为叶子节点，但是倒数第二层也可能存在叶子节点。 -
下列关于向下调整算法的说法正确的是（ ）
A.构建堆的时候要对每个结点都执行一次
B.删除操作时要执行一次
C.插入操作时要执行一次
D.以上说法都不正确
答案：B
解析：
A: 建堆时，从每一个非叶子节点开始，倒着一直到根节点，都要执行一次向下调整算法。
B: 删除元素时，首先交换堆顶元素与堆中最后一个元素，对中有效元素个数减1，即删除了堆中最后一个元素，最后将堆顶元素向下调整
C: 插入操作需要执行向上调整算法。 -
在一个堆中，根节点从0开始编号，下标为 i（i > 0） 的结点的左右孩子结点及父结点的下标分别是（ ）
A.2 i、2 i + 1、i /2
B.2i、2i + 1、(i - 1)/2
C.2i + 1、2i + 2、(i - 1)/2
D.2i + 1、2i + 2、i/2-1
选择C
请参考二叉树性质5，注意性质5中根是从0开始编号的 -
下列关于归并排序的说法中正确的是（ ）
A.归并排序不需要辅助空间
B.归并排序的时间复杂度是O(logn)
C.归并排序是稳定排序
D.归并排序的操作方式类似二叉树的前序遍历
答案：C
解析：
归并排序需要一个辅助空间暂时保存部分区间的排序元素
归并排序是一种二分排序算法，每次都需要给n个元素排序，排序的过程需要logn,即树的高度，所以时间复杂度为nlogn
归并排序中，相同元素的相对位置不会发生变化，所以是稳定排序 -
现有数字序列 5 11 7 2 3 17，目前要通过堆排序进行降序排序，那么由该序列建立的初始堆应为（ ）
A.2 3 7 11 5 17
B.17 11 7 2 3 5
C.17 11 7 5 3 2
D.2 3 5 7 11 17
答案：A
解析：
要降序排列，所以要建小堆，每次把堆顶元素放在当前堆的最后一个位置
建堆要进行向下调整算法（从最后一个非叶子节点开始进行向下调整算法，直到根元素）
5
11 7
2 3 17
5
2 7
11 3 17
2
3 7
11 5 17
所以初始堆序列为： 2 3 7 11 5 17 -
下列各排序法中，最坏情况下的时间复杂度最低的是
A.希尔排序
B.快速排序
C.堆排序
D.冒泡排序
答案：C -
若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是
A.快速排序
B.堆排序
C.归并排序
D.直接插入排序
答案：C -
以下排序方式中占用O（n）辅助存储空间的是
A.简单排序
B.快速排序
C.堆排序
D.归并排序
答案：D -
关于排序，下面说法不正确的是
A.快排时间复杂度为O(N*logN)，空间复杂度为O(logN)
B.归并排序是一种稳定的排序,堆排序和快排均不稳定
C.序列基本有序时，快排退化成冒泡排序，直接插入排序最快
D.归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)
答案：D -
下列排序算法中，占用辅助空间最多的是（ ）
A.归并排序
B.快速排序
C.希尔排序
D.堆排序
答案：A
解析：
归并排序空间复杂度：n
快排： logn
希尔，堆排： 1 -
.以下哪种排序算法对[1, 3, 2, 4, 5, 6, 7, 8, 9]进行排序最快（ ）
A.直接插入排序
B.快速排序
C.归并排序
D.堆排序
答案：A
解析：
次序列接近有序，所以如果是插入排序，时间复杂度逼近O(n)
快排： 逼近O(n^2)
归并和堆排仍然是nlogn -
下列选项中，不可能是快速排序第2趟排序后的结果的是（ ）
A.2 3 5 4 6 7 9
B.2 7 5 6 4 3 9
C.3 2 5 4 7 6 9
D.4 2 3 5 7 6 9
答案：C
解析：
这里说的是快排的第二趟，即在第一趟快排的结果的基础上进行的，如果已经经过了一趟排序，则会通过第一趟选择的基准值划分两个子区间，每个子区间也会以区间内选择的基准值划分成两部分。
A: 第一趟的基准值可以为2， 第二趟的基准值可以为3
B: 第一趟的基准值可以为2， 第二趟的基准值可以为9
C: 第一趟的基准值只能是9，但是第二趟的基准值就找不出来，没有符合要求的值作为基准值，所以不可能是一个中间结果。
D: 第一趟的基准值可以为9， 第二趟的基准值可以为5 -
下列关于快速排序的非递归算法的说法中错误的是（ ）
A.快速排序的非递归遍历可以使用栈模拟二叉树的前序遍历的方式实现
B.快速排序的非递归遍历可以使用队列模拟二叉树的层序遍历的方式实现
C.快速排序的非递归遍历可以明显的提升排序的速度
D.快速排序的非递归遍历大大降低了栈空间的开销
答案：C
解析：
快排的非递归是在模拟递归的过程，所以时间复杂度并没有本质的变化，但是没有递归，可以减少栈空间的开销。栈和队列都可以实现。 -
下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）
① 选择排序
② 归并排序
③ 快速排序
④ 堆排序
A.①④
B.①②④
C.①③④
D.①②③④
答案：C
解析：
选择排序每次选一个最值，放在最终的位置
快速排序每次基准值的位置也可以确定
堆排序每次堆顶元素的位置也可以确定
所以这三种方法都可以每次至少确定一个元素的位置
而归并排序每次都需要对n个元素重新确定位置，所以不能保证每次都能确定一个元素位置，有可能每次排序所有元素的位置都为发生变化。 -
下列排序算法中，最坏时间复杂度不为O(n^2)的是（ ）
A.堆排序
B.快速排序
C.选择排序
D.插入排序
答案：A
解析：
堆排： 堆为完全二叉树，每次调整的时间最坏为logn,所以其时间复杂度最坏为nlogn
快排： 如果每次划分只有一半区间，则时间复杂度为n^2
选择排序：时间复杂度始终为n^2
插入排序：如果序列逆序，每次都需要移动元素，时间复杂度n^2 -
用某种排序方法对关键字序列 25 84 21 47 15 27 68 35 20 进行排序，序列的变化情况采样如下：
20 15 21 25 47 27 68 35 84
15 20 21 25 35 27 47 68 84
15 20 21 25 27 35 47 68 84
请问采用的是以下哪种排序算法（ ）
A.选择排序
B.希尔排序
C.归并排序
D.快速排序
答案：D
解析：
此题中的排序是快排二分排序的思想，第一趟的基准值是25，第二趟的基准值分别是20，47，第三趟的基准值分别是15，21，35，68 -
采用哈希表组织100万条记录，以支持字段A快速查找，则下列说法错误的是( )
A.理论上可以在常数时间内找到特定记录
B.所有记录必须存在内存中
C.拉链式哈希法最坏查找时间复杂度是O（n）
D.哈希函数的选择跟A无关
解析：
A正确：哈希表就是用来查找的数据结构，用空间换取的时间，因此哈希表查找的时间复杂度平均为O(1)，也就是常数范围内就可以找到
B正确：哈希属于内存数据库，即集合中的数据必须在内容中通过哈希的方式组织，才能准确的查找
C错误：哈希表实现时，会通过一些机制限制链表过长的情况，比如：扩容，使用红黑树替换链表，因此肯定不会让所有元素挂到一个链表下的情况发生，因此不会出现O(n)的场景
D正确：哈希函数的选择和数据整体情况有关，与单个元素没有直接关联 -
散列函数有一个共同性质，即函数值应按（）取其值域的每一个值。
A.最大概率
B.最小概率
C.同等概率
D.平均概率
哈希函数设计原则：- 哈希函数应该尽可能简单
- 哈希函数的值域必须在哈希表格的范围之内
- 哈希函数的值域应该尽可能均匀分布，即取每个位置应该是等概率的
因此：选择C
-
下面关于哈希说法正确的是（）
A.哈希是一种查找的方法，不是数据结构
B.采用哈希方式解决问题时，可以不用哈希函数
C.哈希查找的时间复杂度一定是O(1)
D.哈希是以牺牲空间为代价，提高查询的效率
解析：
A：错误，哈希是一种用来进行高效查找的数据结构，查找的时间复杂度平均为O(1)
B：错误，哈希之所以高效，是引用使用了哈希函数将元素与其存储位置之间建立了一一对应的关 系，因此必须使用 哈希函数
C：错误，不一定，因为存在哈希冲突，一般基本都是O(1)
D：正确，采用哈希处理时，一般所需空间都会比元素个数多，否则产生冲突的概率就比较大，影哈希的性能
因此：选择D -
关于二叉搜索树特性说法错误的是（ ）
A.二叉搜索树最左侧的节点一定是最小的
B.二叉搜索树最右侧的节点一定是最大的
C.对二叉搜索树进行中序遍历，一定能够得到一个有序序列
D.二叉搜索树的查找效率为O(log_2N)
二叉搜索树的概念：
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3. 它的左右子树也分别为二叉搜索树
从概念中可以得出以下性质：
1. 二叉搜索树中最左侧节点一定是最小的，最右侧节点一定是最大的
2. 对二叉搜索树进行中序遍历，可以得到一个有序的序列
A：正确
B：正确
C：正确
D：错误，二叉搜索树最差情况下会退化为单支树，因此：其查找的效率为O(N)
因此：选择D -
下面关于二叉搜索树正确的说法是（ ）
A.待删除节点有左子树和右子树时，只能使用左子树的最大值节点替换待删除节点
B.给定一棵二叉搜索树的前序和中序遍率历结果，无法确定这棵二叉搜索树
C.给定一棵二叉搜索树，根据节点值大小排序所需时间复杂度是线性的
D.给定一棵二叉搜索树，可以在线性时间复杂度内转化为平衡二叉搜索树
解析：
A：错误，当待删除节点的左右子树均存在时，既可以在左子树中找一个最大的节点作为替代节 点，也可以在右子树中找一个最小的节点作为替代节点，左右子树中都可以找替代节点
B：错误，根据前序遍历和中序遍历，是可以确定一棵树的结构，使用两个遍历结果确定树的结构， 其中有一个遍历结果必须要是中序遍历结果。
C：正确，二叉搜索树遍历一遍，就可以得到一个有序序列，因此，时间复杂度为O(N)
D：错误，这里面还需要牵扯到旋转等其他操作，时间复杂度不是线性的
因此：选择C -
给定n个节点的平衡二叉搜索树，每个节点的值是整数。给定一个整数，在树中找出与该整数最接近的节点的最小算法复杂度是（）
A.Θ(logn)
B.Θ(n^2)
C.Θ(nlogn)
D.Θ(n)
E.Θ(1)
注意：二叉平衡搜索树是二叉树，同时也是平衡树，即：每个节点左右子树高度差的绝对值不超过1，换句话说每个节点左右子树顶多差一层，
在平衡二叉树中查找元素时，找的规则和二叉搜索树的规则一样，最差情况下比较的是树的高度
二叉平衡搜索树的高度为：O(logn) 以2为底
故选择A -
设哈希表长度为11,哈希函数H(K)=(K的第一个字母在字母表中的序号)MOD11,若输入顺序为(D,BA,TN,M,CI,I,K,X,TA),采用内散列表,处理冲突方法为线性探测法,要求构造哈希表,在等概率情况下查找成功平均查找长度为()
A. 4
B. 3
C. 20/9
D. 23/9
根据需要存放到哈希表的数据使用线性探测法进行存放。得出如下表结构：
表格下方的数字，就是查找成功的次数。得出答案选择C。 -
若负载因子a为1,则向哈希表中散列元素时一定会产生冲突()
A.对
B.错
答案：B
哈希冲突不是一定会产生，只有待插入元素通过哈希函数计算出要插入的位置，该位置上有数据时才会发生哈希冲突 -
解决散列法中出现冲突问题常采用的方法是()
A.数字分析法、除余法、平方取中法
B.数字分析法、除余法、线性探测法
C.数字分析法、线性探测法、多重散列法
D.线性探测法、多重散列法、链地址法
解析：
注意要区分清楚：哈希冲突的处理方法和哈希函数
哈希函数作用是：建立元素与其存储位置之前的对应关系的，在存储元素时，先通过哈希函数计算 元素在哈希表格中的存储位置，然后存储元素。好的哈希函数可以减少冲突的概 率，但是不能够绝对避免，万一发生哈希冲突，得需要借助哈希冲突处理方法来 解决。
常见的哈希函数有：直接定址法、除留余数法、平方取中法、随机数法、数字分析法、叠加法等
常见哈希冲突处理：闭散列（线性探测、二次探测）、开散列(链地址法)、多次散列
因此：选择D -
Java中的集合类包括ArrayList、LinkedList、HashMap等，下列关于集合类描述错误的是？
A.ArrayList和LinkedList均实现了List接口
B.ArrayList的访问速度比LinkedList快
C.随机添加和删除元素时，ArrayList的表现更佳
D.HashMap实现Map接口，它允许任何类型的键和值对象
解析：
A正确：ArrayList 和 LinkedList都是线性结构，都实现了List接口
B正确：ArrayList底层是连续的空间，支持随机访问，访问任意位置元素时间复杂度为O(1) 而LinkedList底层是链式接口，访问任意位置元素时必须遍历链表，时间复杂度为O(N)
C错误：随机添加和删除元素时，顺序表要慢一点，因为要将插入或者删除位置的元素整体往后或者往前搬移，时间复杂度为O(N)而LinkedList只需要修改几个引用的指向即可，时间复杂度为O(1)
D正确，HashMap中存放的元素类型为键值对，注意内置类型不能直接来实例化HashMap，必须要找其对应的包装类型 -
判断对错。List，Set，Map都继承自继承Collection接口。
A.对
B.错
List 和 Set 继承自Collection接口，Map没有
故选择B -
已知有一个关键字序列：（19，14,23,1,68,20,84,27,55,11,10,79）散列存储在一个哈希表中，若散列函数为H（key）=key%7，并采用链地址法来解决冲突，则在等概率情况下查找成功的平均查找长度为()
A.1.5
B.1.7
C.2.0
D.2.3
14、1、23、10、11、19、20: 比较1次就可以找到
84、79、68、27：需要比较两次才可以找到
55: 需要比较三次才可以找到
总的比较次数为：7+4*2+3=18，总共有12个元素
故：等概率情况下查找成功的平均查找长度为：18/12 = 1.5
因此：选择A -
已知某个哈希表的n个关键字具有相同的哈希值，如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行（）次探测。
A.n-1
B.n
C.n+1
D.n(n+1)
E.n(n+1)/2
F.1+n(n+1)/2
解析：
元素1：探测1次
元素2：探测2次
元素3：探测3次
。。。
元素n：探测n次
故要将n个元素存入哈希表中，总共需要探测：1+2+3+…+n = n*(n+1)/2
因此：选择E -
采用开放定址法处理散列表的冲突时，其平均查找长度？ （）
A.高于链接法处理冲突
B.高于二分查找
C.低于链接法处理冲突
D.低于二分查找
开放定址法一旦产生冲突，冲突容易连在一起，引起一连篇的冲突，链地址法一般不会
因此：选择A -
采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置空,因为这会影响以后的查找()
A.对
B.错
C.不一定
D.以上说法都不对
线性探测采用未删除法，当从哈希表中删除某个元素时，并没有将该元素真正的删除掉，而是采用标记的方式处理，但是不能直接将该位置标记为空，否则会影响从该位置产生冲突的元素的查找。
因此：选择A -
用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是 ()
A.存储效率
B.数列函数
C.装填（装载）因子
D.平均查找长度
冲突越多，查找时比较的次数就越多，对平均查找长度影响比较大。
因此：选择D -
设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（ ）个
A.11
B.12
C.13
D.14
答案：C
解析：
设Ni表示度为i的节点个数，则节点总数 N = N0 + N1 + N2
节点个数于节点边的关系： N个节点的树有N-1个边
边与度的关系：N - 1 = N1 + 2 * N2
故：N0 + N1 + N2 - 1 = N1 + 2 * N2
因此，得：N0 = N2 + 1
回到原题，N0 = 3，N1 = 8，可得N2 = 2。
因此答案是 3 + 8 + 2 = 13。 -
将一个顺序表利用向下调整的方式整理成堆的时间复杂度为（ ）
A.O(nlogn)
B.O(logn)
C.O(1)
D.O(n)
答案：D
解析：
题目说了是利用向下调整的方式建堆， 正确的证明方法应当如下：
A.具有n个元素的平衡二叉树，树高为㏒n，我们设这个变量为h。
B.最下层非叶节点的元素，只需做一次线性运算便可以确定大根，而这一层具有2(h-1)个元素，我们假定O(1)=1，那么这一层元素所需时间为2(h-1) × 1。
C.由于是bottom-top建立堆，因此在调整上层元素的时候，并不需要同下层所有元素做比较，只需要同其中之一分支作比较，而作比较次数则是树的高度减去当前节点的高度。因此，第x层元素的计算量为2^(x) × (h-x)。
D.又以上通项公式可得知，构造树高为h的二叉堆的精确时间复杂度为：
S = 2^(h-1) × 1 + 2^(h-2) × 2 + …… +1 × (h-1) ①
E.通过观察第四步得出的公式可知，该求和公式为等差数列和等比数列的乘积，因此用错位相减法求解，给公式左右两侧同时乘以2，可知：
2S = 2^h × 1 + 2^(h-1) × 2+ …… +2 × (h-1) ②
用②减去①可知： S =2^h × 1 - h +1 ③
将h = ㏒n 带入③，得出如下结论：
S = n - ㏒n +1 = O(n)
