AP Computer Science A 考前复习相关内容

Jimmy Carlson posted @ 2017年5月01日 00:49 in OI / CS , 368 阅读
2017 JCarlson Works All Rights Reserved

UPD1(Mar 1st 12:00) : 文章末尾增加了一些算法相关的内容。

UPD2(Mar 1st 14:20):在==和equals()比较的地方进行了一些修改。(点击跳转)


嘛,必须承认,AP的CS还是比较恶心的= =把14~16年的FREE-RESPONSE做了一下,基本上在33左右,所以还是要自己写个总结啥的,自己加深一下印象。

今年AP CS的Free-response Question为4大题90分钟,AP官网上有14~16年的题目(需要CB账号),其中除14年第2题题目描述严重不清以外,都是不错的题目,可以拿来练手,其中特别推荐16年卷子,最后冲刺做一下。

 

然后讲一下一些Java的要点吧,基础的东西不会太多。

AP中Java不考输入,如果涉及到输入的话,一般使用Scanner。

Scanner in = new Scanner (System.in);
int n = in.nextInt();

这样就读入了一个int类型的n。

关于Java的输出,是有题目出现过,所以稍微记一下,有点长。

System.out.print();
System.out.println();

两者区别是前者不换行,后者换行。

 

关于数学运算,AP中只会涉及加减乘除和模运算(+,-,*,/,%),其中特别要注意的一点是乘除和模运算同一优先级。

与C++类似的地方,可以使用++和--,以及+=,*=等算数运算符。

关系运算符和逻辑运算符与C++保持一致,包括(==,!=,>,<,>=,<=)以及(!not,&&and和||or)。

字符串运算符仅有+,表示两串合并。

 

关于变量的声明和赋值,与C++类似。

<type> <var_name> = <value>;

基本数据类型只会涉及int(-2147483648~2147483647,简单记为±20亿即可),double(用于存储小数),和boolean(布尔值,true & false)

强制类型转换仅会在int和double类型之间转。(int) (double)

 

重点,关于比较。

==,!=与.equals()之间的混用。这里特作说明。

如无特殊情况,用于比较两个值是否相等用.equals()没有任何问题,由于.equals()是Object类函数,对于任何对象都可以使用.equals(),推荐优先使用。

==和!=所比较的两个对象,当且仅当两个对象指向同一对象的时候为true。

基本类型(即int/double/boolean)只能使用 == 和 != 来比较。字符串类型需要使用.equals()来比较。

但是,对于非字符串类型的,比如两个对象之间的比较,这个时候.equals()会比较两个对象是否指向同一个内存地址。

 

package Pos;

public class Position {
	private int x;
	private int y;
	public Position(int a, int b) {
		setX(a);
		setY(b);
	}
}

public class PositionTest {
	public static void main(String []args) {
		Position p1 = new Position(2, 3);
		Position p3 = new Position(2, 3);
		System.out.println(p1.equals(p3));
	}
}

运行结果为FALSE,因为p1和p3指向的是不同的两个对象,因此不能使用.equals()和==来比较两个是否相同。

举例。

String a = new String("F**k CB");
String b = new String("F**k CB");
System.out.println(a==b);
System.out.println(a.equals(b));

结果,上方是false,下方是true。

此处a和b所表示的内容,也就是值完全相同,但是a和b指向两个不同的对象,所以==判断为false。

如果在打印之前加上一句a=b或者b=a,就指向同一对象,此时为true。

同时,如果我们要比较字符串的大小(字典序)的话,可以用.compareTo()解决,.compareTo()值为0时也表示两串相同。

 

if、while循环、for循环和C++完全一致,不作赘述。for-each仅需理解不会强制要求使用,用for代替即可。

break和continue不考,就跳过。

 

Java的异常处理

每年必考一个题目,可以考虑放弃,但还是说一下。AP中涉及到的仅有5个异常。注意,这五个都是RuntimeException,也就是说在运行程序当中才会出现的问题,编译是能通过的。

