牛客专项训练之数据结构_用二进制来编码字符串“xyzwxyxx”,需要能够根据编码解码回原来的字符串,则我们最

牛客专项训练之数据结构

字符串

1. 2022 小鹏汽车 Java
   System.out.println(“5” + 2);的输出结果应该是（）
   A 52
   B 7
   C 2
   D 5
   正确答案：A
   官方解析：Java会自动将2转换为字符串
   知识点：字符串
   单选题

自如真题
2.
2022 自如 Java
定义如下程序：
public class Student{
public String name;
public Student(String name){
this.name = name;
}
}
public class Test implements Cloneable{
public Student st;
public static void main(String[] args){
Student s1 = new Student(“Tom”);
Test t1 = new Test();
t1.st = s1;
Test t2 = (Test) t1.clone();
}
}
以下表达式中值为true的是?
A
t1 == t2
B
t1.equals(t2)
C
t1.st != t2.st
D
t1.st.equals(t2.st)
正确答案：D
官方解析：
深拷贝和浅拷贝：浅拷贝实际上是复制了被拷贝对象的引用，也就是说浅拷贝的和被拷贝对象指向的是同一块内存空间，而深拷贝则是连同引用的对象也被拷贝，两者指向的是不同的内存空间。必须是Test类中的Student属性是相等的，故选D。
知识点：字符串
单选题

自如真题
3.
2022 自如 Java
下面哪个流类属于面向字符的输入流
A
BufferedWriter
B
FileInputStream
C
ObjectInputStream
D
InputStreamReader
正确答案：D
官方解析：Java的IO操作中有面向字节(Byte)和面向字符(Character)两种方式。 面向字节的操作为以8位为单位对二进制的数据进行操作，对数据不进行转换，这些类都是InputStream和OutputStream的子类。 面向字符的操作为以字符为单位对数据进行操作，在读的时候将二进制数据转为字符，在写的时候将字符转为二进制数据，这些类都是Reader和Writer的子类。
知识点：字符串
单选题

京东真题
4.
2022 京东 Java
KMP匹配算法中，子串S= ’aaaab‘，主串T= ’abaaaabca‘。求匹配过程中的比较次数？
A
6
B
7
C
8
D
9
正确答案：C
官方解析：
第一轮

a b a a a a b c a

a a a a b(比较2次)

第二轮

a b a a a a b c a

a a a a b(比较1次)

第三轮

a b a a a a b c a

a a a a b(比较5次)

共8次

知识点：字符串
多选题

远景真题
5.
2022 远景智能 Java
String str = new String(“abc”)，“abc”在内存中是怎么分配的？
A
堆
B
栈
C
字符串常量区
D
寄存器
正确答案：AC
官方解析：首先将这行代码分成String str、=、"abc"和new String()四部分来看待。String str只是定义了一个名为str的String类型的变量，因此它并没有创建对象；=是对变量str进行初始化，将某个对象的引用（或者叫句柄）赋值给 它，显然也没有创建对象；现在只剩下new String(“abc”)了。我们是使用new调用了String类的上面那个构造器方法创建了一个对象，并将它的引用赋值给了str变量。但是发现该构造函数的参数是一个String类型的，我们要知道String本身就是一个对象。而该对象正是“abc”。

所以得出结论，这行代码一共创建了两个对象，一个是str引用所指向在堆内存中的对象，一个是“abc”，故选AC。

知识点：字符串

2022 游卡 Java
正则表达式不能进行下面哪个操作？
A
替换所有数字。
B
将最外层成对双引号（"）内的字符解析出来。
C
替换字符串内的所有ABC/Abc/abc为空字符串。
D
检查字符串内的括号是否成对出现。
正确答案：D
官方解析：正则表达式只能匹配字符是否出现，或者匹配多次，无法匹配括号是否成对出现。
知识点：字符串
单选题

哔哩哔哩真题
2.
2021 哔哩哔哩 Java
用正则表达式a+?b来尝试匹配aaabbb可以匹配到的结果是
A
aaabbb
B
ab
C
aaab
D
b
正确答案：C
官方解析：
+表示匹配多个字符，?表示匹配一个或者0个字符，故这里可以把3个a匹配完，然后匹配一个b，选C。
知识点：字符串
单选题

360集团真题
3.
2022 奇虎360 Java
在串的简单模式匹配中，当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是？
A
i++
B
i=j+1
C
i=i-j+1
D
i=j-i+1
正确答案：C
官方解析：在简单的模式匹配中，当两个字符不等时，目标串i回溯到原来未知的下一个位置，即i=i-j+1
知识点：字符串
单选题

奇安信真题
4.
2021 奇安信 Java
中缀表达式5+4*(x+3)-6所对应的后缀表达式为
A
5 4 x 3 + * 6 + -
B
5 4 x 6 3 + * + -
C
5 4 x 3 6 + * + -
D
5 4 x 3 + * + 6 -
正确答案：D
官方解析：
中缀表达式中应该先计算x+3，因此后缀表达式中+应该出现在x和3的后面，排除BC。
然后计算乘法，故之后是*，再计算加法，因此+要在6的前面，不然就是计算4*(x+3)+6了，故选D。
知识点：字符串
单选题

自如真题
5.
2022 自如 Java
用二进制来编码字符串“xyzwxyxx”，需要能够根据编码解码回原来的字符串，则我们最少需要多长的二进制字符串
A
12
B
14
C
15
D
18
正确答案：B
官方解析：
xyzwxyxx：x：4位、y：2位、z：1位、w：1位
用4、2、1、1构造哈夫曼树
知识点：字符串

2022 自如 Java
只能输入零和非零开头的数字，正确的正则表达式是
A
^(0|[1-9][0-9])$
B
^(0|[1-9][1-9])$
C
^(0|[1-9][0-9])$
D
^+[1-9][0-9]*$
正确答案：A
官方解析：只能输入至少n位的数字：“^\d{n,}$"。只能输入零和非零开头的数字：{"}^{(}0|[1-9][0-9]\ast )$”。
知识点：字符串

数组

2022 自如 Java
下列哪个可以存储重复的数据元素？
A
List
B
Set
C
HashMap
D
Collection
正确答案：A
官方解析：
List特点：有序(存进去和取出来的顺序一致)，有索引，方便查询，但是增删元素较慢，可以存储重复元素；
其余容器都是要去重的。
知识点：数组
单选题

远景真题
2.
2022 远景智能 Java
有一个二维数组A[10][5]，每个数据元素占1个字节，且A[0][0]的存储地址是1000，则A[i][j]的地址是多少 ？
A
1000+10i+j
B
1000+i+j
C
1000+5i+j
D
1000+10i+5j
正确答案：C
官方解析：A[5][5]的地址为：51002+5*2+10=1020，千万不要忘记基址是10，不是0
知识点：数组
单选题

小米集团真题
3.
2022 小米 Java
下面程序段运行结果是什么？
int i=0;
int a[]={3,6,4,8,5,6};
do{
a[i]-=3;
}while(a[i++]<4);
for(i=0;i<6;i++)
{
printf(“%d”,a[i]);
}
A
031556
B
064856
C
031523
D
364856
正确答案：A
官方解析：
第一个do while循环，将数组每个元素都依次减3，直到减后的数字不小于4，故此时的数组为031556，然后第二个for循环输出该数组，结果选A。
知识点：数组
单选题

