2017年除夕的傳說(shuō)作文

　　先總體說(shuō)下題型，共有20道選擇題，4道簡(jiǎn)答題，3道編程題和1道擴展題，題目都比較簡(jiǎn)單，限時(shí)一小時(shí)完成。

　　一、選擇題

　　選擇題非常簡(jiǎn)單，都是基礎題，什么死鎖發(fā)生的條件、HashMap和HashSet查找插入刪除的時(shí)間復雜度、Thread類(lèi)和Runnable接口、排序復雜度比較、建堆調整堆等等，具體的也記不得了。

　　二、簡(jiǎn)答題

　　1. 簡(jiǎn)述Servlet的生命周期

　　2. 寫(xiě)出至少8個(gè)Java常用的包名稱(chēng)

　　3. Overload和Override的區別，Overloaded方法能不能修改返回值類(lèi)型?

　　4. 不用中間變量交換a和b的值

　　三、編程題

　　1. 有N個(gè)人圍一圈依次報數，數到3的人出列，問(wèn)當只剩一個(gè)人時(shí)他原來(lái)的位子在哪里?

　　2. 有兩個(gè)已遞增有序的單鏈表pLinkList和qLinkList，將這兩個(gè)鏈表合并成一個(gè)遞增有序的鏈表，請自己定義單鏈表的結構。

　　3. 具體題目不記得，大概意思就是：從N個(gè)數中隨機抽取出M個(gè)數(M < N)，為了使抽取比較均勻，請自己定義抽取函數使得抽取的數既均勻又盡量隨機。

　　四、擴展題

　　具體題目也記不清了，一大堆，大概意思是：有一個(gè)海量日志庫，里面的每條日志記錄都有相應的關(guān)鍵詞和訪(fǎng)問(wèn)次數，但記錄是無(wú)序的，為了挖掘客戶(hù)偏好，需要找出前N個(gè)最高訪(fǎng)問(wèn)次數的日志記錄，請設計算法盡量使時(shí)間復雜度和空間復雜度最低。

　　下面是我自己寫(xiě)的答案，不一定正確，歡迎大家批評指定和提出自己更好的想法和意見(jiàn)：

　　二、簡(jiǎn)答題1. 簡(jiǎn)述Servlet的生命周期

　　答：Web容器加載servlet，生命周期開(kāi)始，通過(guò)調用servlet的的init()方法進(jìn)行servlet的初始化，通過(guò)調用service()方法實(shí)現，根據請求的不同調用不同的doGet()和doPost()方法，結束服務(wù)，web容器調用servlet的destroy()方法。

　　一個(gè)servlet的生命周期由部署servlet的容器控制，當一個(gè)請求映射到一個(gè)servlet時(shí)，容器執行下步驟：

　　1.加載servlet類(lèi)

　　2.創(chuàng )建一個(gè)servlet類(lèi)的實(shí)例

　　3.調用init初始化servlet實(shí)例，

　　4.調用service方法，傳遞一個(gè)請求和響應對象

　　5.容器要移除一個(gè)servlet，調用servlet的destroy方法結束該servlet

　　2. 寫(xiě)出至少8個(gè)Java常用的包名稱(chēng)

　　答：答出以下的任意8個(gè)就行了

　　1. java.lang Java 編程語(yǔ)言的基本類(lèi)庫

　　2. java.applet 創(chuàng )建 applet 需要的所有類(lèi)

　　3. java.awt 創(chuàng )建用戶(hù)界面以及繪制和管理圖形、圖像的類(lèi)

　　4. java.io 通過(guò)數據流、對象序列以及文件系統實(shí)現的系統輸入、輸出

　　5. java.net 用于實(shí)現網(wǎng)絡(luò )通訊應用的所有類(lèi)

　　6. java.util 集合類(lèi)、時(shí)間處理模式、日期時(shí)間工具等各類(lèi)常用工具包

　　7. java.sql 訪(fǎng)問(wèn)和處理來(lái)自于 Java 標準數據源數據的類(lèi)

　　8. java.test 以一種獨立于自然語(yǔ)言的方式處理文本、日期、數字和消息的類(lèi)和接口

　　9. java.security 設計網(wǎng)絡(luò )安全方案需要的一些類(lèi)

　　10. java.beans 開(kāi)發(fā) Java Beans 需要的所有類(lèi)

