1、英特爾筆試題發(fā)布時間:2010-05-22 來源:應(yīng)屆畢業(yè)生求職網(wǎng)概率題x,y為隨機(jī)變量，聯(lián)合概率密度 f(x,y) = intig(0,1)*dx*intig(0,x)*k*dy，k為常數(shù)，求k=? E(xy)=? 注：intig(a,b)為a到b的定積分。2、概率題A,B為隨機(jī)事件，以下哪個正確A. P(A U B)*p(AB) = P(A)P(B)C. P(A U B)*p(AB) = P(A) + P(B)3、信道帶寬200kHz,信噪比10dB，求信道波特率? 1奈奎斯特定理奈奎斯特證明，對于一個帶寬為W赫茲的理想信道，其最大碼元（信號）速率為2W波特。這一限制是由于存在碼間干擾。如

2、果被傳輸?shù)男盘柊薓個狀態(tài)值（信號的狀態(tài)數(shù)是M），那么W赫茲信道所能承載的最大數(shù)據(jù)傳輸速率（信道容量）是：C =2Wlog2M（bps）假設(shè)帶寬為W赫茲信道中傳輸?shù)男盘柺嵌M(jìn)制信號（即信道中只有兩種物理信號），那么該信號所能承載的最大數(shù)據(jù)傳輸速率是2Wbps。例如，使用帶寬為3KHz的話音信道通過調(diào)制解調(diào)器來傳輸數(shù)字?jǐn)?shù)據(jù)，根據(jù)奈奎斯特定理，發(fā)送端每秒最多只能發(fā)送23000個碼元。如果信號的狀態(tài)數(shù)為2，則每個信號可以攜帶1個比特信息，那么話音信道的最大數(shù)據(jù)傳輸速率是6Kbps；如果信號的狀態(tài)數(shù)是4，則每個信號可以攜帶2個比特信息，那么話音信道的最大數(shù)據(jù)傳輸速率是12Kbps。因此對于給定的信道

3、帶寬，可以通過增加不同信號單元的個數(shù)來提高數(shù)據(jù)傳輸速率。然而這樣會增加接收端的負(fù)擔(dān)，因?yàn)?，接收端每接收一個碼元，它不再只是從兩個可能的信號取值中區(qū)分一個，而是必須從M個可能的信號中區(qū)分一個。傳輸介質(zhì)上的噪聲將會限制M的實(shí)際取值。2香農(nóng)定理奈奎斯特考慮了無噪聲的理想信道，而且奈奎斯特定理指出，當(dāng)所有其他條件相同時，信道帶寬加倍則數(shù)據(jù)傳輸速率也加倍。但是對于有噪聲的信道，情況將會迅速變壞。現(xiàn)在讓我們考慮一下數(shù)據(jù)傳輸速率、噪聲和誤碼率之間的關(guān)系。噪聲的存在會破壞數(shù)據(jù)的一個比特或多個比特。假如數(shù)據(jù)傳輸速率增加了，每比特所占用的時間會變短，因而噪聲會影響到更多比特，則誤碼率會越大。對于有噪聲信道，我們希

4、望通過提高信號強(qiáng)度來提高接收端正確接收數(shù)據(jù)的能力。衡量信道質(zhì)量好壞的參數(shù)是信噪比（Signal-to-Noise Ratio，S/N），信噪比是信號功率與在信道某一個特定點(diǎn)處所呈現(xiàn)的噪聲功率的比值。通常信噪比在接收端進(jìn)行測量，因?yàn)槲覀冋窃诮邮斩颂幚硇盘柌⒃噲D消除噪聲的。如果用S表示信號功率，用N表示噪聲功率，則信噪比表示為S/N。為了方便起見，人們一般用10log10（S/N）來表示信噪比，單位是分貝（dB）。S/N的值越高，表示信道的質(zhì)量越好。例如，S/N為1000，其信噪比為30dB；S/N為100，其信噪比為20dB；S/N為10，其信噪比為10dB。對于通過有噪聲信道傳輸數(shù)字?jǐn)?shù)據(jù)而言

5、，信噪比非常重要，因?yàn)樗O(shè)定了有噪聲信道一個可達(dá)的數(shù)據(jù)傳輸速率上限，即對于帶寬為W赫茲，信噪比為S/N的信道，其最大數(shù)據(jù)傳輸速率（信道容量）為：C = Wlog2(1+S/N)（bps）例如，對于一個帶寬為3KHz，信噪比為30dB（S/N就是1000）的話音信道，無論其使用多少個電平信號發(fā)送二進(jìn)制數(shù)據(jù)，其數(shù)據(jù)傳輸速率不可能超過30Kbps。值得注意的是，香農(nóng)定理僅僅給出了一個理論極限，實(shí)際應(yīng)用中能夠達(dá)到的速率要低得多。其中一個原因是香農(nóng)定理只考慮了熱噪聲（白噪聲），而沒有考慮脈沖噪聲等因素。4、以下代碼運(yùn)行結(jié)果是什么int main()int a,b,c,abc = 0;a=b=c=40;i