虾皮信息真题
4.
2022 shopee Java
线性表常用操作是随机存取第n个元素和其前驱的值，采用（ ）存储方式节省时间
A
单链表
B
双链表
C
单循环链表
D
顺序表
正确答案：D
官方解析：题目要求了随机访问第n个元素，顺序表才能满足
知识点：数组
多选题

小米集团真题
5.
2022 小米 Java
关于数组和链表以下说法错误的是
A
数组逻辑上相邻的元素在物理存储位置上也相邻，而链表一定不相邻
B
链表的长度是按实际需要可以伸缩，而数组的长度是在定义时要给定
C
插入和删除时，数组平均需要移动n/2个元素，而链表只需修改指针即可
D
查找制定节点，数组和链表平均时间复杂度都为O(1)
正确答案：AD
官方解析：
A选项，数组在物理内存中不一定是相邻的，这取决于数组是位于物理内存还是虚拟内存，现代CPU大多是分页内存系统，把物理内存以固定大小映射给虚拟内存，并且用MMU进行虚拟内存地址到物理内存地址的转换。而MMU可以被CPU开关，如果关闭，直接访问物理地址，如果MMU打开，则直接查找page table结构进行转换。
D选项，链表需要遍历查找，平均复杂度为O(n)
知识点：数组

2022 奇虎360 Java
选择下列错误的选项？
A
数组大小无法扩容
B
数组添加、删除操作方便
C
数组支持索引访问
D
数组是线性数据结构
正确答案：B
官方解析：数组不擅长插入（添加）和删除元素。数组的优点在于它是连续的，所以查找数据速度很快。但这也是它的一个缺点。正因为它是连续的，所以当插入一个元素时，插入点后所有的元素全部都要向后移；而删除一个元素时，删除点后所有的元素全部都要向前移。
知识点：数组
单选题

星环科技真题
2.
2022 星环科技 Java
下面哪一个java 的数据结构，在多线程情况下，是线程不安全的
A
vector
B
ArrayList
C
hashtable
D
ConcurrentHashMap
正确答案：B
官方解析：在多线程的任务执行中，常用的Java数据结构是线程不安全的——ArrayList HashMap HashSet等 非同步——多个线程可能同时读写，出现数据错误或抛出异常传统
知识点：数组
单选题

游卡真题
3.
2022 游卡 Java
Array 实例的方法不包括
A
copyWithin
B
length
C
reverse
D
toString
正确答案：B
官方解析：
length是属性不是方法
reverse和toString是常见的方法
copyWithin() 方法用于从数组的指定位置拷贝元素到数组的另一个指定位置中。
知识点：数组
多选题

途虎真题
4.
2021 途虎养车 Java
在Java中类型ArrayList中，添加一个元素（add方法）的时间复杂度是
A
O(1)
B
O(logn)
C
O(n)
D
O(nlogn)
正确答案：AC
官方解析：
在Java中类型ArrayList中，添加一个元素（add方法）默认添加到末尾，则平均复杂度为O(1)，
若是要添加到指定位置，则平均复杂度为O(n)，故选AC。
知识点：数组
多选题

真题
5.
2021 光汇石油 Java
下列说法错误的有
A
数组是一种对象
B
数组属于一种原生类
C
int number=[]={31,23,33,43,35,63}
D
数组的大小可以任意改变
正确答案：BCD
官方解析：
a、数组是能被Object 一切能被Obj 接收的均为对象；
b、数组不是原生类 原生类有8种， int double boolean float byte short long char ；
c、语法错误、
d、数组的大小一开始就已经确定了 int[]test=new test[2];
知识点：数组

二叉树

2022 自如 Java
二叉树的根节点计为第1层结点，则第9层最多有多少个结点？
A
18
B
256
C
128
D
64
正确答案：B
官方解析：
二叉树的第i层最多有2^{i-1}个节点，故第9层有256个，选B。
知识点：树
单选题

小米集团真题
2.
2022 小米 Java
一棵完全二叉树共有54711个节点，则它有多少个叶子节点？
A
27356
B
10824
C
21944
D
32768
正确答案：A
官方解析：, 故二叉树一共16层；
前15层总结点数为, 最后一层的叶子节点数为, 最后一层空节点数为, 故倒数第二层的叶子数为, 最后两层的叶子节点数加起来为
知识点：树
单选题

星环科技真题
3.
2022 星环科技 Java
树的高度是指根到叶子节点的最长路径的边数(根的高度为0)。一个二叉树的中序遍历序列为 KAFDEBGC，前序遍历序列为 EFAKDGBC，则该二叉树的高度为
A
2
B
3
C
4
D
5
正确答案：B
官方解析：
重构后的二叉树如下：

知识点：树
多选题
4.
2022 小米 Java
关于以下说法正确的有
A
二叉查找树的节点如果有左右子树，那么左右子树都是二叉查找树
B
一个树有四个节点（abcd), 他们的值为(1234)，每一个节点都是前一个节点的右节点，如c是b的右节点，则该树是二叉查找树
C
红黑树是一种接近平衡的二叉树，且根节点是黑色
D
红黑树如果一个节点是红色，则它的子节点必须是黑色
正确答案：ABCD
官方解析：
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。 在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 结点是红色或黑色。
性质2. 根结点是黑色。
性质3. 所有叶子都是黑色。（叶子是NIL结点）
性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
故选ABCD。

知识点：树
题友讨论(0)
多选题

小米集团真题
5.
2022 小米 Java
有一颗二叉树的前序遍历和后序遍历分别是1,2,3,4和4,3,2,1，则该二叉树的中序遍历可能是
A
1 2 3 4
B
2 3 4 1
C
4 3 2 1
D
3 2 4 1
正确答案：ABC
官方解析：分别用前序序列依次跟A、B、C、D四个选项的中序序列搭配，求其对应后序序列是否跟题目给的一致。即：前+中=>后
前序 + 中序 => 后序的关键点在于：（以A为例）
1、前序的第一个节点为根，即：1；
2、在中序中找到根节点的位置，划分左右子树（根节点左边的是左子树，根节点右边的是右子树），即2，3，4都是右子树；
3、现已确定根节点位置，再借助递归的思想分别求出其他节点位置。即：将根节点从原先序列中去掉，则前序序列｛2，3，4｝，中序序列｛2，3，4｝，再次利用步骤1、2做法，2为根节点，3，4是其右子树，这样确定下来2的位置；递归下去，确定所有树中节点位置。然后便可求得其后序序列｛4，3，2，1｝，与题目符合，A正确。
同样的方法BC正确，D不正确。

知识点：树

2022 小米 Java
在一棵二叉树上第10层的节点数最多是
A
128
B
256
C
512
D
1024
正确答案：C
官方解析：
二叉树，每个节点最多有两个子节点，第n层最多有2^(n-1)个，故选C。
知识点：树
单选题

