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

Jimmy Carlson posted @ 2017年5月01日 00:49 in OI / CS , 813 阅读
2019 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。

2019 JCarlson Works All Rights Reserved
Avatar_small
Meghalaya Board Ques 说:
2022年8月25日 19:51

Meghalaya Board Model Paper 2023 Class 11 Pdf Download with Answers for Bengali Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Meghalaya Board Question Paper Class 11 Type Questions to Term1 & Term2 Exams at official website. New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

Avatar_small
AP 1st Inter Economi 说:
2022年9月08日 21:01

The AP Intermediate students can download the Economics question bank with solved study material with practice questions in chapter wise to every TM, EM, UM student, and the economics subject paper-1 AP 1st Inter Economics Model Paper and paper-2 important questions with suggestions are available through AP Jr and Sr inter Economics Model Paper 2023 Pdf with guess paper.


登录 *


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