中科院计算所06年部分试题

松花江里的鱼

中科院计算所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,该图中会有环，请设计一算法，删除一些边，使图中没有环，并使删除的边数最少。
海文专业课 http://www.VIPkaoyan.com/

松花江里的鱼

海文提供！