选择题
-
给定一个整数sum，从有N个有序元素的数组中寻找元素a，b，使得a+b的结果最接近sum，最快的平均时间复杂度是（ ）
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn) -
分析以下函数的空间复杂度
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) -
下列判断带头结点双向循环链表为空的语句中，正确的是（ ）
A.head == null;
B.head.next == null;
C.head.next == head;
D.head != null; -
下列数据结构中，不属于线性表的是（ ）
A.循环队列
B.链表
C.动态顺序表
D.二叉树 -
关于链表和顺序表间的区别，叙述错误的是（ ）
A.链表和顺序表都属于线性表
B.链表不能随机访问其中的某个元素，顺序表可以
C.链表能做的事，顺序表都可以完成，只是操作方法不同，效率不同
D.链表在进行插入和删除的时候，速度总是比顺序表快 -
链栈与顺序栈相比，比较明显的优点是（ ）
A.插入操作更加方便
B.删除操作更加方便
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) -
下列关于用栈实现队列的说法中错误的是（ ）
A.用栈模拟实现队列可以使用两个栈，一个栈模拟入队列，一个栈模拟出队列
B.每次出队列时，都需要将一个栈中的全部元素导入到另一个栈中，然后出栈即可
C.入队列时，将元素直接往模拟入队列的栈中存放即可
D.入队列操作时间复杂度为O(1) -
将一颗有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根节点编号为 1 ，则编号为 98 的节点的父节点编号为（ ）
A.47
B.48
C.49
D.50 -
将一棵二叉树的根结点放入队列，然后递归的执行如下操作，将出队结点所有子结点先左后右式的加入队。以上操作可以实现哪种遍历？
A.前序遍历
B.中序遍历
C.后序遍历
D.层序遍历 -
如果一颗二叉树的前序遍历的结果是ABCD，则满足条件的不同的二叉树有（ ）种
A.13
B.14
C.15
D.16 -
二叉树的( )遍历相当于广度优先遍历，( )遍历相当于深度优先遍历
A.前序 中序
B.中序 前序
C.层序 后序
D.层序 前序 -
多选：下面关于栈和队列的说法中错误的是（ ）
A.队列和栈通常都使用链表实现
B.队列和栈都只能从两端插入、删除数据
C.队列和栈都不支持随机访问和随机插入
D.队列是“先入先出”，栈是“先入后出” -
下列关于顺序结构实现循环队列的说法，正确的是（ ）
A.循环队列的长度通常都不固定
B.直接用队头和队尾在同一个位置可以判断循环队列是否为满
C.通过设置计数的方式可以判断队列空或者满
D.循环队列是一种非线性数据结构 -
一颗完全二叉树有1001个结点，其叶子结点的个数是（ ）
A.251
B.500
C.501
D.不能确定 -
下列关于二叉树的叙述错误的是（ ）
A.二叉树指的是深度为 2 的树
B.一个 n 个结点的二叉树将拥有 n-1 条边
C.一颗深度为 h 的满二叉树拥有 2^h-1 个结点（根结点深度为1）
D.二叉树有二叉链和三叉链两种表示方式 -
在一颗度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，则叶子结点有（ ）个
A.4
B.5
C.6
D.7 -
设根结点的深度为1，则一个拥有n个结点的二叉树的深度一定在（ ）区间内
A.[log(n + 1)，n]
B.[logn，n]
C.[log(n + 1)，n - 1]
D.[log(n + 1)，n + 1] -
一颗拥有1000个结点的树度为4，则它的最小深度是（ ）
A.5
B.6
C.7
D.8 -
已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（ ）
A.ABDGHJKCEFILM
B.ABDGJHKCEILMF
C.ABDHKGJCEILMF
D.ABDGJHKCEIMLF -
一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
A.所有的结点均无左孩子
B.所有的结点均无右孩子
C.只有一个叶子结点
D.至多只有一个结点 -
在一颗完全二叉树中，某一个结点没有其左孩子，则该结点一定（ ）
A.是根结点
B.是叶结点
C.是分支结点
D.在倒数第二层 -
下列关于向下调整算法的说法正确的是（ ）
A.构建堆的时候要对每个结点都执行一次
B.删除操作时要执行一次
C.插入操作时要执行一次
D.以上说法都不正确 -
在一个堆中，根节点从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 -
下列关于归并排序的说法中正确的是（ ）
A.归并排序不需要辅助空间
B.归并排序的时间复杂度是O(logn)
C.归并排序是稳定排序
D.归并排序的操作方式类似二叉树的前序遍历 -
现有数字序列 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.希尔排序
B.快速排序
C.堆排序
D.冒泡排序 -
若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是
A.快速排序
B.堆排序
C.归并排序
D.直接插入排序 -
以下排序方式中占用O（n）辅助存储空间的是
A.简单排序
B.快速排序
C.堆排序
D.归并排序 -
关于排序，下面说法不正确的是
A.快排时间复杂度为O(N*logN)，空间复杂度为O(logN)
B.归并排序是一种稳定的排序,堆排序和快排均不稳定
C.序列基本有序时，快排退化成冒泡排序，直接插入排序最快
D.归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN) -
下列排序算法中，占用辅助空间最多的是（ ）
A.归并排序
B.快速排序
C.希尔排序
D.堆排序 -
.以下哪种排序算法对[1, 3, 2, 4, 5, 6, 7, 8, 9]进行排序最快（ ）
A.直接插入排序
B.快速排序
C.归并排序
D.堆排序 -
下列选项中，不可能是快速排序第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 -
下列关于快速排序的非递归算法的说法中错误的是（ ）
A.快速排序的非递归遍历可以使用栈模拟二叉树的前序遍历的方式实现
B.快速排序的非递归遍历可以使用队列模拟二叉树的层序遍历的方式实现
C.快速排序的非递归遍历可以明显的提升排序的速度
D.快速排序的非递归遍历大大降低了栈空间的开销 -
下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）
① 选择排序
② 归并排序
③ 快速排序
④ 堆排序
A.①④
B.①②④
C.①③④
D.①②③④ -
下列排序算法中，最坏时间复杂度不为O(n^2)的是（ ）
A.堆排序
B.快速排序
C.选择排序
D.插入排序 -
用某种排序方法对关键字序列 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.快速排序 -
采用哈希表组织100万条记录，以支持字段A快速查找，则下列说法错误的是( )
A.理论上可以在常数时间内找到特定记录
B.所有记录必须存在内存中
C.拉链式哈希法最坏查找时间复杂度是O（n）
D.哈希函数的选择跟A无关 -
散列函数有一个共同性质，即函数值应按（）取其值域的每一个值。
A.最大概率
B.最小概率
C.同等概率
D.平均概率 -
下面关于哈希说法正确的是（）
A.哈希是一种查找的方法，不是数据结构
B.采用哈希方式解决问题时，可以不用哈希函数
C.哈希查找的时间复杂度一定是O(1)
D.哈希是以牺牲空间为代价，提高查询的效率 -
关于二叉搜索树特性说法错误的是（ ）
A.二叉搜索树最左侧的节点一定是最小的
B.二叉搜索树最右侧的节点一定是最大的
C.对二叉搜索树进行中序遍历，一定能够得到一个有序序列
D.二叉搜索树的查找效率为O(log_2N) -
下面关于二叉搜索树正确的说法是（ ）
A.待删除节点有左子树和右子树时，只能使用左子树的最大值节点替换待删除节点
B.给定一棵二叉搜索树的前序和中序遍率历结果，无法确定这棵二叉搜索树
C.给定一棵二叉搜索树，根据节点值大小排序所需时间复杂度是线性的
D.给定一棵二叉搜索树，可以在线性时间复杂度内转化为平衡二叉搜索树 -
给定n个节点的平衡二叉搜索树，每个节点的值是整数。给定一个整数，在树中找出与该整数最接近的节点的最小算法复杂度是（）
A.Θ(logn)
B.Θ(n^2)
C.Θ(nlogn)
D.Θ(n)
E.Θ(1) -
设哈希表长度为11,哈希函数H(K)=(K的第一个字母在字母表中的序号)MOD11,若输入顺序为(D,BA,TN,M,CI,I,K,X,TA),采用内散列表,处理冲突方法为线性探测法,要求构造哈希表,在等概率情况下查找成功平均查找长度为()
A. 4
B. 3
C. 20/9
D. 23/9 -
若负载因子a为1,则向哈希表中散列元素时一定会产生冲突()
A.对
B.错 -
解决散列法中出现冲突问题常采用的方法是()
A.数字分析法、除余法、平方取中法
B.数字分析法、除余法、线性探测法
C.数字分析法、线性探测法、多重散列法
D.线性探测法、多重散列法、链地址法 -
Java中的集合类包括ArrayList、LinkedList、HashMap等，下列关于集合类描述错误的是？
A.ArrayList和LinkedList均实现了List接口
B.ArrayList的访问速度比LinkedList快
C.随机添加和删除元素时，ArrayList的表现更佳
D.HashMap实现Map接口，它允许任何类型的键和值对象 -
判断对错。List，Set，Map都继承自继承Collection接口。
A.对
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 -
已知某个哈希表的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 -
采用开放定址法处理散列表的冲突时，其平均查找长度？ （）
A.高于链接法处理冲突
B.高于二分查找
C.低于链接法处理冲突
D.低于二分查找 -
采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置空,因为这会影响以后的查找()
A.对
B.错
C.不一定
D.以上说法都不对 -
用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是 ()
A.存储效率
B.数列函数
C.装填（装载）因子
D.平均查找长度 -
设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（ ）个
A.11
B.12
C.13
D.14 -
将一个顺序表利用向下调整的方式整理成堆的时间复杂度为（ ）
A.O(nlogn)
B.O(logn)
C.O(1)
D.O(n)