星环科技真题
2.
2022 星环科技 Java
若一颗完全二叉树中某节点无左孩子，则该节点是
A
高度为1的节点
B
高度为2的节点
C
分支节点
D
叶子节点
正确答案：D
官方解析：完全二叉树可以看做是满二叉树从右往左，从下往上删除节点得到的。也就是说，完全二叉树的生成遵从从左往右，从上到下的顺序。一棵完全二叉树某节点如果没有左孩子，则一定不会有右孩子，那这个节点一定是个叶子结点。
知识点：树
单选题

阿里巴巴真题
3.
2022 阿里巴巴 Java
由权值分别为1、12、13、4、8的叶子节点生成一颗哈夫曼树，它的带权路径长度为
A
12
B
68
C
43
D
81
正确答案：D
官方解析：
Hoffman树如下：
38
*13 25
*12 13
5 *8
*1 4
其中带为原始元素，总共4层（不算根节点） 带权路径长度
38+25+13+5=81
知识点：树
单选题

自如真题
4.
2022 自如 Java
如果一个二叉树中任意节点的左右子树“高度”相差不超过 1，我们称这个二叉树为“高度平衡二叉树”。根据如上定义，一个高度为 8 的高度平衡二叉树至少有几个节点？
A
33
B
34
C
54
D
55
正确答案：C
官方解析：
使用递推的思想:
P(N)=N层平衡二叉树的最少节点数
那么P(N)=P(N-1)+P(N-2)+1
P(1)=1
P(2)=2
P(3)=P(1)+P(2)+1=4
…
P(8)=P(6)+P(7)+1=20+33+1=54
知识点：树
多选题

小米集团真题
5.
2022 小米 Java
关于二叉树描述正确的有哪些？
A
在二叉树的第 i 层上至多有2的 i次方个结点。(i≥1)
B
深度为 k 的二叉树至多有 2的 k次方减1个结点。（k≥1）
C
叶子结点只可能在层次最大的一层上出现
D
子树有左右之分，其次序不能任意颠倒
正确答案：BD
官方解析：
在二叉树第i层上至多有2^{i-1}个结点，最少有一个
深度为k的二叉树至多有2^k-1个结点，最少有k个
叶子结点：度为0的结点，非完全二叉树，可能存在不同层上
知识点：树

链表

2021 奇安信 Java
单链表中指针p指向节点m，若要删除m之后的结点（若存在），则需修改指针的操作为
A
p->next=p->next->next
B
p=p->next
C
p=p->next->next
D
p->next=p
正确答案：A
官方解析：
直接将节点m的next指针指向它后一位节点的后一位。
知识点：链表
单选题

人人网真题
2.
2022 人人网 Java
设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点x，则在结点A和结点B插入结点X的操作序列是？
A
s.next=p.next; p.next=s;
B
q.next=s; s.next=p;
C
p.next=s.next; s.next=p;
D
p.next=s; s.next=q;
正确答案：B
官方解析：
因为在这里A节点的后继已经被p指针记录了，所以不必担心丢失。可以先断开链接，再指向。
一般情况下，中间结点要先指向后继节点，才能断开链接。故选B。

知识点：链表
单选题

小米集团真题
3.
2021 小米 Java
在双向链表中，删除指针p所指向的结点时需要的操作是
A
p->next->prior=p->prior p->prior->next=p->next
B
p->next=p->next->next p->next->prior=p
C
p->prior->next=p p->prior=p->prior->prior
D
p->prior=p->next->next p->next=p->prior->prior
正确答案：A
官方解析：
如图所示：

说明：p->prior = o p->next = q(“=”代表指向，不代表赋值)

则p->prior->next = o->next

删除节点两步走：

q->prior (p->next->prior) = o(p->prior); //让q的前指针指向p的前节点

o->next(p->prior->next) = q(p->next); //o的后指针指向p的后节点（把原来的p跳了）

即：让p的前后节点连在一起

知识点：链表
单选题

小米集团真题
4.
2022 小米 Java
单向链表已经可以实现非连续存储，为什么还需要双向链表？
A
双向链表更稳定
B
双向链表删除前驱节点更方便
C
双向链表中的任意一个结点都可以直接访问前驱结点和后继结点
D
双向链表复杂度更低
正确答案：B
官方解析：
C选项，双向链表可以删除前驱结点，删除更加方便。
B明显错误，首尾结点分别没办法直接定位到前驱和后驱结点。
知识点：链表
多选题

小米集团真题
5.
2021 小米 Java
下列关于顺序表和链表的说法中，正确的有：
A
顺序表中，逻辑上相邻的元素，对应的物理存储位置也相邻；
B
从长度为N的表中找出第i个元素时，顺序表的时间复杂度为O(1)，链表的时间复杂度为O(n)；
C
顺序表需要预先分配存储空间，在静态存储分配情形下，一旦存储空间装满就不能扩充；链表则只需要在插入元素时申请存储空间，只要内存还有空间就可以分配；
D
存储同样的数据，顺序表和链表占用的存储空间大小相同；
正确答案：ABC
官方解析：
D选项，链表要分配指针的空间，故存储空间更大。
知识点：链表

2022 人人网 Java
在以下哪个操作中，数组比链表更快？
A
原地逆序
B
头部插入
C
返回头结点
D
返回随机结点
正确答案：D
官方解析：A.原地逆序如果是双向链表会比数组快 B.头部插入，链表只需要操作一个指针插入即可，数组需要一个一个挪 C.返回头节点，评论说是一样快，所以要看更快不行 D.数组返回比链表一个个快，给个下标就行，数组是连续存储，一次性分配很多内存空间，非常好找 链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。
知识点：链表
单选题

百度真题
2.
2021 百度 Java
在⼀个带头结点的单链表HL 中，若要在第⼀个元素之前插⼊⼀个由指针p 指向的结点，则执⾏？
A
p.next = HI ;p =HL ;
B
p.next = HL ;HL =p ;
C
HL =p; p.next =HL ;
D
p.next = HL.next;HL.next =p;
正确答案：D
官方解析：
第一个元素之前有一个头指针。首先p->next = HL -> next
再将头指针指向当前的首个元素 HL -> next = p

知识点：链表
单选题

小米集团真题
3.
2021 小米 Java
带头结点的循环双向链表（头指针记为L）为空的判定条件是：
A
LNULL
B
L->nextL
C
L->nextNULL
D
L->priorNULL
正确答案：B
官方解析：首先题目假设是带头节点，所以题目中至少包含一个节点，带头循环双向链表为空表示只有当前头结点。
由于给定链表是循环的，不可能出现L.prior == NULL或L.next == NULL的情况。所以C、D错。
由于链表是带头节点的链表，L !=NULL，所以A错。
B表示当前链表只有头结点，无其他节点，符合题意，选择B选项。
知识点：链表
单选题

小米集团真题
4.
2022 小米 Java
在一个单链表中，用指针p节点替代指针q节点的下一个节点(下一个节点不是最后一个节点)，则执行
A
p->next = q->next -> next; q->next = q->next->next; q->next = p;
B
q->next = q->next->next; p->next = q->next; q->next = p;
C
p->next = q->next->next; q-next-> = p; q->next = q->next->next;
D
q-next-> = p; q->next = q->next->next; p->next = q->next -> next ;
正确答案：B
官方解析：q->next=q->next->next 删除q的下一个点

