中科院计算所06年部分试题（大概题型）
这是部分真题，下载见附件
一、用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)所能表示的文法集合之间的关系。
操作系统
2 设备分配中有什么分配策略，优缺点是什么。
3 文件系统按名查找是怎么实现的。
4 OS 中将中断频繁进程的分配短的时间片，
计算时间多的进程分配长的时间片，问这样有什么好处。]
windous NT 是个大题 10分，应该是单独一个题。
数据结构
3 输入图中边的
信息，问构造邻接表的时间复杂度是多少？
4 排序中哪种方法在最后一次前，元素都不在最终位置。
五、1，有一个单片机，n个设备使用，处于就绪、阻塞的设备数目的范围是多少？
2、windousNT操作系统的虚拟分页的实现所需要的数据结构及其
作用.
七、选择题：
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个叶子结点，则其总共有多少个结点？
八、以下程序能否正常输出："hello world",请说明理由。
char *GetMemory()
{
p=char* malloc(100);
}
void main()
{
char* str;
str=GetMemory();
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,该图中会有环，请设计一算法，删除一些边，使图中没有环，并使删除的边数最少。
