|
1、 兩個(gè)二進(jìn)制數(shù)的異或結(jié)果
2、 遞歸函數(shù)最終會結(jié)束，那么這個(gè)函數(shù)一定（不定項(xiàng)選擇）： 1. 使用了局部變量 2. 有一個(gè)分支不調(diào)用自身 3. 使用了全局變量或者使用了一個(gè)或多個(gè)參數(shù) 3、以下函數(shù)的結(jié)果？ int cal(int x) { if(x==0) return 0; else return x+cal(x-1); } 4、 以下程序的結(jié)果？ void foo(int*a, int* b) { *a = *a+*b; *b = *a-*b; *a = *a-*b; } void main() { int a=1, b=2, c=3; foo(&a,&b); foo(&b,&c); foo(&c,&a); printf("%d, %d, %d", a,b,c); } 5、下面哪項(xiàng)不是鏈表優(yōu)于數(shù)組的特點(diǎn)？ 1. 方便刪除 2. 方便插入 3. 長度可變 4. 存儲空間小 6、T(n) = 25T(n/5)+n^2的時(shí)間復(fù)雜度？ 7、n個(gè)頂點(diǎn)，m條邊的全連通圖，至少去掉幾條邊才能構(gòu)成一棵樹？ 8、正則表達(dá)式(01|10|1001|0110)*與下列哪個(gè)表達(dá)式一樣？ 1.(0|1)* 2.(01|01)* 3.(01|10)* 4.(11|01)* 5.(01|1)* 9、如何減少換頁錯(cuò)誤？ 1. 進(jìn)程傾向于占用CPU 2. 訪問局部性（locality of reference）滿足進(jìn)程要求 3. 進(jìn)程傾向于占用I/O 4.使用基于最短剩余時(shí)間（shortest remaining time）的調(diào)度 機(jī)制 5. 減少頁大小 10、實(shí)現(xiàn)兩個(gè)N*N矩陣的乘法，矩陣由一維數(shù)組表示 11、找到單向鏈表中間那個(gè)元素，如果有兩個(gè)則取前面一個(gè) 12、長度為n的整數(shù)數(shù)組，找出其中任意(n-1)個(gè)乘積最大的那一組，只能用乘法，不可 以用除法。要求對算法的時(shí)間復(fù)雜度和空間復(fù)雜度作出分析，不要求寫程序。 1 0
2。2 3。(n+1)*n/2 4.1 3 2 5.4 6. O(n^2*lgn) 對于T(n) = a*T(n/b)+c*n^k;T(1) = c 這樣的遞歸關(guān)系，有這樣的結(jié)論： 后面的幾題在想，最后一題要不要考慮負(fù)數(shù)？ ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 1、0 2、2，3（eg, if(n&2) return 1; else return a(n-1)+a(n-2)） 應(yīng)該要使用參數(shù)滿足某個(gè)條件然后退出。 3、x(x+1)/2 4、1，3，2 5、4 6、O(log5(n)) 7、(n-1)(n-2)/2＝n(n-1)/2-(n-1) 8、3 9、2，4 ? 10、 void matrixmul(int a[N][N], int b[N][N], int result[N][N]) { memset(result, 0, sizeof(int) * N * N); for(int i = 0; i & N; i++) { for(int j = 0; j & N; j++) { for(int k = 0; k & N; k++) { result[i][j] += a[i][k] * b[k][j]; } } } } 11、用兩個(gè)指針，一個(gè)步長為1，一個(gè)步長為2，當(dāng)步長2的那個(gè)指針走到頭時(shí)，這個(gè)時(shí)候步 長為1的那個(gè)指針剛好指著中間的那個(gè)結(jié)點(diǎn)。 12、 思路：定義一臨時(shí)量保存當(dāng)前最小的數(shù)(min)，和一個(gè)保存總數(shù)的(sum)，開始比較（從第 2個(gè)開始）如果有比這大的，那么乘上，如果比這小，那么乘于min,把小數(shù)放到min中。 算法復(fù)雜度為O(n) 空間復(fù)雜度為O(2) ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． ． 11 somestruct* FindMiddle(somestruct* pHead) { if (pHead == NULL || pHead->next == NULL) return pHead; somestruct* p1 = pHead, p2 = pHead->next; while (p2 != NULL && p2->next != NULL) { //每次p1前進(jìn)一位，p2前進(jìn)2位 p1 = p1->next; p2 = p2->next->next; } return p1; } 1.寫程序判斷是否字符串A里每個(gè)字符在A中出現(xiàn)的次數(shù)都大于在字符串B中出現(xiàn)的次數(shù)。
注：此題我是對每個(gè)字符出現(xiàn)的次數(shù)分別統(tǒng)計(jì)，然后比較。重復(fù)的字符重復(fù)統(tǒng)計(jì)比較，所以效率很低。不知有什么好的改進(jìn)方法？ 2.對一個(gè)數(shù)組S，求其中滿足要求的最大元素C。要求C滿足等式C=A*B，其中A、B也是數(shù)組S中的元素。請用能想到的最優(yōu)算法，分析時(shí)間和空間復(fù)雜度。（用語言描述算法，不用寫程序） 注：這個(gè)題我當(dāng)時(shí)做的方法在時(shí)間上要用o(n^3)，事后想出了個(gè)o(n^2 logn)的方法。不知有沒有更好的方法。 1. typedef struct { typedef struct { 請寫出深拷貝函數(shù)：Tree * deepCopy(Tree *tree); 2. 輸入一個(gè)整型數(shù)組，對該數(shù)組進(jìn)行隨機(jī)排序，寫出該函數(shù) 3. N個(gè)人排成一圈，指定第一個(gè)人，去除他，然后跳著一人去除第3人，以次類推，最后
的那一人獲勝。給定這N個(gè)人和第一個(gè)人的位置，你該如何選取位置才會獲勝。 讓你寫最優(yōu)算法，并計(jì)算時(shí)間和空間復(fù)雜度。不要求寫出代碼，解釋算法即可。 一、 選擇題：
1.
456×567＝150216
問這是在什么進(jìn)制下？ A.9 B.10 C.12 D.18
2.
二叉樹前序：ABCEDF，中序：CBADEF，請問后序？
3.
char s[][10]={"hello","google"};
char *p=s[0]; printf("%d",strlen(p+10)); 結(jié)果為
A. 10 B.0 C.5 D.6
4 G: S->uvSvu|w，請問S
5
給出前序遍歷和中續(xù)遍歷 求后序遍歷（題目似乎有錯(cuò)）
6
f(0)=1, f(n)=n*f(n-1)+1 求它的復(fù)雜度
7
等待 就緒 運(yùn)行 掛起的 關(guān)系
8
有6個(gè)進(jìn)程以及7個(gè)同類資源。每個(gè)進(jìn)程每次申請一個(gè)資源，并且最多需要2個(gè)資源，問會不會死鎖
9
一個(gè)自動機(jī)的文法題目10
一個(gè)文件分成3份，并且每份有一個(gè)拷貝，每個(gè)拷貝出現(xiàn)錯(cuò)誤的概率10％，問整個(gè)文件出錯(cuò)的概率
（3％）
二、 算法題：
1 一個(gè)圖G，編寫兩點(diǎn)間是否存在路徑的函數(shù)
2 有一棵樹，每個(gè)節(jié)點(diǎn)與子節(jié)點(diǎn)間看成是有距離的，都給定一個(gè)整數(shù)?，F(xiàn)在要延長某些邊，使得根節(jié)點(diǎn)到所有葉節(jié)點(diǎn)的路徑長度都相等。求這種情況下，所有路徑長度最短是多少。
1、 一些奧運(yùn)組委會每個(gè)月都有定期的會議，有一些委員同時(shí)在多個(gè)組委會中，假設(shè)這些組 委會是：C1={A,B,C} C2={D,E,F} C3={A,C,E} C4={B,D,F} C5={E,F} C6={B,F}。并且任何 一名委員在同一天只能參加一個(gè)會議，問每月至少有一個(gè)組委在開會的日子最少有幾天？ A. 3 B. 4 C. 5 D. 6 2、 下面一段代碼的輸出是 void f(char *p) { if (*p >= ‘A’ && *p <=’Z’) *p = *p – ‘A’ + ‘a’; if (*p >= ‘a’ && *p <= ‘z’) *p = *p – ‘a’ + ‘A’; } int main() { char s[] = “ABC+abc=defDEF”; while (*p != ‘\0’) { f(p); p++; } cout << s; return 0; } A. abc+ABC=DEFdef B. abc+abc=defdef C. ABC+ABC=DEFDEF D. abcABCDEFdef 3、 高度為H的堆的最小元素?cái)?shù)目是多少？ A. H^2 B. H^2-H C. 2^H-1 D. 2^(H-1) E. 2^(H-1)+1 4、 下列排序算法中，當(dāng)要排序的數(shù)列已經(jīng)為有序時(shí)，耗費(fèi)時(shí)間最多的是 A. 冒泡排序 B. 選擇排序 C. 插入排序 D. 歸并排序 5、 定義函數(shù)f如下： int f(int n) { if (n <= 10) return n+3; return f(f(n – 7)); } 那么f(30)的輸出結(jié)果是 A. 10 B. 11 C. 12 D. 13 6、 已經(jīng)樹T的結(jié)點(diǎn)集為{A, B, C, D, E, F, G, H, I, J}，邊的集合為{<A,B>, <B,E>, <B ,F>, <F,G>, <F, H>, <A, C>, <C,I>, <C,J>, <A,D>}，可知樹T至少有多少個(gè)葉節(jié)點(diǎn)？ A. 3 B. 4 C. 5 D. 6 7、 下面對進(jìn)程的描述中錯(cuò)誤的是 A. 進(jìn)程是動態(tài)的概念 B. 進(jìn)程需要處理機(jī) C. 進(jìn)程是有生命周期的 D. 進(jìn)程是指令的集合 8、 產(chǎn)生死鎖的原因不包括 A. 系統(tǒng)資源不足 B. 共享互斥資源 C. 進(jìn)程的推進(jìn)順序不當(dāng) D. 并發(fā)執(zhí)行的進(jìn)程數(shù)太多 9、 某服務(wù)器要與大量客戶端進(jìn)行頻繁的小數(shù)據(jù)量通信，為了達(dá)到更好的性能，應(yīng)該采用下 面的哪種協(xié)議？ A. TCP B. ICMP C. HTTP D. UDP 10、下面文法（或者用自動機(jī)表示）描述的語言是：S=aA|bB; A=aS|bC|e; B=bS|aC; C=bA| aB; A. 奇數(shù)個(gè)a和一些b B. 偶數(shù)個(gè)a和一些b C. 奇數(shù)個(gè)a和偶數(shù)個(gè)b D. 偶數(shù)個(gè)a和奇數(shù)個(gè)b 程序設(shè)計(jì)與算法 1、 用單鏈表實(shí)現(xiàn)一個(gè)存儲空間管理器，包括分配和釋放空間。要求釋放的時(shí)候合并相連空 閉地址。分配空間的策略可以自選，并說明所用的策略的優(yōu)點(diǎn)和缺點(diǎn)。（下面的框架是C++ 描述的，你可以用你熟悉的語言。） void* xmalloc(unsigned int size) void xfree(void* p) 2、 給定n個(gè)數(shù)，要從中選出m個(gè)數(shù)使其標(biāo)準(zhǔn)差最小。分析你的算法的時(shí)間復(fù)雜度，解釋算法 即可，不必寫代碼。 3、 你編寫過的最有創(chuàng)意的項(xiàng)目是什么？有人使用這個(gè)創(chuàng)意嗎？ |
|
|
Joseph問題的數(shù)學(xué)方法
無論是用鏈表實(shí)現(xiàn)還是用數(shù)組實(shí)現(xiàn)都有一個(gè)共同點(diǎn)：要模擬整個(gè)游戲過程，不僅
程序?qū)懫饋肀容^煩，而且時(shí)間復(fù)雜度高達(dá)O(nm)，當(dāng)n，m非常大(例如上百萬，上
千萬)的時(shí)候，幾乎是沒有辦法在短時(shí)間內(nèi)出結(jié)果的。我們注意到原問題僅僅是要
求出最后的勝利者的序號，而不是要讀者模擬整個(gè)過程。因此如果要追求效率，
就要打破常規(guī)，實(shí)施一點(diǎn)數(shù)學(xué)策略。
為了討論方便，先把問題稍微改變一下，并不影響原意：
問題描述：n個(gè)人（編號0~(n-1))，從0開始報(bào)數(shù)，報(bào)到(m-1)的退出，剩下的人繼
續(xù)從0開始報(bào)數(shù)。求勝利者的編號。
我們知道第一個(gè)人(編號一定是m%n-1) 出列之后，剩下的n-1個(gè)人組成了一個(gè)新的
約瑟夫環(huán)（以編號為k=m%n的人開始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且從k開始報(bào)0。
現(xiàn)在我們把他們的編號做一下轉(zhuǎn)換：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
變換后就完完全全成為了(n-1)個(gè)人報(bào)數(shù)的子問題，假如我們知道這個(gè)子問題的解：
例如x是最終的勝利者，那么根據(jù)上面這個(gè)表把這個(gè)x變回去不剛好就是n個(gè)人情況
的解嗎？?。∽兓厝サ墓胶芎唵?，相信大家都可以推出來：x‘=(x+k)%n
如何知道(n-1)個(gè)人報(bào)數(shù)的問題的解？對，只要知道(n-2)個(gè)人的解就行了。(n-2)
個(gè)人的解呢？當(dāng)然是先求(n-3)的情況 ---- 這顯然就是一個(gè)倒推問題！好了，思
路出來了，下面寫遞推公式：
令f[i]表示i個(gè)人玩游戲報(bào)m退出最后勝利者的編號，最后的結(jié)果自然是f[n]
遞推公式:
f[1]=0
f[i]=(f[i-1]+m)%i; (i>1)
有了這個(gè)公式，我們要做的就是從1-n順序算出f[i]的數(shù)值，最后結(jié)果是f[n]。因
為實(shí)際生活中編號總是從1開始，我們輸出f[n]+1,由于是逐級遞推，不需要保存每
個(gè)f[i]，程序也是異常簡單：
#include
int main()
{
int n, m, i, s=0;
printf ("N M = ");
scanf("%d%d", &n, &m);
for (i=2; i
int mod(int x,int n)
{ return (x%n+n)%n; }
int f(int n,int m,int t) {
if(n==2) return mod(t,n)==1?2:1;
else if(mod(t,n)!=mod(m,n))return mod(f(n-1,m,mod(t-m-1,n)+1)+m-1,n)+1;
else return mod(f(n-1,m,n-1)+m,n)+1;
}
int main(int arg, char* args[])
{
int k,n,m,t;
freopen(args[1], "r",stdin);
scanf("%d",&k);
while( k-- ) {
scanf("%d%d%d",&n,&m,&t);
printf("%d\n",f(n,m,t));
}
return 0;
}