根据回忆录入，不好意思，有些csdn的文档中心不兼容。
1.
求f
For I=1 to n
A[I]=a[n+1-I]
求循环后数组值，每个数都有两个拷贝
什么叫amdahl（字迹模糊，不确定）法则
Amdahl法则
在计算机编程的并行处理程序中，少数必需顺序执行的指令是影响性能的一个要素，即使增加新的处理器也不能改善运行速度。这就是Amdahl法则。有人正是在这一点上对并行处理提出了挑战。一部分人认为，并行处理擅长的是那些增加处理器个数就能提高吞吐量和性能的大问题。
判断是否
NP
判断C、D等价
判断C是否存在输入使之输入为真
判断C可缩减（是否已经最小化）
均为NP
RSA是基于整数分解的什么性质：
假如存在整数分解的更好法则，则此方法的安全性下降。(√)
该方法基于一个未被证明的基础：RSA的强度等价于大数分解。
该方法基于整数分解及逆运算的运算量的差别。
牛顿迭代有效数字位数的增加速度。
给出牛顿公式：……….
每次增加一位
每次增加2位
每次double? 如xn-a=0.001,则xn＋1-a=0.00001(√)
S→A
A→AA|0
问00000有多少种分析树
I. 10 II. 14 III. 24 IV.72
下面哪个不是线性计算的
求连通子图
求双连通子图
求单源点最短路径
求各定点的度
求生成森林
那些是多线程特点
自己的栈与上下文
自己的地址空间
共享文件与数据
哪些是专家系统的推理方法
由已知的结论推出事实（向后推）
由已知事实推出结论（向前推）
由已知结论，由用户给出事实，推出矛盾或已知事实。
(II III)
多线程要调用函数fill填充一块buffer，返回指向buffer的指针，fill放在临界区中，问下面哪个可以保证互斥。
Buffer是全局变量。
Buffer是调用者的局部变量，把buffer的指针传给fill。
Buffer是filll的局部变量，返回指向buffer的指针。
RISC指令定长: |opcode|RA|RB|offset|
RA←(RB+offset)
寄存器数加一倍后，问寻址空间的大小的变化。
I. ×4 II. ×2 III. 不变 IV. 除2 V. 除4
调用者或被调用者都要保存的寄存器
在RISC机中，保存寄存器值可由调用者或被调用者保存，问下面程序中，哪个寄存器在这两种方法中都被保存。
给出数学公式，问下面5段程序的哪段符合功能。
a[i]=(i2+1) mod n
x=seed; y=x; seed是初值
do
x=a[i];y=a[a[y]]
while x!=y
问
I) 始终中止（√） II) 和n及seed有关 III) 之和n有关
问哪个与log n同阶
T[n]=T[n/2]+1
T[n]=T[n/2]+log n
RAW读后写，哪个会产生I写数据然后了读
WAW
WAR
流水线机没有数据直接通路（Data forward）
问哪种情况需要停机等待
流水线在何时检测中断
每个时钟周期
流水线为空
每个转移指令发生的时候
7个处理器每个可以和相邻元交换，问排序的best lesser live（任何排序方法）最好情况
a) 2 b)3 c) 6 (√) d) 24 e)42
Hash线性探测，函数是 i mod 10
给17 28
添Hash表
何时为真
当且仅当其中两个变量为真时，为真。
C++抽象基类，问哪个是不对的（虚基类和抽象类不一样）
Virtual center () = 1/2*( L()+R())
Virtual int L()=…..
Virtual int R()=…
U()=…
D()=…
I) 不能生成实例 II) 它的继承类必须保持center的行为。
它的继承类必须定义L….
Knapsack问题（背包问题）
I）这函数不满足前后断言 II) 满足而且是多项式时间
III) 满足且为指数时间 IV) 此程序不终止
Krusal是哪种算法的一种
I) 贪心 II） 分枝界限 IV) 二分法
n(5/4)、nlog n, n*e16
哪个增长最慢
call by value,(考传值)求程序结果
12 3
call by reference（考引用），求程序结果
31+3
A=0m1n(m小于等于n), B=0m1n(m大于等于n), B→0B
A＋B是正则的
A∩B是上下文无关的
A，B都是正则的。
{XX|X∈L}是否也∈L
L是正则
L是上下文无关
L是递推可枚举
not true (不全，五个选择)
a和b正则，则a∩b正则
a和b上下文无关，则a∩b上下文无关
若A可数则B可数，若A有限则B有限
若B可数则A可数，若B有限则A有限
冒泡排序，1……i,排序到i,问A[i]与A[i+1]交换的概率。
a) 1/2 b) i/(i+1) c) 1/n d) n/2
多线程系统如UNIX,NT,VMX,哪些依靠中断
I/O
任务切换
缺页
缺页的块数比 TLB 缺页 的少（不全）
Translation Lookaside buffer
page fault比cahe missing 少
page fault比TLB missing少
页表在虚存里，地址转换时最大缺页次数
不缺页
一次
两次
三次
三次以上
问下列哪个不能用以上形式表示， 表示浮点数 S|E|F
(-1)s(1.F)2e-127
a) 100 b) 15.5 c) 0.1 d)0.25 e)0.0625
-14.5 1|1010|1101
把以上浮点数代入数学公式求值
哪个相对误差大
A*A+B+C b) A*A-B*C c) A*A*(B+C) d) A*A/B*C
SQRT(A*A+B*C)
链表的两种实现
两种插入 每插入一个就排序
把插入的放在一个临时队列里，查找时用merge，再与原来的队列归并。
有n个元素，插入m个元素，最后查找一次，问时间复杂度。
O(m(n+m))
题同上。问第二种插入法的时间复杂度
O(m+n)log(m+n)
O(m(log(m+n))
给了两串数列，问第二个数列是第一个数列哪种排序的中间结果。
表示通用信号灯最少用几个二值信号灯。（n值）
I) log2n II) n III) n2 IV) n!
问哪个x是一直被正确加1, P,V均为二值信号灯
（P X=X+1 V）
求Feb数列f-f1+t执行的次数
问递归的次数 O(n)
接上题 f跟n的关系
cn b) n2
main
P
Var x
R
End {p}
Q
考Pascal调用的嵌套关系。
接上题 用静态指针要dereference多少次（考静态链）
完成功能insert(**p X) C++程序 问哪个错
利用内存引用技术 废物收集，想完成P=Q、P、Q均为指针
引用什的
（P的引用技术，Q的引用技术＋1）
长度为5 的有几种
接上题 长度为2n+1的有多少种
（指数）
一个自动机，给出状态转换表。有一个未知状态，要识别一个字符串，问
输入0,转到哪个状态。
设n>2的有限自动机所接收的最小长度字长度。
i) 1 ii) 1< <n iii) >n <2n-1 iv) 2n< <n2
insert , delete , find
问哪种数据类型实现这三种最快
平衡二叉树
E→E*E E→(E)
E→E+E 算符优先
问以下哪个不对
E*E * shift
"×(P(x)ÇQ(x))与哪个等价
~X(~P(x)È~Q(X))
"× P(x) Ç Q(x)
"×"y (P(x) Ç Q(y))
二叉树，问最少节点数
L是叶子数，S为有单孩子的结点数
F为有双孩子的节点数
2L－1
哪个正确
2L-1=
全对
E® FÉE|T
F®
T®not T 问哪个对
I not左结合
II É优先级低于not
III É右结合
Page变大会导致
内部碎片少
页表entry变少
保护粒度粗
f(x,y)+f(x,y)使计算时间减半，可以采用以下什么编译优化算法
（消除子表达式）
选择有 拷贝传播，代码外提等
动态类型检查，静态类型检查
编译时间长，动态执行时间长
静态全部检查
静态代码长，动态代码短
3种操作使P指向R
int *P
int **Q=&P
int R
*P=R
*Q=&R
Q=*P
调用必须做的事
保存程序计数器
屏蔽中断
保存寄存器
a(b*c)* 不能推出
bb
以0 1开头and/or 以01结尾有多少种，长度是10的字符串个数
a和b之差是17 的整数倍
这一关系符合
I) 自反 II)对称 III）传递
slice A[100,50] 求A[i,7] （在二维数组中的序号）的地址
address(A[i,j] -50+50j
临界区可用于
I/O设备
共享内存
下面哪个不能加快流水线
展开循环
将程序改为过程调用
