2015中科大复试真题
（题目不全，题号也不是对应）
离散（10题，一题4分）：
1.R是反自反的，R
,证明R是反对称的。

R⊆
R
2.<G,*>是群，且a∈G，如果对于每一个x∈G，有a * x = x * a,则由这样的元素a可以构成的一个集合S.证明.<S,*>是<G,*>的子群。

（书上原题）
3.证)
A
f
f⋃
⋃
A
=
B
(
)
)
(B
(
f
4.求一个式子的析取范式和合取范式
5.)
x
x
P
y
y
∀
∃是否是永真式，不是请举出反例
P
↔
∀
x∃
y
(
)(
)
(
,
y
(
(x
)
)(
)
,
6.证K5不是平面图，且删去一边后是平面图
7.证明二部图中的简单回路的边数是偶数
编译（5题）：
1.求0*(0|11|10(0|00)*01)*的极小DFA M
2.求S→aAC A→bAb|b 的所有LR(1)的同心集，并判断是不是LALR(1)文法
3.求一个翻译方案的自下而上的属性栈代码，求出a的嵌套深度，式子记不清了，没做出来
4.类型声明：a[5]:Int，b[10][8]:Bool
求它的语法制导定义，输出类型的长度。

如a：20（字节），b：80
5.记不清了，是一个C的程序，有两个函数，一共六问，包括报错原因和类型声明和错误修改等等。

很综合的一题，比较难，就写了几问还不一定对。

机试（4题）：
1.一个字符数组直接在程序中定义{a,b,c,d,e,f,g,h,i,j}，求出所有5个字符的组合序列，如果字母组合一样，顺序不同，只用输出一次。

结果输出到output_1.txt 中。

如：
第一种结果：a,b,c,d,e
第二种结果：a,b,c,d,f
......
2.一个小学数学问题，在0-50之间随机产生2个数，随机产生运算‘+’或‘-’，
从屏幕输入这个运算的结果，两次机会，第一次答对得10分，第二次5分，做10道，最后结果输出到屏幕。

3.从文件input_3.txt输入一个树，建树并输出层数为奇数的节点到output_3.txt 中。

输入：
A B C
B D
C E F H
D G
输出：
第一层：A
第三层：D,E,F,H
......
4.从文件input_4.txt中输入一个图，要求输出从1经过k到n的最短路径，可以有环，输出到output_4.txt中。

输入：
n=5
k=3
1 2 10 5 30
2 3 20
3 4 60 5 10
4 5 20
5
60
20
10
20
2 5
30
10
B
A
C
D E F H G
1
3 4
输出：1 2 3 5。