中科院化工治金研究所微生物学99/00试题，由于无法复制，只给出链接地址！http://ebioe.com/ky/datum/shiti/200412/1358.html

http://ebioe.com/ky/datum/shiti/200412/1358_2.html

AD:溴气体气体检测仪、探测器、报警器

博士家园论坛也有中科院的一些试题，给出链接

http://www.bossh.net/forums/index.php?showtopic=518

st5432考研试题笔记也有免费下载，给出链接

http://kaoyanshop.3322.org/st/search.php?keyword=%D6%D0%BF%C6%D4%BA&type=all&ordertype=date&action=result

[此贴子已经被作者于2005-2-16 19:04:53编辑过]

中国科学院软件所
一九九六年招收硕士学位研究生入学考试试题
试题名称：离散数学
数理逻辑部分
一.(10分).
试求 的主合取范式和主析取范式。
二.        证明:
1).(5分).
2).(7分).
三.(10分).
        办案人员得到下列线索:
        1).不是张某就是王某杀了厂长,而且两人不会合谋.
        2).张某不可能在半夜作案.
        3).王某说半夜厂长家灯亮着.
        4).王某若没作案,则他不会说谎.
        5).若厂长家半夜灯亮着,则案发生在半夜.
        请你根据线索找出作案者,形式化证明你的结论.
代数结构部分
四.(10分）.
        设 , , .记S上的恒同映射为 .
证明:如果 , , ,则f, g ,h均为双射,并求
出 .
五.        G是{1,2,3}上的置换群，|G|=6.
1). (4分).已知 ，试G列出的全部元素。
2). (5分).令 ，在F上定义关系，对任意 , 存在 ，使对任何 ，均有 ，证明R是F上的等价关系。
3). (3分).求R所确定的等价类。
六.        设 是集合A上的二元运算，对任意 ，满足.
1). ，
2). ，
3). ，
现定义A上关系 ， 证明：
1). (5分). 是A上的序关系
2). (7分).对任何 ， 均有一个最小上界和一个最大下界。

图论部分
七.        .(10分).设T是树，且 ，则T中至少k有个结点的度数（或次数）为1。
八.        (2分).设G是无向完全图，若对G的每条边指定一个方向，所得到的图称为竞赛图，证明：无有向回路（或有向圈）的竞赛图D:<V(D),E(D)>中，对任意 , 。
九.        (12分).证明：设 是简单无向连通图，且 ，则G中存在一条不小于 的通路（或轨道）。

中国科学院自动化研究所94考研题

一、基本概念(30分)
1·下面四个概念仅有一个是更准确的，试在正确的地方画"√"号。(5分)
a)·算法是解决问题的过程;
b)算法是以数学方式表示的问题的求解方法;
c）算法是设计、编制和调试程序的过程;
d) 算法是解决问题方法的精确描述。
2.计算三角函数SinX(l5分)
     
若按精确度预先给定 n后，其流程图见下图。请在流程图中A，B处填上正确的句子或表达式。

3．下面是数据结构名词的英文缩写，它表示什么意思（4分）
        a  FIFO（       ）              b  LIFO（        ）。
4．下面是某个数据类型的语法图，指出是何种数据类型，采用什么表示法。（6分）
   
   表示法（           ）；  数据类型（             ）。
二．数据结构（30分）
1．        阅读下列程序说明和程序，填充程序中的   
[程序说明]
a. 假设在程序中定义：
typedef   struct   node  *link;
struct     node   {datatype       data;
                   link          next;};
其中： link为指向node类型的指针类型；   
        datatype为数据域的类型，它可以是任何类型；
data为数据域，存放了该结点的数据；
next为指针域，它指向该结点的后继结点。
一个link类型的变量p及其指向的结点可以表示如下：
        p               结  点
      .               data    next
*p表示有指针p所指向的结点；
(*p).data或p      data表示由p所指向的结点的数据域；
(*p).next或p      next表示. P所指向结点的后继结点。
用∧或NULL表示链表中最后一个结点的指针域为空。
b.函数reverse 完成将链表逆转的操作，它将链表；
   p     a1  •         a2  •      ••••• • •        an  ∧