p->next = q->next,q->next=p 将p插入q后面，实现对原来q->next的替换
知识点：链表
多选题

虾皮信息真题
5.
2022 shopee Java
关于翻转一个长度为n的单向链表，以下说法中正确的是
A
可以在O(1)的常量级别空间复杂度完成
B
时间复杂度最低可以是O(N)
C
可以通过递归的方式实现
D
以上都不正确
正确答案：ABC
官方解析：
翻转链表可以使用双指针在链表上直接操作，空间复杂度为O(1)；时间复杂度不管是递归还是迭代都要遍历整个链表，故选ABC。
知识点：链表

队列

2021 阿里巴巴 Java
下面关于队列和栈的描述正确的选项
A
栈是先进先出的数据结构
B
队列是先进先出的数据结构
C
栈内元素可以随机访问
D
队列内的元素可以随机访问
正确答案：B
官方解析：
A选项，栈是先进后出的数据结构；CD选项，栈和队列都不允许随机访问。
知识点：队列
单选题

小米集团真题
2.
2021 小米 Java
一个由7维数组(数组索引从0开始)构成的循环队列，队头索引为3，队尾索引为6，如果先入队两个元素，再出队两个元素后，队头和队尾的索引分别是
A
5和1
B
1和5
C
4和2
D
2和4
正确答案：A
官方解析：
6 + 2 = 8
8 % 7 = 1 (rear)
3 + 2 = 5
5 % 7 = 5 (front)
知识点：队列
单选题

阿里巴巴真题
3.
2022 阿里巴巴 Java
有一个用数组C[1…m]表示的环形队列，m为数组的长度。假设f为队头元素在数组中的位置，r为队尾元素的后一位置（按照顺时针方向）。若是队列非空，则计算队列中元素个数的公式应该为？
A
(m+r-f)mod m
B
r-f
C
(m-r+f) mod m
D
(m-r-f) mod m
正确答案：A
官方解析：
分情况讨论：

1. 若f<r<=m, 则有r-f <m，即队尾没有超出边界，则为r-f
2. 若r<f<=m, r-f < 0, 即队尾超出边界m，那么应为m+r -f
   综合两种情况，得到答案 (m+r-f) mod m
   知识点：队列
   单选题

远景真题
4.
2021 远景智能 Java
使用一个长度最大为150的队列，对满二叉树进行广度优先遍历时，能够容纳的二叉树的最大深度（第一层深度为1）为（）
A
8
B
10
C
9
D
7
正确答案：A
官方解析：满二叉树每一层的结点个数为（第一层深度为1）第n层的节点数：2^(n-1),如果使用150的队列进行广度优先遍历，
则每一层的节点数不大于150，2^{(n-1)≤150，2}7=128,2^8=256，n-1最多为7，所以最大深度n=8.
知识点：队列
单选题

360集团真题
5.
2021 360 Java
下列关于顺序存储的循环队列的说法，正确的一项是
A
在直接使用顺序存储的循环队列时，仍存在类似于使用顺序队列时存在的“假溢出”问题
B
在直接使用顺序存储的循环队列时，若有队头指针与队尾指针指向同一单元，则此时队列为空
C
在直接使用顺序存储的循环队列时，若有队头指针与队尾指针指向同一单元，则此时队列为满
D
在直接使用顺序存储的循环队列时，队头指针与队尾指针的逻辑循环均可使用取模运算来实现
正确答案：D
官方解析：在顺序队列操作中，假溢出的现象为：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间。所以A错。
在这种循环队列中，队列满时，front 与tail也是相等的。所以BC错。

知识点：队列
1.
2021 360 Java
设有一个大小为6的顺序循环队列，采用少用一个存储单元的策略来区分队满与队空。若当前front=2，rear=5，则最多还可入队的元素个数是？
A
0
B
2
C
4
D
5
正确答案：B
官方解析：
rear在5，经过循环队列的6、1之后就与front相遇，因此还能加入2个元素。
知识点：队列
单选题

虾皮信息真题
2.
2022 shopee Java
设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，每一个元素出栈后立即进入队列Q，若6个元素出队列的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是？
A
6
B
4
C
3
D
2
正确答案：C
官方解析：
每操作一次 栈的状态是 e1
e1 e2
e1
e1 e3
e1 e3 e4
e1 e3
e1
e1 e5
e1 e5 e6
e1 e5
e1
空
所以要求最小值应该为 3
知识点：队列
单选题

奇安信真题
3.
2021 奇安信 Java
循环队列的队满条件为
A
ring.end%maxsize == ring.front
B
(ring.end+1)%maxsize == ring.front
C
(ring.end+1)%maxsize == ring.front+1
D
(ring.end+1)%maxsize == (ring.front+1)%maxsize
正确答案：B
官方解析：约定循环队列的队头指针指示队头元素在数组中实际位置的前一个位置，队尾指针指示队尾元素在数组中的实际位置。当队尾指针“绕一圈”后赶上队头指针时，视为队满。
知识点：队列
单选题

哔哩哔哩真题
4.
2021 哔哩哔哩 Java
用俩个栈模拟实现一个队列，如果栈的容量分别是O和P(O>P),那么模拟实现的队列最大容量是多少？
A
O+P
B
2O+1
C
2P+1
D
2O-1
正确答案：C
官方解析：最后p和o全部出栈，不能有p+1在p前面的情况，必须保证先进先出，所以p全部出栈时是1、2…p，o比p大，我们暂且存p+1个就是从p+1…2p+1，出栈后放入p中，只能放2p+1…p+2，此时o中还剩个p+1，现在我们已经得到1…p，再将o中的p+1出栈，再将之前o压到p中的元素出栈，可以得到1…2p+1；如果o中再多存一个，存到2p+2的话，那最后o中就会剩p+2和p+1，出栈的时候p+2在p+1前面，不符合队列的先进先出了，所以最多只能到2p+1
知识点：队列
多选题

奇安信真题
5.
2021 奇安信 Java
关于栈和队列，下列说法正确的有
A
可以使用队列模拟栈，但栈不能模拟队列
B
栈和队列都不支持随机访问
C
栈是一种树形数据结构
D
栈具有后进先出的特征
正确答案：BD
官方解析：
A选项，栈和队列都可以相互模拟；
C选项，栈和队列都是线性数据结构。
故选BD。
知识点：队列

堆

2021 奇安信 Java
已知关键码序列6，9，12，19，28，20，16，22，23，30是最小堆，插入关键码7，调整后得到的最小堆是？
A
6,9,12,7,19,28,20,16,22,23,30
B
6,7,12,19,9,20,16,22,23,30,28
C
6,9,12,7,19,30,20,16,22,23,28
D
6,7,12,19,28,29,9,16,22,23,30
正确答案：B
官方解析：
首先将要插入的元素加入到堆的末尾，然后观察其与父节点的关系，父节点为28大于7，交换位置，此时28到了对的最末尾，排除AD。然后继续与父节点9交换位置，故选B。
知识点：堆
单选题

