下列关于线性链表的叙述中，正确的是（ ）
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)); } } } } }