ArithemicException:仅会在1个情况下出现,Divided by 0

NullPointerException:概括起来,就是你是用对象的时候,这个对象值为null,会出现这样一个异常。

http://baike.baidu.com/item/NullPointerException

IndexOutOfBoundsException:下标越界异常(包括数组和字符串)

上一个的子项:ArrayIndexOutOfBoundsException:数组下标越界异常,比如 int[] a = new int[5]; a[5] = 1; 就会发生。

IllegalArgumentException:参数不合法,是你调用方法的时候,传递了不合法的参数所造成的。

 

然后谈到数组。数组必需学会,大重点,大部分的Free Request都会用到,不会就GG。

关于数组的定义,数组的赋值,以及相关的操作,书上应该都有。

关于List和ArrayList,定义为“List<type> <list_name> = new ArrayList<type>”。前后要注意。

List所考的方法包括:

.size()返回包含总共有多少数据。.add(value)在末尾添加;.set(index,value)把index位置的变成value;.get(index)返回index位置的value;.remove(index)抹去index位置的value。

 

在Free-response里的几个易混淆表示总数的:

array.length     VS     String.length()     VS    List.size()

数组没有()                    字符串有()                   表有()且是size()

 

重点,类。默认知道各种奇怪的关键词。类的格式大多是这样的:

(abstract) <visibility> class <class_name> (extends <superclass>) (implements <interface1>,(<interface2>...)) {

    private (static) ...... // local variables,注意绝大多数class里的局部变量需要设置为private,即仅有本类方法才能调用,体现Java封装性

    public <class_name>(<List of parameters>) {

        //constructor,构造函数。

    }

    (abstract) <visibility> (static) <return_value_type> <method_name>(<List of parameters>){

        //method,方法。抽象方法不需要内容。

    }
   //...other variables and methods not shown

}

上面的程序段中有的()是需要的,有的()表示括起来的内容可以不需要。<>内的内容表示对应的地方所需要的内容。

然后挨个讲,首先是两个概念,overload和override。

overload叫重载,根据参数表的不同,可以同时存在多个名字相同,但参数表不同的方法。构造函数也能够被重载。

override叫覆写,是指子类的方法和父类的方法重名且完全相同,此时调用该名称的方法时优先调用子类的方法,父类方法被覆盖了。如果想调用父类的方法,需要用到关键词super。讲super之前,先提一个概念,继承。

 

继承(extends),是指在已有类的基础上构造一个新的类。

其中,已有类叫做父类,新的类叫做子类。子类拥有父类所有的属性和方法,并且同时拥有自己独有的属性和方法。

public class A {
  private int n = 10;
  public int getN() { return n;}
}
public class B extends A {
  private int m = 20;
  public int getM() { return m;}
}

....

B k1 = new B;
System.out.println(k1.getN());
输出为10。这里相当于class B有n,m,getN,getM四个组成部分,它将A的两个组成部分继承了下来。
 
之后我们可以再讲super了。Super一个小重点。super用到的地方有两个。第一个考过有几次
public class A {
  public A() { System.out.print("A"); }
}
public class B extends A {
  public B() { System.out.print("B"); }
}

....
  B fun = new B();

输出结果将会是AB。

创建一个对象的时候,它会优先自动调用自己父类的无参数构造函数!

若想要调用有参构造函数,用到super(<List of parameters>);(大部分考的是这个) 这是super的第一个用法。

第二个就是刚才提到的override,子类需要用到父类的方法的时候,用到super.<method_name>(<list of parameters>);

 

super讲完有一个概念,叫做多态(polymorphism)。多态是指“同一个方法,根据上下文的不同,使用不同的定义”的能力。

从定义出发,override和overload都可以看作是多态的。但是多态更多是和动态绑定一起看的,举例。

public class Food {
  String name;
  public void eat() {
    System.out.println("Eat Food");
  }
}

