在战盟客户端上进行的笔试
1.链表不具有的特点是（）
A 可随机访问任意元素 B 不必事先估计存储空间
C 插入数据元素时不需移动数据元素 D 删除数据元素时不需移动数据元素
A为顺序表的特点
2.栈的特点
后进先出
3.线性数据结构有哪些（）
线性的数据结构有：线性表、栈、队列、双端队列、数组和串
4.下列排序算法中，其时间复杂度和记录的初始排列无关的是 ( )
A．插入排序 B．堆排序 C．快速排序 D．冒泡排序
5.哪种排序法对1234576最快（）
基本有序
6.第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。这是哪种排序方法的工作原理
选择排序
7.一共三个结点的二叉树可能出现多少种结构
5种
8.一个数据库有几个模式
数据库领域公认的标准结构是三级模式结构，它包括外模式、概念模式、内模式
9.一个数据库中现有A、B、C、D、E、F六个语句，但目前这个数据库是不协调的。必须删除某些语句才能恢复数据库的协调性。已知： (1) 如果保留语句A，那么必须保留语句B和语句C。 (2) 如果保留语句E，则必须同时删除语句D和语句C。 (3) 只有保留语句E，才能保留语句F。 (4) 语句A是重要的信息，不能删除。 以上各项如果为真，则以下哪项一定为真（）
A．保留语句E并且删除语句C
B．同时保留语句C和语句D
C．保留语句E并且删除语句D
D．同时删除语句E和语句F
10.对滑动窗口不正确的描述是()
A.能够提高传输效率
B.能够提高信道利用率
C.能够进行流量控制
D.能够防止报文段顺序出错
11.在一个3 级页表结构的系统中，内存共有8192 页，每页2048 字节。请问内存的物理地址需要多少位？（）
24位。
内存有8192*2048=2^24Byte，就需要24位地址来寻址
12.往一个栈顺序push下列元素：ABCDE，其pop可能的顺序，下列不正确的是（）
A. BACDE
B. ACDBE
C. AEBCD
D. AEDCB
13.对关键字{25,15,30,10,50,3,5,60}序列进行快速排序，第一趟从小到大一次划分结果为（ ）
A. {3，5，10，15} 25{50，30，60}
B. {5，15，3，10} 25 {50，30，60}
C. {3，15，10，5} 25 {50，30，60}
D. {5，15，3，10} 25 {30，50，60}
题目解析：
本题快排采用枢轴交换的方式：
从右往左，第一个比25小的数，和25交换位置。
从左往右，第一个比25大的数，和25交换位置。
......
直到25左边没有比其大的数，右边没有比其小的数。
14.稳定的排序算法与时间复杂度
稳定的排序算法：冒泡排序、插入排序、归并排序、基数排序
不稳定的排序算法：选择排序、快速排序、希尔排序、堆排序
冒泡排序、直接插入排序、选择排序：O（n*n）
快速排序、归并排序、堆排序：log2(n)*n
希尔排序：n的1.2次幂
15.一颗二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有结点个数为（）
25个
16.一个具有n个顶点的有向图，其所有顶点的出度之和为Dout，则所有顶点的入度之和为( )
A．Dout B．Dout-1 C．Dout+1 D．n
17.一个具有n个结点的二叉树，若他有m个叶子结点,则该二叉树中度为1的结点个数是多少（）
n-2m+1
18.设数组定义为a[60][70]，每个元素占2个存储单元，数组按照列优先存储，元素a[0][0]的地址为1024，那么元素a[32][58]的地址为（）
8048
19.（）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
队列
20.进程和线程在拥有资源方面的区别
21.tcp协议是面向字节流的网络协议，这意味着（）
意味着数据是以字节流的形式传递给接收者的，没有固定的“报文”或“报文边界”的概念。
22.应用层如何解决没有消息边界的问题
1.发送固定长度消息
2.将消息长度与消息一起发送
3.使用特殊标记分隔消息
23.数据表字段char和varchar的区别
24.求数组中a+b+c=0的所有满足条件且不重复的三元组
题目描述
给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
解题思路：
三个之和相加等于0，
1、那么需要将所给数组进行从小到大进行排序。
2、如果排序后第一个数大于0，则他们之和用于不能为0，返回null;
3、以第一个数作为基准不动，定义其他两个指针（双指针），依次动第二位和最后一位进行遍历判断
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
ArrayList<ArrayList<Integer>> res=new ArrayList<>();
//1、数组不够三个数字，直接返回
if(num==null || num.length<3){
return res;
}
// 从小到大排序
Arrays.sort(num);
for(int i=0;i<num.length-2;i++){
if(num[i]>0){
break;// 如果当前数字大于0，则三数之和一定大于0，所以结束循环
}
//重复的三个数不算
if(i>0 && num[i]==num[i-1]){
continue;// 去重
}
//定义两个指针，从前往后 和 从后往前
int L=i+1;
int R=num.length-1;
while(L<R){
int sum=num[i]+num[L]+num[R];
if(sum==0){
ArrayList<Integer> list=new ArrayList<>();
list.add(num[i]);
list.add(num[L]);
list.add(num[R]);
res.add(list);
//去重
while(L<R && num[L]==num[L+1]){
L++;
}
//去重
while(L<R && num[R]==num[R-1]){
R--;
}
L++;
R--;
}
else if(sum>0){
R--;
}
else if(sum<0){
L++;
}
}
}
return res;
}相关文章