阿里巴巴真题
2.
2022 阿里巴巴 Java
下列关键字序列为堆的是？
A
100，60，70，50，32，65
B
60，70，65，50，32，100
C
65，100，70，32，50，60
D
70，65，100，32，50，60
正确答案：A
官方解析：
最大（最小）堆是一棵每一个节点的键值都不小于（大于）其孩子（如果存在）的键值的树。大顶堆是一棵完全二叉树，同时也是一棵最大树。小顶堆是一棵完全完全二叉树，同时也是一棵最小树。

结果中， 是数组形式存储的树。只有A符合定义。
知识点：堆
单选题

微众银行真题
3.
2021 微众银行 Java
堆是一种有用的数据结构，在以下排序码序列中小根堆是
A
16,72,31,23,94,53
B
94,53,31,72,16,53
C
16,53,23,94,31,72
D
16,31,23,94,53,72
正确答案：D
官方解析：
父节点要比子节点小，一个个检查：
A选项23<72；
B选项53<94;
C选项31<94。
知识点：堆
单选题

远景真题
4.
2021 远景智能 Java
堆的形状是一颗什么树？
A
完全二叉树
B
满二叉树
C
二叉排序树
D
平衡二叉树
正确答案：A
官方解析：堆总是满足一下特性：
1.堆中某个结点的值总是不大于或不小于其父结点的值。
2.堆总是一棵完全二叉树。
故选A。
知识点：堆
多选题

奇安信真题
5.
2021 奇安信 Java
关于堆数据结构，下面描述中正确的有
A
可以用堆实现优先队列（priority_queue）
B
使用堆可以实现排序算法，复杂度为N * log N
C
从M个元素中查找最小的N个元素时，使用大顶堆的效率比使用小顶堆更高
D
堆数据结构可以用数组方式存储，存储的是一棵完全二叉树
正确答案：ABCD
官方解析：
A选项，堆排序的时间复杂度符合优先队列要求，故可以使用堆实现优先队列；
B选项，堆排序的时间复杂度为O(NlogN)；
C选项，可以建立一个大小为N个元素的大顶堆记录目前为止最小的N个元素，其中堆顶为这最小N个元素中最大的，后续若是遇到比堆顶更小的元素，说明堆顶不在这N个元素之内，弹出，将更小的新元素加入，直到遍历完M个元素，堆中就是最小的N个元素，这样的复杂度只有O(MlogN)，比起小顶堆直接排序的O(MlogM)要高效不少；
D选项，堆可以使用完全二叉树的形式，用数组记录，再哪一层与数组下标有关。
知识点：堆

2022 阿里巴巴 Java
下列关键字序列为堆的是？
A
100，60，70，50，32，65
B
60，70，65，50，32，100
C
65，100，70，32，50，60
D
70，65，100，32，50，60
正确答案：A
官方解析：
最大（最小）堆是一棵每一个节点的键值都不小于（大于）其孩子（如果存在）的键值的树。大顶堆是一棵完全二叉树，同时也是一棵最大树。小顶堆是一棵完全完全二叉树，同时也是一棵最小树。

结果中， 是数组形式存储的树。只有A符合定义。
知识点：堆
单选题

中国电子云真题
2.
2021 中国系统 Java
下列关键字序列为堆的是
A
60，70，65，50，32，100
B
65，100，70，32，50，60
C
100，60，70，50，32，65
D
32，50，100，70，65，60
正确答案：C
官方解析：
最大（最小）堆是一棵每一个节点的键值都不小于（大于）其孩子（如果存在）的键值的树。大顶堆是一棵完全二叉树，同时也是一棵最大树。小顶堆是一棵完全完全二叉树，同时也是一棵最小树。结果中， 是数组形式存储的树。只有C符合定义。
知识点：堆
单选题

奇安信真题
3.
2021 奇安信 Java
已知关键码序列6，9，12，19，28，20，16，22，23，30是最小堆，插入关键码7，调整后得到的最小堆是？
A
6,9,12,7,19,28,20,16,22,23,30
B
6,7,12,19,9,20,16,22,23,30,28
C
6,9,12,7,19,30,20,16,22,23,28
D
6,7,12,19,28,29,9,16,22,23,30
正确答案：B
官方解析：
首先将要插入的元素加入到堆的末尾，然后观察其与父节点的关系，父节点为28大于7，交换位置，此时28到了对的最末尾，排除AD。然后继续与父节点9交换位置，故选B。
知识点：堆
单选题

腾讯真题
4.
2022 腾讯 Java
初始序列为1 8 6 2 5 4 7 3一数组采用堆排序，当小根堆建立完毕时，堆所对应的二叉树的中序遍历是多少？
A
8 3 2 5 1 6 4 7
B
3 2 8 5 1 4 6 7
C
3 8 2 5 1 6 7 4
D
8 2 3 5 1 4 7 6
正确答案：A
官方解析：初始化序列1 8 6 2 5 4 7 3，小根堆就是要求节点的值小于其左右孩子节点的值，左右孩子的大小之间没有关系，那么排序后的小根堆为1 2 4 3 5 6 7 8，中序遍历先遍历左孩子，然后访问根节点，最后访问右孩子，故结果为8 3 2 5 1 6 4 7。
知识点：堆
单选题

伴鱼少儿英语真题
5.
2021 伴鱼 Java
有一个小顶堆构建于数组之上 [1、2、3、4、5、6、7、8、9] 当删除了根节点1，调整后结果应该是
A
[2、3、4、8、5、6、7、9]
B
[2、4、3、5、8、6、7、9]
C
[2、3、4、8、5、7、6、9]
D
[2、4、3、8、5、6、7、9]
正确答案：D
官方解析：
删除根节点1，2上升变成根节点，2的字节点中取较小的4代替2的位置，然后4的字节点取较小的8代替4的位置，为了维持完全二叉树的形状，9移动到之前8的位置，故删除之后的顺序应该是24385679，选C。
知识点：堆

2022 shopee Java
对数组[45, 31, 47, 50, 90, 78, 34]构建一个大顶堆， 则结果是：
A
[90, 50, 47, 78, 45, 31, 34]
B
[90, 45, 78, 50, 31, 34, 47]
C
[90, 50, 78, 45, 21, 47, 34]
D
[90, 47, 78, 50, 45, 31, 34]
正确答案：C
官方解析：
大根堆从最后开始最后一个非叶子节点开始，也即数组长度一半-1，为47，与其两个子节点比较，78>47，将78换上来。然后下一个非叶子节点31与90交换。然后下一个非叶子节点45与90交换。这样左边子树部分不满足堆的条件， 因为换下来的45<50，需要再交换位置。因此最终的序列是[90, 50, 78, 45, 21, 47, 34]，故选C。
知识点：堆
单选题

小米集团真题
2.
2021 小米 Java
现有一整型数组，a[8] = { 4,8,7,0,3,5,9,1}，现使用堆排序的方式原地对该数组进行升序排列。那么在进行第一轮排序结束之后，数组的顺序为
A
8 4 7 0 5 3 9 1
B
7 8 4 0 9 1 3 5
C
8 3 7 1 0 5 4 9
D
8 4 7 0 1 5 9 3
正确答案：C
官方解析：先按序列建堆，然后调整为大顶堆，9是序列的最大值，第一轮排序时，9为堆的根节点，9出堆，与堆的最末元素交换位置，此时堆再此调整为大顶堆，第一轮排序结束，即为8 3 7 1 0 5 4 9
知识点：堆