public class Milk extends Food {
  public void eat() {
    System.out.println("Drink Milk");
  }
}

public class Bread extends Food {
  public void eat() {
    System.out.println("Eat Bread");
  }
  public void eat2() {
    System.out.println("Eat Bread with milk");
  }
}

Food []arr = new Food[3];
arr[0] = new Food();
arr[1] = new Milk();
arr[2] = new Bread();
arr[0].eat();
arr[1].eat();
arr[2].eat();

/*
result:
Eat Food
Drink Milk
Eat Bread
*/

 

一个存放Food类型的数组,每个对象分别存放food类型,milk类型和bread类型。

Java中对象是多态的,以上程序为例,虽然arr是Food类型,但是他能够存储它的所有子类类型,且在执行eat方法时自动调用对应类型的方法,这就是动态绑定,是多态最常见的一种形式。

题外话,不能直接访问arr[2].eat2()。需要访问的时候可以用(Bread)arr[2].eat2()来强制转换。

 

讲完super,还有一个比较搞的关键字是static。

static本意是“静态”的,在Java中我建议翻译成“公用”的。static一般加在变量前和方法前。

先讲static variables,静态变量。一般各种变量都是属于某个“对象”的,一旦class内的变量加了static关键字后,这个变量就变成了所有“对象”共有的,换句话讲就变成了整个类的一个变量。举例。

public class Try{
  public static int a=0;
  public Try(){
    a++;
  }
}

...
  Try k1 = new Try();
  System.out.println(k1.a);
  Try k2 = new Try();
  System.out.println(k2.a);

此处结果为1 2。生成k1后,Try.a = 1,也就表示k1.a = 1。生成k2后,Try.a = 2,也就表示 k1.a == k2.a == 2。

然后是static method,静态方法。静态方法一般是用来形容“工具”的,它专门去处理一些事情,可以方便的调用。

比如Math库里常用的abs(),pow(),sqrt()等,都是以静态方法的形式去实现的。

通常使用静态方法时,以“<Class_name>.<Static_method_name>”的格式去调用。

有一点请注意,静态的方法不能直接访问非静态的变量。比如这个是错误的。

public class std{
    int x=0;
    public static void main(String[] args) {
        System.out.println(x);
    }
}

//error: non-static variable x cannot be referenced from a static context

this关键字不考也就pass掉。

 

回过头来讲抽象,abstract。

抽象必需被继承,即,在一个类中定义一个方法,但是只是定义,不去实现,具体的实现工作交给它的子类去实现。

abstract public class A {
  public int method1() { .... }
  abstract public int method2();
}
public class B extends A {
  public int method2() {......}
}

 

在classA中method2仅仅是占了一个位置,在它的子类classB中去具体实现了这个方法。

这个的目的可以和上面讲过的动态绑定一起理解。

 

那么类的东西终于讲完,最后讲一下接口(Interface)。

接口可以被看作是一种完全抽象类,定义了一系列的抽象方法和常量,相当于打了一个框架。在接口里定义的方法都不需要立即去实现。在使用接口的类中,你必须实现所有接口定义的方法,除非这个类是抽象类且这个方法也是抽象方法。

具体的格式和使用接口的格式为:

public Interface <interface_name> {

  <var_type> <var_name> = <value> //接口中定义的所有量都默认为常量,即无法改变的量。

  <return_type> <method_name>(<List of parameters>);

}

 

public class <class_name> implements <interface1>(,....) {

...

}

接口和抽象类的最重要的区别,一个类可以有多个接口,但一个类仅能继承一个抽象类。接口里的方法全都是抽象的,但抽象类里可以有非抽象的方法。

二者都可以实现多态。

 

