今年的題分兩部分，時間為晚上7:00-9:30,題目分不定項選擇與兩道編程題。

下面是我自己抄下來的一部分題，盡饗讀者。

1.堆排序屬于下面哪種排序方法？

A、選擇排序 B、插入排序、C、交換排序 D、歸并排序

答案： A

2. 用RSA算法加密時,已知公匙是（e=7,n=20）,私匙是（d=3,n=20）,用公匙對消息M=3加密,得到的密文是?

A . 13 ? ? B.12 ? ? C.19 ? ? ?D.7

答案：D

解析：

?n=20
e=7 公鑰
d=3 私鑰
對M=3 進行加密
M'=M^e%n (M的e次方，然后除以n取余數)
M'=3^7%20=2187%20=7 加密后等于7

對M'=7進行解密
M=M'^d%n=7^3%20=343%20=3 解密后又變成3了

因此答案是D

3.編程題：

已知一個二維數組n*n,我們希望二維數組的每一位均>=右邊的數，同時也>=下面的數，請編寫函數調整數組，使之滿足要求（邊界除外）。

如： A=

? ? ? ? 10 5 ? 0?

? ? ? ? 4 ?6 ? 1?

? ? ? ? 2 ?3 ? ?7 ??

調整后：

? ? ? 10 ? 6 ? 5

? ? ? 7 ? ?4 ? 3

? ? ? 2 ? ?1 ? ?0

解析：
? ? 我用了兩種辦法，一種不動腦筋的，直接將上面從大到小按照從左往右，從上往下的順序填寫即可。排序時間復雜度為O(n^2log(n^2))

第二種辦法：對每一行從大到小排序，然后每一列從大到小排序，即可。時間復雜度為O(n^2logn)，稍好一些，應該還有其它的方法。這個問題的答案不唯一啊。

方法一、

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
void RecombineArray(int* a, int n)
{sort(a,a+n*n,std::greater<int>());}
int main()
{int a[3][3] = { { 10, 5, 0 }, { 4, 6, 1 }, { 2, 3, 7 } };RecombineArray2((int*)a,3);for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){cout << a[i][j] << " ";}cout << endl;}return 0;
}

注：由于二維數組存儲正好是按照從上往下，從左往右的順序存儲，所以二維數組很容易拉成一維數組，然后按照一維數組的方式對其正常排序即可

方法二、

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;void RecombineArray(int* a, int n)
{for (int i = 0; i < n;i++)//對行從大到小排序{sort(a+n*i,a+n*i+n, std::greater<int>());}for (int j = 0; j < n;j++)//對列從大到小排序{vector<int> temp;temp.reserve(n*n);for (int i = 0; i < n;i++){temp.push_back(*(a + n*i + j));}sort(temp.begin(),temp.end(), greater<int>());for (int i = 0; i < n; i++){*(a + n*i + j) = temp[i];}}}int main()
{int a[3][3] = { { 10, 5, 0 }, { 4, 6, 1 }, { 2, 3, 7 } };RecombineArray((int*)a,3);for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){cout << a[i][j] << " ";}cout << endl;}return 0;
}

? ?