搜索
整理版2010中科大计算机复试内容笔试：离散8道大题，1小时。难度不是很大，但是时间很紧。第一题：是一个等价命题的判断，不难。第二题：所有羊都是吃草的，所有死羊都是不吃草的，所以死羊不是羊。能得出这个结论吗，证明之！第三题：‘+’，‘-’，|x-y|，Min在实数集内是不是可交换的，可结合的，是否有逆元，是否有幺元第四题：证明N={0，1，2，3，4}，N对+mod5是群，N-{0}对*mod5是群第六题：R和S都是A上的自反，对称，传递关系，求R交S的自反，对称，传递闭包是什么第七题：给一个5个节点的图，画出方向矩阵，然后问从A到B长度为4的路径的条数第八题：一个连通图所有顶点的度为偶数，证明删除一个顶点后，连通分量数目小于等于deg(v),v是顶点编译原理也是1小时第一题：写出生成由a,b组成，且不含2个连续的a的字符串的正规式，并画出最简的DFA第二题：简述SLR，LR，LALR所描述的语言集合的关系第三题：给了2个函数f(),g()，f()中调用了g(),画出程序运行时的活动记录站的结构，以及控制链，假设返回值用寄存器存储第四题：structstu{intn;longm}val;main(){structstu{intn;longm;}val;f(val);}为什么f(val)会提示类型不匹配第五题：题目记不清了，就是3个指针指来指去的，然后问你最后结果多少2011中科大计算机复试内容离散数学：（与编译一起两个小时）比较简单，好好看书一定没问题。图那一章只考书上的简单定理证明。11年考的是证明度数等于顶点数的两倍！有一个群的证明题，很简单，有两个命题的证明，有两个谓词命题的判断（求真值）然后举反例或证明。还有一个是求最小生成树（数据结构学过的）。1、找出一个正规式，它所表示的语言就是右边的DFA所接受的语言。并请依据教材上提供的方法确认该DFA是最简的DFA。2、下面是类型表达式的语法：type-integer|boolean|array[num]oftype|recordfield_listend|typefield_list-id:type|id:type;field_list若规定：在记录类型中不能出现数组类型（包括不能出现数组的指针类型）。请重新设计一个文法，把该约束体现在文法中，即它和上述文法的区别就是所定义的语言满足这个约束。3、有人认为，下面C程序中结构体类型record的定义方式可用来动态生成其中a数组的大小不一样的结构体，以适应某些编程场合的需要。你认为这样的程序能够通过C编译器的类型检查吗？请说明理由。#includemalloc.htypedefstruct{doubler;intn;floata[];}record;main(){record*p;p=malloc(sizeof(record)+sizeof(float)*5);p-n=5;p-a[4]=100.0;…}4、下面是一个C语言程序：main(){longi;longa[0][4];longj;i=4;j=8;printf(“%d,%d\n”,sizeof(a),a[0][0]);}虽然出现longa[0][4]这样的声明，在X86/Linux机器上该程序还是能通过编译并生成目标代码。请回答下面两个问题：（1）sizeof(a)的值是多少，请说明理由。（2）a[0][0]的值是多少，请说明理由2012中科大计算机复试内容离散第一题是逻辑运算，很简单，估计随便看下书都会。第二题是判断命题等价，这种题还是用真值表法最把稳。第三题也挺简单的。求R1R2，就令R1={i,j|j=i||j=i/2},R2={j,k|jk}。于是R1R2={i,k|(j=i||j=i/2）与(jk)}={i,k|2ik}同理也可以求出R2R1；只有第二问，关系矩阵和关系图画出来就很容易判断是否自反之类的特性。第四题，a,b属于H，则a*(b的逆)属于H（1）因为H非空，所有不妨设其中的任意元素a,则a*（a的逆）属于H，推出e属于H。有么元。（2）因为e,b属于H，所以e*(b的逆)属于H，推出b的逆属于H，有逆。（3）因为a，b属于H，由于（2），b的逆属于H，然后由题设知道a*（b的逆的逆）属于H，推出a*b属于H。封闭。又H,*非空，所以H,*是G,*的子群。第五题，证明大体思路如下，因为每个节点度数为偶数，这样去掉v之后，就有d(v)个节点是奇数度。但是我们知道任何连通图都是偶数个度。所以对于每个连通分量至少有2个这样奇数度的节点。所以连通分量个数=1/2d(v)。第六题，w（g-v）=2明显错误，一个例子就是奔驰的标的那个图形，去掉中间的点，连通分量为4.w（g-e）=2为真。具体证明分两种情况。如果e所在的割集的边个数大于等于2，则去掉e之后仍为连通图，第二种情况，e是桥，这样去掉e之后，连通分量为2，证毕。编译原理书是有点难度，但是很多题目都是编译原理配套习题上面的，或者是根据上面改编，所以只要认真看看配套习题，估计就能轻松应付编译原理的题目第一题就是不出现bb的所有字符串，包括空。这样理解自动机就很好画了。第二题也很简单，首先A-aAa|a有左递归，导致first(aAa)交first(a)不为空，所以不是LL（1）。第三题我用了继承属性。好像用综合属性很难表示。但是继承属性超纲，这里就不说了。第四题，由于b是指向c的指针，a是指向c的指针的指针。而f（c,b,a）只有c是传值，b和a都是传地址。所以**ppz+=1;*py+=2;之后，a的值为8.然而c传的是值，所以运行f时，x是临时变量，这样x*=3后x是15。x+*py+**ppz;就是返回15+8+8=31.第五题很简单。一个错误是他们的参数个数不一致，另外一个是因为c对struct是使用名字匹配，而程序中仅仅是结构匹配。第六题，&i和&k是pointer（int）和pointer（char）型。&i-&k是int型。c语言规定对于同一类型的数据的指针的相减结构为他们地址之间这种结构的数据个数。2013中科大计算机复试内容离散部分：1.求A和B的关系（1）A-B=B-A(2)A∪B=A2.给了一个表，后面两小题（1）证明其中一子集合是群(2)证明该集合不是群3.三个小题，证明是否永真式，永假式，非永真非永假式4.判断(1)AVC=BVC求A=B?（2）A/\C=B/\C求A=B?5.一个无向树，已知度为3和2的节点个数，求度为1节点的个数6.12年第五题原题，貌似前几年也考过编译原理：1DFA构造：10（（（10）*|111）*|0）*0（差不多是这样）2验证一个文法是不是LL（1）文法（不是），重写一个同义的LL(1)文法S-bAa|a;A-Sd;A-ε3第三题语法制导翻译类似于习题集（05版）第四章4.64.164.174#includemalloc.htypedefstruct{doublea;intn;inta[];}record;main(){record*p;p=malloc(sizeof(record)+sizeof(int)*5);p-n=5;p-a[4]=100;…}（1）问为什么能通过编译，写出t，p的类型表达式（2）double大小为8int大小为4为t的大小是多少（3）t.a[]类型表达式（4）程序中出现p-a[10]编译时会不会报错5从习题集（05版）上第七章7.5改编而来考察C程序编译后产生的汇编代码要求解释汇编代码中L2~L6各段的含义6（书上原题）char*a[]=123456789;char*p=123456789;a[2]='3';p[2]='3'报错，然后说明原因，写p的类型表达式2014中科大计算机复试内容离散：9道题1.判断永真式、永假式2.证明一个命题(…（A→A）→A)....→A大概就是这么个题目3.证明A∪(B∩C)=(A∪B)∩(A∪C)4.让你判断谓词推理是否正确？为什么？EX(P(X))EX(Q(X))...EX(P(X)Q(X))5.给你4个关系，判断性质：自反，反自反，对称，反对称，传递。题目大概是：整数集合I上，|x+y|=10;xy0;|x-y|=4；整除6.证明在群G中，若|G|=n，则群中元素a的最高阶数不超过n，而且阶数必为n的因子。（书上定理吧）7.用kruskal算法，计算一个图的最小生成树，图已给出8一个图用临接矩阵表示，怎么判断两点之间是否联通，并求最短距离图，是否有连通分量9.证明二部图的一个定理：m=1/4*n*n(书上原定理吧)编译：6道题1.写一个DFA，包含00子串的（0|1）*字符串集合2.文法G是二义文法？是LL（1）文法？大概是下面的正规定义S→(S)S∣εS-SS|(S)3.编写翻译器的栈操作代码4.intn;f(g){staticm;n=m;if(m==0)return1;else{n=n-1;;returnm*f();}}main（）{n=4;printf(%d的阶乘是%d,n,f(f));}输出：0的阶乘是0问题：a．为什么两处对f（）的调用能通过编译...b．为什么是输出：0的阶乘是0，而不是4的阶乘245.inti,j,n;charc;n=&i-&j;c=&i-&j;大概就是这么个程序...就是两个指针相减，问你指针相减的结果，并说明为什么。6.intf()….main(){printf(%d,fx());}在编译运行时出现两个问题：****.cwarning:ambiguousreferenceprintf****.oerror:undeclearedreferencefx问第一个警告是编译错误还是链接错误？下一个是编译错误还是链接错误？由于没有把所有的知识点完全覆盖，离散就那两个书上定理没搞定，编译那个栈代码没写，其它的基本都会儿写，应该也基本写对了~2015中科大计算机复试内容一．离散1.判断集合关系是否正确，正确证明。错误举反例(1)ABB,ACCBCA(大概)(2)AB,DCACBD2.求一个命题公式（记不住）的合取范式，析取范式。4.甲乙丙丁参加比赛，A,B,C三人对他们的名次做了预测，每人有2个断言，且其中只有一个正确。求4人的比赛名次。5.f(X)Y.AX,BX,f:ABYf:AYBY(大概)6.G,*是群，且aG，如果对于每一个xG，有a*x=x*a,则由这样的元素a可以构成的一个集合S.证明.S,*是G,*的子群。7.证明5k不是平面图。任去除一条边后是平面图8.证明二分图的充要条件图中所有回路的长度为偶数二，编译1.求DFA.（正则式记不住）2.S-aAcA-bAb|b求LR(1)的同心项目集的规范族，判断是否为LALR(1)文法。3.写文法的自下而上栈操作，输出每个a的嵌套深度。可以修改文法，但要保持左递归。用的记号可能不一要，效果一样S-(L)|aL-L,S|S4.记得不是很清楚。doublef1(g)doubleg(double*);{g(g);}doublef2(doubleg(double*)){g(g);}main(){f1|f1(f2);printf(“balabal..\n”);f2&&f1(f2);}程序编译有2警告，1提醒。1..是参数f2中g(g)参数不兼容，2.warning:incompatibleimplicitdeclarationofbuilt-infunction‘printf’[enabledbydefault]3.(1)写出f2的类型(2)支持警告出现的原因和出现在编译的哪个阶段(3)修改程序，消除警告。和提醒(4)程序运行时会Segmentationfault，指明原因。