6、f(c)int abc;abc = a*b+c;printf(%d,%d, abc, c);return 0;/0 405、給出了從紐約出發(fā)和到達(dá)洛杉磯的各種航班信息，寫出找到一條從紐約到洛杉磯的最短距離的航班組合的代碼。單源最短路：Dijkstra 迪杰斯特拉 n2Bellman Ford veSPFA O(ke)， 其中k為所有頂點(diǎn)進(jìn)隊的平均次數(shù)，可以證明k一般小于等于2各點(diǎn)最短路：Floyd-Warshall 弗洛伊德 n3最小生成樹Prim 普里姆 n2Kruskal 克魯斯卡爾 eloge代碼如下/*=*| Dijkstra數(shù)組實(shí)現(xiàn)O（N2）| Dijkstra - 數(shù)組實(shí)現(xiàn)(在此基

7、礎(chǔ)上可直接改為STL的Queue實(shí)現(xiàn))| lowcost - beg到其他點(diǎn)的最近距離| path - beg為根展開的樹，記錄父親結(jié)點(diǎn)*=*/#define INF 0x03F3F3F3Fconst int N;int pathN, visN;void Dijkstra(int costN, int lowcostN, int n, int beg)int i, j, min;memset(vis, 0, sizeof(vis);visbeg = 1;for (i=0; in; i+)lowcosti = costbegi; pathi = beg;lowcostbeg = 0;pathbe

8、g = -1; / 樹根的標(biāo)記int pre = beg;for (i=1; in; i+)min = INF;for (j=0; jn; j+)/ 下面的加法可能導(dǎo)致溢出,INF不能取太大if (visj=0 & lowcostpre+costprejlowcostj)lowcostj = lowcostpre + costprej;pathj = pre;for (j=0; jn; j+)if (visj = 0 & lowcostj =表示求最小值, 作為最長路，=表示求最大值, 作為最短路 （v-u distu + c) distv = distu + c;prev = u; retu