　　11. java.math 簡(jiǎn)明的整數算術(shù)以及十進(jìn)制算術(shù)的基本函數

　　12. java.rmi 與遠程方法調用相關(guān)的所有類(lèi)

　　3. Overload和Override的區別，Overloaded方法是否可以改變返回值類(lèi)型?

　　答：Overload是重載的意思，Override是覆蓋的意思，也就是重寫(xiě)。

　　(1)重載Overload表示同一個(gè)類(lèi)中可以有多個(gè)名稱(chēng)相同的方法，但這些方法的參數列表各不相同(即參數個(gè)數或類(lèi)型不同)，重載發(fā)生在同一個(gè)類(lèi)中。

　　(2)重寫(xiě)Override表示子類(lèi)中的方法可以與父類(lèi)中的某個(gè)方法的名稱(chēng)和參數完全相同，通過(guò)子類(lèi)創(chuàng )建的實(shí)例對象調用這個(gè)方法時(shí)，將調用子類(lèi)中的定義方法，這相當于把父類(lèi)中定義的那個(gè)完全相同的方法給覆蓋了，這也是面向對象編程的多態(tài)性的一種表現。子類(lèi)覆蓋父類(lèi)的方法時(shí)，只能比父類(lèi)拋出更少的異常，或者是拋出父類(lèi)拋出的異常的子異常，因為子類(lèi)可以解決父類(lèi)的一些問(wèn)題，不能比父類(lèi)有更多的問(wèn)題。子類(lèi)方法的訪(fǎng)問(wèn)權限只能比父類(lèi)的更大，不能更小。如果父類(lèi)的方法是private類(lèi)型，那么，子類(lèi)則不存在覆蓋的限制，相當于子類(lèi)中增加了一個(gè)全新的方法。重寫(xiě)發(fā)生在不同的類(lèi)(父類(lèi)和子類(lèi))中。

　　(3)至于Overloaded的方法是否可以改變返回值的類(lèi)型這個(gè)問(wèn)題，要看你倒底想問(wèn)什么呢?這個(gè)題目很模糊。如果幾個(gè)Overloaded的方法的參數列表不一樣，它們的返回者類(lèi)型當然也可以不一樣。但我估計你想問(wèn)的問(wèn)題是：如果兩個(gè)方法的參數列表完全一樣，是否可以讓它們的返回值不同來(lái)實(shí)現重載Overload。這是不行的，我們可以用反證法來(lái)說(shuō)明這個(gè)問(wèn)題，因為我們有時(shí)候調用一個(gè)方法時(shí)也可以不定義返回結果變量，即不要關(guān)心其返回結果，例如，我們調用map.remove(key)方法時(shí)，雖然remove方法有返回值，但是我們通常都不會(huì )定義接收返回結果的變量，這時(shí)候假設該類(lèi)中有兩個(gè)名稱(chēng)和參數列表完全相同的方法，僅僅是返回類(lèi)型不同，java就無(wú)法確定編程者倒底是想調用哪個(gè)方法了，因為它無(wú)法通過(guò)返回結果類(lèi)型來(lái)判斷。

　　4. 不用中間變量交換a和b的值

　　答：很多種方法，我這里給出最簡(jiǎn)單的：

　　a = a + b;

　　b = a - b;

　　a = a - b;

　　三、編程題1. 有N個(gè)人圍一圈依次報數，數到3的倍數的人出列，問(wèn)當只剩一個(gè)人時(shí)他原來(lái)的位子在哪里?

　　解答：經(jīng)典的轉圈踢人問(wèn)題，好吧專(zhuān)業(yè)一點(diǎn)，約瑟夫環(huán)問(wèn)題，相信大家都會(huì )，下面給我的code：

　　int main()

　　{

　　int N, i, j;

　　printf("Please enter the number of people(N): ");

　　scanf("%d", &N);

　　int *pArray = (int *)malloc(sizeof(int) * N);

　　int count = 0;

　　/pic/p>

　　for(i = 0; i < N; i++)

　　{

　　pArray[i] = i;

　　}

　　for(i = 0, j = 0; i < N; i = (i + 1) % N)

　　{

　　if(pArray[i] != -1)

　　{

　　j++;

　　if(j % 3 == 0)

　　{

　　pArray[i] = -1;

　　count++;

　　if(count == N)

　　{

　　printf("The last people is %d\n", i);

　　break;

　　}

　　}

　　}

　　}

　　return 0;

　　}

