A GRE computer science test practice book, containing: actual tests; complete instructions and answer sheets; answers; score comparison data; and test-taking . Discover ideas about Computer Science. GRE - Computer Science Test Practice Book. Computer ScienceComputer Technology. More information. Saved by. The Computer Science test is primarily based on the concepts that you have studied in your undergraduate days but you can not ignore preparing for it.
|Language:||English, Spanish, Portuguese|
|Genre:||Academic & Education|
|ePub File Size:||20.31 MB|
|PDF File Size:||8.35 MB|
|Distribution:||Free* [*Sign up for free]|
GRE G r a d u a t e R e c o r d E x a m i n a t i o n s® Computer Science Test Practice Book This practice book contains n one actual, full-length GRE® Computer. PRACTICE. BOOK. This practice book contains one actual full-length GRE. Computer Science Test test-taking strategies. Become familiar with test structure and. Science Test. Practice Book. This practice book contains one actual full-length GRE Computer Science Test test-taking strategies. Become familiar with.
To browse Academia. Skip to main content. You're using an out-of-date version of Internet Explorer. Log In Sign Up. Ahmed Ayoub. Visit GRE Online at www. Note to Test Takers:
Question: Is the GRE subject test score required or simply strongly recommended? However, these are rare exceptions and decisions on such students are delayed. If you want your application to be considered promptly, you should arrange to take the GRE subject test.
Subject GRE The GRE Subject Tests are designed to help graduate school admission committees and fellowship sponsors assess the qualifications of applicants in specific fields of study.
The tests also provide students with an assessment of their own qualifications. Because the tests are standardized, the test scores permit comparison of students from different institutions with different undergraduate programs. Because they identify areas of weakness, students should attempt to use the GRE subject test scores to help plan their future studies.
Why subject GRE test? MS courses in and computer science, biological sciences and pure sciences. A good performance in the test proves you have adequate preparation to enter a graduate program. Moreover the subject GRE test score may be an added advantage for getting financial aid. Candidates should contact graduate schools of choice to determine which, if any, of the GRE subject tests should be taken. The Scoring Process In calculating reported scores for traditional paper-and-pencil tests, the number of questions answered correctly is adjusted according to the difficulty level of the questions on the test form.
Thus, the same number of correct responses on different test forms will not necessarily result in the same reported score. In paper-and-pencil tests, the differences in difficulty among test forms are relatively small and are adjusted through a process known as score equating.
Consider the following pseudocode. Which of the following is the most appropriate data structure to store the symbol table of a compiler? A software requirements specification is I. A full binary tree is a rooted tree in which every internal node has exactly two children. How many internal nodes are there in a full binary tree with leaves? Suppose that Professor X develops a new model of computation, called a neutron machine.
Which of the following would be a consequence of the Church-Turing thesis? A No neutron machine can solve the Traveling Salesman problem in polynomial time. B No neutron machine can solve the Maximum Matching problem for bipartite graphs in polynomial time. C No neutron machine can determine whether the decimal expansion of has 7 consecutive 7s. D No neutron machine can simulate a given Turing machine in polynomial time. E No neutron machine can determine in polynomial time whether a given Turing machine halts when its input tape is initially blank.
Unauthorized copying or reuse of any part of this page is illegal. Consider the following pseudocode in which all variables are integers and m 1.
Consider the following page reference string: Consider the following binary search tree. Starting from an empty binary search tree, the insertion of which of the following sequences of integer keys could produce the binary tree above? A 5, 9, 1, 7, 3, 4 B 5, 7, 4, 9, 3, 1 C 5, 4, 7, 3, 9, 1 D 5, 3, 4, 9, 1, 7 E 5, 3, 1, 7, 9, 4 Unauthorized copying or reuse of any part of this page is illegal.
Consider a relational database schema with the following instance of a relation R A, B, C. A C III. A computer memory system has a 64KB byte-addressable main memory with bit addresses. This same system has a one-level cache memory that can hold 16 blocks of data, where each block contains 16 bytes. Assuming this is a direct-mapped cache, to which cache block will main memory address 9A map? Which of the following problems is are decidable? Given a natural number n, does M n starting with an empty tape halt in fewer than n steps?
Given a natural number n, does M n starting with an empty tape halt in exactly n steps? Given a natural number n, does M n starting with an empty tape halt after at least n steps? Consider the pseudocode block below.
Assume that the variables x and y are integers. Which of the following best describes the difference between paging and segmentation? B Paging suffers from external fragmentation, whereas segmentation suffers from internal fragmentation.
C Paging requires page tables for address translation, whereas segmentation does not require segment tables for address translation. D Paging requires one page table per process, whereas segmentation requires only one global segment table for the entire system.
E Page tables are typically very small, whereas segment tables are always very large. Consider the following two fragments of Java programs.
A For all x, y, and z, P1 x, y, z and P2 x, y, z have the same behavior. B For all x and y, there exists z such that P1 x, y, z and P2 x, y, z behave differently. C For all x and z, there exists y such that P1 x, y, z and P2 x, y, z behave differently. D For all y and z, there exists x such that P1 x, y, z and P2 x, y, z behave differently.
E For all x, y, and z, P1 x, y, z and P2 x, y, z behave differently.
Which of the following statements about positive integers is NOT true? A If x is a composite integer, then x has a prime divisor less than or equal to the square root of x. B There are infinitely many prime integers. C Integers a and b are congruent modulo m if and only if there is an integer k such that a b km.
D If a divides bc, then either a divides b or a divides c. E If a divides b and b divides c, then a divides c. Any pair of adjacent nodes are within range of each other, and nonadjacent nodes do not interfere. If the link bandwidth is L bits per second for successful transmissions and reliable transmission is desired, what is the maximum possible total bandwidth attainable for this network, in bits per second?
Consider the following directed graph. Which of the following is a topological sort of the nodes of the graph? A 5, 7, 10, 13, 14, 17, 20, 30 B 10, 5, 13, 14, 7, 30, 17, 20 C 10, 5, 13, 17, 20, 14, 7, 30 D 10, 5, 20, 13, 17, 30, 14, 7 E 10, 20, 5, 17, 13, 14, 7, 30 Unauthorized copying or reuse of any part of this page is illegal. Consider a brute-force password-guessing attack that can submit authentication requests at a rate of one every millisecond.
Assume that a password consists of 1—6 characters from a symbol alphabet. In the average case, approximately how many seconds would it take to determine the password using this type of attack? A B C D 1, E 1, Consider the following two problems.
Nearest Neighbors: Given an unsorted array of n floating-point numbers as input, return two of the numbers that are closest in value to each other. Farthest Neighbors: Given an unsorted array of n floating-point numbers as input, return two of the numbers that are farthest in value from each other. Further assume that each allowed operation has unit cost. What are the worst-case optimal asymptotic running times for algorithms that solve the two problems?
Which of the following typically occurs when a procedure call is executed on a processor? Program counter is updated. Stack pointer is updated. Data cache is flushed to avoid aliasing problems. The routing table below uses the longest prefix match in its routing decisions. Next Hop to Next Hop to Consider a recursive algorithm for sorting an array of n 2 integers that works as follows.
What is the asymptotic running time complexity of this algorithm measured in terms of the number of comparisons made? Consider the following Java code. A B C D E Unauthorized copying or reuse of any part of this page is illegal. A hash function h maps bit inputs to 8-bit hash values. What is the largest k such that in any set of 1, inputs, there are at least k inputs that h maps to the same hash value?
Consider three processes P1, P2, and P3 with respective arrival times of 0 ms, 10 ms, and 20 ms and respective processing times of 30 ms, 15 ms, and 30 ms. The three processes are preemptively scheduled on a single-CPU system using the shortest-remaining-processing-time-first scheduling policy. Which of the following shows the order in which the processes complete, from first to last? Which of the following statements about fixed-length and variable-length instruction set architectures ISAs is are true?
Consider the following pseudocode program. Let G be the graph shown below. Which of the following is its associated directed acyclic graph G '? Which of the following algorithms has an RTR ratio closest to 0?
The MST must contain the shortest edge of G.
The MST must contain the second-shortest edge of G. The MST can never contain the longest edge of G. A color RGB raster-scan graphics system provides 18 bits per pixel and uses no color lookup table. If black and white count as shades of gray, how many different shades of gray does the system offer? A 64 B C D , E , Unauthorized copying or reuse of any part of this page is illegal. If the delay through a single-bit adder is 3 measured in gate delays to the sum output and 2 to the carry output, what is the delay through a k-bit ripple-carry adder?
Consider the following pseudocode fragment. Consider the following concurrent tasks, in which each assignment statement executes atomically. Initially, the shared variables x and y are set to 0. Which of the following must be true? Five balls are placed randomly into four boxes, labeled A, B, C, and D. Each ball has an equal chance of being placed into any box.
What is the expected total number of balls in boxes A and B? One garbage collection algorithm is semispace copying collection. Which of the following characteristics of garbage collection apply to semispace copying collection? Collects dead objects that reference each other II. Incurs overhead on every assignment operation to a reference variable III.
Which of the following statements about caches is are true?
A direct-mapped cache can have a lower miss rate than an associative cache of the same size number of blocks. Programs with high spatial locality have a low cache miss rate primarily because the exact same addresses are re-referenced. Programs with high temporal locality have a low cache miss rate primarily because the exact same addresses are re-referenced. A k-sorted array is a nearly sorted array in which no element is more than k locations away from its final position in the sorted array.
Thus, a 0-sorted array is completely sorted and every array of size n is n-sorted. Suppose that A is a k-sorted array of size n. If insertion sort is used to sort A, what is the order of growth of the number of comparisons performed by the sorting algorithm in the worst case? The subtype principle describes when one type may be substituted for another.
Which of the following is true? A An instance of a subtype may be used in any expression in which an instance of the supertype may be used because the subtype must support a superset of the operations supported by the supertype. B An instance of a subtype may be used in any expression in which an instance of the supertype may be used because the subtype must support a subset of the operations supported by the supertype.
C An instance of a supertype may be used in any expression in which an instance of the subtype may be used because the subtype must support a superset of the operations supported by the supertype. D An instance of a supertype may be used in any expression in which an instance of the subtype may be used because the subtype must support a subset of the operations supported by the supertype. E Instances of subtypes and supertypes may be used interchangeably.
Consider a regular language L over 0, 1. Which of the following languages over 0, 1 must also be regular? In order to create a good solution for the mutual exclusion problem for concurrent processes, which of the following conditions must hold? No process should have to wait forever to enter its critical region. No process running outside of its critical region may block other processes from entering their critical region.
There should be no assumptions about the speed or number of CPUs. What is the negation of the predicate x y p y q x?
Consider the following MIPS-like instructions in which the destination register is the first leftmost register. The instruction set supports i register-indirect addressing, which is indicated by using parentheses and ii displacement addressing, which is indicated as an integer offset from a register indirect value.
There are 7 items to be packed into the knapsack, each with value vi and weight wi as shown in the following table. The optimality criterion is to maximize the total value of the items that are placed in the knapsack. When this heuristic algorithm is used, what is the total value of the items that are packed, and is this total optimal? In this context, speedup is the ratio of original running time to improved running time. What is the asymptotic growth of T n?
Suppose that stacks and queues are provided as opaque data types, offering only operations to add elements, to remove elements, and to test for emptiness. Suppose that a programmer wants to count the number of elements in a given stack or queue C, which is currently in some state t, using only one auxiliary stack or queue D. The structures C and D can be used in any way possible based on the methods they offer, but C must be restored to its state t after counting its elements. Counting elements as described above is possible for which of the following data types?
C is a queue and D is a queue. C is a stack and D is a stack. C is a queue and D is a stack. Which of the following problems is are known to be solvable in running time O n3? Find the shortest path from a given start vertex to a given end vertex in a directed graph on n vertices with nonnegative integer weights. Find the longest simple path from a given start vertex to a given end vertex in a directed graph on n vertices with nonnegative integer weights.
Find the longest path from a given start vertex to a given end vertex in a directed acyclic graph DAG on n vertices with nonnegative integer weights. What is the minimal number of D flip-flops required along with combinational logic to design a counter circuit that outputs the first seven Fibonacci numbers i.
An algorithm takes a list of 2 n numbers a1 , a2 , ,a and replaces it with b1 , b2 , ,b , where 2n 2n 1 b1 max a1 , a2 , b2 max a3 , a4 , and so on. Then it performs the same operation on the resulting list replacing each pair of consecutive elements with their maximum , and it continues doing the same until there are only two elements left in the list.
For instance, if the initial list is [3, 7, 6, 8, 2, 1, 4, 5], then after the first run, it becomes [7, 8, 2, 5] and then [8, 5].
Suppose that the elements of the initial list are the integers 1 through 64 in random order. What is the probability that the number 63 will appear in the final two-element list? Consider the following instruction sequence for a hypothetical RISC processor.
R1 R2 R3 U. R4 R5 R6 V. R5 R7 R8 W. R9 R5 R1 X. R10 R4 R1 Y. R11 R10 R1 Z. R9 R1 R4 Which of the following is a possible legal execution order for the instructions on an out-of-order processor without register renaming? Consider the following three statements. If language L is recognized by a nondeterministic finite automaton, then L is recognized by a deterministic finite automaton.
If language L is recognized by a nondeterministic pushdown automaton, then L is recognized by a deterministic pushdown automaton. If language L is recognized by a nondeterministic polynomial-time Turing machine, then L is recognized by a deterministic polynomial-time Turing machine.
Which of the following best describes what is currently known about the statements? A One of the three statements is known to be false; it is not currently known whether the other two statements are true or false. B Two of the three statements are known to be false; it is not currently known whether the other statement is true or false.
C One of the three statements is known to be true; another statement is known to be false; it is not currently known whether the remaining statement is true or false. D One of the three statements is known to be true; the other two statements are known to be false. E Two of the three statements are known to be true; the other statement is known to be false. Query optimizers typically use summaries of data distributions to estimate the sizes of the intermediate tables generated during query processing.
One popular such summarization scheme is a histogram, whereby the input range is partitioned into buckets and a cumulative count is maintained of the number of tuples falling in each bucket. The distribution within a bucket is assumed to be uniform for the purposes of estimation. The following shows one such histogram for a relation R on a discrete attribute a with domain [ Recall that a predicate logic statement is contingent if its truth value depends on the choice of the universe and on the interpretations of the predicate symbol S and the constant symbol b involved.
Consider the following predicate logic statements in which b, x, and y are elements of the universe U. In the graph below, each edge label represents the probability that the connection between its endpoints is working.
If these probabilities are mutually independent, what is the probability that there is a path of working edges from S to T? Suppose that in RSA encryption, the public encryption key is the pair e, n 3, 55 and the private decryption key is the pair d , n d , 55 , where d n is a positive integer. What is the value of d? If L 1 is a decidable language and L 2 is an undecidable language, then L 1 L 2 , the union of L 1 and L 2 , is A possibly finite and possibly infinite, but definitely decidable B possibly finite and possibly infinite, but definitely undecidable C infinite, but possibly decidable and possibly undecidable D infinite and decidable E infinite and undecidable STOP If you finish before time is called, you may check your work on this test.