9、rn 1;return 0;int bellman (int src)int i, j;for (i=0; in; +i) disti = inf; prei = -1;distsrc = 0; bool flag;for (i=1; in; +i)flag = false; / 優(yōu)化for (j=0; jm; +j) if( 1 = relax(edgej0, edgej1, edgej2) ) flag = true;if( !flag ) break; for (j=0; jm; +j) if (1 = relax(edgej0, edgej1, edgej2)return 0; / 有

10、負(fù)圈return 1;/*=*| SPFA(Shortest Path Faster Algorithm)Bellman-Ford算法的一種隊列實(shí)現(xiàn)，減少了不必要的冗余計算。 它可以在O(kE)的時間復(fù)雜度內(nèi)求出源點(diǎn)到其他所有點(diǎn)的最短路徑，可以處理負(fù)邊。原理：只有那些在前一遍松弛中改變了距離估計值的點(diǎn)，才可能引起他們的鄰接點(diǎn)的距離估計值的改變。判斷負(fù)權(quán)回路：記錄每個結(jié)點(diǎn)進(jìn)隊次數(shù)，超過|V|次表示有負(fù)權(quán)。*=*/ POJ 3159 Candiesconst int INF = 0x3F3F3F3F;const int V = 30001;const int E = 150001;int pntE

11、, costE, nxtE;int e, headV; int distV; bool visV;int main(void)int n, m;while( scanf(%d%d, &n, &m) != EOF )int i, a, b, c;e = 0;memset(head, -1, sizeof(head);for( i=0; i m; +i )/ b-a distu + c ) distv = distu + c; return 1;return 0;inline void addedge(int u, int v, int c)pnte = v; coste = c; nxte =

12、headu; headu = e+;int SPFA(int src, int n) / 此處用堆棧實(shí)現(xiàn)，有些時候比隊列要快int i;for( i=1; i = n; +i ) / 頂點(diǎn)1.nvisi = 0; disti = INF;distsrc = 0;int QE, top = 1;Q0 = src; vissrc = true;while( top )int u, v;u = Q-top; visu = false;for( i=headu; i != -1; i=nxti )v = pnti;if( 1 = relax(u, v, costi) & !visv ) Qtop+ =

13、 v; visv = true;return distn;語法：Floyd_Washall(Graph G,int n,Graph D,Graph P);參數(shù)：G：圖，用鄰接矩陣表示n：圖的頂點(diǎn)個數(shù)D：Di,j表示從i 到j(luò) 的最短距離P：Pi,j表示從i 到j(luò) 的最短路徑上j 的父節(jié)點(diǎn)自定義:MaxN;返回值：null注意:此算法允許圖中帶有負(fù)權(quán)的弧,但不允許有路徑長度為負(fù)值的回路. 源程序： void Floyd(int GMaxN,int n,int DMaxN,int PMaxN)int i,j,k;for (i=0;in;i+)for (j=0;jn;j+) Dij=Gij;Pij=

14、i; for (i=0;in;i+) Dii=0;Pii=0; for (k=0;kn;k+)for (i=0;in;i+)for (j=0;jDik+Dkj) Dij=Dik+Dkj;Pij=Pkj; void Floyd(int n,int DMaxN) /G 不用再輸出的情況下.int i,j,k;for (i=0;in;i+) Dii=0; for (k=0;kn;k+)for (i=0;in;i+)for (j=0;jDik+Dkj) Dij=Dik+Dkj;/*=*| Prim求MST| INIT: cost耗費(fèi)矩陣(inf為無窮大);| CALL: prim(cost, n);

15、返回-1代表原圖不連通;*=*/#define typec int / type of costconst typec inf = 0x3f3f3f3f; / max of costint visV; typec lowcV;typec prim(typec costV, int n) / vertex: 0 n-1int i, j, p;typec minc, res = 0;memset(vis, 0, sizeof(vis);vis0 = 1;for (i=1; in; i+) lowci = cost0i;for (i=1; in; i+) minc = inf; p = -1;for

16、 (j=0; j lowcj) minc = lowcj; p = j;if (inf = minc) return -1; / 原圖不連通res += minc; visp = 1;for (j=0; j costpj)lowcj = costpj;return res;Kruskal 算法#include #include #include #include #include #include #include using namespace std;#define Maxn 1010struct Edge int u,v; int w; /*bool operatorE.w; */edg

17、e1000010;bool cmp(Edge E1,Edge E2) return E1.wE2.w;int n,m;int rankMaxn,pMaxn;void makeset(int n) for(int i=0;iranky) py=x; else px=y; if(rankx=ranky) ranky+; /* * */int main(int argc, char* argv) int t; int T=0; scanf(%d,&t); while(t-) T+; scanf(%d%d,&n,&m); makeset(n); for(int i=0;im;i+) scanf(%d%

18、d%d,&edgei.u,&edgei.v,&edgei.w); sort(edge,edge+m,cmp); int ans; for(int i=0;im;i+) if(findset(edgei.u)!=findset(edgei.v) unionset(edgei.u,edgei.v); if(edgei.wans)ans=edgei.w; if(findset(1)=findset(n)ans=edgei.w;break; printf(Scenario #%d:n,T); printf(%dnn,ans); return (EXIT_SUCCESS);6、從計算機(jī)圖形上截取某個物體

19、邊緣的若干個坐標(biāo)，求這個物體面積，并跟判斷是方形還是圓形，為啥。7、離散卷機(jī)與DFT的區(qū)別與關(guān)系?？焖偾蟛粷M足2N長度的離散傅立葉變換的方法有哪些？如何用fft求N*M點(diǎn)的離散卷機(jī)？8、給出fir和iir的優(yōu)缺點(diǎn)。9、如何計算線性標(biāo)量量化器的量化噪聲？需要那些假設(shè)？10、設(shè)計一個重采樣系統(tǒng)，說明如何anti-alias。11、y1（n）=x（2n），y2（n）=x（n/2），問：如果y1為周期函數(shù)，那么x是否為周期函數(shù)？如果x為周期函數(shù)，那么y1是否為周期函數(shù)？如果y2為周期函數(shù)，那么x是否為周期函數(shù)？如果x為周期函數(shù)，那么y2是否為周期函數(shù)？12、如果模擬信號的帶寬為5kHz，要用8k的采樣

20、率，怎么辦。13、某個程序在一個嵌入式系統(tǒng)（200M的CPU，50M的SDRAM）中已經(jīng)最優(yōu)化了，換到另一個系統(tǒng)（300M的CPU，50M的SDRAM）中運(yùn)行，還需要優(yōu)化嗎？14、x4+a*x3+x2+c*x+d最少需要做幾次乘法。15、三個float:a,b,c 問值：（a+b）+c=（b+a）+c（a+b）+c=（a+c）+b16、把一個鏈表反向填空。17、下面哪種排序法對12354最快？A. quick sortB. buble sortC. merge sort (,要求其它信息盡量按輸入的順序排列時很重要.這也是它比快速排序優(yōu)勢的地方.)18、哪種結(jié)構(gòu)平均來講獲取一個值最快？A. b

21、inary treeB. hash tableC. stack19、#include using namespace std;struct bit int a:3; int b:2; int c:3; ; int main(int argc, char* argv) bit s; char *c=(char*)&s; *c =0x99; for(int i=7;i=0;i-)printf(%d,*c&(1 -1，等到反碼 - 然后得到原碼。11 - 1 = 10 - 10 取反，得原碼01，所以其數(shù)值為“-1”。100 - 1 = 011 - 011 取反，得原碼100，所以其數(shù)值為“-4”。

22、統(tǒng)一用這種方法求補(bǔ)碼，或求補(bǔ)碼的真值！以前那種很容易錯！求-15的補(bǔ)碼第一步：+15：00001111第二步：逐位取反（1變成0，0變成1），然后在末尾加1。11110001再舉一個例子驗(yàn)證下：求-64的補(bǔ)碼+64：0100000011000000逆：二進(jìn)制值：10111111（-65的補(bǔ)碼）各位取反：01000000加1：01000001（+65的補(bǔ)碼）20、挑bug，在linux下運(yùn)行：#include char*reverse(char* str)int len=0, i=0;char *pstr=str, *ptemp,*pd;while(*+pstr)len+;pstr-;/ptemp=(char