栈

2022 阿里巴巴 Java
设有四个元素A、B、C、D顺序进栈，在进栈过程中可以出栈，出栈次序错误的排列是？
A
ABCD
B
ACDB
C
DCAB
D
ACBD
正确答案：C
官方解析：
A：A进A出，B进B出，C进C出，D进D出。
B：A进A出，B进，C进C出，D进D出，B出。
D：A进A出，BC进CB出，D进D出。

知识点：栈
单选题

京东真题
2.
2022 京东 Java
栈S1，S2,大小分别是2，1。先进栈A，再进栈B。栈满再出，A、B、C、D依次进栈，则出栈顺序是？
A
BCDA
B
BACD
C
CDAB
D
DCAB
正确答案：A
官方解析：
因为要求栈满才能出，因此A进入S1，B进入S2，此时S1不能出，但是S2可以出，因此B出栈，然后C和D进栈，因此C要在D之前出去，因此C进入S2，D进入S1，刚好填满两个栈，依次出栈刚好是CDA，故选A。
知识点：栈
单选题

百度真题
3.
2021 百度 Java
若栈 S1 中保存整数，栈 S2 中保存运算符，函数 F()依次执行下述各步操作：
（1）从 S1 中依次弹出两个操作数 a 和 b；
（2）从 S2 中弹出一个运算符 op；
（3）执行相应的运算 b op a；
（4）将运算结果压人 S1 中。
假定 S1 中的操作数依次是 3, 9, 3, 2（2 在栈顶），S2 中的运算符依次是*, - , +（+在栈顶）。调 用 3 次 F()后，S1 栈顶保存的值是?
A
12
B
-12
C
9
D
-9
正确答案：A
官方解析：
S1第一次 弹出 a,b 即 2,3 S2 弹出 “ +” 操作为 b + a 即 （3 + 2） 压入 S1 现在 S1 为 3 9 5
S1第二次弹出 a,b 即 5 ，9 S2弹出"-" 操作为 b - a 即（9-5） 压入S1 现在 S1 为 3 4
S1第三次弹出a,b 即 3,4 S2弹出 “” 操作为 ba 即 3*4 压入S 现在S1 为 12
所以三次后S1 栈顶为12
知识点：栈
单选题

阿里巴巴真题
4.
2021 阿里巴巴 Java
栈中有元素abcdef，每次出栈可以选择一个或者两个元素出栈，当有两个元素出栈时可以选择其中一个重新入栈，当所有元素为空，那么可能的出栈方式有（ ）种？
A
22
B
21
C
32
D
20
正确答案：C
官方解析：
当只有一个元素a时，只有1种出栈方式；
当只有两个元素ab时，有2种出栈方式，（ba正常出栈，ab先出两个，再把b加入栈中）；
当只有三个元素abc时，可考虑先出元素c，那么ab有两种方式，可以考虑先出cb，然后将c加入回栈中，剩下的ac也有两种方式，总共4种；
按照此规律，每增加一个元素，就会在上一个的基础上增加2倍的出栈方式，当元素个数为6时，有32种方式，选A。
知识点：栈
多选题
5.
2021 小米 Java
若元素a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列有
A
a f e d c b
B
a b c d e f
C
a b c f e d
D
b a e f c d
正确答案：ACD
官方解析：
首先判定逻辑，将入栈标记为1，2，3……所以某数出栈时栈内只会有比他小的数并且按顺序排列好。所以得结论，出栈时任意数右边比他小的数组成的子序列必将降序。ABCD逻辑都对，继续判定题目要求，不能连续出栈3次。那就找连续降序序列。B中连续降序序列大小为5，故不符合。
知识点：栈

2021 小米 Java
假设有一个栈，元素依次进栈的顺序是A,B,C,D,E。下列不可能的出栈顺序是
A
E,D,C,B,A
B
A,B,C,D,E
C
B,C,D,E,A
D
E,A,B,C,D
正确答案：D
官方解析：
进一个出一个的序列为B
AB进栈B出栈C进栈出栈D进栈出栈E进栈出栈A出栈的序列为D
全部进栈再出栈的序列为A，栈为先进后出的数据结构，无论如何都不会出现D的情况，故选D
知识点：栈
单选题

阿里巴巴真题
2.
2022 阿里巴巴 Java
一个栈的入栈序列为abcde，则不可能的输出序列为哪个？
A
edcba
B
dceab
C
decba
D
abedc
正确答案：B
官方解析：
e已经进栈了，a不可能比b先出栈，故选B。
知识点：栈
单选题

美团真题
3.
2022 美团 Java
设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进⼊栈S。若每个元素出栈后⽴即进⼊队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量⾄少是？
A
2
B
3
C
4
D
5
正确答案：B
官方解析：
ABCDEF依次进栈，出列的顺序为CDBFEA，栈的特点是后进先出
A进栈，（栈内为A）
B进栈，（栈内为A，B）
C进栈，（栈内为A，B，C）
C出栈，（栈内为 A，B）
B出栈，（栈内为A）
E进栈，（栈内为A，E）
F进栈，（栈内为A，E，F）
F出栈，（栈内为A，E）
E出栈，（栈内为A）
A出栈，
所以容量至少要有3
知识点：栈
单选题

小米集团真题
4.
2021 小米 Java
以下哪一个不是栈的基本运算？
A
删除栈顶元素
B
删除栈底的元素
C
判断栈是否为空
D
将栈置为空栈
正确答案：B
官方解析：栈是一种特殊的线性表，只能在固定的一端进行插入和删除操作。允许插入和删除的一端称为栈顶(TOP)，另一端称为栈底(BOTTOM)。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素。因此不能直接删除栈底的元素。
知识点：栈
单选题

星环科技真题
5.
2022 星环科技 Java
栈S最多能容纳4个元素。现在6个元素按A、B、C、D、E、F的顺序进栈，下列哪一个序列不是可能的出栈序列？
A
A、B、C、D、E、F
B
A、F、E、D、C、B
C
C、B、E、D、A、F
D
C、D、B、E、F、A
正确答案：B
官方解析：A的操作为，A入栈，出栈，B入栈，出栈，C入栈，出栈，D入栈，出栈，E入栈，出栈，F入栈，出栈，
B的操作为，A先入栈，然后出栈，接着BCDEF，然后出栈，但是由于S最多容纳4个元素，所以不可能实现。
C的操作为，ABC入栈，C出栈，B出栈，DE入栈，E出栈，D出栈，A出栈，F入栈，F出栈
D的操作为，ABC入栈，C出栈，D入栈，D出栈，B出栈，E入栈，E出栈，F入栈，F出栈，A出栈
知识点：栈

图

2021 小米 Java
已知有向图，G = (V, E), V = {V1,V2,V3,V4,V5}, E = {<V1,V4>,<V1, V2>,<V2, V4>, <V2, V3>, <V4, V3>, <V3, V5>, <V4, V5>}
则G的拓扑序列为：
A
V1,V2,V3,V4,V5
B
V1,V2,V4,V3,V5
C
V1,V2,V3,V5,V4
D
V1,V2,V5,V3,V4
正确答案：B
官方解析：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。
（1）每个顶点出现且只出现一次；
（2）若A在序列中排在B的前面，则在图中不存在从B到A的路径。
此拓扑排序的思想是：

