中科院计算机所试题
- 格式：docx
- 大小：34.07 KB
- 文档页数：20
1 / 20
中科院计算机所试题
中科院计算所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 * func ( )
{
return(a);
}
在linux上用gcc编译报告:第6行warning: return from incompatible
pointer type
(2) typedef int A[10][20]
A a;
A *func( )
{
return(
}
无类型方面错误
(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,
}
main( )
{ 2 / 20
func( );
}
结果：134518112，134518192，134518912
第二部分操作系统（40’）
五. 1、操作系统内核有强内核和微内核，unix是前者，windowsNT是后者，简介微内核比强内核的优点。（4?）
（强内核：弱内核：各自优缺点：）
2、若只有进程控制，其独立性表现在？引入线程后，独立性有何改变?（4?）
3、请求调页存储系统确定页面大小的标准（4?）
六、1.死锁的证明，在m个同类资源，n个进程共享它，每次进程只能获得或释放至多一个资源，问会不会
发生死锁，若：(1)、设每个进程所需资源数为ri 1rlink=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分)在用除余法作为散列函数、线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不致于断裂。 3 / 20
中科院计算机技术研究所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; iS(S),
S->ε /*空产生式*/
试写出一个语法制导定义,它输出配对的括号个数. 4 / 20
五.(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.详述在设有快表的请求分页存储管理系统中,一个虚地址转换成物理内存地址的过程.
