Java面向对象编程

下列关于线性链表的叙述中，正确的是（）

A. 各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致

B. 各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续

C. 进行插入与删除时，不需要移动表中的元素

D. 以上说法均不正确

答案：C

一个栈的初始状态为空。现将元素 1,2,3,A,B,C 依次入栈，然后再依次出栈，则元素出栈的顺序是（）

A. 1,2,3,A,B,C

B. C,B,A,1,2,3

C. C,B,A,3,2,1

D. 1,2,3,C,B,A

答案：C

下列数据结构中，不能采用顺序存储结构的是（）

A. 非完全二叉树

B. 堆

C. 队列

D. 栈

答案：A

递归函数最终会结束，那么这个函数一定？

A. 使用了局部变量

B. 有一个分支不调用自身

C. 使用了全局变量或者使用了一个或多个参数

D. 没有循环调用

答案：B

已知二叉树后序遍历序列是bfegcda，中序遍历序列是badefcg，它的前序遍历序列是（）

A. abcdefg

B. abdcefg

C. adbcfeg

D. abecdfg

答案：B

某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（）

A. ABDHECFG

B. ABCDEFGH

C. HDBEAFCG

D. HDEBFGCA

答案：A

设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79}，用链地址法构造哈希表,哈希函数为H(key)=key MOD 13，哈希地址为1的链中有（）个记录

A. 1

B. 2

C. 3

D. 4

答案：D

假设你只有100Mb的内存，需要对1Gb的数据进行排序，最合适的算法是（）

A. 归并排序

B. 插入排序

C. 快速排序

D. 冒泡排序

答案：A

某系统总体结构如下图所示, 该系统结构图的深度是（）

A. 4

B. 3

C. 2

D. 1

答案：A
汽水瓶
题目描述：某商店规定：三个空汽水瓶可以换一瓶汽水，允许向老板借空汽水瓶（但是必须要归还）。 
小张手上有n个空汽水瓶，她想知道自己最多可以喝到多少瓶汽水。
 数据范围：输入的正整数满足 1<= n <=100
注意：本题存在多组输入。输入的 0 表示输入结束，并不用输出结果。 输入描述：输入文件最多包含 10 组测试数据，每个数据占一行，仅包含一个正整数 n（ 1<=n<=100 ），表示小张手上的空汽水瓶数。n=0 表示输入结束，你的程序不应 当处理这一行。 
输出描述：对于每组测试数据，输出一行，表示最多可以喝的汽水瓶数。如果一瓶也喝不到，输出0。
样例 1：解释：用三个空瓶换一瓶汽水，剩一个空瓶无法继续交换 
样例 2 解释：用九个空瓶换三瓶汽水，剩四个空瓶再用三个空瓶换一瓶汽水，剩两个空瓶，向老板 借一个空瓶再用三个空瓶换一瓶汽水喝完得一个空瓶还给老板
方法1：public class Main22 {//汽水瓶public static void main(String[] args) {Scanner scanner=new Scanner(System.in);while (scanner.hasNext()){int n=scanner.nextInt();if (n !=0){System.out.println(n/2);}else {break;}}}}
方法2：public class Main23 {public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int num=0;while ((num =scanner.nextInt()) !=0){System.out.println(getNum(num));}}public static int getNum(int num){//累加汽水的个数int sum=0;//while( num >0)死循环while (num > 1){//兑换的汽水的个数sum +=num/3;//剩余的空瓶子num=num/3+num%3;if (num==2){//借一瓶++sum;break;}}return sum;}}
查找两个字符串a,b中的最长公共子串
题目描述：查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
 注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！
数据范围：字符串长度 1<=length<=300
进阶：时间复杂度： O(n^3)，空间复杂度：O(n)
 输入描述：输入两个字符串 
输出描述：返回重复出现的字符
public class Main24 {//查找两个字符串a,b中的最长公共子串public static String getMaxSubstr(String str1,String str2){char[] arr1=str1.toCharArray();char[] arr2=str2.toCharArray();int len1=arr1.length;int len2=arr2.length;//最长字串的起始位置int start=0;//最长字串的长度int maxLen=0;//多增加一行一列，作为辅助状态//状态：以a的第i个字符结尾和以b的第j个字符结尾的最长公共字串的长度int[][] maxSubLen=new int[len1+1][len2+1];for (int i = 0; i <= len1 ; i++) {for (int j = 0; j <= len2 ; j++) {//如果第i个字符和第j个字符相等，则进行累加if (arr1[i-1]==arr2[j-1]){maxSubLen[i][j]=maxSubLen[i-1][j-1]+1;//更新if (maxLen < maxSubLen[i][j]){maxLen=maxSubLen[i][j];start=i-maxLen;}}}}return str1.substring(start,start+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();while ((str1 =reader.readLine()) != null){if (str1.length() < str2.length()){System.out.println(getMaxSubstr(str1,str2));}else {System.out.println(getMaxSubstr(str2,str1));}}}}}