（1）从有向图中选取一个没有前驱的顶点，并输出之；

（2）从有向图中删去此顶点以及所有以它为尾的弧；
第一步： 删除V1，
第二步： 可选的没有前驱的点只有V2
第三步 ：下一步选择删除V2，可选的只有V4
第四步： 下一步选择删除V4，可选的只有V3
第五步： 下一步选择删除V5，可选的只有最后剩下V5
所以排序为V1,V2,V4,V3,V5

根据以上思路，可以推出只有答案B才是对的。

知识点：图
单选题

百度真题
2.
2021 百度 Java
设有6个结点的⽆向图，该图⾄少应有（）条边，才能确保是⼀个连通图？
A
8
B
11
C
6
D
5
正确答案：D
官方解析：已知有N个结点的无向图，该图至少应有(N-l)条边才能确保是一个连通图，最多含有(N(N-1)／2)条边。
因为有两种图，一种是完全连通图，一种是连通图。 完全图是指任意两个结点之间都有一个边相连,也就是结点两两相连；连通图是指任意两个结点之间都有一个路径相连，也就是说只要有连线能相通就好。故选D。
知识点：图
单选题

哔哩哔哩真题
3.
2021 哔哩哔哩 后端开发
下面哪一方法可以判断出一个有向图是否有环（回路)
A
求节点的度
B
拓扑排序
C
求最短路径
D
求关键路径
正确答案：B
官方解析：
利用拓扑排序算法可以判定有向图中是否存在有向回路,即在拓扑排序算法结束后如果还有顶点没有输出,则说明剩下这些结点都还有前驱,它们构成一个有向回路，故选B。
知识点：图
单选题

伴鱼少儿英语真题
4.
2021 伴鱼 后端开发
设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为( )
A
aedfcb
B
acfebd
C
aebcfd
D
aedfbc
正确答案：A
官方解析：A是可以的
B的话f后面应该是d,不应该是e
C的话b后面应该是d,不应该是c
D的话f后面应该是c,不应该是b
知识点：图
单选题

微众银行真题
5.
2021 微众银行 Java
如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是
A
有向完全图
B
连通图
C
强连通图
D
有向无环图
正确答案：D
官方解析：
对角线元素为零,说明没有回路,上三角矩阵说明这个图是有向的(注:无向图的邻接矩阵是对称矩阵),综上:为有向无环图。

知识点：图
1.
2022 阿里巴巴 Java
以下使用了贪心算法的是
A
KMP算法
B
希尔排序算法
C
Floyd算法
D
Dijkstra算法
正确答案：D
官方解析：采用贪心策略，需要满足两个性质：贪心选择性质和最优子结构性质。

求最小生成树的Prim和Kruskal都是漂亮的贪心算法。贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式
知识点：图
单选题

小米集团真题
2.
2021 小米 Java
已知图的邻接矩阵表示为{{0,0,0,1,0,1},{0,0,1,1,0,0},{0,1,0,0,0,0},{1,1,0,0,1,1],{0,0,0,1,0,0},{1,0,0,1,0,0}}，那么从顶点4（顶点的索引从0开始）开始做广度优先遍历，得到图的节点的遍历序列为
A
023145
B
430152
C
532401
D
431205
正确答案：B
官方解析：
根据邻接矩阵，顶点4只和顶点3有连接，顶点另外还连接了顶点015，然后顶点1连接了顶点2，但是因为是从顶点4出发的广度优先搜索，所以105必须连在一起（顺序不用管），故选B。
知识点：图
单选题

远景真题
3.
2021 远景智能 后端开发
对有n 个顶点、 e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是
A
O(n)
B
O(e)
C
O(n+e)
D
O(ne)
正确答案：C
官方解析：广度优先遍历时，也是每个顶点表结点和每个边表结点均查找一次，每个顶点进入队列一次。 所以是选C.
知识点：图
单选题

猿辅导真题
4.
2021 猿辅导 后端开发
一个含有n个顶点和e条边的有向图，在其邻接矩阵存储结构中共有（）个零元素。
A
e
B
2e
C
n^2-2e
D
n^2-e
正确答案：D
官方解析：有向图有几条边，邻接矩阵中就有几个元素非零，因此零元素有n^2-e个。
知识点：图
多选题

远景真题
5.
2021 远景智能 后端开发
下面算法中可以判断出一个有向图是否有环的是：
A
求最短路径
B
深度优先遍历
C
广度优先搜索
D
拓扑排序
正确答案：BD
官方解析：有向图是否有环的判定算法，主要有深度优先和拓扑排序两种方法，所以答案选 BD
知识点：图
1.
2021 远景智能 后端开发
有权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为
A
24
B
73
C
48
D
53
正确答案：B
官方解析：
树的形状如下：
32
11 21
8 13
6 7
2 5
故它的带权长度为111+82+63+24+5*4=73，故选B。
知识点：图
单选题

微众银行真题
2.
2021 微众银行 Java
设某无向图中有n个节点e条边，则建立该图邻接表的时间复杂度为
A
O(n+e)
B
O(n^2)
C
O(ne)
D
O(n^3)
正确答案：A
官方解析：若采用邻接链表存储，建立邻接表或逆邻接表时，
若输入的顶点信息即为顶点的编号，则时间复杂度为O(n+e);
若输入的顶点信息不是顶点的编号，需要通过查找才能得到顶点在图中的位置，则时间复杂度为O(n*e);
故选B。
知识点：图
多选题

小米集团真题
3.
2021 小米 Java
下面关于图的说法中，正确的有：
A
可以使用邻接表或邻接矩阵来存储图；
B
对有n 个顶点、 e 条边且使用邻接表存储的有向图进行广度优先遍历的时间复杂度是O(n+e)；
C
没有回路的连通图也是树；
D
一个确定的有向无环图有且只有一种拓扑排序
正确答案：ABC
官方解析：
A选项，邻接表和邻接矩阵都是图的存储方式；
B选项，邻接表形式存储时，每个顶点均需搜索一次，每次结点被入队一次，出队一次，所以时间复杂度是 O(V)，但是遍历某个顶点所有邻接点的复杂度是 O(ei), ei为第 i 条链表的弧的条数，也就是邻接点个数，所以查找所有邻接点的复杂度为 O(e1 + e2 + … + en) = O(E), 加上对每个结点进行入队出队的复杂度 O(V), 所以总的时间复杂度为O(E + V)；
C选项，树是连通的且没有回路。
D选项，一个有向无环图可能有多种拓扑排序。
知识点：图
多选题

虾皮信息真题
4.
2022 shopee 后端开发
如果一个无向图的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从a顶点出发进行广度优先搜索的可能的顶点序列为
A
abecdf
B
aecbfd
C
aebcdf
D
acebfd
正确答案：ACD
官方解析：a连接着bce三个顶点，因此a后面直接跟bce的任意顺序都行，但如果先遍历e再遍历c，则b、c、e三个顶点都遍历完成后要先遍历与e相连接的顶点，再遍历与c相连接的顶点，因此f不可能在d之前（d与e相连，f与c相连）
知识点：图
多选题