　　好吧，我承認我的算法很臃腫，完全是模擬了整個(gè)游戲過(guò)程，時(shí)間復雜度為O(mn)，這里m=3，網(wǎng)上有個(gè)大牛給出了歸納數學(xué)的方法，具體方法如下：

　　為了討論方便，先把問(wèn)題稍微改變一下，并不影響原意：

　　問(wèn)題描述：n個(gè)人(編號0~(n-1))，從0開(kāi)始報數，報到(m-1)(這里m=3)的退出，剩下的人繼續從0開(kāi)始報數，求最后剩下一個(gè)人的編號。

　　我們知道第一個(gè)人(編號一定是m%n-1) 出列之后，剩下的n-1個(gè)人組成了一個(gè)新的約瑟夫環(huán)(以編號為k=m%n的人開(kāi)始):

　　k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且從k開(kāi)始報0。

　　現在我們把他們的編號做一下轉換：

　　k --> 0

　　k+1 --> 1

　　k+2 --> 2

　　...

　　...

　　k-2 --> n-2

　　k-1 --> n-1

　　變換后就完完全全成為了(n-1)個(gè)人報數的子問(wèn)題，假如我們知道這個(gè)子問(wèn)題的解：例如x是最終的勝利者，那么根據上面這個(gè)表把這個(gè)x變回去不剛好就是n個(gè)人情況的解嗎?!!變回去的公式很簡(jiǎn)單，相信大家都可以推出來(lái)：x'=(x+k)%n

　　如何知道(n-1)個(gè)人報數的問(wèn)題的解?對，只要知道(n-2)個(gè)人的解就行了。(n-2)個(gè)人的解呢?當然是先求(n-3)的情況 ---- 這顯然就是一個(gè)倒推問(wèn)題!好了，思路出來(lái)了，下面寫(xiě)遞推公式：

　　令f[i]表示i個(gè)人玩游戲報m退出最后勝利者的編號，最后的結果自然是f[n]

　　遞推公式

　　f[1]=0;

　　f[i]=(f[i-1]+m)%i; (i>1)

　　有了這個(gè)公式，我們要做的就是從1-n順序算出f[i]的數值，最后結果是f[n]。因為實(shí)際生活中編號總是從1開(kāi)始，我們輸出f[n]+1

　　由于是逐級遞推，不需要保存每個(gè)f[i]，程序也是異常簡(jiǎn)單：

　　#include

　　#include

　　int main()

　　{

　　int N, i, s = 0;

　　printf("Please enter the number of people(N): ");

　　scanf("%d", &N);

　　for (i = 2; i <= N; i++)

　　{

　　s = (s + 3) % i;

　　}

　　printf ("The last people is %d\n", s);

　　return 0;

　　}

　　這個(gè)算法的時(shí)間復雜度為O(n)，相對于模擬算法已經(jīng)有了很大的提高。算n，m等于一百萬(wàn)，一千萬(wàn)的情況不是問(wèn)題了�？梢�(jiàn)，適當地運用數學(xué)策略，不僅可以讓編程變得簡(jiǎn)單，而且往往會(huì )成倍地提高算法執行效率。數學(xué)確實(shí)很重要啊!!!

　　2. 有兩個(gè)已遞增有序的單鏈表pLinkList和qLinkList，將這兩個(gè)鏈表合并成一個(gè)遞增有序的鏈表，請自己定義單鏈表的結構。

　　解答：同樣很經(jīng)典，不用多說(shuō)，直接上我自己的code(不是最好的)：

　　#include

　　using namespace std;

　　struct LinkList {

　　int data;

　　LinkList *next;

　　};

　　LinkList* createList() {

　　LinkList *head = NULL, *p, *q;

　　int data;

　　cin >> data;

　　while(data) {

　　p = new LinkList;

　　p->data = data;

　　p->next = NULL;

　　if(head == NULL) {

　　head = p;

　　q = head;

　　}

　　else {

　　q->next = p;

　　q = p;

　　}

　　cin >> data;

　　}

　　return head;

　　}

　　/pic/p>

