2022年英特尔笔试题.docx

2022年英特尔笔试题 英特尔笔试题 概率题? x,y为随机变量，联合概率密度 f(x,y) = intig(0,1)*dx*intig(0,x)*k*dy，k为常数，求k=? E(xy)=? 注：intig(a,b)为a到b的定积分。? 2、概率题? A,B为随机事务，以下哪个正确? A. P(A U B)*p(AB) <= P(A)P(B)? B. P(A U B)*p(AB) >= P(A)P(B)? C. P(A U B)*p(AB) <= P(A) + P(B)? D. P(A U B)*p(AB) >= P(A) + P(B)? 3、信道带宽200kHz,信噪比10dB，求信道波特率 1奈奎斯特定理 奈奎斯特证明，对于一个带宽为W赫兹的志向信道，其最大码元（信号）速率为2W波特。这一限制是由于存在码间干扰。假如被传输的信号包含了M个状态值（信号的状态数是M），那么W赫兹信道所能承载的最大数据传输速率（信道容量）是： C =2×W×log2M（bps） 假设带宽为W赫兹信道中传输的信号是二进制信号（即信道中只有两种物理信号），那么该信号所能承载的最大数据传输速率是2Wbps。例如，运用带宽为3KHz的话音信道通过调制解调器来传输数字数据，依据奈奎斯特定理，发送端每秒最多只能发送2×3000个码元。假如信号的状态数为2，则每个信号可以携带1个比特信息，那么话音信道的最大数据传输速率是6Kbps；假如信号的状态数是4，则每个信号可以携带2个比特信息，那么话音信道的最大数据传输速率是12Kbps。 因此对于给定的信道带宽，可以通过增加不同信号单元的个数来提高数据传输速率。然而这样会增加接收端的负担，因为，接收端每接收一个码元，它不再只是从两个可能的信号取值中区分一个，而是必需从M个可能的信号中区分一个。传输介质上的噪声将会限制M的实际取值。 2香农定理 奈奎斯特考虑了无噪声的志向信道，而且奈奎斯特定理指出，当全部其他条件相同时，信道带宽加倍则数据传输速率也加倍。但是对于有噪声的信道，状况将会快速变坏。现在让我们考虑一下数据传输速率、噪声和误码率之间的关系。噪声的存在会破坏数据的一个比特或多个比特。假如数据传输速率增加了，每比特所占用的时间会变短，因而噪声会影响到更多比特，则误码率会越大。 对于有噪声信道，我们希望通过提高信号强度来提高接收端正确接收数据的实力。衡量信道质量好坏的参数是信噪比（Signal-to-Noise Ratio，S/N），信噪比是信号功率与在信道某一个特定点处所呈现的噪声功率的比值。通常信噪比在接收端进行测量，因为我们正是在接收端处理信号并试图消退噪声的。假如用S表示信号功率，用N表示噪声功率，则信噪比表示为S/N。为了便利起见，人们一般用10log10（S/N）来表示信噪比，单位是分贝（dB）。S/N的值越高，表示信道的质量越好。例如，S/N为1010，其信噪比为30dB；S/N为101，其信噪比为20dB；S/N为10，其信噪比为10dB。 对于通过有噪声信道传输数字数据而言，信噪比特别重要，因为它设定了有噪声信道一个可达的数据传输速率上限，即对于带宽为W赫兹，信噪比为S/N的信道，其最大数据传输速率（信道容量）为： C = W×log2(1+S/N)（bps） 例如，对于一个带宽为3KHz，信噪比为30dB（S/N就是1010）的话音信道，无论其运用多少个电平信号发送二进制数据，其数据传输速率不行能超过30Kbps。值得留意的是，香农定理仅仅给出了一个理论极限，实际应用中能够达到的速率要低得多。其中一个缘由是香农定理只考虑了热噪声（白噪声），而没有考虑脉冲噪声等因素。 4、以下代码运行结果是什么? int main()? ? int a,b,c,abc = 0;? a=b=c=40;? if(c)? ? int abc;? abc = a*b+c;? ? printf(%d,%d, abc, c);? return 0;? ? /0 40 5、给出了从纽约动身和到达洛杉矶的各种航班信息，写出找到一条从纽约到洛杉矶的最短距离的航班组合的代码。? 单源最短路： Dijkstra 迪杰斯特拉 n2 Bellman Ford ve SPFA O(ke)， 其中k为全部顶点进队的平均次数，可以证明k一般小于等于2 各点最短路： Floyd-Warshall 弗洛伊德 n3 最小生成树 Prim 普里姆 n2 Kruskal 克鲁斯卡尔 eloge 代码如下 /*=* | Dijkstra数组实现O（N2） | Dijkstra - 数组实现(在此基础上可干脆改为STL的Queue实现) | lowcost - beg到其他点的最近距离 | path - beg为根绽开的树，记录父亲结点 *=*/ #define INF 0x03F const 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; i<n; i+) lowcosti = costbegi; pathi = beg; lowcostbeg = 0; pathbeg = -1; / 树根的标记 int pre = beg; for (i=1; i<n; i+) min = INF; for (j=0; j<n; j+) / 下面的加法可能导致溢出,INF不能取太大 if (visj=0 lowcostpre+costprej<lowcostj) lowcostj = lowcostpre + costprej; pathj = pre; for (j=0; j<n; j+) if (visj = 0 lowcostj < min) min = lowcostj; pre = j; vispre = 1; /*=* | BellmanFord单源最短路O(VE) | 能在一般状况下，包括存在负权边的状况下，解决单源最短路径问题 | INIT: edgeE3为边表 | CALL: bellman(src);有负环返回0;disti为src到i的最短距 | 可以解决差分约束系统: 须要首先构造约束图，构造不等式时>=表示求最小值, 作为最长路，<=表示求最大值, 作为最短路 （v-u <= c:auv = c） *=*/ #define typec int / type of cost const typec inf=0x3f3f int n, m, preV, edgeE3; typec distV; int relax (int u, int v, typec c) if (distv > distu + c) distv = distu + c; prev = u; return 1; return 0; int bellman (int src) int i, j; for (i=0; i<n; +i) disti = inf; prei = -1; distsrc = 0; bool flag; for (i=1; i<n; +i) flag = false; / 优化 for (j=0; j<m; +j) if( 1 = relax(edgej0, edgej1, edgej2) ) flag = true; if( !flag ) break; for (j=0; j<m; +j) if (1 = relax(edgej0, edgej1, edgej2) return 0; / 有负圈 return 1; /*=* | SPFA(Shortest Path Faster Algorithm) Bellman-Ford算法的一种队列实现，削减了不必要的冗余计算。 它可以在O(kE)的时间困难度内求出源点到其他全部点的最短路径，可以处理负边。 原理：只有那些在前一遍松弛中变更了距离估计值的点，才可能引起他们的邻接点的距离估计值的变更。 推断负权回路：记录每个结点进队次数，超过|V|次表示有负权。 *=*/ / POJ 3159 Candies const int INF = 0x3F3F const int V = 30001; const int E = 150001; int pntE, 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 <= c, 有向边(a, b):c ，边的方向！ scanf(%d%d%d, a, b, c); addedge(a, b, c); printf(%dn, SPFA(1, n); return 0; int relax(int u, int v, int c) if( distv > distu + c ) distv = distu + c; return 1; return 0; inline void addedge(int u, int v, int c) pnte = v; coste = c; nxte = headu; headu = e+; int SPFA(int src, int n) / 此处用堆栈实现，有些时候比队列要快 int i; for( i=1; i <= n; +i ) / 顶点1.n visi = 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+ = v; visv = true; return distn; 语法：Floyd_Washall(Graph G,int n,Graph D,Graph P); 参数： G：图，用邻接矩阵表示 n：图的顶点个数 D：Di,j表示从i 到j 的最短距离 P：Pi,j表示从i 到j 的最短路径上j 的父节点 自定义:MaxN; 返回值：null 留意:此算法允许图中带有负权的弧,但不允许有路径长度为负值的回路. 源程序： void Floyd(int GMaxN,int n,int DMaxN,int PMaxN) int i,j,k; for (i=0;i<n;i+) for (j=0;j<n;j+) Dij=Gij; Pij=i; for (i=0;i<n;i+) Dii=0;Pii=0; for (k=0;k<n;k+) for (i=0;i<n;i+) for (j=0;j<n;j+) if (Dij>Dik+Dkj) Dij=Dik+Dkj; Pij=Pkj; void Floyd(int n,int DMaxN) /G 不用再输出的状况下. int i,j,k; for (i=0;i<n;i+) Dii=0; for (k=0;k<n;k+) for (i=0;i<n;i+) for (j=0;j<n;j+) if (Dij>Dik+Dkj) Dij=Dik+Dkj; /*=* | Prim求MST | INIT: cost耗费矩阵(inf为无穷大); | CALL: prim(cost, n); 返回-1代表原图不连通; *=*/ #define typec int / type of cost const typec inf = 0x3f3f int visV; typec lowcV; typec prim(typec costV, int n) / vertex: 0 n-1 int i, j, p; typec minc, res = 0; memset(vis, 0, sizeof(vis); vis0 = 1; for (i=1; i<n; i+) lowci = cost0i; for (i=1; i<n; i+) minc = inf; p = -1; for (j=0; j<n; j+) if (0 = visj minc > lowcj) minc = lowcj; p = j; if (inf = minc) return -1; / 原图不连通 res += minc; visp = 1; for (j=0; j<n; j+) if (0 = visj lowcj > costpj) lowcj = costpj; return res; Kruskal 算法 #include <stdlib.h> #include <stdio.h> #include <queue> #include <algorithm> #include <string.h> #include <iostream> #include <math.h> using namespace std; #define Maxn 1010 struct Edge int u,v; int w; /*bool operator<(const Edge E) return w>E.w; */ edge1010010; bool cmp(Edge E1,Edge E2) return E1.w>E2.w; int n,m; int rankMaxn,pMaxn; void makeset(int n) for(int i=0;i<=n;i+) ranki=0; pi=i; int findset(int x) if(x!=px) px=findset(px); return px; void unionset(int x,int y) x=findset(x); y=findset(y); if(rankx>ranky) 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;i<m;i+) scanf(%d%d%d,edgei.u,edgei.v,edgei.w); sort(edge,edge+m,cmp); int ans; for(int i=0;i<m;i+) if(findset(edgei.u)!=findset(edgei.v) unionset(edgei.u,edgei.v); if(edgei.w<ans)ans=edgei.w; if(findset(1)=findset(n)ans=edgei.w;break; printf(Scenario #%d:n,T); printf(%dnn,ans); return (EXIT_SUCCESS); 6、从计算机图形上截取某个物体边缘的若干个坐标，求这个物风光积，并跟推断是方形还是圆形，为啥。? 7、离散卷机与DFT的区分与关系。快速求不满意2N长度的离散傅立叶变换的方法有哪些？如何用fft求N*M点的离散卷机？? 8、给出fir和iir的优缺点。? 9、如何计算线性标量量化器的量化噪声？须要那些假设？? 10、设计一个重采样系统，说明如何anti-alias。? 11、y1（n）=x（2n），y2（n）=x（n/2），问：? 假如y1为周期函数，那么x是否为周期函数？? 假如x为周期函数，那么y1是否为周期函数？? 假如y2为周期函数，那么x是否为周期函数？? 假如x为周期函数，那么y2是否为周期函数？? 12、假如模拟信号的带宽为5kHz，要用8k的采样率，怎么办。? 13、某个程序在一个嵌入式系统（200M的CPU，50M的SDRAM）中已经最优化了，换到另一个系统（300M的CPU，50M的SDRAM）中运行，还须要优化吗？? 14、x4+a*x3+x2+c*x+d最少须要做几次乘法。? 15、三个float:a,b,c 问值：? （a+b）+c=（b+a）+c? （a+b）+c=（a+c）+b? 16、把一个链表反向填空。? 17、下面哪种排序法对12354最快？? A. quick sort? B. buble sort? C. merge sort? (,要求其它信息尽量按输入的依次排列时很重要.这也是它比 快速排序优势的地方.) 18、哪种结构平均来讲获得一个值最快？? A. binary tree? B. hash table? C. stack? 19、? #include <iostream> 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 =0x101; for(int i=7;i>=0;i-) printf(%d,*c(1<<i)?1:0); printf(n); printf(%d %d %dn,s.a,s.b,s.c); return 0; ? 0x101 = 1011 1011 x86 是 小端所以，s.a = 001，s.b = 11，s.c = 101 b和c最高位是1，都是负数。负数在计算机里用补码表示。补码 -> -1，等到反码 -> 然后得到原码。 11 - 1 = 10 -> 10 取反，得原码01，所以其数值为“-1”。 101 - 1 = 011 -> 011 取反，得原码101，所以其数值为“-4”。 统一用这种方法求补码，或求补码的真值！以前那种很简单错！ 求-15的补码 第一步：+15其次步：逐位取反（1变成0，0变成1），然后在末尾加1。 再举一个例子验证下：求-64的补码 +64逆： 二进制值-65的补码） 各位取反加1+65的补码） 20、挑bug，在linux下运行：? #include char? *reverse(char* str) int len=0, i=0;? char *pstr=str, *ptemp,*pd;? while(*+pstr)? len+;? pstr-;? /ptemp=(char*)malloc(len+1);? ptemp=(char*)malloc(len+1);? pd=ptemp;? while(len-)? *ptemp=*pstr; ptemp+;? pstr-;? i+;? ? *ptemp=*pstr; ptemp+;? *ptemp='0' return pd;? ? main()? ? char string40= Hello World!;? char *pstr=string;? printf(%s, pstr);? printf(%s, reverse(pstr);? ? 试验室笔试题? 1写出下列信号的奈亏斯特频率? （1）f（t）=1+cos（2000pait）+sin（4000pait）? （2）f（t）=sin（4000pait）/pait? （3）f（t）=（sin（4000pait）的平方）/pait? 频宽通常以每秒传送周期或赫兹 (Hz)来表示 2有两个线程? void producer()? ? while(1)? ? GeneratePacket();? PutPacketIntoBuffer();? Signal(customer);? ? ? void customer()? ? while(1)? ? WaitForSignal();? if(PacketInBuffer>10)? ? ReadAllPackets();? ProcessPackets();? ? ? ? （1）有没有其他方法可以提高程序的性能? （2）可不行以不运用信号之类的机制来实现上述的功能? 3优化下面的程序? （0）sum=0? （1）I=1? （2）T1=4*I? （3）T2=address(A)-4? （4）T3=T2T1? （5）T4=address(B)-4? （6）T5=4*I? （7）T6=T4T5? （8）T7=T3*T5? （9）sum=sum+T6? （10）I=I+1? （11）IF I<20 GOTO (2) 第26页 共26页第 26 页 共 26 页第 26 页 共 26 页第 26 页 共 26 页第 26 页 共 26 页第 26 页 共 26 页第 26 页 共 26 页第 26 页 共 26 页第 26 页 共 26 页第 26 页 共 26 页第 26 页 共 26 页