http://tinyurl.com/b54pmbt
想對對看答案，有錯的話希望高手指出
1題300P
(1)
(a)
void Fibonacci(int A[],int n)
{
A[0]=0;A[1]=1;int i;
for(i=2;i<n;i++)
{
A[i]=A[i-1]+A[i-2];
}
}
(b)
d=2
A[4,2]=2980
A[2,3]=2988
^ ^ 為column major
2988+L0+[(3-0)*n+2]*2 = L0+6n+4 -> 2984 = L0+6n
2980+L0+[(2-0)*n+4]*2 = L0+4n+8 -> 2972 = L0+4n
-------------
12 = 2n -> n=6;代回得->L0=2948
(1)A[0][0]=2948
A[3][8]=2948+[(8-0)*6+3]*2=3050
(2)A[3][8]為第52項元素，故存A[3][8]=f(52)
6*8+4=52
2.
懶得打，
3.
(a)
void add(stack s,queue q,data)
{
push(s,data);
enqueue(q,data);
}
_
|3|4
0 1 2 3 4 15|3
－－－－－－－－ |6|2
｜2｜4｜6｜5｜3｜ |4|1
－－－－－－－－ |2|0
q s
void delete(stack s,queue q,int M[],k)//k為取出第幾項元素
{
for(i=0;i<n-k;i++)
{
pop(s);//假設要取出M[1]值,就做5-1=4次pop
}
push(s,NULL);//因為是刪除元素，所以把stack該格內放空值
for(i=0;i<k+1;i++)//******************
{
dequeue(q);//為了還原stack剩下元素，故dequeue出stack內有的元素再給stack
}
for(i=0;i<n-k-1;i++)
{
push(s,dequeue(q));//把剩下元素給stack
}
for(i=0;i<n;i++)
{
enqueue(q,s[i++]);//復原queue
}
}//****************
(b)
highlight的del部分為第二個for開始//*****到結束//*******
add部分則是只要放進一個stack即可
概念為做n-k次push(t,pop(s))和push(s,NULL)完後,t可直接push(s,pop(t))
(刪除不要的元素後)
不用做還原動作
(c)
不會，
(d)
因為c不會，所以我只有比較a和b
大致上我寫b較好，轉換較方便，add、del時間複雜度皆為O(1)、O(n)
4.
太長了，結果是
0
U
1 ／ ＼ 0
S X
1 ／ ＼0 ／ ＼ -1
R T V(-1) Y
0 ／ ＼ 0 ＼ 0
Q W Z
5.
也太長了，
R
／ ＼
N T
／ ＼ ／ ＼
E,K O S W
6.
bit數不一定
當找到character時就停止
舉例如下：
編碼110
decoding時愈到1時往右找，0則往左找
故找到11(C)又因下一個為NULL所以停止，從0繼續，直到編碼都被找光為止
O
0/ \1
A O
0/ \1
B C
謝謝各位了，
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 175.181.159.216
※ 編輯: cksh8008 來自: 175.181.145.70 (02/18 13:40)