虾皮信息真题
5.
2022 shopee Java
如果一个无向图的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从a顶点出发进行广度优先搜索的可能的顶点序列为
A
abecdf
B
aecbfd
C
aebcfd
D
acebfd
正确答案：ACD
官方解析：
a连接着bce三个顶点，因此a后面直接跟bce的任意顺序都行，但如果先遍历e再遍历c，则b、c、e三个顶点都遍历完成后要先遍历与e相连接的顶点，再遍历与c相连接的顶点，因此f不可能在d之前（d与e相连，f与c相连），故选ACD。
知识点：图

2021 360 后端开发
在下列有关图的说法中正确的是
A
在有向图结构中，顶点可以没有任何前趋和后继
B
在有向图中，各顶点的入度之和等于各顶点的出度之和
C
具有n个顶点的无向图最多有n(n-1)条边，最少有(n-1)条边
D
在无向图中，边的条数是结点度数之和
正确答案：B
官方解析：
A选项：有向图中定点必须要有前驱和后继；
C选项：最少有0条边，n个顶点的联通图最少n-1条边；
D选项，在无向图中，边的条数是结点度数之和的二分之一。
知识点：图
单选题

人人网真题
2.
2022 人人网 Java
一个含有n个顶点和e条边的简洁无向图，在其邻接矩阵存储结构中共有多少个零元素
A
e
B
2e
C
n^2-e
D
n^2-2e
正确答案：D
官方解析：因为有n个顶点，所以有nn个元素，2e个非零元素（无向图，对称），所以有nn-2e个零元素
知识点：图
单选题

360集团真题
3.
2022 奇虎360 Java
AOV网如下，拓扑序列是？

A
V6, V4, V2, V1, V3, V5
B
V6, V1, V4, V3, V2, V5
C
V1, V2, V3, V4, V5, V6
D
V2, V1, V3, V5, V4, V6
正确答案：A
官方解析：
拓扑排序首先选择没有入度的，V6，V2都可以，故排除B选项；
假设选择了V2，但是V1还有V4的入度，故V2后不能接V1，排除D选项；
假设选择了V6，剩下的没有入度的V2和V4都可以，不能接V1，故排除A选项。选择V4以后，剩余没有入度的只有V2，然后删除V2，剩下没有入度的只有V1，最后剩下V3->V5，故选C。
知识点：图
单选题

奇安信真题
4.
2021 奇安信 后端开发
下列算法中基于图论的图像分割方法是
A
区域生长法
B
分水岭算法
C
Graph Cut
D
Mask R-CNN
正确答案：C
官方解析：raph Cut（图形切割）应用于计算机视觉领域用来有效的解决各种低级计算机视觉问题，例如图像平滑（image smoothing）、立体应对问题（stereo correspondence problem）、图像分割（image segmentation）。

GraphCut利用最小割最大流算法进行图像的分割，可以将图像分割为前景和背景。使用该算法时需要在前景和背景处各画几笔作为输入，算法将建立各个像素点与前景背景相似度的赋权图，并通过求解最小切割区分前景和背景。
故选C。
知识点：图
单选题

360集团真题
5.
2021 360 后端开发
在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为
A
s-1
B
s
C
s+1
D
n
正确答案：B
官方解析：
有向图的每一条边都有一个始顶点和一个终顶点，在有向图中所有顶点的出度之和等于入度之和，故选B。
A
abecdf
B
aecbfd
C
aebcdf
D
acebfd
正确答案：ACD
官方解析：a连接着bce三个顶点，因此a后面直接跟bce的任意顺序都行，但如果先遍历e再遍历c，则b、c、e三个顶点都遍历完成后要先遍历与e相连接的顶点，再遍历与c相连接的顶点，因此f不可能在d之前（d与e相连，f与c相连）
知识点：图
多选题

虾皮信息真题
5.
2022 shopee Java
如果一个无向图的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从a顶点出发进行广度优先搜索的可能的顶点序列为
A
abecdf
B
aecbfd
C
aebcfd
D
acebfd
正确答案：ACD
官方解析：
a连接着bce三个顶点，因此a后面直接跟bce的任意顺序都行，但如果先遍历e再遍历c，则b、c、e三个顶点都遍历完成后要先遍历与e相连接的顶点，再遍历与c相连接的顶点，因此f不可能在d之前（d与e相连，f与c相连），故选ACD。
知识点：图

2021 360 后端开发
在下列有关图的说法中正确的是
A
在有向图结构中，顶点可以没有任何前趋和后继
B
在有向图中，各顶点的入度之和等于各顶点的出度之和
C
具有n个顶点的无向图最多有n(n-1)条边，最少有(n-1)条边
D
在无向图中，边的条数是结点度数之和
正确答案：B
官方解析：
A选项：有向图中定点必须要有前驱和后继；
C选项：最少有0条边，n个顶点的联通图最少n-1条边；
D选项，在无向图中，边的条数是结点度数之和的二分之一。
知识点：图
单选题

人人网真题
2.
2022 人人网 Java
一个含有n个顶点和e条边的简洁无向图，在其邻接矩阵存储结构中共有多少个零元素
A
e
B
2e
C
n^2-e
D
n^2-2e
正确答案：D
官方解析：因为有n个顶点，所以有nn个元素，2e个非零元素（无向图，对称），所以有nn-2e个零元素
知识点：图
单选题

360集团真题
3.
2022 奇虎360 Java
AOV网如下，拓扑序列是？

A
V6, V4, V2, V1, V3, V5
B
V6, V1, V4, V3, V2, V5
C
V1, V2, V3, V4, V5, V6
D
V2, V1, V3, V5, V4, V6
正确答案：A
官方解析：
拓扑排序首先选择没有入度的，V6，V2都可以，故排除B选项；
假设选择了V2，但是V1还有V4的入度，故V2后不能接V1，排除D选项；
假设选择了V6，剩下的没有入度的V2和V4都可以，不能接V1，故排除A选项。选择V4以后，剩余没有入度的只有V2，然后删除V2，剩下没有入度的只有V1，最后剩下V3->V5，故选C。
知识点：图
单选题

奇安信真题
4.
2021 奇安信 后端开发
下列算法中基于图论的图像分割方法是
A
区域生长法
B
分水岭算法
C
Graph Cut
D
Mask R-CNN
正确答案：C

官方解析：raph Cut（图形切割）应用于计算机视觉领域用来有效的解决各种低级计算机视觉问题，例如图像平滑（image smoothing）、立体应对问题（stereo correspondence problem）、图像分割（image segmentation）。

GraphCut利用最小割最大流算法进行图像的分割，可以将图像分割为前景和背景。使用该算法时需要在前景和背景处各画几笔作为输入，算法将建立各个像素点与前景背景相似度的赋权图，并通过求解最小切割区分前景和背景。
故选C。
知识点：图
单选题

360集团真题
5.
2021 360 后端开发
在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为
A
s-1
B
s
C
s+1
D
n
正确答案：B
官方解析：
有向图的每一条边都有一个始顶点和一个终顶点，在有向图中所有顶点的出度之和等于入度之和，故选B。
知识点：图