变为： p    an  •      an-1  •     • • •      a2  •      a1 ∧   
[程序]
rexerse  (p)
link  *p;
{link  ptr  ,p1,p2;
      ptr=*p
          1
      while (     2      )
     {p2=ptr;
       ptr=ptr       next;
           3
       p1=p2; }
         4
   }
2．        阅读下列程序说明和程序，填充程序中的           
[程序说明]本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。
本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为：
（1）        把根结点放入堆栈。
（2）        当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。
（3）        重复（2）直到堆栈为空时为止。


[程序]
typedef  struct  node  *tree;
struct  node
{  int  data;
   tree  lchild,  rchild;}
exchange(t)
tree  t;
{tree  r,p;
tree  stack [500];
int  tp=0;
   1
  while (  tp>=0)
{    2
if(      3      )
{r=p      lchild;
  p      lchild=p      rchild;
  t     rchild=r
         stack[        4       ]=p         lchild;
         stack[++tp]=p       rchild;
三、算法分析与设计（20分，每小题10分）
    1．说明下面函数的功能。
in fac(int  n)
  {if (!n)return(1);
   else
         return(n*fac(n-1));
  }
3．        有国籍不同的六个人，他们的国籍分别是美国、德国、英国、法国、苏联和意大利。他们的名字分别叫A、B、C、D、E和F。当然这里列出的名字顺序不一定与上面的国籍顺序相同。现已知：
（1）        A和美国的人是医生；
（2）        E和苏联的人是教师；
（3）        C和德国的人是技师；
（4）        B和F曾经当过兵，而德国的人从未当过兵；
（5）        法国籍的人比A年龄大，意大利籍的人比C年龄大；
（6）        B同美国籍的人下周要到英国去旅行，而C同法国籍的人下周要到瑞士去度假
试问：A、B、C、D、E、F各是哪国人？
试设计一个数据结构，并按次数据结构给出分析和解决问题的方法，并求出结果。不要求写程序和算法过程。
提示：A和美国籍的人是医生，那么说明A不是美国人。
四、程序设计（20分，每小题10分）
要求：1。注明使用的语言；2。加上程序说明；3。写出源程序。
1．        求所有满足如下条件的三为数：它除以11得的商等于它各位数字的平方和。
例如550，除以11商为50，          使用穷尽三位数，寻找满足条件的数。
2．        将1——9这九个数填入下图中的九个方格内，使每行、每列，两条对角线上三个数字之和都相等。

中科院计算机技术研究所2003年硕士生入学试题 编译原理与操作系统
第一部分 编译（40’）
一、（1/01）*0*说明是什么语言 画出DFA（10’）
二、S→过程调用语句/数组的赋值语句（10’）
过程调用语句为：id(id,id,…,id)
赋值语句: id(id,…,id):=id(id,…,id)
(a)写一个LR（1）方法（产生式不大于6个）
(b)若在LR分析同时完成语义分析，中间代码生成，基于你的文法有什么困难？
三、E→E*E/+E/-E/unsigned-integer (10’)
为上面表达式产生栈机器代码，代码执行后，表达式值留在栈上，自己设计所需栈机器指令，并写清指令含义。
四、C语言中，a表示数组首址，而&a也表示数组首址，然而使用时有时并不相同，请根据下面写出a与&a类型表达式 （10’）
(1)文件1:
tgpedef int A[10][20]
A a;
A * func ( )
{
return(a);
}
在linux上用gcc编译
报告:第6行warning: return from
incompatible pointer type
(2)typedef int A[10][20]
A a;
A *func( )
{
return(&a);
}
无类型方面错误
(3)typedef int A[10][20]
typedef int B[20]
A a;
B *func( )
{
return(a);
}
无类型方面错误
(4) typedef int A[10][20]
A a;
func( )
{
Printf(“%d,%d,%d/n,a,a+1,&a+1);
}
main( )
{
func( );
}
结果：134518112，134518192，134518912
第二部分 操作系统（40’）
五. 1、操作系统内核有强内核和微内核，unix是前者，windowsNT是后者，简介微内核比强内核的优点。（4’）
2、若只有进程控制，其独立性表现在？引入线程后，独立性有何改变?（4’）
3、请求调页存储系统确定页面大小的标准（4’）
六、
1.死锁的证明
在m个同类资源，n个进程共享它，每次进程只能获得或释放至多一个资源，问会不会发生死锁，若：设每个进程所需资源数为ri 1<=ri<=m (6’)
2、windows NT页面大小为4KB，采用两级页表机构，为提高设了32K或64K的Cache，试叙述windows NT地址变换过程的页面调度策略。（10’）
3、假设有一种新磁盘技术，两者即磁盘与内存访问时间在同一数量级上，作下面哪些修改以采用更快的磁盘访问速度。 （12’）
（1） 进程调度（4’） （2）内存管理（4’） （3）磁盘驱动程序（4’）
第三部分 数据结构（70分）
七. 选择（5×2’）
八.简答（10×2’）
说明:七和八题都很简单,多是考察有关树方面的小问题,第八题和填空题差不多,非常简单,故没抄下来.
九、（5×5’分）
1、广义表，设H表示Get head ，T表示Get Tail 从下表中分解出原子a,请给出H、T操作序列。
L=((( )),(b,c),((b,(c,a)),(c,d)),((e),d))
2、串序列T=“abcabcabca”模式串w=“abca”用kmp算法，求next[1:10]
3、一无向图，边非负权值，问用Dijkstra最短路径算法能否给出一棵生成树？该树是否一定是最小生成树？说明理由。
4、判断向一无环图增加一边是否会使图中产生环的问题时，应选用什么样的数据结构？（一名话简单回答）在使用这种数据结构时该判断所需时间。
5、设向一棵空平衡二叉树（AVL）中插入关键字序列为[45，24，12，62，70，50，10，38]画出每插入一关键字后该树状态示意图，若在此基础上删除关键字62，给出删除后的状态图。
十、（15分）有n张扑克牌，存在由记录组成的数组A（1：n）中，每个记录有三个域，其中，N0为每张扑克初始序号，一旦给定不改变,Cor表示每张扑克花色，梅花<方块<红桃<黑桃 ，Val表子扑克数值1..13，要将这n张由小→大排序，每张只能看一次，低花色比高花色的值小，花色的大小均相同的保持原相对的次序，请写算法，并描述所用附加存储空间结构。

中国科学院计算所
一九九四年招收硕士学位研究生入学考试试题
试题名称：离散数学
代数结构部分（33分）
一．（10分）判断是非（对的打√，错的打×）
1．        对于任意集合A，B，C，若 且 ，则 。
2．        若 和 是集合A上的等价关系，则 也是集合A上的等价关系。
3．        阶数 的群都是交换群。
4．        f是群 到群 的群同态映射，若 是交换群，则 也是交换群。
5．        格 中的运算 的最核心的性质是交换律，结合律和吸收律。
二.（10分）
设R是集合A上的关系，令 使 且 }，证明：如果R是等价关系，则S也是等价关系。
三．（10分）
设 是一个交换群，H是G中的所有有限阶元素构成的集合.证明：
                        1） 是 的正规子群。
                        2）在商群 中，除单位元H外，所有元素的阶都是无限的。

图论部分（34分）
四．（12分）
简单图G由图H和两个孤立结点组成，图H不含孤立结点， 为平面图，证明H为连通图。
五．（12分）
给定图 ，设 ， ，其中 是关联于结点 与 的边，称交替序列 为联结 到 的长为n的路，求完全图 中任意两点间长为k的路的数目。
六．（10分）
若有向图的所有结点的入度都大于1，则此有向图至少含有两个不同的有向圈。
数理逻辑部分（33分）
七．（10分）判断下列各式是否为永真式
                1．
                2．
                3．
                4．
                5．
八．（10分）
        设命题函数：         ：x 属于实数集合A;
              ：x 属于实数集合B;
      ：x>y
试将命题“并非A中的数都不比B中的数大”按下列要求分别用谓词公式表示：
1．只出现全称量词。
2．只出现存在量词。
3．量词全部放在左边。
九．（13分）
        证明：
， ，

中国科学院计算所
一九九三年招收硕士学位研究生入学考试试题
试题名称：离散数学
数理逻辑部分(共34分)
一.(12分)下列推理是否成立?证明你的结论.
a)        前提:
结论:
b)        前提:
结论:
二.(10分)
         是否最小联结词组?即能否仅用联结词组 和 表示所有的命题公式?证明你的结论.
