《中科大计算机复试笔试部分09-15》由会员分享，可在线阅读，更多相关《中科大计算机复试笔试部分09-15（7页珍藏版）》请在金锄头文库上搜索。
1、整理版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 的路径的条数
2、第八题：一个连通图所有顶点的度为偶数，证明删除一个顶点后，连通分量数目小于等于deg(v), v是顶点编译原理也是 1 小时第一题：写出生成由a,b 组成，且不含 2 个连续的a 的字符串的正规式， 并画出最简的DFA 第二题：简述SLR ，LR，LALR 所描述的语言集合的关系第三题：给了2 个函数 f(),g()，f() 中调用了g(), 画出程序运行时的活动记录站的结构，以及控制链，假设返回值用寄存器存储第四题： struct stu int n; long mval; main() struct stuint n;long m;val; f(val); 为什么 f(val) 会提示类型
3、不匹配第五题：题目记不清了，就是3 个指针指来指去的，然后问你最后结果多少2011中科大计算机复试内容离散数学：（与编译一起两个小时）比较简单，好好看书一定没问题。图那一章只考书上的简单定理证明。11 年考的是证明度数等于顶点数的两倍！有一个群的证明题，很简单，有两个命题的证明，有两个谓词命题的判断（求真值）然后举反例或证明。还有一个是求最小生成树（数据结构学过的）。1、找出一个正规式，它所表示的语言就是右边的DFA 所接受的语言。并请依据教材上提供的方法确认该 DFA 是最简的DFA 。2、下面是类型表达式的语法：type -integer | boolean | arraynum of t
4、ype | recordfield_listend |type field_list-id : type | id : type ; field_list 若规定：在记录类型中不能出现数组类型（包括不能出现数组的指针类型）。请重新设计一个文法，把该约束体现在文法中，即它和上述文法的区别就是所定义的语言满足这个约束。3 、有人认为， 下面 C 程序中结构体类型record的定义方式可用来动态生成其中a 数组的大小不一样的结构体，以适应某些编程场合的需要。你认为这样的程序能够通过C 编译器的类型检查吗？请说明理由。#include typedef struct double r; int n; f
5、loat a; record; main() record * p; p = malloc(sizeof(record) + sizeof(float) * 5); p-n = 5; p-a4 = 100.0; , 4、下面是一个C 语言程序：main() long i; long a04; long j; i = 4; j = 8; printf(“%d, %dn”, sizeof(a), a00); 虽然出现long a04这样的声明， 在 X86/Linux机器上该程序还是能通过编译并生成目标代码。请回答下面两个问题：（1）sizeof(a)的值是多少，请说明理由。（2）a00的值是多少
6、，请说明理由2012中科大计算机复试内容离散第一题是逻辑运算，很简单，估计随便看下书都会。第二题是判断命题等价，这种题还是用真值表法最把稳。第三题也挺简单的。求R1R2 ，就令 R1=|j=i|j=i/2,R2=|j|(j=i|j=i/2）与 (j|2i非空，所以是的子群。第五题，证明大体思路如下，因为每个节点度数为偶数，这样去掉v 之后，就有d(v) 个节点是奇数度。但是我们知道任何连通图都是偶数个度。所以对于每个连通分量至少有2 个这样奇数度的节点。所以连通分量个数aAa|a有左递归，导致first(aAa)交 first(a)不为空，所以不是LL（1）。第三题我用了继承属性。好像用综合属
7、性很难表示。但是继承属性超纲，这里就不说了。第四题， 由于 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是使用名字匹配，而程序中仅仅是结构匹配。第六题， A-Sd ;A- 3 第三题语法制导翻译类似于习题集（05 版）第四
8、章4.6 4.16 4.17 4 #include typedef struct double a; int n; int a; record; main() record * p; p = malloc(sizeof(record) + sizeof(int) * 5); p-n = 5; p-a4 = 100; , （1） 问为什么能通过编译，写出t，p 的类型表达式（2） double 大小为 8 int 大小为 4 为 t 的大小是多少（3） t.a类型表达式（4）程序中出现p-a10 编译时会不会报错5 从习题集（ 05 版）上第七章7.5 改编而来考察 C 程序编译后产生的汇编代码
9、要求解释汇编代码中L2L6 各段的含义6（书上原题）char *a = “123456789“ ; char *p = “123456789“;a2 = 3;p2 = 3 报错，然后说明原因，写p 的类型表达式2014中科大计算机复试内容离散： 9 道题1.判断永真式、永假式2.证明一个命题(, （ A A）A) A 大概就是这么个题目3.证明A(BC) = (A B)(A C) 4.让你判断谓词推理是否正确？为什么？EX(P(X) EX(Q(X) . EX(P(X)Q(X) 5.给你 4 个关系，判断性质：自反，反自反，对称，反对称，传递。 题目大概是：整数集合I 上， |x+y|=10;x
10、y0;|x-y|=4 ；整除6.证明在群G 中， 若|G| = n，则群中元素a的最高阶数不超过n，而且阶数必为n 的因子。（书上定理吧）7.用 kruskal 算法，计算一个图的最小生成树，图已给出8 一个图用临接矩阵表示，怎么判断两点之间是否联通，并求最短距离图，是否有连通分量9.证明二部图的一个定理：mSS|(S) 3.编写翻译器的栈操作代码4. int n; f(g) static m; n=m; if(m=0) return 1; else n= n-1; return m*f(); main（） n=4; printf(“%d 的阶乘是 %d“,n , f(f); 输出： 0 的阶
11、乘是0 问题：a为什么两处对f（）的调用能通过编译. b为什么是输出：0 的阶乘是0，而不是4 的阶乘 24 5. int i,j,n; char c; n= c = 大概就是这么个程序. 就是两个指针相减，问你指针相减的结果，并说明为什么。6. int f() ,. main() printf(“%d“,fx(); 在编译运行时出现两个问题：*.c warning:ambiguous reference printf *.o error:undecleared reference fx 问第一个警告是编译错误还是链接错误？下一个是编译错误还是链接错误？由于没有把所有的知识点完全覆盖，离散就那
12、两个书上定理没搞定，编译那个栈代码没写，其它的基本都会儿写，应该也基本写对了 2015中科大计算机复试内容一离散1.判断集合关系是否正确，正确证明。错误举反例(1) AB B, AC C BC A(大概 ) (2) AB,D C AC B D 2.求一个命题公式（记不住）的合取范式，析取范式。4.甲乙丙丁参加比赛，A,B,C 三人对他们的名次做了预测，每人有2 个断言，且其中只有一个正确。求4 人的比赛名次。5. f (X) Y.A X, B X, f : ABY f : AY BY (大概 ) 6.是群，且aG，如果对于每一个xG，有 a * x = x * a, 则由这样的元素a 可以构成
13、的一个集合S.证明 . 是 的子群。7.证明 5 k 不是平面图。任去除一条边后是平面图8.证明二分图的充要条件图中所有回路的长度为偶数 二，编译1.求 DFA.（正则式记不住）2. S-aAc A-bAb|b 求 LR(1) 的同心项目集的规范族，判断是否为LALR(1) 文法。3.写文法的自下而上栈操作，输出每个a 的嵌套深度。可以修改文法，但要保持左递归。用的记号可能不一要，效果一样S-(L)| a L-L,S|S 4.记得不是很清楚。double f1(g) double g(double*); g(g); double f2(double g(double*) g(g); main() f1|f1(f2); printf( “balabaln”); f2 程序编译有2 警告， 1 提醒。1是参数 f2 中 g(g)参数不兼容，2.warning: incompatible implicit declaration of built-in function printf enabled by default 3. (1)写出 f2 的类型(2)支持警告出现的原因和出现在编译的哪个阶段(3)修改程序，消除警告。和提醒(4)程序运行时会Segmentation fault，指明原因。
