Flyingoverseas 版 (精华区)
发信人: bonjovi (nowhere man), 信区: Flyingoverseas
标 题: CSSUB 2001
发信站: 哈工大紫丁香 (2002年01月28日00:11:21 星期一), 站内信件
CSSUB 2001
NOV.10
1.Which of following string is NOT in the language described by the regular
expression (a*b)*c
(A)aaaaac (B)aababc (D)abc (E)bbbbbc
2.A simplified version of the Boolean expression is
(A) XY+XZ+YZ (B) (C) YZ+XYZ (D) X+Y+Z
(E)
3.
A B
/*有两幅图片如题A是NOR门(或非),B是NAND(与非)门*/
Circuit diagrams sometimes use circuit elements with complemented inputs, su
ch as A and B
above. What are the respective logical equivalents for A, which is a NOR wit
h complemented
inputs, and B, which is a NAND with complemented inputs
(A) AND and OR (B) NAND and OR (C) OR and NOR (D) AND and OR
(E) AND and NOR
Question 4-5 refer to the following information
A simple computing device works as follows.
Remove the leftmost two bits x and y from an input string
Computes Z= and places Z both on the left of the input string and on the
right of
initially empty output string
Repeats these steps until the input string has just one bit
For example, the following sequence shows how the device works on the inpu
t string 011010
INPUT OUTPUT
011010
11010 1
0010 10
010 100
10 1001
1 10011
The output string produced is 10011 for this example
4.If the input is 01010,which of the following is the output string
(A) 1010 (B) 1111 (C) 1100 (D) 1101 (E) 0111
5.IF the output is 101,which of the following could be the input string
(A) 1000 (B) 0111 (C) 0110 (D) 0101 (E) 0010
6.A certain architectural feature can be described using the following terms
: high-speed latches,
data dependency hazards, data and control dependency hazards, and preservi
ng initiation
order. This architectural feature is called
(A) pipelining (B )interrupt processing (C) array processing (D) memory
management
(E) caching
7.Which of the following is true about the behavior of comparison-based sort
ing algorithms on
inputs of length n?
(A) They all require ?(nlogn) time (B) They all run O(nlogn) time
(C) They all use divide-and-conquer (D) None of them sort in-place
(E) They all have an expected running time is asymptotically smaller than t
heir worst-case
running time
8. which of the following data structure would programmer be least likely to
use to implement
an abstract data type that must include an efficient implements of the ope
ration find the
maximum.
(A) ordered array (B) binary search tree (C) hash table (D
) heap
(E) ordered linked list
9. accessing memory that is in a processor's virtual address space, not in
its physical address
space, will typically course:
(A) fatal exception (B) an interrupt (C) a page fault (D)
a semaphore
(E) a halt
10. a path is a binary tree can be described by a sequence of binary digit
s as fallows.
if B=X0X1…..Xn is the path that leads from the root X0 to the leaf Xn ,then
the sequence of bits that described B is b0b1….bn-1 where bj=1 if Xj+1 is
the right child of Xj. four of the
following sequences are representations of paths from the root to leaves of
the same tree.
which can not be a representation of a path from the root to a leaf in that
tree
(A) 00 (B) 01 (C) 010 (D) 001 (E) 1
12.An "inversion" in a permutation P1P2……Pn is a pair (i,j),with i<j and P
i>Pj,how many
inversions are there in the permutation 8 4 1 2 7 3 6 5?
(A) 4 (B) 7 (C) 10 (D) 14 (E) 28
13.If a recursive, depth-first search is used on a completed undirected grap
h with n vertices, the
maximum depth of the recursion is
(A) Θ(1) (B)Θ(log) (C)Θ( ) (D)Θ(n) (E) Θ(n2)
15.In the following program fragment, x, y, and h are single-precision varia
bles, and i is an
integer variable.
begin
x:=0.0;
h:=0.1;
for i:=1 to 10 do
x:=x+h;
y:=1.0-x;
write(y)
end
If the value of y that is printed is not zero, what is the most likely expl
anation ?
(A) Single-precision rather than double-precision arithmetic was used
(B) Round-off error was introduced in the statement that preceded "write(y)"
.
(C) There was a machine error.
(D) The number 0.1 has no exact representation in floating point on binary m
achine.
(E) Floating-point arithmetic is never exact with fractional numbers.
16. A certain 32-bit single-precision floating-point format represents the
mantissa in sign and
magnitude form and the exponent via a biased exponent in base 2 as follows
．The most significant bit is the sign bit s
．The next 8 bits are biased exponent with radix x
．The next 23 bits form the mantissa m.. The mantissa is assumed to be norma
lized with its
highest bit (necessarily) not being encoded.
The value of a floating-point number is then (-1)s2e-127(1.m)
Which of the following statements is (are) true
I. No representation of 0 has been specified
II. In adding, there is no need to check the signs of the operands compute t
he mantissa of
the product
III. In multiplying, there is no need to check the signs of the operands to
computer of the
product
(A) I only (B) II only (C) I and II (D) I and II (E) II and III
17.Suppose the statement
X: =(-B+SQRT(B*B-4*A*C))/(2*A)
is used with floating-point arithmetic to compute an approximate solution
to the quadratic
equation Ax2+Bx+C=0. If no overflow or underflow occurs, if A>0 and C 0,the
n the result may
have a large relative error which of the following circumstances?
I. B is positive and B2 is much larger than 4AC
II. B is negative and B2 is much larger than 4AC.
III. B=C=0
(A) I only (B) II only (C) III only (D) I and II (E) II and III
Question 18-19 refer to the following information
An AVL tree is a binary tree which each node has the property that the heigh
t of its left subtree
differs from the its right subtree by at most 1.
18. Which of the following is NOT an AVL tree
(A) (B) (C)
(D) (E)/*图片欠奉*/
19.In an AVL tree with 1,000 nodes, which of following must be true about th
e lengths from
the root to leaves
(A) Every path length is greater then 100 (B) No path length is greate
r than 100
(C) At least one path length is greater than 100 (D) No path length is less
than 101
(E) Every path length is 99, 100, or 101
24. Which of following is (are) likely to exhibit good locality of reference
.
I. sequential processing of a one-dimensional array
II. Maintaining a symbol table by hashing
III. Collecting garbage in linked strictures
(A) None (B) I only (C) I and II only (D) II and III only (E) I, II
and III
26. There are a number of factors that come into play in determining how muc
h CPU time a
program will require. Which of the following contribute(s) directly to the
CPU time?
I. The size secondary memory. II. The number of clock cycles per instruc
tion
III. The number of executed instructions of the program.
(A) II only (B) III only (C)I and III (D)I and III (E) II and III
31. which of the following is(are) typically about a set-associative cache
I. It is cheaper to implement than a direct-mapped cache
II. It usually offers a better hit ratio than a fully associative cache
III. It usually offers a better hit ratio than direct-mapped cache
(A) I only (B) II only (C) III only (D) I and II (E) I and III
32. Consider the following C program
# include <stdio.h>
main ( )
{
float sum=0.0, t=1.0;
for (int i=1;i<0;i++)
{
sum=sum+t;
t=t*2.0/i;
printf("%f\n",sum);
}
}
Which of the following integers is closest to the last number printed?
(A) 5 (B) 7 (C) 9 (D) 11 (E) 15
Question 34-35 refer to the following information.
In a shift -reduce parser with one-token lookahead, the contents of the pars
e stack and lookahead symbol are to determine the parser's actions. The pars
er either shifts symbols from the input to the
stack or reduces the top stack symbol(s)(which correspond(s) to the right si
de of some production)
to a single symbol (which corresponds to the left side of the production).
Consider the actions of a bottom-up parser for the following grammar.
E::=E+E|E*E|(E)|id
34. If the parser enforces the usual rules of precedence and associativity f
or operators, which of
the following parsing actions is INCORRECT?
TOP 3 Stack
SYMBOLS INPUTt ACTION
(A) E+E + Reduce
(B) E+E * Shift
(C) E+E ) Reduce
(D) E*E + Reduce
(E) E*E * Shift
35. How many reductions are needed to reduce the sentence id+id*id to the no
nterminal E?
(A) 3 (B) 5 (C) 7 (D) 9 (E) 11
38. Of the following statements about separate compilation, which is LEAST a
ccurate?
(A) It decrease the expected length of the edit-compile-run cycle by reducin
g the fraction of the
program that must be recompile after a given change.
(B) It facilitates code reuse by allowing functions to be incorporated in mo
re than one program
without source-level modifications.
(C) Its benefits are reduced when external procedures are made into inline p
rocedures.
(D) It provides an encapsulation mechanism for languages such as C that lack
o built-in module
facility
(E) It makes it easier for a compiler to perform global optimizations
40. The recurrence is relationship
A0=2 and An=2An-1-1 for n 1
Defines a sequence of {An}, which of the following characterizes the grow
th of {An}
(A) Logarithmic (B) Linear (C) Quadratic (D) Cubic (E) Exponenti
al
Question 43-44 refer to the following information
In a particular machine, a frame pointer register $fp always points at the f
irst location in the current stack frame. When a procedure with a single act
ual parameter is called, the value of the
procedure's static link is stored at offset-8 in the new stack frame, and th
e value or the address
(depending on the method of parameter transmission) of the actual parameter
(if any) is stored
at offset-12 followed by any local variables. This situation is illustrated
in the following diagram
Offset Frame Contents
$fp---------> 0 Previous value of $fp
-4 return address
-8 static link
-12 parameters(if any) followed by local variables
The instruction
LOAD $r1, offset($r2)
Puts into register $r1 the memory word whose address is computed by adding o
ffset to the
contents of $r2.
Consider the following Pascal program fragment(parameter x is passed by refe
rence)
Procedure P;
var a: integer;
Procedure Q (var x: integer);
begin
x:=a+x;
end;
begin
a:=1;
Q(a)
end;
43. Which of the following corresponds to fetching the value of x in procedu
re Q
(A) LOAD $t0, -8($fp) (B) LOAD $t0, -12($fp)
(C) LOAD $t0, -12($fp) (D) LOAD $t0, -8($fp)
LOAD $t0, -12($t0) LOAD $t0, 0($t0)
(E)LOAD $t0, -12($fp)
LOAD $t0, 0($t0)
44. which of the following corresponds to fetching value of a in procedure Q
?
(A) LOAD $t1, -16($t1) (B) LOAD $t1, -12($t1)
(C)LOAD $t1, -8($fp) (D) LOAD $t1, -8($fp)
LOAD $t1, -12($t1) LOAD $t1, -8($t1)
(E) LOAD $t1, -8($fp)
LOAD $t1, -16($t1)
LOAD $t1, -16($t1)
46 Let M=(Q,∑,δ,s,F) be a deterministic finite automation, where Q is set
of states, is the alphabet
set, is the state transition functions, s is the start state, and F is the
set of final states, let L(M) be
the language accepted by M, which of the following conditions guarantees t
hat if w L(M), then
w can be written as w=uvy, where u, v, y are strings over ∑ , with |v|>=1
, and where uvny is in
L(M) for all n>0?
(A) |w|≥|F| (B) |w|≥|∑ (C) |w|≥|Q| (D)|w|≤|∑|
(E)|w|≤|Q|
47 Program A executed in machine M, there was a record during the execute. 2
0% of all
instruction was branch, 20% of branch was unconditional branch. Half of co
nditional branch
was executed, another half was not. What is the average CPI（cycle per instr
uction）during the
execute. Instructions was taken during 1 cycle per instruction(i.e.,CPI=1)
,except for pipeline
stall make instruction taken longer, branch executed need 3 cycle stalls,
branch did not executed
need 1 cycle stall.
47 程序A在机器M上执行，有运行记录：指令的20%是branch, branch的20%是无条件
分支，一半条件分支执行，一半条件分支没有执行。每条指令的CPI=1，除非由于pipel
ine
stall的原因使指令的执行拉长，在这种情况下，分支执行需要3 cycle stalls, 分支不
执
行需要1 cycle stalls。问平均CPI（cycle per instruction）是多少？
(A) 1.24 (B) 1.36 (C) 1.4 (D) 1.44 (E) 2.2
Question 48-49 refer to the following information
Refer to the language by the regular expression below a*(b+c)*abc*
48. Let f(N) denote the number of string of length N in the language. Which
of the following best describes the growth of f(N) as N increases?
(A) Linear (B) Quadratic (C) Cubic (D) Logarithmic (E) Exponenti
al
49. Let g(N) denote the number of string in the language of length N such th
at all the a's in the
string appear before all the b's and all the b's appear before all the c's
. Which of the following
best describes the growth of g(N) as N increases?
(A) Linear (B) Quadratic (C) Cubic (D) Logarithmic (E) Exponenti
al
50.某Data structure,每个node可包含两个link, link值为null或指向另一node, link
不能指向本node, these structure are not necessarily connected. 设共有2N link
为null，节点数最少为
(A) 3 (B) N/2 (C) N -1 (D) N log N (E) N
51.若一个节点至多有一个link指向它，节点数最多为：
(A) N (B) 2N-1 (C) nlogN+1 (D) 2(N-1)
52. A binary tree, its node has two children or has no children(leaf). The b
inary tree has N nodes
and d-depth. Which of the following decide the leaf's number?
(A) the tree's node number N (B) the tree's depth d
(C) the tree's node number N and depth d , but not the shape of the tree
(D) the tree's node number N and depth d , as well as the shape of the tree
(E) neither N nor d.
52.一个二叉树，其节点或者有两个儿子或者没有儿子（即叶子），现有总节点数N, 深
度d, 问叶子节点的数目和什么有关。
(A) 由N决定 (B)由d决定 (C) N、d,但与二叉树的形状无关
(D) N、d以及二叉树的形状 (E) 总节点数n，深度d都无关
54. multiprogramming system 中使用interleaving技术。共用low-carry bits。相临
的地址放在相临的bank中，在2-way中最minor的操作为操作两个相同的bank要1个周期，
最max的操作为操作两个不同的bank要3个周期，问在8-way中，若minor/max为50/200个
周期，最多可以工作多少个processes？
(A) 1 (B) 2 (C) 4 (D) 8 (E) 16
55. 子程序返回时，堆栈寄存器的值为5678，其紧接下面一个寄存器的值为5789。如何
解
释这两个数值：
（A）程序返回地址在5677中... （B）返回程序不代参数
（C）堆栈共111个字
（D）
（E）
56. Let T(k) be the probability that, given a random input, a given program
P executes k or more
instructions. What is the significance of the infinite sum
T(1)+T(2)+……+T(k)……
In terms of the number of instructions executed by the program
(A) It is an upper bound (B) It is a lower bound (C) It give
s the average value
(D) It gives the variance (E) It gives the standard deviation
Question 57-59 refer to the following information
Let A[1..n] be an array of n numbers, where n is a power 2, consider the fol
lowing high-level code
fragment, where all logarithms are base 2
for 1 j log n do
for 1 i (n/2i) do
A[ i ]:=A[ 2i-1 ]+A[ 2i ]
rof
rof
57. 数组用上面程序初始化后，A[1]为：
(A) (B) (C) (D)
(E) A[1]
58上面程序执行的时间为：
(A) (log n) (B) (n/log n) (C) (n2) (D) (n) (E) (
nlog n)
65. Which of the following provides the most argument that a decision proble
m Q does not have
a polynomial-time algorithm if P NP
(A) Showing that the satisfiablity problem is polynomial-time reducible to Q
(B) Showing that Q is polynomial reducible
(C) Showing that Q is in class NP
(D) Showing that Q is in class P
(E) Showing that Q is polynomial reducible to a problem in class NP
66.Let L be a language accepted by an n-state nondeterministic finite automa
tion with t(n) states
that accepts L. What is the smallest choice of t(n) that is sufficient fo
r all such L ?
(A) n+1 (B) 2*n (C) n2 (D) 2n (E) n!
67. Let L{0,1}* be an arbitrary language. If membership in L is undecidable
(i.e., recursive),
which of the following hold(s)?
I. L is infinite
II. L contains a decidable(i.e., recursive) language
III. is undecidable
(A) I only (B) II only (C) I, II (D) I, III (E)I, I
I, III
68. Which of the following is(are) true of a simple, weighted undirected, co
nnected graph G.
I. If an edge weights are distinct, G must have a unique minimum spanning tr
ee
II. If G has a unique minimum spanning tree, then all edge weights must be d
istinct
III. If two edges e1 and e2 have the same weight and all other edges have la
rger weights,
the both e1 and e2 must appear in every minimum spanning tree
(A) none (B) I, II (C)I, III (D)II, III (E)I, II, III
69 Newton's method for approximating leads to iteration Xi+1=(Xi+2/Xi)/2,
if a certain
machine floating point arithmetic with a sufficiently large mantissa, wha
t is the machine
number of iterations require to compute with an error less than 10-14 usin
g Newton's
method, staring with X0=1.5 ?
(A) 12 (B) 4 (C) 8 (D) 16 (E) 32
70. Consider the languages L1, L2 and L3 defined below
L1={w in {a, b }* | w contains an odd number of a's and an even number of b'
s}
L2={w in {a, b }* | w contains an equal number of a's and b's}
L3={an bm an-m | n m 0}
Which of the following statements is(are) true about L1, L2, L3 ?
I. L1 is a regular language
II. L2 is a regular language
III. L3 is a context-free language
(A) I only (B) III only (C) I and II (D) I and III (E) II
and III
The following questions are in the test taken on November 10,2001 at USA GRE
CS SUB. The questions are different those which be taken at the same time i
n China. So you can refer to
these questions, but maybe some questions did not be recorded correctly or
in wrong order.
59. There are two circuits C and D, consisting of only AND, OR, and NOT. Eac
h circuit has n
inputs, and a single output. Suppose that P=NP, which of the following can
be
computed in polynomial time:
I. The equivalence of C and D.
II. Whether there exist a smaller circuit than C that is equivalent to C.
III. Whether there exist an input to C which returns 1.
(A) I (B) II (C) II and III (D) I, II, and III
(E) None of the above
60. Given a graph G, which of the following can not be solved in linear time
using
Depth First Search. (i.e. in O(V+E) time).
(A) Find the disconnected components of G.
(B) Find the valence of vertices in G.
(C) Find single source shortest paths.
d), e) two other incorrect choices.
61. Using * = intersection. Which of the following is not true?
(A) If L1 can be accepted by a deterministic finite automata, and L2
can be accepted by a deterministic finite automata, then L1*L2 is regular.
(B) If L1 can be accepted by a nondeterministic finite automata, and L2
can be accepted by a nondeterministic finite automata, then L1*L2 is regular
.
(C) If L1 is context free, and L2 is context free, then L1*L2 is context fre
e.
(D) If L1 can be recognized in polynomial time, and L2 can be recognized in
polynomial time, the L1*L2 can be recognized in polynomial time.
(E) If L1 is recursively enumerable, and L2 is recursively enumerable, then
L1*L2 is recursively enumerable.
62-63. For the following two problems, given a binary tree T, with N nodes,
L leafs,
S nodes with only one child, and P nodes with two
children. (letters may be different)
62. If N is written as a function of L, what is the least possible value of
N?
(A) L-1 (B) 2*L (C) 2*L-1 (D) L*L (E) 2L
63. Which of the following is true?
I. 2*L + S = N + 1
II. L - P = 1
III. 2*P + S = N - 1
(A) II (B) I and III (C) II and III (D) I and III
(E) I, II, III
64. Which is the following would strengthen the security of RSA encoding?
I. If algorithms for prime factorization of large numbers improve.
II. RSA is based on unproven complexity.
III. If a person had unlimited tapping power, and computational power,
he can decode the RSA code.
(A) I (B) II (C) III (D) I, II, III. (E) None.
65. Which of the following statements are true?
(A) A set A is a subset of infinite B, then A is finite.
(B) An infinite set A is a subset of B, then B is infinite.
, etc. (very easy.)
(Question Number not known)
Which of the following can be produced by a*(b*c)*:(Note: the test taker's n
otation is such
But I conjecture the correct notation should be a*(b*c)*, only for reference
)
choose the one end with 'bb' (the test-taker do not note the answer for sele
ction, maybe this
is the answer test-taker selected
If A is uncountable and C is finite, which of the following is true:
choose if A is a subset of B, then B is uncountable, D is a subset of C, D i
s finite. (the rest choices are just reposition A, B, C,D, such as if B is a
subset of A, then B is uncountable, etc..)
a 10 bits binary, the possible ways of having either 01 at the beginning or
01 at the end:
A 424, B 448 C 512, D 5**
choose B i think.
{ambn, m>=n} and {ambn, m<=n} which of the followings are correct:
1) a union b is regular expression
2) a intersect b is regular expression
3) a intersect b is context free
w is a word, an expression {ww} is:
1)regular expression
2)context free
3)recursively ....
choose 3 only.
70. Which of the following does not have linear time complexity for operatio
ns in graph G
A) finding connected component
B) finding spanning forest
c) short path from a vertex
d) number of degrees of a vertex
e) detect a cycle in G
--
He‘s a real nowhere man
sitting in his nowhere land
making all his nowhere plan for nobody
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 218.29.157.92]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：202.639毫秒