对于顺序存储的线性表，访问结点和增加结点的时间复杂度为（）。
A. O(n) O(n)
B. O(n) O(1)
C. O(1) O(n)
D. O(1) O(1)
答案：C
若栈采用顺序存储方式存储，现两栈共享空间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
下述有关栈和队列的区别，说法错误的是？
A. 栈是限定只能在表的一端进行插入和删除操作。
B. 队列是限定只能在表的一端进行插入和在另一端进行删除操作。
C. 栈和队列都属于线性表
D. 栈的插入操作时间复杂度都是o(1)，队列的插入操作时间复杂度是o(n)
答案：D
从前有座山，山里有座庙，庙里有个老和尚，再给小和尚讲故事，故事内容是：从前有座山，山里有座庙，庙里有个老和尚，再给小和尚讲故事，故事内容是：从前有座 山，山里有座庙，庙里有个老和尚，再给小和尚讲故事，故事内容是……描述的是()
A. 贪心
B. 回溯
C. 穷举
D. 分治
E. 递归
答案：E
某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（） A. 不存在这样的二叉树
B. 200
C. 198
D. 199
答案：B
某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为（ ）
A. ABCDEF
B. BCDEFA
C. FEDCBA
D. DEFABC
答案：A
初始序列为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. 数字分析法、除余法、平方取中法
B. 数字分析法、除余法、线性探测法
C. 数字分析法、线性探测法、多重散列法
D. 线性探测法、多重散列法、链地址法
答案：D
以下哪种排序算法对(1,3,2,4,5,6,7,8,9)进行的排序最快（）
A. 冒泡
B. 快排
C. 归并
D. 堆排
答案：A
以下数据结构中，（）是非线性数据结构
A. 树
B. 字符串
C. 队
D. 栈
答案：A
字符串反转
题目描述：接受一个只包含小写字母的字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）
输入描述：输入一行，为一个只包含小写字母的字符串。
输出描述：输出该字符串反转后的字符串。
输入：abcd
输出：dcba
方法1：
public class Main33 { //字符串反转 public static void main(String[] args) throws Exception{ BufferedReader reader=new BufferedReader(new InputStreamReader(System.in)); String str; //循环输入（多组输入） while ((str=reader.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); } } }
方法2：
public class Main30 { //字符串翻转 public static void main(String[] args) { Scanner scanner=new Scanner(System.in); String str=scanner.nextLine(); //翻转 //栈 Stack<Character> stack=new Stack<>(); for (int i = 0; i < str.length(); i++) { stack.push(str.charAt(i)); } StringBuilder stringBuilder=new StringBuilder(); while ( !stack.isEmpty()){ stringBuilder.append(stack.pop()); } System.out.println(stringBuilder.toString()); } }
公共字串计算
题目描述：给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。
注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。
数据范围：字符串长度：1<=len<=150
进阶：时间复杂度：O(n^3) ，空间复杂度：O(N)
输入描述：输入两个只包含小写字母的字符串
输出描述：输出一个整数，代表最大公共子串的长度 补充说明： 示例 展开 示例1
public class Main32 { //公共字串计算 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-1][j-1]){ 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.println(getMaxLen(str1,str2)); } } }
