2008年上海交大计算机817计算机基础(I)70%真题（转载）

转载自：http://bbs.sjtu.edu.cn/bbstcon?board=KaoYan&reid=1200876999
os:比较深刻
名词解释
临界区
Copy on Write
工作集模型
辨析
inode放在固定位置有利于加快小文件访问
多道程序设计目标之一是当进程就绪就可立即得到运行
Buddy系统采用最佳适配
系统调用总是由正在运行的程序引起
打开文件由I/O用户无关层实现
缺页是软中断

cp：计算量大
未定义变量，语义错误
活前缀abcd，应为c
n DOM m且m DOM n，则m=n，反对称关系
删除公共子表达式，局部优化
DFA:(a|b|c)*a(a|b|c)
算符优先：
S->aAa
A->bB|c
...
LR(1):
S->V=E|E
E->V
V->x|*E
DAG:
忽略
三地址代码：
if(a and b or x < 10) while (f[i+1,j]<100)f[i+1,j]=f[i+1,j]+1;else x=x+1;
DS:
容易
20分程序题1：判断二叉分类树
20分程序题2：查找二叉分类树中节点，找到则count域+1，否则建立节点，令count域=1
13分链表程序题填空：
已知无头结点链表，L指向首节点，P指向中间节点，求：
a)将S插入P后：
s->next = p->next;
p->next = s;
b)将S插入头节点之前，并令L再次指向头结点:
s->next = l;
l=s;
c)将S插入在最后一个节点之前
while (p->next != NULL) p = p->next;
q=p;
while (p->next != q) p = p->next;
s->next = p->next;
p->next = s;
n个节点的二叉树有几度2分
5个时间复杂度5分
有：深度广度优先遍历（n个节点e条边）
插入排序平均和最好
逐个读取输入建立有序链表
二叉分类树插入平均和最好
选择题3分
A二叉树中序末节点=前序末节点
B二叉树前序末节点=中序末节点
C二叉树中序末节点若为叶子=前序末节点
D二叉树前序末节点若为叶子=中序末节点
C入选

谢谢！[s:2]

这个好啊，题型都有了，不过不知道09年考什么

非常感谢楼主~~~

非常感谢楼主~~~

版主，我想考计算机基础2，难度比基础1大吗？

版主，您有上交电院的计算机专业课课件吗？