🎉🎉🎉点进来你就是我的人了
博主主页：🙈🙈🙈戳一戳,欢迎大佬指点!欢迎志同道合的朋友一起加油喔🤺🤺🤺
目录
一、选择题
二、编程题
🔥字符串反转
🔥公共子串计算
一、选择题
1、对于顺序存储的线性表，访问结点和增加结点的时间复杂度为（）
A O(n) O(n)
B O(n) O(1)
C O(1) O(n)
D O(1) O(1)
正确答案： C
2、若栈采用顺序存储方式存储，现两栈共享空间V[1…m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）
A top[1]+top[2]=m
B top[1]+1=top[2]
C top[2]-top[1]|=0
D top[1]=top[2]
正确答案： B
3、下述有关栈和队列的区别，说法错误的是？
A 栈是限定只能在表的一端进行插入和删除操作。
B 队列是限定只能在表的一端进行插入和在另一端进行删除操作。
C 栈和队列都属于线性表
D 栈的插入操作时间复杂度都是o(1)，队列的插入操作时间复杂度是o(n)
正确答案：D
4、从前有座山，山里有座庙，庙里有个老和尚，再给小和尚讲故事，故事内容是：从前有座山，山里有座庙，庙里有个老和尚，再给小和尚讲故事，故事内容是：从前有座山，山里有座庙，庙里有个老和尚，再给小和尚讲故事，故事内容是……描述的是()
A 贪心
B 回溯
C 穷举
D 分治
E 递归
正确答案： E
参考答案：
递归指的是一个过程：函数不断引用自身，直到引用的对象已知。
5、某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199
正确答案： B
参考答案：
根据二叉树的基本性质，对任何一棵二叉树，度为 0 的结点（即叶子结点）总是比度为 2 的结点多一个。题目中度为 2 的结点为 199 个，则叶子结点为199+1=200 。故本题答案为 B 选项。
6、某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为（ ）
A ABCDEF
B BCDEFA
C FEDCBA
D DEFABC
正确答案： A
参考答案：
二叉树遍历可以分为 3 种：前序遍历（访问根结点在访问左子树和访问右子树之前）、中序遍历（访问根结点在访问左子树和访问右子树两者之间）、后序遍历（访问根结点在访问左子树和访问右子树之后）。二叉树的中序遍历序列和前序遍历序列均为 ABCDEF ，可知该树只有右子树结点，没有左子树结点， A 为根结点。中序遍历序列与前序遍历序列相同说明该树只有右子树没有左子树，因此该树有 6 层，从顶向下从左向右依次为 ABCDEF 。故本题答案为 A 选项。
7、初始序列为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
参考答案：
解析： 堆排序：利用堆的性质进行的一种选择排序 答案：A
8、解决散列法中出现冲突问题常采用的方法是____。
A 数字分析法、除余法、平方取中法
B 数字分析法、除余法、线性探测法
C 数字分析法、线性探测法、多重散列法
D 线性探测法、多重散列法、链地址法
正确答案： D
9、以下哪种排序算法对(1,3,2,4,5,6,7,8,9)进行的排序最快？
A 冒泡
B 快排
C 归并
D 堆排
正确答案： A
近乎有序的数组中，冒泡排序是比较优秀的，当发现元素没有交换时，认为此时数组以及有序，排序退出。
10、以下数据结构中，（）是非线性数据结构
A 树
B 字符串
C 队
D 栈
正确答案： A
二、编程题
🔥字符串反转
字符串反转_牛客题霸_牛客网
【解题思路】：
字符串反转，需要交换首尾字符，设置首尾两个位置start，end，每次交换首尾字符，然后start++, end–，直到start，end相遇，反转完成。
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
BufferedReader bis = new BufferedReader(new InputStreamReader(System.in));
String str;
while((str = bis.readLine()) != null){
char[] arr = str.toCharArray();
int start = 0;
int end = arr.length - 1;
while(start < end){
char tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
++start;
--end;
}
System.out.println(arr);
}
}
}
🔥公共子串计算
公共子串计算_牛客题霸_牛客网
【解题思路】：
求最大公共子串，使用递推实现 假设 x(i): 字符串第i个字符 y(j): 字符串第j个字符 dp[i][j]: 以x(i),y(j)结尾的最大子串长度 比如：x: “abcde” y:“bcdae” dp[2][1]: 以x(2),y(1)结尾的最大子串长度 即：x遍历到"abc", y遍历到"bc", 都以字符’c’结尾时最大公共子串为"bc" 故：当计算dp[i][j]时，首先看x(i),y(j)的值： （1）: x(i) == y(j)当前两个字符串结尾的字符相等，dp[i][j] = dp[i-1][j-1] + 1 即个它的长度加1 （2）: x(i) != y(j) 当前两个字符串结尾的字符不相等，说明没有以这连个字符结尾的公共子串 即dp[i][j] = 0 当dp中的所有元素计算完之后，从中找打最大的值输出
//动态规划
import java.util.*;
import java.io.*;
public class Main {
public static int getMaxLen(String str1,String str2){
char[] arr1=str1.toCharArray();
char[] arr2=str2.toCharArray();
int len1=arr1.length;
int len2=arr2.length;
int[][] maxSubLen=new int[len1+1][len2+1];
int maxLen=0;
for(int i=1;i<=len1;++i){
for(int j=1;j<=len2;++j){
if(arr1[i-1]==arr2[j-1]){
//F(i,j)=F(i-1,j-1)+1
maxSubLen[i][j]=maxSubLen[i-1][j-1]+1;
//是否需要更新最大值
if(maxLen<maxSubLen[i][j]){
maxLen=maxSubLen[i][j];
}
}
}
}
return maxLen;
}
public static void main(String[] args) throws Exception{
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
String str1;
String str2;
while((str1=reader.readLine())!=null){
str2=reader.readLine();
System.out.print(getMaxLen(str1,str2));
}
}
}
