APCS 105-10-29 觀念題解析

by Sean, Jun 2018

題目連結

1

此題並沒有涉及任何交換，直接追蹤 a=2, b=3 的情況
a=2
c=a=2
t=item[2]=3
b=3
item[3]=1 < t=3 成立
c=b=3
t=item[3]=1
printf("%c %d\n",t,c) → 1 3

2

x=10，y=‘a’，停住
x=20，沒有 break，繼續往下走，y=‘b’，停住
x=30，y=‘b’，停住
其他狀況，y=‘c’
因此可知

if(x==10){
	y='a';
}else if(x==20 || x==30){
	y='b';
}else{
	y='c';
}

3

G(3)=K(a,3)
K(a,3)=K(a,2)+a[3]=K(a,2)+2
K(a,2)=K(a,1)+a[2]=K(a,1)+3
K(a,1)=K(a,0)+a[1]=K(a,0)+4
K(a,0)=K(a,-1)+a[0]=K(a,-1)+5
K(a,-1)=0，開始 return
K(a,0)=5
K(a,1)=9
K(a,2)=12
K(a,3)=14
G(3)=14

4

因為都是整數，小數部份會直接捨去
b/a=3/2=1, c/b=4/3=1, d/b=5/3=1
val=1+1+1=3

5

第一個迴圈的 i<n/2 部份是將第 x 個元素與倒數第 x 個元素互換
但是後半部又會將牠們換回來，也就是這個迴圈做了白工
第二個迴圈則是依 x，倒數第 x… 這樣的順序輸出
所以答案為 1 2 3 4 5 6 7 8 9 9

6

• a<3
  F(7)=F(5)+F(4)=3+2=5 (X)
  F(5)=F(3)+F(2)=2+1=3
  F(4)=F(2)+F(1)=1+1=2
  F(3)=F(1)+F(0)=1+1=2

• a<2
  F(7)=F(5)+F(4)=4+3=7 (X)
  F(5)=F(3)+F(2)=2+2=4
  F(4)=F(2)+F(1)=2+1=3
  F(3)=F(1)+F(0)=1+1=2
  F(2)=F(0)+F(-1)=1+1=2

• a<1
  F(7)=F(5)+F(4)=5+4=9 (X)
  F(5)=F(3)+F(2)=3+2=5
  F(4)=F(2)+F(1)=2+2=4
  F(3)=F(1)+F(0)=2+1=3
  F(2)=F(0)+F(-1)=1+1=2
  F(1)=F(-1)+F(-2)=1+1=2

• a<0
  F(7)=F(5)+F(4)=7+5=12 (O)
  F(5)=F(3)+F(2)=4+3=7
  F(4)=F(2)+F(1)=3+2=5
  F(3)=F(1)+F(0)=2+2=4
  F(2)=F(0)+F(-1)=2+1=3
  F(1)=F(-1)+F(-2)=1+1=2
  F(0)=F(-2)+F(-3)=1+1=2

7

$$\sum_{i=1}^nn=n\frac{n(n+1)}{2}=\frac{n^2(n+1)}{2}$$

8

二分搜尋法只適用於已排序的對象，B 為無序

9

70~79 和 60 是錯的，共 11 個

10

• G(P,0,1)

  • a=K(p,0)
    p[0]=0 == 0
    return 0
  • b=K(p,1)
    p[1]=1 == 1
    return 1
  • a=0 != b=1
    change p[1] to 0
  • now p={0 0 2 3 4}

• G(P,2,4)

  • a=K(p,2)
    p[2]=2 == 2
    return 2
  • b=K(p,4)
    p[4]=4 == 4
    return 4
  • a=2 != b=4
    change p[4] to 2
  • now p={0 0 2 3 2}

• G(P,2,4)

  • a=K(p,0)
    p[0]=0 == 0
    return 0
  • b=K(p,4)
    p[4]=0 != 4
    p[4]=K(p,p[4])=K(p,0)
    • p[0]=0 == 0
      return 0
      now p[4]=0
  • a=0 == b=0
  • now p={0 0 2 3 0}

11

中間九格的四個鄰居的和

12

• i=0
  i=5
• i=6
  i=11
• i=12
  i=17
• i=18
  i=23
• kill

13

char array 未被指派的位置，系統會指派 0，也就是 \0

14

• !(1 or 0) or 1 = 0 or 1 = TRUE
• !1 or (0 or !1) = 0 or (0 or 0) = FALSE
• 0 or (1 and (1 or 0)) = 0 or (1 and 1) = 0 or 1 = TRUE
• (1 or 1) and 0 = FLASE

15

-(a[0] ~ a[7])
+(a[1] ~ a[8])
+(a[2] ~ a[9])

= -a[0]+a[8]+a[2] ~ a[9]

= 0+8+44=52

16

a_ptr 存放的值是 &a，對 int 取址，為 int*
a_ptrptr 存放的值是 &a_ptr，對 int* 取址，為 int**

17

觀察第一行，i=0，k 從 6-2*0=6 開始遞減，執行 6 次，故條件為 k>0

18

G(1)
= print(1)
= G(2)
== print(2)
== G(3)
=== print(3)
=== return
== print(2)
= print(1)

故為 1 2 3 2 1

19

任何數 %1 都是0，而且都已經找完錢了，沒意義，選 D

20

A=G(5)=25
A=G(5)+A=25+25=50

21

• (A) ((2 * a)+2) * G(a,x-1)

  測試 a=2,x=1
  (2 * 2+2) * G(2,0)=6 * 1=6

  觀察式子，發現這個其實就是 2 * a+2 的 x 次方
  正確

• B、C、D 在 a=2,x=1 時就錯誤，不必觀察

22

$13*16^{3}+2*16^1+10+5487=4096*13+512+10+5487=58777$

• (A) $2^{15}+2^{14}+2^{10}+2^{8}+2^7+2^4+2^3+1=1024*32+1024*16+1024+256+128+16+8+1=50585$
• (B)
  $1+8^{1}*3+8^{2}*6+8^{3}*2+8^{4}*6+8^{5}*1=58777$
• (C)
  $362375$
• (D)
  $62873$

但這樣硬算很智障，較快的解法是將題目的 5487 轉成 16 進位的 156F
156F+D02A=E599
再把它轉成二進位，每個 16 進位的位數代表 4 個 bit
E=1110，5=0101，9=1001
所以我們要找出二進位為 1110 0101 1001 1001 的值

• A: 不一樣，下一位
• B: 每個位數就是 3 個 bit
  1=001，6=110，2=010，3=011，1=001。001 110 010 110 011 001，找到答案
• C: ‭0101 1000 0111 1000 0111‬
• D: ‭1111 0101 1001 1001‬

23

65536=2^16

• $i=2^3$
  x=4
• $i=(2^3)^3=2^9$
  x=5

此時可以發現，題目要問的就是 x=3+ceil(log(3,16))=3+3=6

24

經典的遞迴，算次方。 $3^7=2187$

25

這題有小 bug，照理說 int/int 會捨去小數
但這題必須用小數去看待 int/int 的結果，再無條件進位

search(1,10,3)

t=6
search(1,5,3)

t=3
search(3,5,3)

t=4
search(3,3,3)
共 4 次