97 GRE CS_SUB 回忆题
（题号、选项次序不全对）
1． 下面哪个16进制玛刻产生0、1交错的二进制串
A．0101 B．AAAA C．FFFF D． BBBB E．1010［Ｂ］
２．数组a[0,…..n]每个元素各不相同，执行如下程序
for i=1 to n do
a[I]=a[n+1-I]
问执行后数组值：
Ａ．与原值相同
Ｂ．每个元素各有两个拷贝
Ｃ．与原值为倒序关系［Ｂ］
３．哪个不是ＮＰ－Ｈard problem?
A．３－color着色Ｂ．４－color着色Ｃ．有权图中两点最短路径
Ｄ．货郎担［Ｃ］
４．函数f接受一个二元算符和二进制数，按以下规则运算：
从输入中最左边截取两位进行该算符运算，结果放到输入的最左断和输出的最右断，直到输入串为空．
例．F(XOR, 101101)运算时输入串变化如下：
１１１０１
０１０１
１０１
１１
０
则输出为１０１１０．则f(XOR, 10011)=
A．10111 B．11101 C．10011 D．11001 E．? [D]
５．f同上题，若f(XOR, x)=101，则x可位：
Ａ．0011 Ｂ．1101 C．1000 D．0101 E．1011 [E]
6．下图中，输出Ｙ的值＝Ｘ的概率是（设a b c d是随机变化）：
a
b Y
c
d
A．100% B．75% C．50% D．25% E．0% [A]
7．用ＰＶ操作使对变量x的存取互斥正确的是：
Ａ．Ｐ；access(x)；P B．V；access(x)；P Ｃ．Ｐ；access(x)；V [C]
8． =
A．θ(nk) B．θ(nk＋１)Ｃ．θ(nlogn) D. θ(kn) [B]
9．对一数列，求最小值，哪个结构不合适？
Ａ．有序链表Ｂ．有序数组Ｃ．搜索数Ｄ．Ｈash表Ｅ．ＡＶＬ数
［Ｄ］
10．程序的循环不变式是什么？设数组a(1….b)的原元素值为a0
k: =1
while k<>b d0
begin
k: =k+1
a[k-1]:=a[k]
end
I．k<b
II．对１≤i<k, a[i]=a0[i+1]
III．对k+1<i≤n, a[i]=a0[i]
Ａ．II,III only Ｂ．I,IIIonly Ｃ．II only D．I,II,IIIonly [C]
11．以太网上发帧的冲突概率为C，用重发来解决，设每次重发的冲突概率互为独立，则平均发出一正确帧之前已发出了几个错误帧？
A. C/(1-C) B. (1-C)/C C. 1/(1-C) D. 1-C E. C [C]
12．有以下程序：
program prog;
var
a:array[1…3] of integer;
j:ingeger
procedure p(x,y:integer);
begin
x:=x+1;
j:=j-x;
y:=y-x
end
begin
for j:=1 to 3 do a[j]:=j;
j:=2;
p(j,a[j]);
writeln(a[1],a[2],a[3],j);
end
若参数传递是by-value,则输出为：
[1，2，3，-1]
13．对上面的程序，若参数传递为by-reference，则输出为：
[1，2，3，0]
14．下列程序计算斐波那契数
f(N:ingeger; var f, f1:integer);
procedure
var t:integer
begin
if N=2 then
begin f:=1; t:=0 end
else
begin
f(N-1,f1,t);
f:=f1+t;
end
end;
问，对调用f(N,y,f1)，递归次数是：
A．θ（N） B. θ（CN） C. θ（NlogN） [A]
(C是常数)
15．对上题，问y与N的关系是：
A. θ（N） B. θ（CN） C. θ（NlogN） [B]
(C是常数)
16. 哪个产生memory leak?
A. p:=nil; new(q); p:=q;
B. p:=nil; new(q); q:=p;
C. p:=nil; new(q); p:=nil; [B]
17. 有下面浮点数格式：
值为：?
则
表示：
18．哪个数不能用上题格式表示：
A. 17 B. -3.5 C. 0.1 D. 0.75 E. 0.25 [C]
19. 实用中通过加优先规则来用LR处理二义反法的目的：
I. 二义反法只产生两种语法树
II. 二义反法可能使分析表状态较少
III. 二义反法可能有较少的产生式 [II III]
20. System崩溃可能使在内存中实用缓冲区的文件系统产生不一致，如何解决？
I. 增加缓冲区大小
II. 缓冲区加倍III.
IV. sidk有自动写多块的功能 [III]
21. 哪个自动机识别语言L: （#a+2#b）mod 3=0? (#a表示a的个数)
①
A. a b b a B.
b
② ③
a
22. 函数式语言：（set n=1 in (set f(x)=x+n in
set n=2 in f(17)）））
则：
Ａ．在静态scope和动态scope下，都有f(17)=19
B. 在静态scope和动态scope下，都有f(17)=18
C. 静态scope:f(17)=19, 动态scope f(17)无定义
D．静态scope:f(17)无定义，动态scope f(17)=18
E．均无定义
23．为使f(x,y)+f(x,y)运算时间减半，怎么编译伏化？
A. 代码处理 B. 拷贝传播 C. 消除子代表示 [C]
24. 有下面程序：
⑴ a:=1
⑵ while a<n do
begin
⑶ a:=a+1
⑷ if odd(a) then
⑸ a:=b
end
用（a,difine,use）表示对变量a的define-use使用。下面哪个不是difine-use?
A.(a,1,3) B. (a,3,3) C. (a,5,3) D. (a,5,4) E. (a,3,4) [D]
25.动、静态类型检查区别为：
I. 静态编译慢，II. 动态执行慢
III. 静态全检查，IV. 动态只检查执行的部分
V. 静态代码长，VI. 动态代码短
A. I II B. II III C. I D. II
26.一般来说，RISC没有哪个特点？
A. 和内存有关的指B. 令只有load,store
C. 运算指D. 令只和寄存器有关
E. RISC编译器较简单
D.
F. integer instructior 一样长
27．Language L是undecidable，则
I． is undecidable
II．L包含在一个recurive的语言中
III． is recursive
28．RISC机指令格式 opcodc Rdost， Rsource1，Rsource2
功能： Rdost=Rsource1 op Rsource2
程序如下：
mor R4, …
mor R0, …
mor R1, …
mor R2, …
call p
load R3, …
add R4, R4, R0
add R4, R4, R3, R0,R?, R4
p: mul R0, R0, R0
mul R1,R1, R1
mul R2,R2,R2
add R4,R1,R2
add R0,R0,R4
return
有两种方法保存寄存器的值在调用中不被破坏, ①调用者保存调用后要用的②被调者保存自己使用的
两种方法都要保存的寄存器是:
A. R0,R1,R2 B.R1,R2,R4 C.R4
29. 上题中求a[i]的值，a初值为10000000，i在R2中不可被破坏，每个元素为4个字节，怎么编程？
A. mov R0, 10000000
mov R3,R2
shl R3, R3,2 (左移两位)
load R1，（R0+R3）
30．
CPU CPU CPU CPU CPU CPU CPU CPU
Cache命中率为95%，剩下的有90%在Cache memory中找到，其余全可在Memory中找到。
CPU每秒发107个访存请求，问Memory每秒收到多少个？
31．已知bus每秒可容。。。个请求，问bus繁忙程度是：
50%
32．哪个错？
A． L1可被DFA识别，B． L2可被DFA识别，C． 则L1∩L2可被DFA识别
D． L1可被NFA识别，E． L2可被NFA识别，F． 则L1∩L2可被NFA识别
G． L1是上下文无关的，H． L2也是，I． 则L1∩L2也是上下文无关的
33．某程序输入需5秒，必须串行，计算需16秒，可以并行，输出需10秒，并行时可利用5个CPU很好的并行，但不能利用更多的。
问：串行时间与在16CPU System上运行时间比为：
45/7
34．单链表，有头尾指针
h t
实现下列结构所需时间？
I．Stock II. Queue III. 优化Queue,每次取min.
35. 设有语言L,O的个数是12的倍数,l的个数是10的倍数,识别它的DFA需几个状态?
A. 12 B. 10 C. D. E 120 [E]
36. n个状态的NFA,转换成DFA,状态必不超过
A. n B. n2 C. 2n D. nlogn E.2n [E]
37. if P≠NP, then:
I. SAT is P II. is P III. SAT is NP [III]
38. 用reference count回收无用单元,执行P:=Q时,要按顺序做什么?
A. P所指B. 的,ref count减1, P:=Q, Q所指C. 的,ref count加1
39. 测试时,有如下3种程度
I. 语句穷举:每个语句都被执行过
II. 分支穷举:条件转移的不III. 同IV. 分支都被测试过
V. 表达式穷举:每个表达式都以不VI. 同VII. 的值被测试过(表达式在分支语句或赋值语句中)
则3者的关系是:
II包含I. III与I II无包含关系
40. 几个并发执行的任务的某个执行顺序如果和某个串行执行顺序的结果是相同的,则称之为可顺序化的.用R2(x)表示任务2对x的读操作,则下面那个执行是不可顺序化的?
I. R1(x) R1(x)W1(Y) W1(Y)
II.
II. R1(x) R1(Y) R2(Y) W2(Y) W1(Y)
41. A. (p q) (7p q)
B. (p q) q
则问公式A.B是否可满足?永真? 或永假?
