2004年中科大软件基础试题(回忆版)

　　2004年中科大软件基础试题(回忆版)

　　2004年中科大软件基础试题(回忆版)，不全，待续

　　操作系统：

　　一、简答(20)

　　1、进程和线程的特点，各自的优缺点。

　　2、系统调用的过程及设计时需要注意的问题。

　　3、内碎片和外碎片的区别

　　4、举个采用动态优先级调度算法的实例

　　二、(10)

　　1、LRU和LFU概念及各自需要的硬件支持

　　2、给定一个页面序列(具体序列记不住了)，要求用LRU 和CLOCK算法写出调页的过程及页面中断的次数

　　三、综合分析(10)

　　大概是给出CACHE ，内存，外存的性能和价格，再给你若干MONEY(似乎是3000)让你组合出性价比最高的机器(题目大概这么个意思但具体我实在记不住了，因为我就没怎么做这题)

　　编译原理：

　　1、(10)给一个文法让你写出其LALR(1)的项目集，并据此说明它是LR(1)而不是LALR(1)的。

　　2、(10)给一个文法写语义动作

　　以上两题很基础，不难，把陈的习题集相关内容搞定就完全可以了

　　3、(5)与类型检查相关，题目记不住了

　　4、(5)类型检查题，C语言相关

　　3、4两题我几乎是白卷，所以别怪俺了，俺也不会做

　　数据结构：

　　一、判断(12)：

　　6道，都很基本，只记得最后一题是：所有O(N平方)的简单排序算法都是稳定的。

　　二、简答(48)：

　　1、顺序表的查找时间是否仅与其所在位置有关?

　　2、有向图可以采用三角矩阵存储，问是否一定无环?

　　3、哈夫曼编码相关，求编码最短长度

　　4、给一个邻接矩阵，画图，并求最短路径，好象没要求哪种算法。(8*8，个人觉得出题老师真有个性)

　　5、给一个二叉排序树的先序序列(序列忘了)，画出该树。(好象题目有问题)

　　6、忘了

　　三、算法设计(20):

　　1、求二叉树第K层的结点个数

　　2、同时找到一个一维数组中的最大最小值，要求空间复杂度为常数，最坏时间<= 3/2*n