　　void merge(LinkList *&pLinkList, LinkList *qLinkList) {

　　LinkList *pre, *p, *q;

　　pre = NULL;

　　p = pLinkList;

　　q = qLinkList;

　　while(p != NULL && q != NULL) {

　　if(p->data < q->data)

　　{

　　pre = p;

　　p = p->next;

　　}

　　else

　　{

　　/pic/p>

　　if(pre == NULL)

　　{

　　pLinkList = q;

　　}

　　else

　　{

　　pre->next = q;

　　}

　　pre = q;

　　q=q->next;

　　pre->next = p;

　　}

　　}

　　/pic/p>

　　if(q != NULL)

　　{

　　pre->next = q;

　　}

　　}

　　void print(LinkList *l) {

　　LinkList *p = l;

　　while(p != NULL) {

　　if(p->next == NULL) {

　　cout << p->data;

　　break;

　　}

　　cout << p->data << " -> ";

　　p = p->next;

　　}

　　cout << endl;

　　}

　　int main() {

　　cout << "Please enter pLinkList: ";

　　LinkList *pLinkList = createList();

　　print(pLinkList);

　　cout << "\nPlease enter pLinkList: ";

　　LinkList *qLinkList = createList();

　　print(qLinkList);

　　merge(pLinkList, qLinkList);

　　cout << "\nThe merge LinkList is: \n";

　　print(pLinkList);

　　return 0;

　　}

　　3. 具體題目不記得，大概意思就是：從N個(gè)數中隨機抽取出M個(gè)數(M < N)，為了使抽取比較均勻，請自己定義抽取函數使得抽取的數既均勻又盡量隨機。

　　解答：當時(shí)時(shí)間太急了，沒(méi)來(lái)得及多想，做法很傻：從1 ~ M*N中隨機抽取一個(gè)數字，然后mod (N + 1)，求得的值為N個(gè)數中的下標，再根據此下標去N個(gè)數中取，重復M次即可。假如這N個(gè)數存在數組nArray[]中，抽取的M個(gè)數存在數組mArray[]中，偽代碼描述如下：

　　for(int i = 0; i < M; i++)

　　{

　　int index = Random(M * N) % N;

　　mArray[i] = nArray[index];

　　}由于覺(jué)得這個(gè)算法實(shí)在是不好，就懶得測試了，大家有好想法的趕緊提出來(lái)吧。

　　四、擴展題具體題目也記不清了，一大堆描述，大概意思是：有一個(gè)海量日志庫，里面的每條日志記錄都有相應的關(guān)鍵詞和訪(fǎng)問(wèn)次數，但記錄是無(wú)序的，為了挖掘客戶(hù)偏好，需要找出前N個(gè)最高訪(fǎng)問(wèn)次數的日志記錄，請設計算法盡量使時(shí)間復雜度和空間復雜度最低。

　　解答：典型的Top K問(wèn)題，我用的算法也是大家都知道的，大致描述下思路：假如關(guān)鍵詞和訪(fǎng)問(wèn)次數成一個(gè)記錄結構體，維護一個(gè)有N個(gè)該結構體的小根堆，初始化為N個(gè)日志記錄的關(guān)鍵詞和訪(fǎng)問(wèn)次數(建堆算法)，每次有新的記錄時(shí)，將該記錄的訪(fǎng)問(wèn)次數與小根堆的堆頂元素進(jìn)行比較，如果大于堆頂元素則與堆頂元素交換記錄，然后調整堆結構使其重新為一個(gè)小根堆，否則置之不理。當所有記錄遍歷完后，所有的堆元素就是所要求的前N個(gè)最高訪(fǎng)問(wèn)次數的日志記錄。時(shí)間復雜度為O(MlgN)，不知道自己分析的對不對，完全是自以為是的想法，如果大家有更好的算法歡迎提出!

【除夕的傳說(shuō)作文】相關(guān)文章：

除夕的傳說(shuō)作文（精選39篇）02-01

美麗的傳說(shuō)05-01

月亮的傳說(shuō)作文-月亮作文01-25

七夕的傳說(shuō)作文02-22

美麗的傳說(shuō)作文400字03-29

元宵節的傳說(shuō)作文04-24

中秋節傳說(shuō)作文03-17

龍的傳說(shuō)的作文300字09-01

“年”的傳說(shuō)故事11-19

家鄉的傳說(shuō)作文（精選12篇）12-14