三.(12分)
         三个前提为:
                 
                 
                 
         两个结论为:
                 
                 
写出推导过程.

代数结构部分(共34分)
一.(10分)
         和 是集合S中的等价关系, 和 是它们产生的划分.证明:
当且仅当 的每一个划分都包含在 的每一个分块中.
五.(10分)
        设 是n阶有限群,e为单位元, 是G 的任意几个元素,不一定两两不同.试证:存在整数p和q,  ,使得 .
六.(14分)
        设 是环,其乘法单位元记为1,加法单位元记为0,对于任意 ,定义 , .求证: 也是环,并且与环 同构

图论部分(共32分)
七.(11分)
        设连通单图G有n个结点(或称作顶点),  ,m条边 ,定义矩阵 , ,分别如下:
        1)  
        2)  
        3)  
证明:
        (其中 为结点 的次数(或称为度数), 为矩阵B 的转置).
八.(11分)
        设G是连通单图,但不是完全图,则存在三个结点u,v,w,使uv,vw E(G),但uw E(G).


九(10分)
        连通图G 的树图是一个图,它的结点 为G的生成树, 与 相连的充要条件是它们恰好有v-2条公共边(其中v为G的结点数).证明:连通图的树图是连通图.

中国科学院计算所
一九九二年招收硕士学位研究生入学考试试题
试题名称：离散数学
（供计算所用）
代数结构部分（共32分）
一．        判断对错（18分）
1．A，B是集合，命题 和 不可能同时成立。
2．若R 是集合A上的传递关系，则 也是集合A 上的传递关系。
3．四阶群中必有四阶元。
4．非循环群的每一个子群必是非循环群。
5．f 是G1 到G2的群同态映射，若G1是交换群，则G2 也是交换群。
6．分配格必是模格。
二．        （14分）
是D={1,2,……n}上所有置换（双射）组成的集合。 对置换乘法（函数复合）运算构成群，G是 的子群。
1.        在 上定义关系R, , 存在
证明：R是 上的等价关系。
2.        取n=3，列出 的所有元素，找出 的一个二元阶子群G，求上述等价关系所确定的 一个划分。

图论部分（共33分）
一.        (8分)
下面列出了一些关于简单图的结论,它们的哪些组合可以作为树的定义,写出所有可能,但不允许在组合中有多余的结论:
a.        无圈.
b.        连通.
c.        边数=结点数-1;
d.        每队结点间有且仅有一条通路(轨);
e.        连通图的每一条边均为割边;
f.          在原图中增加任一条边恰好得到一个圈;
二.        (15分)
1.        右图是否是平面图,为什么?
2.        如何从一连通图的关联距阵中判断一边是否割边?
3.        一个简单图的七个结点的次数分别为6,6,5,4,3,3,1,问这样的图是否存在?若存在,请画出相应的图 ,否则,说明理由.
三.        (10分)
  证明:连通图的任意两条最长的通路(轨)有公共结点.

数理逻辑部分(共29分)
一.        判断对错(9分)
1.         为重言式.
2.        联结词 的定义是 .{ }是最小的联结词组.
3.         的前束范式为 .
二.        (10分)
利用谓词E(x, y)(表示x与y 相同”)来构造命题函数(谓词演算的合式公式),使得该命题函数具有性质:”在个体域 D中可满足:当且仅当D只含有两个个体.”论述你构造的正确性.
三.        (10分)
1.        用真值表证明:  为重言式
2.        用推理规则证明: .
(不准使用规则 ).

中科院计算所1999 一. 选择题. 1.____的遍历仍需要栈的支持. (1) 前续线索树(2)中序线索树 (3)后序线索树 2.若度为m的哈夫曼树中，其叶结点个数为n,则非叶结点的个数为＿＿＿． （１）n-1 (2)|_n/m_|-1 (3)上取整 (n-1)/(m-1)4)[上取整n/(m-1)]-1 (5)[上取整(n+1)/(m+1 )]-1 3.最优二叉树（哈夫曼树），最优查找树均为平均查找路径长度　　wihi最小的树,其中对最优二叉树,n表示___,对最优查找树,n表示 ____;构造这两种树均为——。*（1）结点数（2）叶结点数 （3）非叶结点数 （4）度为2的结点数 （5）需要一张N个关键字的有序表 （6）需要对N个关键字进行动态插入（7）需要N个关键字的查找概率表（8）不需要任何前提。 4.对于前序遍历与中序遍历结果相同的二叉树为_____;对于前遍历和后序遍历 结果相同的二叉为_____. (1) 一般二叉树 (2) 只有根结点的二叉树 (3)根结点无左孩子的二叉树 (4)根结点无右孩子的二叉树 (5)所有结点只有左子数的二叉树 (6)所有结点只有右子树的二叉树. 5.M路B+树是一棵_____,其结点中关键字最多为___个,最少为___个.. (1) M路平衡查找树 (2)M路平衡索引树 (3) M路TRIE 树 (4)M路键树(5)M-1 (6)M (7)M+1 (8)上取整(M/2)-1 (9) 上取整(M/2) (10) 上取整(M/2)+1 二. 填空题 1. 对于给定的N个元素,可以构造出的逻辑结构有___._____. _____.. ____四种. 2. 具有N个关键字的B-树的查找路径长度不会大于________., 3. 克鲁司卡尔算法的时间复杂度为_____,它对_____图较为适合. 4. 深度为可（设根的层数为一）的完全二叉树至少有______个结点,至多有_____个结点,K和结点数N之间的关系是_____. 三. 问答题 1.一棵非空的有向数中恰有一个顶点入度为0, 其他顶点入度为一, 但一个恰有一个顶点入度为0, 其他顶点入度为一的有向图却不一定是一棵有向数,请举例说明. 2.若有N个元素已构成一个小根堆, 那么如果增加一个元素为Kn+1,请用文字简要说明你如何在LG(N)/LG(2) 的时间内将其重新调整为一个堆? 四. 指出程序输出 void g(int**); main() { int line[100],i; int *p=line; for (i=0; i<100;i++) { *p=i; g(&p); } for(i=0; i<100;i+1) printf(“%d/n”,line); } void g(int**p) { (**p)++; (**p)++; } 五 .编程题 1. 设一单向链表的 头指针为HEAD,链表的记录中包含着整数类型的KEY 域,试设计算法,将此链表的记录按照KEY递增的次序进行就地排序. 2. 给定一个整数叔数组b[0..n-1].,b中连续的相等元素构成的子序列称为平台.试设计算法,求出B中最长平台的长度.[ 3. 自由树(即无环连通图)T=(V,E)的直径是树中所有点对间最短路径长度的最大值,即T的 直径定义为MAX D(u,v) ,这里D(u,v)表示顶点U到顶点V的最短 u,v∈V 路径长度(路径长度为路径中所包含的边数). 写一算法求T的直径,并分析算法的时间复杂度(时间复杂度越小得分越高).

2005年中科院广州地化所专业试题

301地球科学基础

一、区分下列术语

1、矿物与宝石

2、矿石与岩石

3、地壳与岩石圈

4、节理与断裂

5、正断层与逆断层

二、尽可能详细说明地球有哪几个圈层

三、全球可分为哪六大板块？板块边界有几种类型？请指出这几种边界的地貌与活动特征

四、花岗岩、花岗片麻岩、长石石英砂岩在何种地质作用环境中可以转换？

五、岩浆岩、沉积岩、变质岩有哪些主要区别？

六、列举岩石定年的方法（3种以上）并说明基本原理。

481自然地理学

一、名词解释

1、富铝化 2、水位 3、潮汐 4、气压 5、太阳辐射

二、选择题

1、平流层主要出现在（ ）的海拨高度

A、>20km B、>80km C、<15km D<5km

2、酸雨的原因是

A、人为因素 B、自然因素 C、两者兼有 D、其它因素

3、南岭位于中国气候带的

A、热带 B、亚热带 C、寒带 D、温带

4、砖红壤主要发要在

A、热带 B、亚热带 C、寒带 D、温带

5、大陆冰盖主要发育在

A、山地 B、极地 C、赤道 D、内陆

三、论述题

1、我国主要气候带划分及其特点

2、主要洋流和水团的类型

3、农业生态系统的特征