unicoi.kennesaw.edu/~jbamford/greguide/gresample.html
Varied Sample Questions: These questions come directly from the materials sent from the ETS with the return registration card. They are actual questions that have appeared on the GRE CS subject exam in the past. I strongly recommend that students interested in taking the GRE purchase the book available from the ETS itself - it is invaluable for its sample problems. The answers are here. Which of the following sort algorithms yield approximately the same worst-case and average-case running time behavior in 0(n log n)? A) Bubble Sort and Selection sort B) Heap sort and Merge Sort C) Quicksort and Radix sort D) Tree Sort and Median-of-3 Quicksort E) Exchange sort and Insertion Sort 2) If all variables are of type integer and if a = b (mod m) and x = y (mod m), which of the following must be true? II. III. A) II only B) III only C) I and II only D) I and III only E) I, II, and III 3) S --> A0B A --> BB|0 B --> AA|1 What is the number of terminal strings the length of 5 generated by the context-free grammar show above? A) 4 B) 5 C) 6 D) 7 E) 8 4) Consider a computer system in which processes can request and release one or more resources. Once a process has been granted a resource, the process has exclusive use of that resource until it is released. If a process requests a resource that is already in use, the process enters a queue for that resource, waiting until the resource, is available. Which of the following will NOT deal effectively with the problem of deadlock? A) Giving priorities to processes and ordering the wait queues by priority B) Having a process request all its required resources when it first begins, and restating if it cannot obtain them all C) Numbering the resources and requiring that processes request resources in order of increasing number D) Having processes time out and restart after a random interval of waiting E) Having the operating system monitor the wait queues and restart the processes to break deadlocks. Many cryptographic protocols base their security on assumptions about the computational difficulty of integer factorization. Integer factorization serves this purpose because it is believed that: A) integer multiplication is a function whose inverse, factorization, remains difficult for a large class of inputs B) P = NP C) Even if P = NP, integer factorization is still likely not to be polynomial-time computable D) Testing primality is computationally intractable E) Integer factorization is NP-hard 6) Suppose one wishes to be certain that after execution of the statement if a > b then x := a; Of the following, which is the weakest (least restrictive) condition that must be necessarily hold before execution of that statement? A) (x = a) \/ (a > b) B) (a > b) /\ (x = a) C) a > b D) x > b E) x = a 7) A relation can be defined by giving the ordered pairs of elements for which the relation holds. If the relation R over {a, b, c} is given by R = {(a,a), (a,b), (b,a), (b,b), (c,c)}, which of the following properties does R have? Symmetry II. Antisymmetry III. Reflexivity IV. Transitivity A) None B) II and III only C) II and IV only D) I, III, and IV only E) II, III and IV only 8) Assume that a data file has an index consisting of N items, where N is large. If a binary search of the index is used to find an item, the, of the following, which best approximates the mean number of comparisons required to locate a specific index entry? A) (N + 1) / 2 B) N (N - 1) /2 C) (log2N) - 1 D) N log2 N E) (N + 1) / log2 N 9) Of the following, which best approximates the ratio of the number of nonterminal nodes to the total number of nodes in a complete K-ary tree of depth N? A) 1 / N B) N - 1 / N C) 1 / K D) K - 1/K E) Log10 1 / N 10) Consider a disk with the following characteristics: Track size: 10,000 bytes Rotational latency: 10 ms/revolution Block size: 1,000 bytes The maximum transfer rate per track measured in bits per second as is conventional for this disk unit is: A) 400 Mbps B) 8Mbps C) 6,400 Mbps D) 4,250 Mbps E) 10 Mbps References Visible links 1. Hidden links: 12.
|