中科院软件所计算机软件基础笔试

http://159.226.4.200/showdoc.jsp?bid=67&recid=40248&pages=2这个贴子
2006软件基础(469)
(以下内容是根据回忆写的，要是有更确切的题的话，请以其它为准。更希望今年考研的同志们补充，以饷读者。)
一、用LL(1)分析方法和用LR分析方法用下列哪一种文法，请说明理由。
d->TL d->TL
T->INT|REAL T->INT|REAL
L->L,id|id L->id,L|id
二、说出SLR(1),LR(1),LALR(1)所能表示的文法集合之间的关系。
三、给出一段代码及其汇编语言代码，写出在栈中的活动记录的相关内容。
（这玩意儿，我压根就不大懂，所以也就没能记下具体内容来。）
四、某程序有两个头文件：link1.c和link2.c,内容分别如下:
link1.c:
{
int buf[1]=100;//好像是，记不大清了;
}
link2.c:
{
#include<>
#include<>
#include<>
extern int *buf;//其它都记不大清楚了;
我稍微补充一些。
replace int buf[1]={100};

第三题：
void fun(char i,long j) //具体函数名和变量名忘了。
{ char *p;
char ch;
long m[3];

p=&i; //可能有点误差，
m[0]=j;
}

给了副图，习题集上的。

问 变量和ebg 的偏移值和分配的字节数。


操作系统
2 设备分配中有什么分配策略，优缺点是什么。//我写了fifo,最高优先级。
3 文件系统按名查找是怎么实现的。
4 OS 中将中断频繁进程的分配短的时间片，
计算时间多的进程分配长的时间片，问这样有什么好处。]


windous NT 是个大题 10分，应该是单独一个题。

数据结构

3 输入图中边的信息，问构造邻接表的时间复杂度是多少？
O(n*e) O(n+e) //不记得其他的了
4 排序中哪种方法在最后一次前，元素都不在最终位置。 //直接插入排序


第8和第9题间少了一个题
如果没记错，就是05年那个画邻接表的题。
问题：画出邻接表并给出A和其他个点的最短距离。


最后一个编程题
还要求时间复杂度为O(n*n)，并且是无向连通图;




然后,程序运行出现错误：segement ------(core dumped)
请解释原因。



五、1，有一个单片机，n个设备使用，处于就绪、阻塞的设备数目的范围是多少？
2、windousNT操作系统的虚拟分页的实现所需要的数据结构及其作用.
3、
4、
六、
1)给出了一个页面访问序列，判断FIFO和LRU缺页的次数。
2)用哪种方法产生最少缺页次数，（要你写出Optimal算法）
七、选择题：
1、C语言中对于double类型的输入命令正确的是：
scanf("%lf,%lf",&a,&b);
scanf("%lf,%lf",a,b);
scanf("%d,%d",&a,&b);
scanf("%d,%d",a,b);
2、赫夫曼树有N个叶子结点，则其总共有多少个结点？
3、
4、
5、
八、以下程序能否正常输出："hello world",请说明理由。
char *GetMemory()
{
p=char* malloc(100);
}
void main()
{
char* str;
str=GetMem

ory();
strcpy(str,"hello world");
printf(str);
}
九、
1、给出一组数，写出构造成二叉排序树的全过程，并求查找成功时的查找长度。
2、给出一组数，写出构造成小根堆的过程，并写出输出最小元素和次小元素的筛选过程。
3、列出一个A[1..15]的数组，使之用快速排序算法排序效果最差，约等于冒泡排序。
4、23个结点的平衡二叉树的最大深度是多少？
十、
1、由链表组成的三叉堆各元素有四个域：lchild,mchild,rchild和DescNum，分别表示：左子树指针，中间树指针、右子树指针和有多少个子元素。初始时，各元素的DescNum值为0，请写一算法求得各元素的DescNum值，并将其填入到DsecNum域里。
2、有一无向图G,该图中会有环，请设计一算法，删除一些边，使图中没有环，并使删除的边数最少。