明天中午更新一下AP CS中提到的算法内容,先去躺了(


根据某本极其不靠谱的AP CS辅导书,会考的算法包括了搜索、排序以及递归,那么就一个一个复习一下吧。

首先是搜索。

一种叫做“线性搜索”(linear search),或者叫顺序搜索,也就是从头到尾过一遍,找找有没有需要的元素。时间复杂度O(N)。

//precondition: int a[50]; 
//postcondition: Find X;
int place = -1;
for (int i=0;i<a.length;i++) {
  if (a[i] == X) place = i;
}

 

另一种叫做“二分查找”(binary search),注意:二分查找仅能用在按照一定顺序排好的序列里!将整个序列分为两半,判断所要查找的元素在哪一半中,然后再从那一半中再分两半查找。时间复杂度O(lg2 N)。

//precondition: int a[50]; Elements in a are in increasing order.
//postcondition: Find X;
int head = 0;
int tail = a.length()-1;
int mid = (head + tail) / 2;
while (a[mid] != X && head <= tail) {
  if (a[mid] < X) head = mid + 1;
  if (a[mid] > X) tail = mid - 1;
  mid = (head + tail) / 2;
}
if (a[mid] == X) return mid;

第二个是排序。基础排序有三种。

选择排序(Selection Sort)

从第一个元素开始,每一次选出最小的一个元素,并且将其固定在现有最前的位置。

for (int i = 0; i < n - 1; i++) {
  for (int j = i; j < n; j++) {
    if (a[i] > a[j]) swap(a[i],a[j]);
  }
}

冒泡排序(Bubble Sort)

就像泡泡一样,重的东西会下沉,轻的东西会上浮。冒泡排序通过n次相邻元素两两交换的操作,达到将大的元素向最右方移动的效果。

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n - 1; j++) {
    if (a[j] > a[j+1]) swap(a[i],a[j]);
  }
}

插入排序(Insertion Sort)

就像摸扑克牌然后理牌一样,我们从第二个元素开始,插到前面已经排好的元素中的合适的位置,保持前面的这些元素仍然有序。

for (int i=1;i<n;i++) {
  int temp = a[i];
  j = i - 1;
  while (j >= 0 && temp < a[j]) {
    a[j+1] = a[j];
    j--;
  }
  a[j+1] = temp;
}

 

最后一个是递归(Recursion)。

什么是递归?

【递归】:参见“递归”。 ——刘汝佳《算法竞赛入门经典》

换句话说,递归就是“自己调用自己”,且每一次调用都会产生一个新的“状态”。

举例。

public static int factorial(int n) {
  if (n == 0) 
    return 1
  else 
    return n * factorial(n-1);
}


factorial = 1;
for (int i=1;i<n;i++) factorial *= i;

就象这样,上下两个程序段是等价的。

比如我们在求factorial(3)的时候,

我们进入factorial(3),它要返回3 * factorial(2),然后我们进入factorial(2),返回 2 * factorial(1)。

求factorial(1),返回1 * factorial(0),然后factorial(0)返回1。

回到factorial(1)里面,返回1 * 1 = 1。

回到factorial(2)里面,返回2 * 1 = 2。

回到factorial(3)里面,返回3 * 2 = 6。

至此我们算出factorial(3)=6。我们看到factorial自己调用了自己3次,每一次传去的参数n都是不同的。

这就是一个递归的初步运用。较复杂的递归运用包括深度优先搜索,快速排序等,但这很明显超出AP范围了,不再赘述。

以上,AP涉及到的几个算法和简单的代码都已经罗列出来了。

 

最后还有一个小补充,上面漏了,Java的字符串函数。

.length()表示长度;

.substring(int from,int to)返回从from到to-1的子串。

.substring(int from)仅有一个参数的情况下,返回from到串末尾的子串。

.indexOf(String str)返回str在原串中的位置,如果没有找到会返回-1。

.compareTo(String str)比较str和原串的字典序大小,如果str字典序大返回负值,原串字典序大返回正值,两串相同返回0。

2017 JCarlson Works All Rights Reserved

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter