中科院计算所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) 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个进程共享它，每次进程只能获得或释放至多一个资源，问会不会
发生死锁，若：(1)、设每个进程所需资源数为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张由小→大排序，每张只能看一次，低花色比高花色的值小，花色的大小均相同的保持原相对的次序，请写算法，并描述所用附加存储空间结构。
中科院2000考研题
一、选择题（20分）
1．下述函数中渐近时间最小的是（）。
A) T1(n)=n+1000. B）T2(n)=n-1000
C）T3(n)= -1000D）T4(n)=2n-1000
2．下述编码中哪一个不是前缀码（）。
A）.（00，01，10，11）B）.（0，1，00，11）
C）.（0，10，110，111）D）.（1，01，000，001）
3．当各边上的权值（）时，BFS算法可用来解决单源最短路径问题
A）均相等B）均互不相等C）不一定相等
4，在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（）位置上。
A）n/2B）n/2-1 C）1 D）n/2+2
5．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）为宜。
A）直接插入B）直接选择C）堆D）快速排序E）基数排序
6．在一棵含有n个关键字的m阶B——树中进行查找，至多读盘（）次。
A）B）1+C）1+D）1+
7．下述文件中适合于磁带存储的是（）。
A）顺序文件B）索引文件C）散列文件D）多关键字文件
8．“typdef int(*F) (char , int)：表示F是一个（）。
A）函数B）指针C）指针类型D）函数指针类型
9．在快速排序中，要使最坏情况的空间复杂度为O()则要对快速排序作（）修改。
A）划分元素为三者取中B）采用表排序
C）先排最小集合D）先排大集合
10．设栈的输入序列是1，2，3，4，则（）不可能是其出栈序列：
A）1，2，4，3，B）2，1，3，4，C）1，4，3，2，
D）4，3，1，2，E）3，2，1，4，
二、（10分）已知在进行置换选择排序时得到14个有序段，其长度分别为2，3，4，5，6，7，8，9，11，13，17，20，21，23；现进行4路平衡归并，要求给出所对应的最佳归并树和总的读/写次数；
三、（10分）由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉连表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。
#define MAX 100
typedef struct Node{
char info;
struct Node *llink,*rlink;
}TNODE;
char pred[MAX],inod[MAX];
main(int aegc,int **argv)
{
TNODE *root;
If(argc<3) exit 0;
Strcpy(pred,argv[1]);
Strcpy(inod,argv[2]);
Root=restore(pred,inod,strlen(pred));
Postorder(root);
}
TNIDE *restire(char *ppos,char *ipos,int n)
{
TNODE *ptr,
Char *rpos;
Int K;
If(n<=0) return NULL;
Ptr->info=(1);
For( (2) ; rpos If(*rpos==*ppos)break; K= (3); Ptr->link=restore(ppos+1, (4),k ); Ptr->rlink=restore (5)+k,rpos+1,n-1-k); Return ptr; } postorder(TNODE*ptr) { if(ptr=NULL) return; postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); } 四．（10分）已知有如下定义的静态链表： TYPE component=Record Data:elemtp; Next:0..maxsize End V AR STALIST:array[0..maxsize] of component; 以及三个指针:aV指向头结点，p指向当前结点，pre指向的前驱结点，现要求静态链表中next域中的内容，使得该静态链表有双向链表功能，从当前结点P既能往后查找，也能往前查找 (1)定义next中的内容。(用老的next中的值表示): (2)如何得到当前结点p的前驱（pre)的前驱，给出计算式; 3)如何得到p的后继，给出计算式; 五、(5分)试求有n个叶结点的非满的完全二叉树的高度; 六、(15分)试以逆邻接表为存储结构，通过每次删除出度为要顶点及其入边来写一拓扑排序算法，要求输出的顶点序列是拓扑有序序列。 七、(15分)设A[1¨100]是一个记录构成的数组，B[1..100]是一个整数组，其值介于1至100之间，现要求按B[1··100]的内容调整A中记录的次序，比如当B[1]=ll时，则要求将A[1]的内容调整到A[11]中去。规定可使用的附加空间为o(1). 八、(15分)在用除余法作为散列函数、线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不致于断裂。 中科院计算机技术研究所1999年硕士生入学试题 数据结构与程序设计 一、选择题.（20分，每空2分） 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.对于前序遍历与中序遍历结果相同的二叉树为_____;对于前遍历和后序遍历结果相同的二叉为_____. 一般二叉树(2) 只有根结点的二叉树(3)根结点无左孩子的二叉树(4)根结点无右孩子的二叉树(5)所有结点只有左子数的二叉树(6)所有结点只有右子树的二叉树. 5.M路B+树是一棵_____,其结点中关键字最多为___个,最少为___个. 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 二、填空题（10分，每空1分） 1．对于给定的N个元素,可以构造出的逻辑结构有___._____. _____.. ____四种. 2．具有N个关键字的B-树的查找路径长度不会大于________., 3．克鲁司卡尔算法的时间复杂度为____________,它对____________图较为适合. 4．深度为可（设根的层数为一）的完全二叉树至少有______个结点,至多有_____个结点,K和结点数N之间的关系是_____. 三、问答题（10分，每题5分） 1. 一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为1.但一个恰有一个顶点的入度为0，其他顶 点入度为一的有向图却不一定是一棵有向树。请举例说明之。 2. 若有n个元素以构成一个小根堆，那么如果增加一个元素为K(n+1)，请用文字简要说明你如何在log2(n) 的时间内将其重新调整为一个堆？ 阅读下述程序，指出程序输出。（10分） 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[i]); } void g(int**p) { (**p)++; (*p)++; } 五.编程题（共50分，要求写出设计思想和程序注解） 1．设一单向链表的头指针为HEAD,链表的记录中包含着整数类型的KEY 域,试设计算法,将此链表的记录按照KEY递增的次序进行就地排序. （10分） 2．给定一个整数叔数组b[0..n-1].,b中连续的相等元素构成的子序列称为平台.试设计算法,求出B中最长平台的长度.（20分） 3．自由树(即无环连通图) T=(V,E)的直径是树中所有点对间最短路径长度的最大值,即T的直径定义为MAX d(u,v) （u,v∈V），这里d(u,v)表示顶点u 到顶点v的最短路径长度(路径长度为路径中所含的边数).试写一算法求T的直径,并分析算法的时间复杂度(时间复杂度越小得分越高) .（20分） 中科院计算所1999年编译原理与操作系统 一.(15分)有表达式如下:A+B*(C-D)**N (**为幂乘) (1)给出该表达式的逆波兰式表示(后缀式); (2)给出上述表达式的四元式和三元式序列. 二.(15分)有C程序如下: main() { printf("%d,%d,%d\n",10); } (1)试着写出上述printf语句输出的结果; (2)从运行环境和printf的实现分析为什么会有这样的输出结果. 三.(5分)构造一个DFA(确定的有限自动机),使之接受含偶数个"1"的0,1串集. 四.(5分)有文法G,其产生式如下: S->S(S), S->ε /*空产生式*/ 试写出一个语法制导定义,它输出配对的括号个数. 五.(10分)已知某语言L={a^(m)b^(n)|n>m>=0}.试写出产生该语言的两个文法G1和G2,其中G1是LR(1)文法,G2是非LR(1)和非二义性文法. 六.填空(每空一分,共20分) 1.现代操作系统的两个最基本的特征是_______和______. 2.进程控制块的初始化工作包括____，____和____。 3.在操作系统中引入线程概念的主要目的是___. 4.unix系统v中,系统向用户提供的用于创建新进程的系统调用是____________;用于建立无名管道的系统调用是______________;用于创建有名管道的系统调用是____________. 5.unix系统v中,引起进程调度的原因有_________,____________,_____________和_____________等. 6.在分区分配算法中,首次适应算法倾向于优先利用内存中__部分的空闲分区,从而保留了___部分的大空闲区. 7.进行设备分配时所需的数据表格主要有___________,__________,___________和________________等. 8.利用符号链实现文件共享时,对文件主删除了共享文件后造成的指针悬空问题,解决的方法是__________. 七.(8分)在消息传递通信方式下, A.发送进程和接收进程在通信过程中可以采用那三种同步方式? B.试以下面给出的发送进程和接收进程(将接收到的数据存入S)为例,说明当接收进程执行到标号为L2的语句时,采用这三种同步方式,X的值可能各是多少? 发送进程P: 接收进程Q: M=10; L1: send M to Q; L1: receive S from P; L2: M=20; L2: X:=S+1; goto L1; 八.（8分）一系统具有150个存储单元,在T0时刻按下表所示分配给3个进程: 进程Maximum demand Current allocation P1 70 25 P2 6040 P3 6045 对下列请求应用银行家算法分析判定是否是安全的: A.第4个进程P4到达,最大需求60个存储单元,当前请求分配25个单元. B.第4个进程P4到达,最大需求50个存储单元,当前请求分配35个单元. 如果是安全的请给出一个可能的进程安全执行序列.如果是不安全的,请说明原因。 九、(14分)设正在处理器上执行的一个进程的页表如下.页表的虚页号和物理块号是十进制数,起始页号(块号)均为0.所有的地址均是存储器字节地址,页的大小为1024字节. A.详述在设有快表的请求分页存储管理系统中,一个虚地址转换成物理内存地址的过程. B.下列虚地址对应与什么物理地址: (1)5499; (2) 2221; 虚页号状态位访问位修改位物理块号 0 1 10 4 111 1 7 2000 --- 3 1 00 2 4 0 00--- 5 1 0 1 0 注释:访问位---当某页被访问时,其访问位被置为1. 中科院计算所1999年编译原理与操作系统参考答案 一.(1)后缀式:ABCD-*+ECD-N**/+ (2)四元式三元式 (1)(-,C,D,t1)(1)(-,C,D) (2)(*,B,t1,t2)(2)(*,B,(1)) (3)(+,A,t2,t3)(3)(+,A,(2)) (4)(-,C,D) (4)(-,C,D,t4) (5)(**,(4),N) (5)(**,t4,N,t5) (6)(/,E,t5,t6) (6)(/,E,(5)) (7)(+,t3,t6,t7) (7)(+,(3),(6)) 四.(5分)为符号S引入综合属性h,语法制导定义如下:产生式语义规则S->S1(S2)S.h:=S1.h+S2.h+1S->ε S.h:=0S'->Sprint(S.h)/*输出其配对括号数*/ 五.(10分)G1:LR(1)文法G2:非LR(1),非二义性文法S->A,BS->aSb|BA->aAb|εB->Bb|bB->Bb|b 六.填空1.并发,共享2.初始化标识符信息,初始化处理机状态信息,初始化处理机控制信息;3.为了减少程序并发执行时所需付出的时空开销,提高程序执行的并发度;4.forkpipemknod5.正在执行的进程时间片完;正在执行的进程执行了sleep系统调用;正在执行的进程执行了exit系统调用;正在执行的进程在用户态运行时有优先级更高的进程进入就绪队列6.中低地址,高地址7.设备控制表,控制器控制表,通道控制表,系统设备表8.只让文件主拥有指向该文件索引结点的指针,而共享该文件的其他用户只有该文件的路径明而不是指向索引结点的指针. 中科院98考研题数据结构与程序设计 要求:算法设计题目要求写注解,否则扣分.写出正确设计思想和伪代码给分. 一．填空 1．用循环链表表示的队列长度为n, 若只设头指针,则出队列和入队的时间复杂度分别是______和______; 若只设尾指针,则出队和入队的时间复杂度分别是____________和________. 2．设广义表L=(( ),( )), 则DEAD(L)是_______; TAIL(L)是__________;L 长度是________;深度是__________. 3．深度为H 的完全二叉树至少有____个结点;至多有____个结点; H和结点总数N之间的关系是____,. 4．在N个记录的有序顺序表中进行折半查找,最大的比较次数是______. 5．在一棵M阶B_树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是____,若是某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是_____. 6．N个顶点的连通图用邻接距阵表示时,该距阵至少有_____个非零元素. 二．请在下列个题中选择一个正确的答案（20分，每题２分） 1．算法的时间复杂度取决于__ (A)问题的规模(B)待处理数据的初态 (C) .(B)和(A) 2．消除递归不一定需要使用栈,此说法__ (A)正确(B).错误 3．假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行多少次探测(A)K-1次(B).K次(C).K+1次(D).K(K+1)/2次 4．若需要在O(nLOG2N)的时间内完成对数的排序,且要求排序是稳定的,则可选则的排序方法是 (A)快速排序(B)堆排序(C)归并排序(D) 直接插入排序 5．用ISAM和VSAM组织文件属于___ 顺序文件(B)索引文件(C)散列文件 6．若一个有向图的邻接距阵中,主对角线以下的元素均为另零,则该图的拓扑有序__（A）序列存在(B)不存7．在将两个各有N个元素的有序表并成一个有序表,其最少的比较次数是__ (A) N (B) 2N-1 (C)2N (D)N-1 8．下述二叉树中,哪一种满足性质: 从任一结点出发到跟的路径上所经过的结点序列按其关键字有序______ (A).二叉排序树(B)哈夫曼树(C)A VL树(D)堆 9．已知待排序的N个元素可分为N/K个组，每个组包含K个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的各元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为_ (a)o(klog2k) (b)o(klog2n) (c)o(nlog2k) (d)o(log2n) 10．在叶子数目和权值相同的所有二叉树中,最优二叉树一定是完全二叉树,该说法__ (a) 正确(b)错误三．设二叉树T中各结点关键字各不相同.X^是T的叶子,Y^是X^的双亲.证明Y^.KEY 是T 中大于X^.KEY 的所有关键字中的最小者.或是小于X^.KEY的所有关键字中的最大者. 四．设数组A的长度为2N,前N个元素A[1..N]递减有序,后N个元素A[N+1…2N]递减有序,且2N是2的整数次幂,既K=LG(2N)/LG2 为整数.例如A[1..8]=[90,85,10,30,65,80,100]满足上述要求,这里N=4,K=3,A的前4个元素和后4个元素分别递减和递增有序.用此例调用如下的DEMO过程,并要求: (1) 给出FOR循环中每次执行PERFECTSHUFFLE(A,N) 和COMPAREEXCHANGE(A,N)的结果. (2) 解释DEMO的时间复杂度. (3) 给出DEMO的时间复杂度. Procedure perfectshuffle (var a;arraytype;n:integer) { I:=1;J:=1; WHILE I<=n do {b[j]:=a[I]; b[j+1]:=a[I+n]; I:=I+1; J:=j+2;} A[1..2N]:=B[1..2N]; //B COPY TO A } Procedure compareexxhange(var a:arraytype;n:integer) { J:=1; While j<2n do {if a[j]>a[j+1] then a[j] a[j+1]; //交换A[J]和A[J+1] J:=J+2 } } PROCEDURE DEMO(V AR A:ARRAYTYPE; N:INTEGER) { //A的长度为2N,K=LG(2N)/LG2 为整数 FOR J:=1 TO LG(2N)/LG2 DO {Perfectshuffle(a,n); Compareexchange(a,n); } } 五．(1).设二叉排序中关键字由1 至1000 的整数构成,现要检索关键字为363的结点,下述关键字序列中哪些可能是二叉排序树上搜索到的序列,哪些不可能是二叉排序数上搜索到的序列? 2,252,401,398,330,344,397,363 924,220,911,244,898,258,362,363 925,202,911,240,912,245,363 2,399,387,219,266,382,381,278,363 (2).通过对(1)的分析,写一个算法判定的关键字序列(假定关键字各不相同)_是否可能是二叉排序树的搜索序列.若有可能是反回真,否则返回假.可假定被判定的序列已存入树组中. 六．图的DFS搜索类似与BFS,不同之处在于使用栈代替BFS中的队列，入、出队列的操作改为入、出栈的操作。即当一个顶点的所有邻结点被搜索之后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。用邻接表做存贮结构,写一个D__搜索算法。用D__搜索方法的访问次序和相应的生成树，当从某顶点出发搜索它的邻接点，请按邻接点序号递增序搜索，以使答案唯一。 中科院计算所1998年编译原理和操作系统 一.(10分)某操作系统下合法的文件名为device:name.extension ，其中第一部分(device:)和第三部分(.extension)可缺省,若device,name和extension都是字母串,长度不限,但至少为1,画出实现这种文件名的确定有限自动机. 二.(10分)下面的二义文法描述命题演算公式,为他写一个等价的非二义文法. S->S and S|S or S|not S|p|q|(S) 三.(10分)把表达式- (a+b)*(c+d)+(a+b+c) 翻译成四元式. 四.(10分)由于文法二义引起的LR(1)分析动作冲突,可以根据消除二义的规则而得到LR(1)分析表,根据此表可以正确识别输入串是否为响应语言的句子.对于非二义非LR(1)文法引起的LR(1)分析动作的冲突,是否也可以根据什么规则来消除LR(1)分析动作的冲突而得到LR(1)分析表,并且根据此表识别相应语言的句子?若可以,你是否可以给出这样的规则? 五.(10分)下面程序的结果是120.但是如果把第5行的abs(1)改成1的话,则程序结果为1. 试分析为什么会有这不同的结果. int fact() { static int i=5; if(i=0) {return(1); } else { i=i-1; return(( i+abs(1))*fact()); } } main(){ printf("factor or 5=%d\n",fact()); } 六.名词解释(每小题2分,共10分) 1) 线程2)管程3)管道4)I/O重定向5)动态地址重定位 线程：是进程内的调度，也称为轻权进程 七.填空(每空0.5分, 共10分) 1.为了赋予操作系统以某些特权,使得操作系统更加安全可靠地工作,实际操作系统中区分程序执行的两种不同的运行状态是核心态，用户态程序不能执行特权指令. 2.引起进程调度的原因有:______________,______________和____________. 3.在一个请求式页式存储系统中,一个程序的页面走向为1,2,1,4,3,2,3,5,1,2,1,3.假定分配给该程序的存储块数为4,则采用FIFO,LRU和LFU 页面置换算法时,访向过程中的缺页次数分别为___,___和___. 4.通道技术的引入,实现了_______与_______的并行;________与_________的并行;________与_______的并行. 5.设备分配程序除了向提出I/O请求的进程分配设备外,还要为他分配设备控制器，DMA控制器和通道. 6.文件系统通常向用户提供的接口有命令接口和编程接口.以及图形接口 7.UNIX文件系统中通过引入文件索引结点来提高文件的检索效率. 八.简答题(共10分) 1.试述缺页中断的处理步骤;与一般中断相比,主要的区别是什么? 2.UNIX文件系统使用的地址索引结构是什么?与一般的地址索引结构相比有什么优点?付出的代价是什么? 九.算法题(共10分) 遵循同步机制的四条准则,写出用锁机制实现的解决读者--写者问题的同步算法. 解：同步机制的四条准则是：有空则进，让权等待，有限等待， 十.(10分)简述UNIX系统V中块设备数据缓冲池的管理技术,给出缓冲池的结构和缓冲区的分配与释放操作. 中国科学院计算所1997年 编译原理试题（共25分） 1．(10分) 为正规式（a|b）*a(a|b)构造一个确定的有限自动机。 2．(15分) 试画出如下中间代码序列的程序流图，并求出： ①各结点的必经结点集合D（n）；②流图中的回边与循环。 J：=0； L1：I：=0； If I< 8 goto L3; L2：A:=B+C B:=D*C; L3：if B = o goto L4; Write B; goto L5; L4 ：I:= I+1; If I<8 goto L2 L5：J:= J+1 If J<=3 goto L1; HALT 中科院计算所1996年程序设计 一、单项选择：（20分） 1、具有N个结点的完全二叉树的深度是：（） (1)[log2n] (2)[LOG2N]/1 (3)[LOG2(N/1)] (4)[LOG2N]-1 2、用单循环链表表示队列，正确的说法是：（） (1)可设一个头指针使入队、出队都方便 (2)可设一个尾指针使入队、出队都方便 (3)必须设头尾指针才能使入队、出队都方便 (4)无论如何,只可能使入队方便 3、对无向图而言，同一条边在邻接表中用两个结点表示，而在邻接多重表中只用一个结点表示，故此邻接多重表所需存储量比邻接表（）(1)少一半(2)多，但差异不大(3)少，但差异不大 4、一个哈希函数被认为是“好的”，如果它满足条件（） (1)哈希地址分布均匀(2)保证不产生冲突(3)所有哈希地址在表长范围内(4)满足(2)和(3) 5、ISAM文件和VSAM文件属于（） (1)索引非排序文件(2)索引顺序文件(3)顺序文件(4)散列文件 6、在下述排序算法中( )算法是稳定的排序算法。 (1)希尔排序(2)快速排序(3)冒泡排序(BUBBLE SORT) 7、平衡二叉树中，若某个结点在左、右子结点的平衡因子为零，则该因子的平衡因子也一定是零，这种说法（）(1)不正确(2)正确 8、在下述三种排序算法中，所需辅助存储量最多的是（），所需存储量最少的是（），平均速度最快的是（） (1)堆排列(2)快速排列(3)归并排列 二、问答题（25分） 1、已知某电文中共出现十种不同的字母，各个字母出现的频率分别为A：8，B：5，C：3，D：2，E：7，F：23，G：9，H：15，I：3，J：35，现在对这段电文用三进制进行编码（即码字由0，1，2，组成），问电文编码总长度最少有多少位？并画出图。 2、A是一个三对角短阵、行数与列数相等，用压缩存储的方法将其压缩存储列一堆的数组SA[1 3n-2]中（按行顺序存储），则SA[K]对应的短阵元素的下标为：行值I=（），列值J=（），反过来，若知道A中元素的下标I，J，则其存储住值置K=（）。（写出表达式） 3、设A是一个栈，栈中共有N个元素，依次为A1，A2，AN，站顶元素为AN，B是一个循环队列，队列中N个元素依次为B1，B2，BN，对头元素为B1，A，B均采用顺序存储结构且存储空间足够大，现要将站中元素全部移到队列中，使得队列中元素与站中元素交替排列，即B中元素为B1，A1，B2，A2，B3，A3，BN，AN，问至少需要多少次基本操作才能完成上述工作，请写出具体步骤（要求除A，B外所用的其他附加存储量为1，每次出栈、入栈、出队列可均看作一次基本操作）。 4、试为下列二叉树建立后序线索，画出相应的后序线索二叉树。 三、算法描述（15分）以二叉链表作存储结构，编写按层次顺序（从根结点开始）遍历二叉树的算法。 四、阅读下列程序，并回答：下列程序是否正确？为什么？如何修改？ var a,b,c,d,e,f :integer; procedure mult(var x,y,z:integer); begin z:=0; while x<>0 do begin if odd(x) then z:=z+y; y:=y+z; z:=x div 2; end; end; begin a:=5;b:=7;d:=11;e:=13; mult(a,b,c);{要求输出c=15} mult(d-b,e-a,f);{要求输出f=32} end. 五、阅读下列程序说明和C程序，把应填入其中方框处的字句，写在答卷的对应栏内。 [程序说明] 对于正整数N，输出其和等于N且满足以下限制条件的所有正整数的和式，即组成和式的数字自左至右构成一个非递增的序列。如N=4，程序输出为： 4=4 4=3+1 4=2+2 4=2+1+1 4=1+1+1+1 程序中分别采用递归和非递归解法的两个函数RD（）和ND（）。 函数RD（）采用递归解法，它有两个参数N和K。其意义分别是被分解和式的数N，及当前第K度分解。算法思想是对N的所有合理的和式分解，将分解出的数（称为和数）存于数组A{}中。当其中一个分解已不再需要进一步分解时，即找到一个解，将存于数组A{}中的一个完整和式的和数输出。当还需要进一步分解时，以要进一步分解的数及分解深度为参数，递归调用分解和式函数。 函数ND（）以要分解的数为参数，另开设一个数组R{}，用于存储当前还未分解的余数。在求一个解的第K 步时，A{K}为第K个和数，R{K}为相应的余数。当找到一个分解后（此步R{K}等于0），输出解，并作回溯处理，从当前K退回到第一个不为1的和数，将其减1，并将其余数加1，准备去找另一个解，否则，生成下一步的分解和数与余数。（15分） 答：（1）----------（2）--------------（3）----------（4）--------------（5）----------（6）-------------- [程序] #defin MAXN 100 int a[MAXN],a[MAXN]; rd(int n,int k) { int j,i; for(j=(1);j>=1;j--) {a[k]=j; if( (2) ) { printf("%d=%d",a[0],a[1]}; for(i=2;i <=k;i++) printf(" +%d",a[i]); printf("\n"); eise(3) } } nd(int n) { int i,k; k=0; r[0] =n; do { if ( (4) ) {printf("%d=%d",a[0],a[1]); for(i=2;i <=k;i++) printf(".+ %d",a[i]); printf("\n"); while (k >0 &&(5) ) k--; if (k > 0) {a(k)--;r(k)++;} } else { a[k+1] =(6); r[k+1] = r[k] -a[k+1]; k++; } } while (k >0); } int test_data[] = {3,4,5}; main() { int i; for(i =0;i < sizeof (test_data)/sizeof(int);i++) { a[0] =test_data[i]; rd(test_data[i],1); printf("\n________________\n\n"); nd(test_data[i]); printf("\n________________\n\n") } } 六、设计一个程序读入一个字符串，统计该字符串中出现的字符及其次数，然后以表的形式输出结果。要求用一个二叉树来保存处理结果，字符串中的每个不同的字符用树中不同的结点描述，每个结点包含四个域，格式为： 字符 该字符的出现次数 指向ASCII码小于该字符的左子树指针 指向ASCII码大于该字符的右子树指针 因此程序的功能是依次从输入字符串中取出一个字符，把它们插入到树中（新出现字符）或修改原树中相应结点的“出现次数域”（已出现字符）。（20分） 部分参考答案： 一、2、2、2、1、2、3、1、3、1、2 二、（1）4*2+3*2+5*2+1 =25 （2）I=[K/3]+1 J=K-2[K/3] K=ZI-2+J （3）步骤：1、先将站中所有元素依次入队，则站空，队为B1----BNAN---A1 2、将B1~BN依次出队、入队，则队列变为AN---A1B1---BN 3、将AN~~~A1出队入站则站为A1---AN （A1为站顶），队为B1----BN 4、顺次BI出队、入队，AI出站入队，则最后为B1A1---BNAN 总共有2N+2N+2N+4N=10N个基本操作。 （4） 中国科学院计算所一九九六年软件基础 一．（10分）已知序列17，31，13，11，20，35，25，8，4，11，24，40，27。请画出该序列的二叉排序树，并分别给出下列操作后的二叉树； ①插入数据9；②删除结点17；③再删除结点13。 二．（15分）请编写一个程序，生成如下序列的前n项。 1，2，1，2，3，2，1，2，3，4，3，2，1，2，3，4，5，4，3，2，1, 2，…… 三．（15分）已知平面上（直角坐标系）的n个点，请编一个函数，求同一条直线所能通过的最多点数。四．（10分）下面的文法产生a的个数和b的个数相同的非空a，b串。 S aB | bA B bS | aBB | b A aS | bAA | a 其中非终结符B推出b比a的个数多1个的串，A则反之。说明该文法是二义的。 对上述文法略作修改，使之非二义，并产生同样的语言。略作修改的含义是：不增加非终结符。 五．（10分）某些语言允许给出名字表的一个属性表，也允许声明嵌在另一个声明里面，下面文法抽象这个问题。 D attrlist namelist | attrlist（D） namelist id，namelist | id attrlist A，attrlist | A A decimal | fixed | float | real D attrlist（D）的含义是：在括号中的声明提到的所有名字有attrlist中给出的属性，而不管声明嵌套多少层。写一个翻译方案，它将每个名字的属性个数填入符号表。 六．（10分）下面是一个C语言程序及其运行结果。从运行结果看函数func中四个局部变量i1，j1，f1，e1的地址间隔和它们类型的大小不一致，试分析不一致的原因。 #include func(i , j , f , e ) short i , j ; float f1 , e1; { short i1, j1; float f1, e1; i1 = i; j1 = j; f1 = f; e1 = e; printf(“Addresses of i, j, f, e = %d, %d, %d, %d\n”, &i, &j, &f, &e); printf(“Addresses of i1, j1, f1, e1 = %d, %d, %d, %d\n”, &i1, &j1, &f1, &e1); printf(“Size of short, int, long, float, double = %d, %d, %d, %d, %d\n” , sizeof(short), sizeof(int), sizeof(long), sizeof(float), sizeof(double)); } main() { short i, j; float f, e; i = j = 1; f = e = 1.0; func(i , j , f , e); } 运行结果: Addresses of i, j, f, e = -268438178, -268438174, -268438172, -268438164; Addresses of i1, j1, f1, e1 = -268438250, -268438252, -268438256, -268438260; Size of short , int , long , float , double = 2, 4, 4, 4, 8 七．（5分）在UNIX系统中，对换区的功能是什么？UNIX系统V是如何对对换区进行管理的？ 八．（5分）UNIX系统V为进程之间的通信提供了哪些工具？各用于什么场合？ 九．（5分）操作系统中的文件共享有几种形式？它们是如何实现的？各有什么特点？ 十．（5分）Dijkstra（1965）提出的银行家算法的主要思想是什么？它能够用来解决实际中的死锁问题吗？为什么？ 十一．（10分）有五个批处理的作业（A，B，C，D，E）几乎同时到达一个计算中心，估计的运行时间分别为2，4，6，8，10分钟，它们的优先数分别为1，2，3，4，5（1为最低优先级）。对下面的每种调度算法，分别计算作业的平均周转时间。 ①最高优先级优先； ②时间片轮转（时间片为2分钟）； ③FIFO（作业到达的顺序为C，D，B，E，A）； ④短作业优先。 中国科学院计算所一九九六年软件基础答案 1． 4．句子aabbab有两种不同的推导： S → aB → aaBB → aabB → aabbS → aabbaB → aabbab； S → aB → aaBB → aabSB → aabbAB → aabbaB → aabbab； S aBS | bAS | aB | bA B aBB | b A bAA | a 8．UNIX系统V提供的工具有： Sleep/Wakeup：核心态进程的同步； 软中断信号机制（signal/kill）：同一用户进程间的通讯（小数据量）； 基于文件系统的pipe机制：进程间大数据量的通讯； 共享存储器、信号量集和消息传递机制。 9．采用全路径名访问他人文件。共享时间短； 采用目录表项之间的链接。即使一个用户目录中的表项直接指向另一个目录中的表项。长久共享。 采用基本文件目录和符号文件目录的组织方式，便于用户文件的共享。 中科院计算所1995年程序设计 一.选择 1.一棵深度为6的平衡二叉树,其每个非终端结点的平衡因子均为1,则该树共有__个终端结点.(2分) a.14 b.16 c.18 d.20 e.22 f.24 2.一个有18条边的非连通无向图,至少应有__个结点.(2分) a.6 b.7 c.8 d.9 e.10 f.11 3.一棵124个叶结点的完全二叉树,最多有__个结点.(2分) a.247 b.248 c.249 d.250 e.251 4.按锦标赛排序的方法，决定出8位运动员之间的名次顺序排列,至少需编排__场次的比赛.(考虑最坏) (2分) a.13 b.14 c.15 d.16 e.17 5.已知Head(Tail([Head(S),Head(Tail(Tail(S))]))广义表满足上式,则S为___. a.[[a,b],b,a] b.[[b,a],[a],[b]] c.[[a],[a,b],[b]] d.[b,[a],[a,b]] e.[[a],[b],[b,a]] f.[[b],[b,a],[a]] (其中,方括号表示广义表,圆括号表示函数,Head()表示取广义表的头部)(2分) 6.在下列三种次序的线索二叉树中,___对查找指定结点在该次序下的后继效果较差.(2分) a.前序线索树 b.中序线索树 c.后序线索树 7.由二叉树的前序和后序遍历序列___唯一地确定这棵二叉树.(2分) a.能b. 不能 8.在下列两种求图的最小生成树的算法中,__算法最适合于求边稀疏的网的最小生成树(2分) a.Prim b.Kruskal 9.下列无向图的存储结构中，在对无向图的边进行操作时(如删除一条边)，_______存储结构更为适合. a.邻接表 b.邻接多重表. 10.在下述几种树当中,__可以表示静态查找表. a.次优查找树; b.二叉排序树; c.B-树 d.平衡二叉树 11 (1).在文件局部有序或文件长度较小的情况下,最优内部排序的方法是_A__. (2).快速排序在最坏的情况下,时间复杂度是_B__,_C__的性能差; (3)就平均时间而言,_D__最佳. A.: (1)直接插入排序(2)起泡排序(3)简单选择排序; B.: (1)O(nlog(n)) (2)O(n^2) 3.O(n^3) C.: (1)堆排序(2)起泡排序(3)选择排序. D.:(1)堆排序(2)快速排序(3) 归并排序. 12.一程序规定的职能是"输入三个整数作为三边的边长构成三角形,判别是等腰三角形,等边三角形,或是一般三角形.再做计算..."若用等价类划分方法对该程序作功能测试,至少应对该程序的输入数据考虑_A_个等价类,其中包括_B_个有效等价类和_C_个无效等价类. A.___B.___C.___ (1)3; (2)5; (3)7; (4)12; (5)15; (6) 18; (7)21; (8)25; (9)33; (10)40; 13.设二叉树如图所示: (共四分) 1.给出先序遍历的结点,访问顺序________. 2.给出中序遍历的结点,访问顺序________. 3.给出后序遍历的结点,访问顺序________. 4.若用二叉链表作为存储结构,将出现多少个空指针域?__ 14.下列函数 function calc(x,y :integer): integer; begin if y=1 then calc:=x else calc:=calc(x,y-1)+x end; a,b均为正整数,则calc(a,b)=___. (1).a*(b-1) (2).a*b (3)a+b (4)a+a 15.程序段 read(a,b); c:=3.0*a+b; if c=0 then a:=1 else a:=1.0+1.0/c+1.0/b; 保证该程序段运行不出错的必要条件是:___ (1).b>0; (2).a>0 and b>0; (3).b!=0; (4).b!=0 and c!=0; 二.程序改错与填空: 1.指出下列程序段中的错误位置,对错误编号说明理由: 程序段1:(8分) Label 1: const max=50; type day={Mon,Tue,Wed,Thu,Fri,Sat,Sun}; var date:day; N:integer; begin a: N:=N-ord('0'); b: for date:=Mon to Sun do N:=ord(succ(date))-1 c: for n:=1 to 10 do begin ...... 1:语句; end; ...... goto 1; ...... end. 答:__________________________. 程序段二.(8分) Program type(input,output); var R:real; Procedure print(var x:integer,y:real); var z:real; Procedure sum(x:integer; y:real); var k:real; begin z:=x+y; k:=3*z; x:=x+y; end;{sum} begin sum(x,y); writeln(x,y,z,k); end;{print} begin readln(R); print(15,R); print(R,R) end.{main progam} 2.阅读下列程序,填空使之成为一个完整的程序: 该程序输出N个元素的全排列. 程序: program pic(input,output); const n=10; var A:array[1..n] of integer; i,k:integer; procedure output1; begin for i:=1 to n do write(A[i]:3); writeln; end{output1} procedure permute(k:integer); var i,t:integer; begin if k=1 then output1 else begin ________; for i:=1 to ___do begin T:=A[k]; A[k]:=A[i]; A[i]:=T; ____________; T:=_________; ____________; end; end; end;{permute} begin K:=n; for i:=1 to k do A[i]:=i; permute(k); end. 三.编程题:(语言任选) 1.(15分)编写程序将一个循环队列的内容倒置,该循环队列存储在一个数组A[1..n] 中,例如图a中为倒置前的队列,图b中为倒置后的队列.要求倒置后的队列从数组的第一个元素开始,整个程序的运行时间为O(n). 0|≥>m n b a n m 2.设计一个程序,使输入的句子按如下方式改造后输出: (1).单词之间只留一个空格作间隔; (2).句子结束后必须紧跟句号; (3).如果把句子的单词从左到右依次编号为1,2,3...,则对于第奇数个单词,只要直接复制就行了,而对于第偶数个单词,应按反序打印。 中科院计算所1994年软件基础 语言与编译部分（35分） 一．（7分）把下面不确定的有限自动机化为确定的有限自动机。 二．（8分）有文法： S （L ）| a L L ，S | S 给此文法配上语义动作子程序（或者说为此文法写一个语法制导定义），它输出配对的括号的个数，如对于句子（a,(a,a)）输出是2。 三．（15分）为语言{ }写三个文法，它们分别是二义文法，LR(1)文法和非LR(1)且非二义的文法。不必证明所写文法的正确性，但每个文法的产生式不能超过4个。 四．（5分）右边是一个FORTRAN 77程序。 CALL SUB 按语言的语义，程序的输出结果是什么？ CALL SUB 在静态存储分配情况下，实际的输出结 END 果是什么？两者是否有区别？说明理由。 SUBROUTINE SUB DATA I/10/ WRITE （*，*）I I=100 END 程序设计与数据结构部分（35分） 一、（8分）下面的程序段是合并两条链（F 和G ）为一条链F 的过程。作为参数的两条链都是按结点上NUMBER 值的由大到小链接。合并后新链仍按此方式链接。请填写下述空框，使程序正确工作。 type pointer= ^ node; node =record number:integer; next :pointer end; procedure combine(var f:pointer; g:pointer); var h,p : pointer; begin new(h); h^. next :nil; p:=h; while (f<> nil) and (g<> nil) do if f^. number >=g^.number then begin p^.next:=__A__; P:=__B___; __C__ end else begin p^. next:=__D____; P:=___E___; ____F__ end; if f=nil then __G__; if g=nil then __H__; f:=h^.next ; dispose(h) end; 二、（12分）如果一个数列中的某一段（至少有两个元素）的各元素值均相同，则称之为等值数列段。等值数列段中元素的个数叫做等值数列段的长度。现有由N个元素组成的整数数列A，编一程序求A中长度最大的所有等值数列段的始末位置，如果没有等值数列段，则输出特殊标志。 三、（15分）编一个程序，对输出的任意正整数N，打印出集合{0，1，…，n-1}的所有子集。例如，输出为3时，输出是 { } {0} {1} {0，1} {2} {0，2} {1，2} {0，1，2} 操作系统部分（30分） 一、填充（每空一分，共14分） 1、采用单级文件目录的主要缺点是存在（文件名冲突）_____________问题。 2、在单道程序运行环境下，常用的作业调度算法有（FCFS）__________、(SJF)__________、和__________。 3、特权指令是只能由（操作系统）__________使用的指令。 4、存储器的保护机制（硬件）有___________保护和_________保护。 5、预防死锁中的预先分配法和标准（有序）分配法，它们分别破坏了产生死锁必要条件中的_____________ 条件和_____________条件。 6、在段式虚拟存储管理中，段表设置“改变位”的目的是为了___________________________________。 7、进程有三种基本状态，即①___________状态， ②_____________状态，③______________状态。 当进程由①演变为②或③时，就会立即引起___________ 。 进程有三种基本状态，即[1]执行状态，[2]等待状态，[3]就绪状态。当进程由[1]演变为[2]或[3]时，就会引起（进程调度）。 二、判断。（每题1分，共5分） 1、（正确）有了动态重定位机构，作业地址空间的代码就可以原封不变的装入到给定的内存中。 2、（错误）任一时刻，若有执行状态的进程，就一定有就绪状态的进程。 3、（错误）文件系统中，设置OPEN操作的目的是为了将文件复制到内存中。 4、（错误）临界段是不可中断的程序。 5、（正确）作业的提交状态进入后备状态的过程是由作业调度程序完成的。 三、（5分）分页式存储管理与分段式存储管理的主要区别是什么？ 四、（6分）以下是高级通讯原语SEND和RECEIVE不完整的框图。请填充以适当的P、V操作，并说明所 用信号量的意义和初值。 SEND：RECEIVE： ↓ ↓ 申请一消息区（3） ↓ ↓ 消息送消息区（4） ↓ ↓ （1）从消息链上摘下一消息 ↓ ↓ 消息区挂入消息链（5） ↓ ↓ （2）消息送接收区 ↓ ↓ V（S2）释放消息区 ↓ ↓ 中国科学院软件所一九九四年软件基础答案 操作系统部分： 一．填空 1．重名。 2．先进先出，最短作业优先，最高响应比优先。 3．操作系统。4．界地址，存储键。 5．保持和请求，环路。6．避免将被淘汰段不必要地写回外存，减少信息传输量。 7．执行，就绪，封锁（阻塞），进程调度。 二．判断 1．√ 2．× 3．× 4．× 5．× 三． 四．① P（S1）② V（S1）③ P（S2）④ P（S1）⑤ V（S1）S1是（消息链）互斥信号量，初值为1。 S2是（记录消息个数）同步信号量，初值为0。 语言与编译部分： 一． 二．拓广文法，加入新开始符号S’和产生式S’ S。 S’ S print（S.num） S (L) S.num:=L.num+1 S a S.num:=0 随机过程考试试题及答案详解 1、（15分）设随机过程C t R t X +?=)(，),0(∞∈t ，C 为常数，R 服从]1,0[区间上的均 匀分布。 （1）求)(t X 的一维概率密度和一维分布函数； （2）求)(t X 的均值函数、相关函数和协方差函数。 【理论基础】 （1）? ∞ -= x dt t f x F )()(，则)(t f 为密度函数； （2）)(t X 为),(b a 上的均匀分布，概率密度函数?? ???<<-=其他,0,1 )(b x a a b x f ，分布函数 ?? ??? >≤≤--<=b x b x a a b a x a x x F ,1,,0)(，2)(b a x E += ，12)()(2a b x D -=； （3）参数为λ的指数分布，概率密度函数???<≥=-0,00 ,)(x x e x f x λλ，分布函数 ?? ?<≥-=-0 ,00,1)(x x e x F x λ，λ1)(=x E ，21 )(λ=x D ； （4）2 )(,)(σμ==x D x E 的正态分布，概率密度函数∞<<-∞= -- x e x f x ,21 )(2 22)(σμπ σ， 分布函数∞<<-∞= ? ∞ --- x dt e x F x t ,21)(2 22)(σμπ σ，若1,0==σμ时，其为标准正态分布。 【解答】本题可参加课本习题2.1及2.2题。 （1）因R 为]1,0[上的均匀分布，C 为常数，故)(t X 亦为均匀分布。由R 的取值范围可知， )(t X 为],[t C C +上的均匀分布，因此其一维概率密度?? ???+≤≤=其他,0,1 )(t C x C t x f ，一维分布 函数?? ??? +>+≤≤-<=t C x t C X C t C x C x x F ,1,,0)(； 北京航空航天大学计算机学院计算机学科专业基础 综合历年考研真题汇编 最新资料，WORD格式，可编辑修改！ 目录 说明：2007～2008的科目名称为“计算机专业综合”，代码分别为461和961；2009～2014年的科目代码与名称为“408计算机学科专业基础综合”；2015年起，科目代码与名称改为“961计算机学科专业基础综合”，本书书名以此为准。 2014年北京航空航天大学计算机学院408计算机学科专业基础综合真题及详解 一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是符合题目要求的。 1．下列程常段的时间复杂度是（） count＝0; for（k＝1;k<＝n; k*2） for（j＝1;j<＝n;j+1） count++; A．O（log2n） B．O（n） C．O（nlog2n） D．O（n2） 【答案】C 【解析】外部循环的退出条件是k>n，而对于k，每次循环都执行k＝k*2,所以循环次数为log2n；内部循环的退出条件是j>n,对于j，每次循环都执行j＝j+1，所以每次循环次数为n次。所以此程序段的时间复杂度为O（nlog2n），即选C。 2．假设栈初始为空，将中缀表达式a() b c d e f g +*-*转换为等价后缀表达式的过程中，当扫描到f时，栈中的元素依次是（） A．(+*- B．(+-* C．(+*-* D．+-* 【答案】B 【解析】中缀表达式转后缀表达式遵循以下原则： （1）遇到操作数，直接输出； （2）栈为空时，遇到运算符，入栈； （3）遇到左括号，将其入栈； （4）遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号， 左括号不输出； （5）遇到其他运算符'+''-''*''/'时，弹出所有优先级大于或等于该运算符的栈顶 元素，然后将该运算符入栈； （6）最终将栈中的元素依次出栈，输出。 所以扫描到’/’，入栈‘描到’+’,由于’+’优先级比’/’低，所以将’/’弹出，’+’入栈；扫描到’*’,优先级比’+’高，入栈；扫描到’（‘,入栈;扫描到’-‘,将栈中优先级更高的’*’弹出，‘-’ 入栈;扫描到’*’,优先级比’-‘高，入栈。所以扫描到f的时候，栈中元素为：(+-* （1） 设}0),({≥t t X 是一个实的零均值二阶矩过程，其相关函数为 t s s t B t X s X E ≤-=),()}()({，且是一个周期为T 的函数，即0),()(≥=+τττB T B ，求方差函数)]()([T t X t X D +-。 解：由定义，有： )(2)0()0()}()({2)0()0()]} ()()][()({[2)] ([)]([)]()([=-+=+-+=+-+--++=+-T B B B T t X t X E B B T t EX T t X t EX t X E T t X D t X D T t X t X D （2） 试证明：如果}0),({≥t t X 是一独立增量过程，且0)0(=X ，那么它必是一个马 尔可夫过程。 证明：我们要证明： n t t t <<<≤? 210，有 } )()({})(,,)(,)()({11112211----=≤=====≤n n n n n n n x t X x t X P x t X x t X x t X x t X P 形式上我们有： } )()(,,)(,)({} )()(,,)(,)(,)({} )(,,)(,)({} )(,,)(,)(,)({})(,,)(,)()({1122221111222211112211112211112211--------------========≤= ======≤=====≤n n n n n n n n n n n n n n n n n n n n x t X x t X x t X x t X P x t X x t X x t X x t X x t X P x t X x t X x t X P x t X x t X x t X x t X P x t X x t X x t X x t X P 因此，我们只要能证明在已知11)(--=n n x t X 条件下，)(n t X 与2 ,,2,1,)(-=n j t X j 相互独立即可。 由独立增量过程的定义可知，当2,,2,1,1-=<<<-n j t t t a n n j 时，增量 )0()(X t X j -与)()(1--n n t X t X 相互独立，由于在条件11)(--=n n x t X 和0)0(=X 下，即 有)(j t X 与1)(--n n x t X 相互独立。由此可知，在11)(--=n n x t X 条件下，)(n t X 与 2,,2,1,)(-=n j t X j 相互独立，结果成立。 （3） 设随机过程}0,{≥t W t 为零初值（00=W ）的、有平稳增量和独立增量的过程， 且对每个0>t ，),(~2t N W t σμ，问过程}0,{≥t W t 是否为正态过程，为什么？ 解：任取n t t t <<<≤? 210，则有： n k W W W k i t t t i i k ,,2,1][1 1 =-=∑=- 2020年中科院计算机863考研真题回忆 （题号和顺序仅供参考） 选择题（选择题记住的不多了） 1.进程进入临界区时首先要执行什么指令（特权指令、原子指令、向量指令，xx指令） 2.对称密码和非对称密码的（不会，具体题也忘啦） 3.用户使用操作系统资源时通过什么方法（系统调用） 4.三级页表，虚拟地址24位，每级页号占8位，每个页表项4B，页面大小1KB，先一进程大小128KB，问其页表大小为（1KB，2KB，3KB，4KB） 5.对称多处理系统能在多个处理器上同时运行线程还是进程 6.下列措施是为了实现保密性的是（根目录只有root能访问） 7.下列不是死锁预防措施的是（两阶段加锁，重启系统，假脱机，按顺序分配资源） 8.RAID6的特征（6块磁盘并行，可以容忍1？2？3？块磁盘损坏） 9.第一次打开文件时的操作（把超级快读入内存，把inode读入内存，xxx） 10.CPU流水线5阶段时间分别为xxxns，问你时钟频率最高是多少 11.采用程序查询方式，每次程序执行需xxx个周期，每秒需执行xxx次，主频给出，求程序查询占用时间比例 问答题 41.一般的文件系统在磁盘上有哪些组成部分，分别有哪些功能？ 42.进程共5个页面，工作集大小为4，给出一组页面访问顺序，问分别采用FIFO、LRU、Optimum（最优置换）算法时缺页次数及缺页时替换的分别为哪个页 43.给出一个cache-主存地址转换结构图，问你cache的映射方式、总大小、块大小、写回策略等等（主要是看懂图，看出来是四路组相连） 44.给了一个局域网拓扑图，主机通过交换机连接了一个www服务器和一个DNS服务器，让你简述访问www服务器主页的过程，用了哪些协议，分别是什么功能 45.一个单周期CPU，5个阶段（取指、析址、执行、访存、写回）第一问问你一条指令执行时间，第二问将执行和访存结合成一个阶段（2选1）问你此时指令执行时间，第三问问这 《随机过程期末考试卷》 1．设随机变量X 服从参数为λ的泊松分布，则X 的特征函数为 。 2．设随机过程X(t)=Acos( t+),- 中国科学院大学计算机考研经验 1.专业基本情况（含报考人数，录取人数，报录比；） 专业基本情况：对于咱们报考中科院计算机的考生来说，毋容置疑是考863计算机学科综合考试的，其中包含数据结构、计算机网络、计算机操作系统、计算机组成原理四门课，也是我们常说的四大门。 简介：计算所拥有"计算机科学与技术"、"网络空间安全"两个一级学科，包括计算机系统结构、计算机软件与理论、计算机应用技术、信息安全等多个专业方向。可研究大数据、人工智能、计算机视觉、机器学习、图形图像处理、移动计算和可持续计算、并行处理体系结构、分布式操作系统等众多研究方向。 报考人数比例：对于报考中科院计算所的考生每年大约三四百人，如果没有意外，每年进入复试的人数大约是八十人左右，最后录取人数大约五十人左右。根据这个数字，按每年报考三百人，录取五十人计算，报录比为6:1，进入复试的比例为3.75:1。整体来说有点难度，但难度不大。 2. 每年录取分数线是多少，近三年为例； 2019年 复试线总分为：322 录取最低分数线：322 2018年 复试线总分为：304 录取最低分数线：309 2017年 复试线总分为：320 录取最低分数线：321 3. 写出公共课与专业课的官方参考书目； 4. 公共课与专业课的备考经验，今年专业课更改的情况与复习方式； 对于公共课： 数学：是考研的一大关，我们要及早进入数学的复习，第一轮：数学的复习过程是先把课本过一遍，基本知识点弄会，课后习题要做一遍；第二轮：买一本数学复习全书，跟着全书把知识点弄一遍，对应全书的习题要弄懂，特别是例题讲解；第三轮：要做真题，做真题，一定要多做真题，把近十年的真题全做一遍，做懂，做会。 英语：是个长久战，也要尽早进入复习，英语可以报个辅导，跟着老师的步伐走，英语重点在作文和阅读，要多练习，前提肯定是要先过单词的关，多做真题。政治：非常建议报个班，政治是最不好复习的，尤其是自己复习，根本抓不住重点，有老师跟着，可以帮我们提取重点，分析热点。 对于专业课： 首先是复习顺序：建议顺序为数据结构、操作系统、计算机组成原理、计算机网络 对于数据结构是注重逻辑理解，将逻辑结构和物理结构理解透彻，对于每一种数据结构要知道怎么通过顺序存储和链式存储实现，对于涉及数据结构的算法，要理解过程中的每一步；后面三科比较偏文，所以需要识记，操作系统是最为简单的一个科目，需要对操作系统的线程、进程、临界区保护等热点热考的考点理解透彻，识记东西较多；组成原理中需要逻辑理解的内容较多，主要偏重计算机硬件内部结构，以及在硬件上怎么进行计算机执行的，主要还是抓住重点，进行结构和内容的识记；计算机网络虽然内容多，但是能考的考点比较少，所以重点比较突出。 5. 复试的过程与经验。 中国科学院大气物理研究所 中国科学院大气物理研究所简介 大气物理研究所前身是1928年成立的原中央研究院气象研究所。现有职工325人，其中科技人员251人，有中国科学院院士7人，研究员46人，副研究员和高级工程师86人，中级科技人员108人。大气所是博士、硕士学位授予单位和博士后流动站建站单位。是中国科学院博士生重点培养基地，国家毕业生就业重点保证单位。现有在学博士生211人，硕士生105人，博士后18人。 大气物理研究所主要研究大气中各种运动和物理化学过程的基本规律及其与周围环境的相互作用，特别是研究在青藏高原、热带太平洋和我国复杂陆面作用下的东亚天气气候和环境的变化机理、预测理论及其探测方法，以建立东亚气候系统和季风环境系统的理论体系及遥感观测体系，发展新的探测和试验手段，为天气、气候和环境的监测、预测和控制提供理论和方法。四个优势创新研究领域是：气候系统动力学和预测理论研究、大气环境和人类生存环境变化动力学和预测理论研究、中层大气与遥感理论和技术研究、中小尺度天气系统与灾害研究。 大气物理研究所拥有的科研部门包括：大气科学和地球流体力学数值模拟国家重点实验室、大气边界层物理与大气化学国家重点实验室、中国科学院东亚区域气候-环境重点实验室、中层大气遥感与探测开放实验室、云降水物理与强风暴实验室、国际气候与环境科学中心、竺可桢--南森国际研究中心、灾害性气候研究与预测中心、中国生态系统研究络大气分中心、季风系统研究中心。另外还设有信息科学中心。 2005年，大气物理所知识创新工程全面推进阶段工作进展顺利，科研工作取得若干重要进展，气候数值模式、模拟及气候可预报性研究项目荣获2005年度国家自然科学二等奖；获得湖北省科技进步一等奖1项，中国人民解放军科学技术进步二等奖1项，中国气象局气象科技奖成果应用奖一等奖 1项，国家教育部科学技术进步二等奖1项。共发表科技论文469篇，其中ScI收录论文126篇，申报专利5项。队伍建设和人才培养工作成效显著，叶笃正荣获国家科学技术最高奖，并作为第一主持人荣获国家科学技术进步二等奖；吕达仁当选为中国科学院院士。一批科研和管理人员以及研究生获得了各类奖项，取得佳绩。制度化、民主化、科学化三化建设继续向前推进。 2005年，申请获得973项目北方干旱化与人类适应1项、973课题2项、863专题3项；获得国家自然科学基金各类项目29项，包括4个重点基金、面上基金23项，杰出A和杰出B各1项；获院方向性项目3项，课题1项。还获 803计算机学科基础综合 ——此内容为零一教育为您收集整理，如需详细资料可以关注我们的微信公共号（零一计算机圈、零一职业规划） 一、考查目标 计算机学科基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 二、考试形式和试卷结构 1、试卷满分及考试时间 本试卷满分为150分，考试时间为180分钟。 2、答题方式 答题方式为闭卷、笔试。 3、试卷内容结构 数据结构45分 计算机组成原理45分 操作系统35分 计算机网络25分 4、试卷题型结构 单项选择题80分(40小题，每小题2分) 综合应用题70分 三、考查内容 数据结构 【考查目标】 1、掌握数据结构的基本概念、基本原理和基本方法。 2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3、能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1、顺序存储 2、链式存储 3、线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的基本概念 （二）二叉树 1、二叉树的定义及其主要特征 2、二叉树的顺序存储结构和链式存储结构 3、二叉树的遍历 4、线索二叉树的基本概念和构造 （三）树、森林 1、树的存储结构 2、森林与二叉树的转换 3、树和森林的遍历 （四）树与二叉树的应用 1、二叉排序树 2、平衡二叉树 3、哈夫曼(Huffman)树和哈夫曼编码 四、图 （一）图的基本概念 （二）图的存储及基本操作 1、邻接矩阵法 2、邻接表法 3、邻接多重表、十字链表 （三）图的遍历 1、深度优先搜索 2、广度优先搜索 （四）图的基本应用 1、最小（代价）生成树 2、最短路径 3、拓扑排序 4、关键路径 五、查找 （一）查找的基本概念 （二）顺序查找法 （三）分块查找法 （四）折半查找法 （五）B树及其基本操作、B+树的基本概念（六）散列(Hash)表 （七）字符串模式匹配 （八）查找算法的分析及应用 六、排序 （一）排序的基本概念 （二）插入排序 1、直接插入排序 2、折半插入排序 （三）气泡排序(bubble sort) （四）简单选择排序 一．填空题（每空2分，共20分） 1．设随机变量X 服从参数为λ的泊松分布，则X 的特征函数为it (e -1) e λ。 2．设随机过程X(t)=Acos( t+),- 北京邮电大学2018年专业课803计算机学科基础综合考试大纲 新祥旭考研：十年专注考研一对一辅导 803计算机学科基础综合 一、考查目标 计算机学科基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 二、考试形式和试卷结构 1、试卷满分及考试时间 本试卷满分为150分，考试时间为180分钟。 2、答题方式 答题方式为闭卷、笔试。 3、试卷内容结构 数据结构 45分 计算机组成原理 45分 操作系统 35分 计算机网络 25分 4、试卷题型结构 单项选择题 80分(40小题，每小题2分) 综合应用题 70分 三、考查内容 数据结构 【考查目标】 1、掌握数据结构的基本概念、基本原理和基本方法。 2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3、能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1、顺序存储 2、链式存储 3、线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的基本概念 （二）二叉树 1、二叉树的定义及其主要特征 2、二叉树的顺序存储结构和链式存储结构 3、二叉树的遍历 4、线索二叉树的基本概念和构造 （三）树、森林 1、树的存储结构 2、森林与二叉树的转换 3、树和森林的遍历 （四）树与二叉树的应用 1、二叉排序树 2、平衡二叉树 3、哈夫曼(Huffman)树和哈夫曼编码 四、图 （一）图的基本概念 （二）图的存储及基本操作 1、邻接矩阵法 2、邻接表法 3、邻接多重表、十字链表 （三）图的遍历 1、深度优先搜索 2、广度优先搜索 （四）图的基本应用 1、最小（代价）生成树 2、最短路径 3、拓扑排序 4、关键路径 五、查找 （一）查找的基本概念 （二）顺序查找法 （三）分块查找法 （四）折半查找法 （五）B树及其基本操作、B+树的基本概念（六）散列(Hash)表 （七）字符串模式匹配 （八）查找算法的分析及应用 六、排序 （一）排序的基本概念 （二）插入排序 1、直接插入排序 2、折半插入排序 （三）气泡排序(bubble sort) （四）简单选择排序 （五）希尔排序(shell sort) 北京工业大学2009-20010学年第一学期期末 数理统计与随机过程(研) 课程试卷 学号 姓名 成绩 注意：试卷共七道大题，请写明详细解题过程。 考试方式：半开卷，考试时只允许看教材《概率论与数理统计》 浙江大学 盛 骤等编第三版（或第二版）高等教育出版社。可以看笔记、作业，但不允许看其它任何打印或复印的资料。考试时允许使用计算器。考试时间120分钟。考试日期：2009年12月31日 一、随机抽取某班28名学生的英语考试成绩，算得平均分数为80=x 分，样本标准差8=s 分，若全年级的英语成绩服从正态分布，且平均成绩为85分，问：能否认为该班的英语成绩与全年级学生的英语平均成绩有显著差异（取显著性水平050.=α）？ 解：这是单个正态总体 ),(~2σμN X ，方差2σ未知时关于均值μ的假设检验问题，用T 检验法. 解 85:0=μH ，85:1≠μH 选统计量 n s x T /0 μ-= 已知80=x ，8=s ，n ＝28，850=μ， 计算得n s x T /0μ-= 31 .328/885 80=-= 查t 分布表，05.0=α，自由度27，临界值052.2)27(025.0=t . 由于052.2>T 2622.2>，故拒绝 0H ，即在显著水平05.0=α下不能认为 该班的英语成绩为85分. 050.= 解：由极大似然估计得.2?==x λ 在X 服从泊松分布的假设下，X 的所有可能的取值对应分成两两不相交的子集A 0, A 1,…, A 8。 则}{k X P =有估计 =i p ?ΛΛ,7,0, !2}{?2 ===-k k e k X P k =0?p 中国科学院大学2020考研大纲：863计算机学科 综合(专业) 计算机学科综合考研大纲公布了没？考研大纲频道为大家提供中国科学院大学2019考研大纲：863计算机学科综合(专业)，更多考 研资讯请关注我们网站的更新! 中国科学院大学2019考研大纲：863计算机学科综合(专业) 一、考试形式 闭卷，笔试，考试时间180分钟，总分150分。 二、试卷结构 题型：概念题(填空、选择、判断、简答)，应用题(计算、画图、分析、设计)等。 三、考试科目 数据结构、计算机组成原理、操作系统、计算机网络四门课程，每门课程各占25%。 四、数据结构 (一)考试大纲 1、绪论 (1)数据结构的基本概念，数据的逻辑结构、存储结构。 (2)算法的定义、算法的基本特性以及算法分析的基本概念。 2、线性表 (1)线性表的定义、基本操作。 (2)线性表的存储结构(包括顺序存储结构、链式存储结构)及操 作实现。 (3)线性表的应用。 3、栈与队列 (1)栈与队列的基本概念、基本操作。 (2)栈与队列的存储结构(包括顺序存储结构、链式存储结构)及操作实现。 (3)栈与队列的应用。 4、数组和广义表 (1)数组、广义表的基本概念、多维数组的实现。 (2)特殊矩阵(包括对称矩阵、稀疏矩阵)的压缩存储。 5、树与二叉树 (1)树、二叉树、森林的基本概念和性质。 (2)树、二叉树、森林的存储结构(包括顺序存储结构、链式存储结构)。 (3)树、二叉树、森林的遍历和转换操作。 (4)线索二叉树的基本概念和构造。 (5)哈夫曼(Huffman)树和哈夫曼编码。 6、图 (1)图的基本概念和性质。 (2)图的存储结构(包括邻接矩阵、邻接表、十字链表、邻接多重表)。 (3)图的遍历操作(包括深度优先遍历、广度优先遍历)。 (4)图的最小生成树，最短路径，关键路径，拓扑排序。 7、查找 经过一年多的复习艰辛，初试的失望，等待成绩的焦躁不安，复试的忐忑，最终终于如愿以偿考上自己向往的中科院，心中有喜悦也有感恩。一路走来真的不容易，在这里把自己的一些经验和感悟给大家说一下，希望能够帮助后来的考研学子，也是对曾经给过我指导和帮助的热心人的感恩。 首先自我介绍，我是来自一个普通二本里的三本学生，软件工程专业，至于学费我想大家都知道。我今年的考研分数：数学105 英语61 政治70 专业课92 报考学校：中科院计算所。如果你是大牛考名校那就不要参考了，因为，我很平庸，报的也不是大学。而如果你也像我一样不是很优秀，又希望考上全公费另外还有零花钱去旅游得同学，你可以参考。 我的基本情况就是以上那些，在一个普通二本里的三本学习，大家可以想想学习环境，但是我想说，事在人为，只要努力就能改变命运。大学期间担任班长创建社团，连续2年国家励志和一次学校一等奖学金，大学前三年积极参加各种活动，数学建模大赛，IT创新大赛，河南省863软件大赛等活动。专业上领导社团成员并参与三个软件的开发工作。各类级别证书二十多项。我说这些不是炫耀自己，我只是证明，出身在那里不重要，重要的是你努力没有，你奋斗没有，你有没有被现实屈服。我不聪明但我一直在努力。我相信努力可以改变一些命运。所以不论你在那里上学，学校如何，都不要抱怨，而是要问自己是否努力过。Q1：为何选择中科院？ 第一全公费，我的目的很明确，每月1000-2000的补助。远远领先名校奖学金。 第二，就业好，北京的计算所最好也最难考，对我们这样的有点出身歧视。而京外所好点。我报的沈阳计算所，每年毕业不到50人，全部百分之百就业，就在前几天复试时。公寓老师说，你们毕业月薪过万没啥了不起。最好的今年有几个签百度的，据说年薪22w。 第三，复试容易。大学要选导师，这里不用，第一年在中国科技大学或者北京中科院学习一年再回来选导师。复试这几年几乎是百分之百接受。今年生源不好，招收调剂的了，前几年从不招收。所以上线300就能录取。当然这也是我算好的，算定今年分数不高。如何计算，参看我的考研数据分析。 第四，中科院导师每人最多带三个人，一般二个。项目多，做不完的项目。保证培养质量。 第五，无论在那个所上，毕业证学位证全国统一，都是中国科学院授予。没有地方的名字。 第六，生活条件好，除了上学期间不用担心钱不够花外，住宿是宾馆的标间配置，三人间。三个床。缺点：生活单调，有钱没地方花。地理位置偏僻荒凉。不过就在所里一年半，努力学习专业技术也是很好的地方。 Q2：中科院是不是有特殊要求？ 没有任何特殊要求，我们复试很多都是跨考的，比如数学系的，生物的。没有动手能力也不歧视。只要以后肯学，中国科技大学加上中科院会把你调教成专业能手的。相比大学，不用提前联系导师，具有考过初试，就不用再操心的好处。前提分数达到他们所里要求的复试线而不是国家线。 Q3: 能不能推荐几个性比价高的研究所？ 第一，我报考的沈阳计算所。专业研究计算机，数控机床很领先。今年所有学科升级为国家一级学科。首批国家工程博士培养单位。就业100%，就业单位所主页有详细历年介绍。不过分数线比较起伏，但是不管如何都比北京的好考。2013个人预测比国家线多出20分以上，因为今年比较低。估计2014年比国家线多出10分左右。详细情况参考历年数据。 第二，成都计算所，这个单位比较特殊。每年招不满，很大程度上由于专制为企业。其实，研究生培养还是中科院。就业也很好，就是招生的人不如沈阳计算所多。如果你很没有把握，只是抱着过线的心，那就考虑他吧。 中国科学院大气物理研究所 2006年博士生入学试题 《大气化学》(满分100) 一、解释下列各对名词（每组２分，共计４０分） １）干沉降和湿沉降２）光学等效直径和空气动力学等效直径３）气溶胶及 PM 10、PM 2.5 ４）热化学平衡和光化学平衡５）原生粒子和次生粒子６）元素 和同位素７）细粒子和硫酸盐８）反应物和前体物９）自由基和链式反应１０）化学反应速率常数和平衡常数１１）雾和光化学烟雾１２）粒子数浓度和质量浓度13）pH 值和酸雨14）光化学反应和量子效率１５）温室气体和温室效应１６）人工降雨和凝结核１７）爱根核和云１８）酸雨和酸沉降１９）大气寿命和半衰期２０）均相化学反应和非均相化学反应 二、简答题（每题10分，共计20分） 1.写出《京都议定书》明确要求发达国家减少排放的6种（类）人造物质名称和 分子式，并从它们大气化学降解速率和过成的角度说明必须减少向大气排放这些物质的原因。（10分） 2.N 2 O是一种重要的温室气体，主要从土壤排放到大气，消耗于平流层。当前国 际上测量土壤N 2 O排放普遍使用的方法是用一定体积的箱子罩在一定面积的土壤 上，通过测量箱内N 2 O浓度随时间的变化率，从而计算其界面交换通量（单位时 间单位面积的质量）。设在两地分别测量土壤N 2 O的排放，采样箱参数和测定值如下表，请问A、B哪个排放通量大？(提示：使用理想气体状态方程，0 ℃＝273.5 K ) （10分） （t0浓度是指开始罩箱时的N2O浓度；t1是指开始罩箱后的t1时刻N2O浓度） 三、述题（40分，每题２０分） 1.目前城市大气中两种最重要的O 3前体物是VOC和NOx（NO+NO 2 ），下图显示的是 第1页共2页 北京邮电大学2018年硕士研究生入学考试试题 考试科目：计算机学科基础综合 请考生注意：①所有答案（包括选择题和填空题）一律写在答题纸上，否则不计成绩。 ②不允许使用计算器 一、 单项选择题（每小题2分，共80分） 1. 算法分析的作用是 A ．分析算法的效率 B ．分析算法中的输入和输出的关系 C ．分析算法是否正确 D ．分析算法能否转换为计算机语言 2. 设某数据对象(,)DR D R =，其数据元素集合为{}12345,,,,D a a a a a =，关系R 表达为 {}1,|4,3,2,1i i R a a i +==，DR 是 A ．集合结构 B ．线性结构 C. ．树结构 D ．图结构 3. 若线性表最常用的运算是删除第一个元素、在末尾插入新元素，则最适合的存储方式 是 A ．顺序表 B ．带尾指针的单循环链表 C ．单链表 D ． 带头指针的单循环链表 4. 数组通常具有两种基本操作是 A ．插入和删除元素 B ．插入和查找元素 C ．修改和删除元素 D ． 查找和修改元素 5. 已知字符串""pqppqpqp ,它的nextval 数组值是 A ．01021040 B ．01021243 C ．01122240 D ．01122343 6. 一棵二叉树的先序遍历序列为abcde ，中序遍历序列为cbade ，则该二叉树对应的森林 所包含的树的棵树是 A ．1 B ．2 C ．3 D ．5 7. 若高度为n 的二叉树恰有n 个结点，则满足此条件的二叉树树形有 A ．2种 B. 2n 种 C. 12n ? 种 D. 21n ?种 8. n 个顶点的无向连通图用邻接矩阵存储，矩阵中非零元素的个数最少是 A ．2n B ．1n ? C ． n D ．()21n ? 9. 下列关于图的遍历的叙述中，错误的是 A ．图的深度优先遍历不适用于有向图 2.设{X (t ),t ≥0}是独立增量过程, 且X (0)=0, 证明{X (t ),t ≥0}是一个马尔科夫过程。 证明：当12n 0t t t t <<< <<时， 1122n n P(X(t)x X(t )=x ,X(t )=x ,X(t )=x )≤= n n 1122n n P(X(t)-X(t )x-x X(t )-X(0)=x ,X(t )-X(0)=x , X(t )-X(0)=x )≤= n n P(X(t)-X(t )x-x )≤，又因为n n P(X(t)x X(t )=x )=≤n n n n P(X(t)-X(t )x-x X(t )=x )≤= n n P(X(t)-X(t )x-x )≤，故1122n n P(X(t)x X(t )=x ,X(t )=x , X(t )=x )≤=n n P(X(t)x X(t )=x )≤ 3.设{}n X ,n 0≥为马尔科夫链，状态空间为I ，则对任意整数n 0,1 一、微电子学院简介 中国科学院大学微电子学院成立于2013年，以中科院微电子所为主承办单位，中科院半导体所、中科院上海高研院、中科院上海微系统所、中科院电子所、中科院声学所参与共同建设，覆盖从设计、制造、设备和材料等微电子技术领域的绝大部分学科方向，是目前国内综合研究能力最高，设备最完善，学科覆盖最广的微电子学院，也是首批国家示范性微电子学院建设单位之一。微电子学院硕士研究生招生专业包括：微电子学与固体电子学（080903，由微电子所代招）、电子与通信工程（085208）、集成电路工程（085209）、计算机技术（085211）。 2019年预计招收硕士研究生共240人，实际招生人数以当年度下达的指标数为准。微电子学院欢迎并鼓励学习微电子专业及信息与通信工程类、计算机类、自动化类、软件类、光电技术、物理与应用物理学、材料学等相关专业的同学报考。 二、中国科学院大学计算机技术专业招生情况、考试科目 三、中国科学院大学计算机技术专业分数线 四、中国科学院大学计算机技术专业考研参考书目 856电子线路 1、Robert L.Boylestad, Louis Nashelsky（作者）, 李立华, 李永华(译者)，模拟电子技术，电子工业出版社; 第1版(2008年6月1日)，国外电子与通信教材系列 2、童诗白、华成英，模拟电子技术基础（第五版），高等教育出版社，2015年 3、(美)John F.Wakerly 林生葛红金京林（翻译）数字设计:原理与实践(原书第4版) ，机械工业出版社，2007 年5月 4、阎石，数字电子技术基础（第六版），高等教育出版社，2016年 859信号与系统 郑君里等，《信号与系统》，上下册，高等教育出版社，2011年3月，第三版。 奥本海姆等，《信号与系统》，电子工业出版社，2013，第二版。 863计算机学科综合（专业） 1、计算机网络（第七版）. 谢希仁编著，北京：电子工业出版社，2017年。 五、中国科学院大学计算机技术专业复试原则 1、专业考核 重点考查考生大学学习情况及对专业知识掌握的深度和广度，对知识灵活运用的程度以及考生的实验技能和实际动手能力等，了解考生从事科研工作的潜力和创新能力。专业课复试范围：考核《半导体物理》、《半导体集成电路》、《信号与系统》、《电子线路》等方面的综合基础知识，注重基本概念和知识面。 2、英语听力和口语考核 主要考核考生运用英语知识与技能进行听说交际的能力，由我所组织专家进行考核。听力要求考生能听懂日常生活中的通知、讲话、一般性谈话或讨论等。口语要求考生能用英语回答有关日常生活、家庭、工作、学习等方面的问题，并能就某个话题进行连续性的英语表达。 3、思想政治品德考核 思想政治品德主要考核考生的政治态度、思想表现、道德品质等方面的基本情况。 4、综合素质考核 考核考生的工作学习态度、团队合作精神、人文素养、沟通和交流能力等方面的基本素质。 六、中国科学院大学计算机技术专业录取原则以及录取名单（2018） 总成绩＝初试成绩/5×50％＋复试成绩×50％ 其中，复试成绩＝专业考核×95%＋外语测试×5%，复试总成绩采用百分制，60分为及格。复试成绩不合格者，不予录取。同时参考思想政治品德和综合素质考核。同一类型考生的考核优先级按总成绩（初试＋复试）从高到低依次择优录取，体现第一志愿考生优先的原则。 一、软件研究所简介 中国科学院软件研究所成立于1985年，是一所致力于计算机科学理论和软件高新技术的研究与发展的综合性基地型研究所。 作为中国科学院大学研究生培养单位之一，2019年预计在计算机科学与技术(A+)[ 在全国第四轮学科评估中，计算机科学与技术一级学科被评为A+，软件工程（0835）一级学科被评为A-.]、软件工程(A-)和网络空间安全[ 网络空间安全为2016年新增一级学科。]等一级学科招收79名学术型硕士研究生；在软件工程专业领域招收16名全日制专业学位硕士生。2019年预计招收硕士研究生95人，其中推荐免试研究生70人左右。最终招生人数以正式下达的招生计划文件为准，招收推免生人数以最后推免系统确认的录取人数为准。 二、中国科学院大学计算机应用技术专业招生情况、考试科目 三、中国科学院大学计算机应用技术专业分数线 四、中国科学院大学计算机应用技术专业考研参考书目 863.计算机学科综合（专业） 1、计算机网络（第七版）. 谢希仁编著，北京：电子工业出版社，2017年。 考试要求： 1. 掌握计算机网络的基本概念、基本原理和基本方法； 2. 掌握计算机网络的体系结构和典型网络协议，了解典型网络设备的组成和特点，理解典型网络设备的工作原理； 3. 能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计和应用。 五、中国科学院大学计算机应用技术专业复试原则 复试成绩＝笔试（含上机考核成绩）成绩×50％＋面试成绩×50％ 思想品德考核（调阅考生档案或政审）及体检不作量化计入总成绩。有严重违纪记录的即视为思想品德考核不合格。 复试采取分组差额复试，复试与录取比例约为1.2:1。复试主要包括： 1）笔试（机试） 主要考核考生对本学科专业理论知识和应用技能掌握程度，利用所学理论发现、分析和解决问题的能力，对本学科发展动态的了解以及在本专业领域发展的潜力等。各复试组可根据情况增加上机实践考核，分数计入笔试成绩（权重为50%）。笔试考试时间2小时（不含上机考核时间）。笔试（含机试）采取百分制，低于60分为不合格。 2）面试 3）面试主要对考生的英语听说能力、专业素养、创新能力和综合素质等进行考查。每个考生的面试时间一般不少于20分钟，其中英语听说能力测试时间5分钟左右。面试计分采取百分制，其中英语听说测试成绩占10%。面试成绩低于60分为不合格。 六、中国科学院大学计算机应用技术录取原则以及录取名单（2018） 考生总成绩＝初试总成绩/5×60％＋复试成绩×40％ 各组根据考生总成绩，按学位类别分别由高到低依次进行拟录取。优先拟录取第一志愿考生。有特殊学术专长或具有突出培养潜质者，以及在科研和相关实践中表现特别突出者，经复试小组提议（附说明材料），所教育领导小组审核同意，可予以优先考虑录取。 凡具有下列情况之一的考生，均不予录取： l 思想品德考核不合格； l 体检不合格； l 复试阶段，笔试（含上机考核）成绩或面试成绩不合格； l最新随机过程考试试题及答案详解1
北京航空航天大学计算机学院计算机学科专业基础综合历年考研真题汇编
中国科学大学随机过程(孙应飞)复习题及答案
2020年中科院计算机863考研真题回忆
期末随机过程试题及标准答案
中科院计算机经验贴
中国科学院大气物理研究所
北京邮电大学803计算机学科基础综合考试大纲
随机过程试题及答案
北京邮电大学2018年专业课803计算机学科基础综合考试大纲
学期数理统计与随机过程(研)试题(答案)
中国科学院大学2020考研大纲：863计算机学科综合(专业)
中科院计算机研究所考研必看的经验
中国科学院大气物理研究所
北京邮电大学2018年803计算机综合考研真题
随机过程复习试题及答案
2020年中国科学院大学计算机技术考研招生情况、分数线、参考书目、录取名单、备考经验
2020-2021年中国科学院大学计算机应用技术考研招生情况、分数线、参考书目、录取名单、复习经验指导
相关主题
文本预览