1. In-Order表达式到Post-Order表达式转换的最佳工具是：
A. Array B. List C. Stack D. Binary tree E. Hash table
2. 以下哪些集合是完工的（用他们的组合可以表示所有的逻辑运算）
A. {⌉, ⋁} B. {⌉, ⋀} C. {⌉, ⊕}
3．关于WORLD WIDE WEB(WWW),下面哪些说法正确
A. WWW is a satellite-connected network that connects computers world wide.
B. WWW is a computer-mediated network.
C. WWW is associated with a group of software that work on computers which are connected to the Internet.
4关于packet switch network ,哪些正确
A The packets of the same message must follow the same route
B the packets of the same message may arrive out of order
C node A and node B must establish A独占的connection before A can send packets to B
5What is the value of A and B if Q is to be forced to be 1?
A A=0,B=0 B.A=0,B=1 C.A=1 B= 0 D. A=1 B=1 E none
6template ,overload ,isomorphic function 与下面三个概念如何分别对应
A a module which can be initiated with a type so that it can generate modules of different type
B a function that can be different operations in different contexts
C a function that can take arguments of different type in different contexts
7对一个simple, connected, acyclic , weighted graph 求最小生成树，设
1） e是所有边中权最小的边 2）f是除e外所有边中权最小的边
A e,f在所有生成的最小生成树中
B e在所有生成的最小生成树中，f可能不在其中某些树中
C e 可能不在其中某些树中，f可能不在其中某些树中
8？的数量级为
A O(logn) B O(nlogn) C O((logn)2)
9.若Ｐ≠NP,那么下列哪一条可保证问题k无多项式解
A K∈P B K NP C K可多项式规约于SAT D SAT可多项式规约于K E K可多项式规约于某一NP问题
10~11某structure,每个可包含两个link,link值为null或指向另一node, link值不能指向本node, these structure are noe necessarily connected. 设共有2N+link为null，节点数最少为
A? BN/2 CN-1 DNlogN E N
若一个节点至多有一个link指向它，节点数最多为：
A N B2N-1 CnlogN+1 D2(N-1)
12. 初始时，A=B=0,问AB序列如何随时钟变化
13. 若文法L的判定问题为NP-Complete，可知有
A. L的判定问题有多项式解法
B. 的判定问题有多项式解法
C. L可多项式规约至多项式解法
D. 不E. 能期望得到L判定问题容易的解法
14. Odd-Parity Checking技术可用于计算机图形学，当将它用于多边形时，有以下结论：
A. 将得到稳定连续的输出
B. 将得到杂乱令人不C. 安的结果
D. 得到需填充的多边形的边
E. 将降低图形的分辨率
15－17. 一个BAG的NEW INSERT REMOVE算法如下
bag newbag(){
bag b = newbag();
b -> tail = NULL;
return b;
}
bag insert(bag b, int x){
bag temp = newnode();
temp -> data = x;
temp -> tail = b;
b = temp;
return b;
}
remove(b, int x){
/*该函数中题中未给函数体，只给出了：
precondition: b为一链表，可能有或没有X；
postcondition: 若b能分解为不含X的链表b1，含X节点与链表b2的concatenation, 返回b1与b2的concatenation, 否则返回b;*/
15. 对remove(bag b, int x)的断言正确的是：
A. 若X在b中，B. remove 函数将删去所有含X的节点
C. b为空链表时返回空链表
16. invariant定义为：对初始化函数之外所有对该对象操作的函数皆成立，bag对象的invariant为：
A.
B 存在整数K，对b作K次求tail域操作将得到NULL
D. b中不E. 含重复F. 的元素
17. remove 函数的一种实现如下：
bag remove (bag b, int x) {
bag temp = b;
1 while ( temp -> tail -> data != x) do temp -> tail;
2 if ( temp -> tail && temp -> tail -> data == x)
3 { delete ( temp -> tail);
temp -> tail = temp -> tail -> tail;
}
}
应作哪些修改
A. ①改为 while ( temp -> tail && temp -> tail -> data != x)do temp -> tail;
B. ②改为if ( temp -> tail -> data == x)
C. ③改为（？）
18． int I;
sum=0.0;t=1.0;
for(I=1;I<10;I++){
sum = sum + t;
t = t*2.0;
printf(“%f”,sum);}
问最后一次输出的值与下面那个数最接近A 5 B 7 C 9 D 11 E 13
19．一种pipeline共4个stage，取指，取操作数，执行，写回，每个stage用一个clock下面一段代码需多少clock?
R1 = R2 + R1;
R3 = R1 + 1;
R5 = R2 + 1;
A. less than 5 B. 5 C. 6 D. 7 E. more than 7
20. 若L1, L2为3型语言，哪些正确
I. { x y | x∈ L 且|x| = 2|y|} 为3型语言
II. { x y | x∈ L 且|x| = 2|y|} 为2型语言
III. { x y | x∈ L 且|x| = 2|y|} ∩L1∩L2 = ф
A. None B. I C. II D. III E. All
21. 对于平衡二叉树实现词典的INSERT、Delete、Find操作的最坏情况复杂度，正确的是
A. 至少有一种为常数时间
B. 多于一种为常数时间
C. 三种都是0（nlogn）
22．Heap-Sort，正确的是
A. 它的最坏情况复B. 杂度为0（nlogn）
C. It sorts in place
D. It’s average time complexity is more than a constant’s time faster than it’s cost
23. 某一元素有K个域，每个域可取值0或1，一个table地定义为，对每个域均有确定值，要得到105个不同的table,K至少为
A. 5 B. 10 C. 40
24－25. 一个activation record 的格式为
θ %fp
-4 return address
-8 static address
-12 arguments ( if any) followed by local variables
程序段 procedure P
var a:int;
procedure Q(var int x)
begin
x := x + a
end
begin
Q(a);
End
24. 在Q中，读取x值得操作将译为下列哪段机器代码
A. mov t0 -12(%fp)
B. mov t0 -12(%fp)
mov t0 θ(q ＋ 0)
C. mov t0 -12(%fp)
mov t0 -4(%t0)
25. Q中，读取x值的操作将译为
A. mov t1 -8(%fp)
mov t1 0(%t1)
B. mov t1 -8(%fp)
mov t1 -4(%t1)
C. mov t1 -8(%fp)
mov t1 -8(%t1)
D. mov t1 -8(%fp)
mov t1 -12(%t1)
26. IO设备用cycle stealing方式传送数据，总线107MHz,一次可读4byte(32bit)的word，若接了一个28Kbps(bit per second)或3600 byte per second的modem站用了多少CPU时间
A. 40% B. 1% C. 0.4% D. 0.1% E. 0.01%
27.?题目
A该浮点表示法不能表示6 B做加法时，求mantisa不用考虑operand 的符号
C做乘法时，求mantisa不用考虑operand 的符号
28. 对于2’s complement,不正确的是
A. overflow/underflow can be checked easily
B. 能表示的负数多于正数
C. θ的表示不D. 唯一
E. adding don’t have to check operands’ signs
29. float sum = 1.0; j ：＝ 0.1；
int I;
for (I=1;I 10;i++)
sum = sum - j
printf(“%f”,sum);
若输出不为0，原因是
A. sum and j should use double float
B. a machine error happened
C. 0.1 can’t be represented accurately
30. 下面哪个原因不会引起flushing of pipeline:
A. I/O interrupt B. page fault C. cache missing D. Invalid instruction
D. divide by 0
31. 对于图，正确的是
I. 它是Hamiltatien
II. 它是Euler图
III. 它是planar图
32．若某算法用10ms可实现106个词条的最坏情况查找操作，查4×106个词条需时
A. 11ms B. 40ms
33. 若 是这样的语言：串中θ的数目m可被12整除，且m = 4（mod 10），识别L的DFA最少需多少个状态
A. B. 12 C. 24 D. 48 E. 60
34. m, n都为很大的整数，m < n,下面哪个问题是已知最难解的
A. m是否整除n
B. 求m, n的最大公约数
C. n是否为完全平方数
D. 求最大的q < m使q整除n
35. 有一边长为2的立方体C, 内有一球形空间S，若C中均匀分布的100个点有s个落在S，求S的体积
A. S B. s/100 C. 2s/100 D. 4s/100 E. 8s/100
36. 下面哪些是进程死锁的必要条件
A. hold & wait
B. circular wait
C. no preemption
37. 若两进程同时操作某共享数据，最后结果取决于他们执行操作的顺序，这种现象的
A. mutual exclusion
B.
C. racing condition
D.
E. dead clock
38. 通常compiler不直接生成I/O机器指令，而是generate call to function that will invoke：
A. run-time system
B. application system
C. data managing system
D. co-processor system
E. real-time system
39.
Begin P(x); P(y); A := a+1; B := b+1 V(y); V(x); End Begin P(y); P(x); A := a+1 B :=b+1 V(x); V(y); End;
X, Y为二元信号量，则
A. A和B必将死锁
B. A和B有时将死锁，C. 但并不D. 总是死锁
E. A和B总是引起corrupted data
F. A和B有时引起corrupted data
40－41. 某问题的解法为
1 将问题用O(n)的时间分解成3个大小n/2的子问题
2 递归地解问题
3 用O(n)时间把子问题的解集合起来
40． 这种解法是：
A. Dived and conquer
B. Greedy
C. Back track
41.这种方法的时间复杂度是
A. O(n)
B.
C.
D.
42.
递归版本：function (int *p){ int x; x = *p; …… …… p = &x; F(p); ….. } 非递归版本：function F(int *p){ int x; x = *p; L: …. … p = &x; goto L; }
一下哪些正确
A. p和&x will reference the same location in the recursive version
B. p和&x will never reference the same location in the recursive version
C. 递归版本所用空间大小总多于非递归版本
43. 给出一中序遍历树的算法，求其具体树的节点遍历顺序
44. 在题43的算法中，所需栈高度与什么有关
A. 树的节点数
B. 树的叶子数
C. 树的高度
D. 树的最左儿子深度
E. 树的最右儿子深度
45. 下面哪个式子的结果的相对误差可能达到单个操作相对误差的5倍以上
A. x = x + y + z
B. x = x * y * z
C. x= x * y / z
46. 若区间[a, b]上的多项式函数f有 f(a)>0, f(b) < 0，则：
A. 二分法求根一定收敛
B. 二分法和牛顿叠代法都收敛时，C. 二分法收敛较快
D. 用二分法求根需要求f的导数
47. 求Ax = b的根时，若A0x = b0, A1x = b1两方程中A0,A1的detriment分别近似于0和1，则：
A. 用A0求根速度更快
B. 用A0求根比用A1的相对误差大
C. 用A0比用A1在计算时容易溢出
48－49 ，其中EE为？操作
*高于EE,高于+， +，*运算为左结合
48. 下列说法哪个错误
A. id∈FIRST(E)
B. id∈follow(E)
C. *∈FIRST(E)
D. *∈follow(E)
49. 下列动作，哪个错误
栈状态 Lookahead symbol 动作
A. E + E + 规约
B. E + E * 移进
C. EE + 移进
D. E + E id 移进
E. E * id 移进
50. 一个6面骰子，掷两次相加的和为7的概率是
A. 1/7 B. 1/6
51. A[1, 100]中放100个不同的数
for I = 1 to 100 do
begin
temp = A[I]
for j = I+1 to 100 do
begin
A[I] = A[I] + A[j]
A[j] = A[j] + temp +1;
End
End
A. A[1…100]中仍为100个不B. 同C. 的数
D. A[1] is dividable by 100
E. A[1…100]中只有30个不F. 同G. 的数
52－53. n为2的幂
for I := 1 to log n do
for j := 1 to do
A[j] := A[2*j-1] + A[2*j]
52. A[1]中最后为
A. ..
B.
C.
53. 若上述程序在n个并行处理机上运行，其中第k个处理器做 for j:= 1 to 2n/j中第k个loop，则算法时间复杂度为
A. O(log n)
B. O(nlog n)
54-55某虚有地址如下组织
segment page Byte
31 21 20 12 11 0
54. 它可以存取：
A. 256个大小为4096byte的页
B. 512个大小为2048byte的页
C. 1024个大小为1024byte的页
D. 2048个大小为512byte的页
E. 1024个大小为256byte的页
55. 若要取第18段第256字节，虚有地址应为
56． Test-and-set可用于
A. unconditional jump
B. conditional jump
C. mutual exclusion
57. 若set-assaciative cache, 若s为某一页在cache中映射到的set,采用LRU算法，那么？
A. 整个cocle中最近最少使用的页
B. 整个cocle中改变最少的页
C. s集合中改变最少的页
D. s集合中最近最少使用的页
58－59用数组实现集合三种方法
I. 元素are unsorted, may have redundant copies
II. 元素are unsorted, don’t have redundant copies
III. 元素are sorted, don’t have redundant copies
58. 计算集合的事实那种实现最好
A. I
B. II
C. III
D. I与II相同E. ，F. 优于II
G. II与III相同H. ，I. 优于I
59. 求某些元素是否属于集合时，哪种实现最好（选项同38）
60． 以下这些形容词描述的是high-speed latch data dependency, data and control dependency initiate order accomplish data forwarding
A. pipe line
61. copying the entire content of one disk to ? marls synhnunication, which of following can do this
A. CISC processor
B. Second processor
C. another I/O bus buffer in memony
62-63 L为a*(b+c)*ab*c*
62. 若N为串长，f(N)为L中串长为N的个数，f(N)数量级
A. Linear
B. Quardric
C. Cubic
D. Log
E. Exponential
63. 若要求所有a在所有b前，所有b在所有c前f(N)的数量级
A. Linear
B. Quardric
C. Cubic
D. Log
E. Exponential
64. 若H(x)表示“x很诚实”，F(x, y)表示“x抢劫了y”，下面哪个表示“没有诚实的人会抢劫别人”
A.
B.
C.
65. 对操作系统的最佳描述为
A. ??
B. ??
C. resource manager
D. ??
E. interrupt head
