08年计算所 专业课 计算机软件基础 试题（考完回忆版）

欢迎各位支持补充，以帮助大家，也从本站获得了许多，回馈大家来了。本人今年是没指望了，唉，闲话不提。
数据结构

开始是几个链表的判断题。记不太清了
链表，有序的和无序的，线性查找，时间复杂度有没区别

选择
判断邻接表结构下图的某顶点的边数，数学式子给出


填空，

hafuman树权值给出，计算平均什么度，就是书了说的那种度。

查找hash表的判断，考到的有线性探测法，链表法，再hash法，（真没想到这节知识点这么重）
快速排序考了两题，一个是给出一堆数，快速排序后某数在第几个未知，一个是快速排序对有序和无序的数组的时间复杂度影响，形如基本有序的数组，完全无序，等等。
那几个排序算法的时间复杂度，就是第十章那个表列出的，要结合每个算法后面上的评论理解来背下。问了好几个空。还有一个是带点变形的


问答题
B-树查找的最大涉及量，在严慰敏《数据结构》老版的241页，要求写出推导过程，10分题。

度为M的hafuman树，叶子节点为n，试问非叶节点数。5分题



算法也是10分，给出数组A[0...n-1],将其中奇数排到偶数前面，不允许附加空间，时间复杂度要求O(n).


编译原理

选择题
从那几个中，语法分析，语义分析，中间代码生成，代码生成，代码优化等中抽出几个，问你哪几个叫做编译的综合？
逆波兰式的判断，有了取负的操作，形如 -a+b*(-d+c)这种。


问答题

画(a|b)*b(ba)*的最小DFA

写出S→aSb|bSa|ab的所有LR(0)项目，判断是否为LR(0)算法。

后面一个是陈意云那本习题上的一个题，就是写出语法制导翻译，101.101=6.625的那个,记不太清，大家知道是形如下面的就可以了
有S→L.L
   S→LR
  n →1
  n →0
   后面记不清，大家去查书吧

操作系统

问答题
试从动态、并发、独立方面比较进程和程序
为什么要引入动态重定位，如何做。

Unix系统的共享方式，Unix的进程影像有哪几部分，说明用途

哪一种CPU调度算法可以避免进程饥饿，为什么？
哪些（看清楚了是哪些）CPU调度算法会导致饥饿，为什么？

N个进程，M个资源，每个进程可分配到x个资源，当有N(x-1)+1<M时，会否死锁，为什么？

关于FIFO和LRU的缺页调度问题，给出了一堆字地址，形如115，216，312，415，共有七八个，每页100字，共300字，让你调度，假设0页已经被调入。计算两种算法的缺页率


P,V 算法问题，在两个缓冲池中的那种，大家去查书看看相似的吧，记不得了。

如果还想到什么，我会补充的。

综合感受，不是去年同一个老师出的题（今年偏重后面的章节）

今年题量大,nnd3个小时不停写才写完,整整写了十页纸!

是啊  做之前感觉纸给得太多了 后来才发现都写满了的  题量真是够可以了
B－树那道题原来书上出现过啊？可恶，我到现在还不会做
另外，09年考的同学考前一定要把历年的真题过一下
印象中有好几题是以前考过的
只是题型不一样，以前的填空选择变成了现在的简答
那道很基础的编程题也是以前出过的吧

[ 本帖最后由 mythSun 于 2008-3-28 09:23 编辑 ]

多多交流啊

[t:26][t:26][t:26]