GRE Computer Science Questions and Answers

 

 Contents


1 Computer Science
1.1. With regard to the Pascal declarations
1.2. In the NoNicks operating system, the time required by a single file-read operation has four nonoverlapping components:
1.3. Sometimes the object module produced by a compiler includes information (from the symbol table) mapping all source program names to their addresses. The most likely purpose of this information is
1.4. In block L2 the variables g and h are best described as
1.5. If the notation L1-L2 means "the portion of block L1 that is not in block L2," then the scopes of the variables a and b declared in the statement numbered (1) are
1.6. Suppose there is an open (external) hash table with four buckets, numbered 0,1,2,3, and integers are hashed into these buckets using hash function h(x) = x mod 4. If the sequence of perfect squares 1,4,9,...,i2,... is hashed into the table, then, as the total number of entries in the table grows, what will happen?
1.7. Two single-user workstations are attached to the same local area network. On one of these workstations, file pages are accessed over the network from a file server; the average access time per page is 0.1 second. On the other of these workstations, file pages are accessed from a local disk; the average access time per page is 0.05 second. A particular compilation requires 30 seconds of computation and 200 file page accesses. What is the ratio of the total time required by this compilation if run on the diskless (file server) workstation to the total time required if run on the workstation with the local disk, if it is assumed that computation is not overlapped with file access?
1.8. Two expressions E and F are said to be unifiable if there are substitutions for the variables of E and F that make the expressions lexically identical. In the following three expressions, only w, x, y, and z are variables. I. f(w,w) II. f(x,1) III. f(y,g(z)) Which pairs of these expressions is (are) pairs of unifiable expressions?
1.9. Several concurrent processes are attempting to share an I/O device. In an attempt to achieve mutual exclusion, each process is given the following structure. Busy is a shared Boolean variable.
1.10. The construct cobegin Statement1; Statement2 coend means Statement1 and Statement2 are to be executed in parallel. The only two atomic actions in this construct are loading the value of a variable and storing into a variable. For the program segment
1.11. The following algorithm solves a system of equations Lx = b where L is a unit lower-triangular matrix (ones on the diagonal and zeros above the diagonal).
1.12. A lexical analyzer for Pascal scans the input character-by-character, from a beginning point p until it knows what token begins at p. Assume that the tokens of Pascal are the usual ones: identifiers, constants, keywords, and operators. Sometimes the lexical analyzer must scan beyond the token that begins at p in order to determine what that token is. For which of the following character strings can a lexical analyzer for Pascal determine, without looking at the next character, that it has seen the complete token? I. then II. < III. ;
1.13. The following syntax-directed translation scheme is used with a shift-reduce (bottom-up) parser that performs the action in braces immediately after any reduction by the corresponding production.
1.14. For procedures P1, P2, P3, and for Boolean variable B, the repeat loop
1.15. A stack can be defined abstractly by the following rules. Let s be a stack, and let X be a symbol. Then:
1.16. For x = 0, y = 0, define A(x, y) by A(0, y) = y + 1, A(x + 1, 0) = A(x, 1), and A(x + 1, y+ 1) = A(x, A(x+ 1, y)). Then, for all non-negative integers y, A(1, y) is
1.17. The following program is written in a language having the syntax of Pascal, but one in which passing parameters might not be limited to call by value and call by reference, as in Pascal.
1.18. Consider the following algorithm for n > 0.
1.19. A microcomputer used for data acquisition and control is required to digitize and process four analog input signals and to output their average continually; i.e., in real time. The time for an external analog-to-digital converter (which is triggered by a CPU instruction) to digitize one input is 12 microseconds, and only one digitization occurs at a time. Five CPU instructions, including the triggering instruction, must be executed for each signal digitized. Ten CPU instructions are executed in order to average each set of four samples and output this value. The time to convert the output from digital to analog form is to be ignored. If it is assumed that suitable data buffering is employed, then the maximum average instruction execution time that allows the microcomputer to keep up with the input-output data rates, is
1.20. Two alternatives for interconnecting a set of processors with bidirectional links are (1) the fully interconnected network, in which each processor is directly connected to every other processor, and (2) the ring network, in which each processor is connected to two other processors. The worst-case path length for a network is the maximum, over all pairs of nodes in the network, of the minimum length paths (measured in number of links) between the nodes. For each type of interconnection of n processors, a figure of merit can be formed as the product of the number of links required for the network times the worst-case path length connecting any two processors. The ratio of this figure of merit for the fully interconnected network compared to that of the ring network, for even n > 2, is
1.21. If each stage can act on only one item in any time unit, at which time unit(s) between t1 and t6 could one introduce a second item into this assembly line?
1.22. If throughput is to be maximized for the assembly line, at which constant interval, measured in time units, could new items be periodically introduced without violating the time constraints?
1.23. What is the earliest time at which processing of all jobs can be completed?
1.24. For the preceding table, assume that the criterion for scheduling is to minimize the delay in starting the processing of each job and assume no preemption. This minimum average delay in starting time is most nearly
1.25. A major advantage of direct mapping of a cache is its simplicity. The main disadvantage of this organization is that
1.26. Two computers communicate with each other by sending data packets across a local area network. The size of these packets is 1,000 bytes. The network has the capacity to carry 1,000 packets per second. The CPU time required to execute the network protocol to send one packet is 10 milliseconds. The maximum rate at which one computer can send data to another is approximately
1.27. The circuit below is to be used to implement the function z = f(A,Y) = A + Y. Inputs I and J can be selected from the set (0,1,Y,?}. What values should be chosen for I and J?
1.28. If no gaps or special formatting is assumed, then the nominal storage capacity, in bytes, of one such disk is
1.29. Assume that data transfers between the disk and the memory of a host system are interrupt-driven, one byte at a time. If the instructions to accomplish a one-byte transfer take 8µs and the interrupt overhead is 10µs, then the time available, in µs for other computing between byte transfers is
1.30. The additional input is LEAST likely to be used for signals derived from the
1.31. Suppose that the same clock signal is used to increment the microprogram counter and to load the control register. Which of the following assertions is (are) true? I. Microinstruction execution time is at least two clock periods. II. Microinstruction execution can be overlapped with fetching the next microinstruction. III. Unconditional branch microinstructions must necessarily take longer than other types.
1.32. A 10-unit heap of memory uses an allocation algorithm in which a block is allocated at the left end of the leftmost block in which it fits. Which of the following allocation/deallocation patterns CANNOT be satisfied?
1.33. The figure below shows a control circuit, consisting of a 3-bit register and some combinational logic. This circuit is initially in the state Q1Q2Q3 = 000. On subsequent clock pulses, the circuit is required to generate the control sequence: (100)?(010)?(001)?(001)?(001)?… Which of the following is a correct set of equations to be implemented by the combinational logic?
1.34. A hypothetical microprocessor communicates with its memory and peripherals over an 8-bit data bus and a 16-bit address bus. It contains an 8-bit accumulator A and two 16-bit registers: program counter PC and index register X. (see diagram below.) The opcode of each instruction is one byte (8 bits) long. Assume that any internal processor time is negligible and that the time to address memory and transfer one byte in either direction over the data bus equals unity (one memory cycle). The time taken to fetch and execute the 3-byte instruction "store A in some address indexed by X" is
1.35. The state table for a controller with a single input X is shown on the left below. It is to be implemented by means of an 8-word by 2-bit, read-only memory (ROM) and a 2-bit register, as shown on the right below. A2 is the most significant address bit of the ROM. (When X changes, it does so synchronously with the CLOCK, so that it does not cause a race condition.) Which of the following lists the requisite contents of ROM locations 0-7, respectively?
1.36. Sam and Sue are using a program P to generate personalized greeting cards on their Cucumber AT microcomputer. Business is so good that they must generate one card every 3 seconds. However, the memory requirements of a run of program P range between 0 and 1,000,000 bytes, distributed uniformly. Furthermore, if a run requires r bytes, and the Cucumber's memory is m bytes, then the run takes (i) 1 second if r = m, and takes (ii) r/m seconds if r > m, because of byte swapping. The minimum amount of memory that Sam and Sue must buy so that they can produce an average of one card every 3 seconds is approximately
1.37. Which of the following sorting algorithms has average-case and worst-case running times of O(n log n)?
1.38. The language {ww | w (0 + 1)*} is
1.39. Consider the following program fragment. (1) for i := 1 to n do (2) M[i] := 0 Let A represent the initialization (i := 1) in line (1); let B represent the "body" of the loop; i.e., line (2). Let I represent the incrementation of i by 1 implied by line (1), and let T represent the test for i = n also implied by line (1). Which of the following regular expressions represents all possible sequences of steps taken during execution of the fragment, if it is assumed that n is arbitrary and that no abnormal terminations of the loop can occur?
1.40. In the figure below, a finite automaton M has start state A and accepting state C. Which of the following regular expressions denotes the set of words accepted by M?
1.41. Which of the regular expressions below describes the same set of strings as the following grammar (with root S)?
1.42. Consider the following program segment for finding the minimum value of an array.
1.43. Let the syntactic category < S > be defined by the Backus-Naur form description: < S > :: = r | r < S > | < S > < S > Which of the following strings can be generated from < S > according to this definition? I. rr r II. r rrr III. rr r r r rr
1.44. Consider N employee records to be stored in memory for on-line retrieval. Each employee record is uniquely identified by a social security number. Consider the following ways to store the N records. I. An array sorted by social security number. II. A linked list sorted by social security number. III. A linked list not sorted. IV. A balanced binary search tree with social security number as key. For the structures I-IV, respectively, the average time for an efficient program to find an employee record, given the social security number as key, is which of the following?
1.45. In a height-balanced binary search tree, the heights of the left and right descendents of any node differ by at most 1. Which of the following are true of such a tree? I. Worst-case search time is logarithmic in the number of nodes. II. Average-case search time is logarithmic in the number of nodes. III. Best-case search time is proportional to the height of the tree. IV. The height of the tree is logarithmic in the number of nodes.
1.46. Three common operations on the symbol table of a compiler are: Insert - insert an identifier and its attributes, Find - return the attributes of a particular identifier, List - list all identifiers and their attributes in lexicographic order. A particular compiler maintains its symbol table as a hash table with 2n buckets. For a symbol table with approximately n identifiers, which of the following gives the order of the average cost of efficient programs performing these three operations?
1.47. If L is a language accepted by some automaton M, which of the following is (are) true? I. If M is a nondeterministic finite automaton, then L is accepted by some deterministic finite automaton. II. If M is a deterministic pushdown automaton, then L is accepted by some nondeterministic pushdown automaton. III. If M is a nondeterministic pushdown automaton, then L is accepted by some deterministic Turing machine.
1.48. Which of the following assertions has the property that if the assertion is true before executing the program fragment z := z * a; y :=y - 1 then it will also be true afterward?
1.49. Which of the following regular expressions is equivalent to (describes the same set of strings as) (a* + b)*(c + d)?
1.50. The number of 1's in the binary representation of 13*163+ 11*162 + 9*16 + 3 is which of the following?
1.51. The binary relation on the integers defined by R = {(x, y) : |y - x| = 1} has which of the following properties? I. Reflexivity II. Symmetry III. Transitivity
1.52. Consider the part of the two-dimensional integer grid bounded by point A = (0, 0) at the "southwest" corner and by point B = (n, n) at the "northeast" corner. How many different ways are there of walking from A to B on grid lines, always moving between any two grid points either east or north?
1.53. A 0-2 binary tree is a rooted tree such that every node has either no child or two children. The height of a binary tree is the maximum number of edges on a path from the root to a leaf. Let n(h) be the minimum number of nodes in a 0-2 binary tree of height h, and let N(h) be the maximum number. For all h > 0, (n(h), N(h)) =
1.54. Let A be an n × n matrix and let P be an n × n permutation matrix. Which of the following must be true?
1.55. Consider a floating-point number system used by a modern computer for solving large numerical problems. Let denote the floating-point addition in this system. Which of the following statements is true about this system?
1.56. Consider the representation of six-bit numbers by two's complement, one's complement, or by sign and magnitude. In which representation is there overflow from the addition of the integers 011000 and 011000?
1.57. A 2-3 tree is a tree in which (i) every interior node has two or three children, and (ii) all paths from the root to a leaf have the same length. An example of a 2-3 tree is shown below. Which of the following could be the number of interior nodes of a 2-3 tree with 9 leaves?
1.58. As n ? 8, the function 2 ; grows faster than
1.59. The bits in the 32-bit word of a hypothetical computer are denoted by: b31b30...b1b0 When such a word represents a nonzero floating-point number, its value is taken to be (1/2 - b31) (1 + 2i-24bi)2s where s = -64 + 2i-24 bi. The correct values for the least positive and greatest positive numbers, respectively, that can be represented are given by which of the following pairs?
1.60. Let Ln be the set of integer points (i, j) in the plane satisfying i, j integer, i = 0, j = 0, i+j = n. L3 is shown below. The neighborhood Nn(i,j) of point (i,j) in Ln is all those points (k,m) whose coordinates differ, respectively, from those of (i,j) by at most 1; i.e., Nn(i,j) = {(k,m) Ln: |i-k| = 1 and |j- m| = 1}. For different (i,j) in Ln, Nn(i,j) may have different sizes. For n > 3, the number of different values that can be the size of Nn(i,j) for some (i,j) Ln is
1.61. Let bqbq-1…b0 be the binary representation of integer b. The integer 3 is a divisor of b if and only if
1.62. The operation W=0 X=1 Y=1 Z=1 applied to Source and Destination would yield which of the following results?
1.63. What set of values W X Y Z would yield the result when applied to Source and Destination as given?
1.64. An information-retrieval system stores records with 5-bit keys. In response to a given query, which is a 5-bit key q, the system lists all records whose keys k have Hamming distance at most 1 from q; i.e., k and q differ in at most one bit position. Suppose the keys of all the records in the system are: 00000 00011 01101 10100 11111 In response to an arbitrary query q, what are the minimum and maximum numbers of these records the system could list?
1.65. Consider the following pseudocode of the recursive function goAgain.
1.66. Consider the binary heap shown below that uses an array a[] = [9, 7, 4, 2, 6, 1, 3] to store its elements. What will be the values of the remaining elements in the array after one delete-max operation from the heap?
1.67. Assume that any n-bit positive integer x is stored as a linked list of bits so that the first element of the list is the least significant bit. For example, x = 14 = 11102 is stored as the linked list (0, 1, 1, 1) of size n = 4. For this data structure, the operation that replaces x by can be done in
1.68. Which of the following is the regular expression corresponding to the automaton above?
1.69. Which of the following grammars over alphabet {x, y} generates the language recognized by the automaton above?
1.70. Consider the following function.
1.71. A privileged instruction may be executed only while the hardware is in kernel mode. Which of the following is LEAST likely to be a privileged instruction?
1.72. Which data structure would be most appropriate to implement a collection of values with the following three characteristics? (1) Items are retrieved and removed from the collection in FIFO order. (2) There is no a priori limit on the number of items in the collection. (3) The size of an item is large relative to the storage required for a memory address.
1.73. A researcher is preparing a questionnaire with 6 questions. The only possible responses to each question are “Yes,” “Maybe,” and “No.” The researcher wants to know how many people answer with any given combination of responses. A programmer is designing a data structure to collate the responses to this questionnaire. The programmer decides to use a base structure containing 6 memory locations, one for each question. Each element will contain a 2 for “Yes,” a 1 for “Maybe,” and a 0 for “No.” One person’s response may look like this:
1.74. Consider the following truth table and implementation.
1.75. Suppose problem A is NP-complete and problem B is in NP but is not necessarily NP-complete. Which of the following statements is (are) necessarily true? I. A polynomial-time algorithm for A implies P = NP. II. A polynomial-time algorithm for B implies P = NP. III. A polynomial-time algorithm for A implies a polynomial-time algorithm for B.
1.76. Two classical algorithms for finding a minimum spanning tree in a graph are Kruskal’s algorithm and Prim’s algorithm. Which of the following are the design paradigms used by these algorithms?
1.77. Consider the following pseudocode.
1.78. Which of the following is the most appropriate data structure to store the symbol table of a compiler?
1.79. A software requirements specification is: I. a contract between developers and clients specifying what the developers will produce for the clients. II. a specification of the features that the target software deliverable must have. III. a specification of the personnel and resources that will be committed to the software development effort.
1.80. 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 500 leaves?
1.81. Consider the following instruction sequence in a single-issue in-order 5-stage pipeline (IF, ID, EX, MEM, and WB).
1.82. 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?
1.83. Consider the following pseudocode in which all variables are integers and m = 1.
1.84. Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1 Assuming there are 4 page frames available and that all frames are initially empty, what is the total number of page faults that would occur for the page reference string above if the least-recently-used (LRU) replacement policy is used?
1.85. Consider the following binary search tree.
1.86. Consider a relational database schema with the following instance of a relation R (A, B, C).
1.87. A computer memory system has a 64KB byte-addressable main memory with 16-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 9A8116 map?
1.88. Let M0, M1, M2, ..., be an effective enumeration of all Turing machines. Which of the following problems is (are) decidable? I. Given a natural number n, does Mn starting with an empty tape halt in fewer than n steps? II. Given a natural number n, does Mn starting with an empty tape halt in exactly n steps? III. Given a natural number n, does Mn starting with an empty tape halt after at least n steps?
1.89. Consider the pseudocode block below. Assume that the variables x and y are integers.
1.90. Which of the following best describes the difference between paging and segmentation?
1.91. Consider the following two fragments of Java programs.
1.92. Which of the following statements about positive integers is NOT true?
1.93. Five wireless nodes - A, B, C, D, and E - are arranged in a line. Any pair of adjacent nodes are within range of each other, and nonadjacent nodes do not interfere. All nodes execute the Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) protocol with Ready to Send/Clear to Send (RTS/CTS) exchange prior to transmission. 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?
1.94. Consider the following directed graph. Which of the following is a topological sort of the nodes of the graph?
1.95. 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 10-symbol alphabet. In the average case, approximately how many seconds would it take to determine the password using this type of attack?
1.96. Consider the following two problems.
1.97. Which of the following typically occurs when a procedure call is executed on a processor? I. Program counter is updated. II. Stack pointer is updated. III. Data cache is flushed to avoid aliasing problems.
1.98. The routing table below uses the longest prefix match in its routing decisions.
1.99. Consider a recursive algorithm for sorting an array of n = 2 integers that works as follows. (a) If there are only 2 elements to be sorted, compare them and swap them if they are out of order. (b) Otherwise, do the following steps in order. (1) Recursively sort the first n - 1 elements of the array. (2) In the resulting array, recursively sort the last n - 1 elements. (3) In the resulting array, recursively sort the first 2 elements of the array. What is the asymptotic running time complexity of this algorithm measured in terms of the number of comparisons made?
1.100. Consider the following Java code.
1.101. A hash function h maps 16-bit inputs to 8-bit hash values. What is the largest k such that in any set of 1,000 inputs, there are at least k inputs that h maps to the same hash value?
1.102. 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?
1.103. Which of the following statements about fixed-length and variable-length instruction set architectures (ISAs) is (are) true? I. Variable-length ISAs allow for a smaller code size over fixed-length ISAs. II. Fixed-length ISAs simplify instruction fetch and decode over variable-length ISAs. III. Variable-length ISAs require more registers than fixed-length ISAs.
1.104. Consider the following pseudocode program.
1.105. Given a directed graph G = (V, E), it is convenient to represent the connectivity properties of G using an associated directed acyclic graph G' = (V', E'), where the vertices in V' are the strongly connected components of G and for S, T V', (S, T) is in E' if and only if there exist u S and v T such that (u, v) E. Let G be the graph shown below.
1.106. An algorithm’s real-time readiness (RTR) ratio is defined as the ratio of its average-case running time to its worst-case running time. Which of the following algorithms has an RTR ratio closest to 0?
1.107. Which of the following properties must be true of a Minimum Spanning Tree (MST) of a connected graph G with at least 3 edges? I. The MST must contain the shortest edge of G. II. The MST must contain the second-shortest edge of G. III. The MST can never contain the longest edge of G.
1.108. 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?
1.109. 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?
1.110. Consider the following pseudocode fragment.
1.111. Consider the following concurrent tasks, in which each assignment statement executes atomically. Initially, the shared variables x and y are set to 0.
1.112. 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?
1.113. One garbage collection algorithm is semispace copying collection. Which of the following characteristics of garbage collection apply to semispace copying collection? I. Collects dead objects that reference each other II. Incurs overhead on every assignment operation to a reference variable III. Avoids fragmentation
1.114. Which of the following statements about caches is (are) true? I. A direct-mapped cache can have a lower miss rate than an associative cache of the same size (number of blocks). II. Programs with high spatial locality have a low cache miss rate primarily because the exact same addresses are re-referenced. III. Programs with high temporal locality have a low cache miss rate primarily because the exact same addresses are re-referenced.
1.115. 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?
1.116. The subtype principle describes when one type may be substituted for another. Which of the following is true?
1.117. Consider a regular language L over {0, 1}. Which of the following languages over {0, 1} must also be regular? I. {the w L | length of w is even} II. {w L | the length of w is prime} III. {w L | the length of w is an integer power of 2}
1.118. In order to create a good solution for the mutual exclusion problem for concurrent processes, which of the following conditions must hold? I. No process should have to wait forever to enter its critical region. II. No process running outside of its critical region may block other processes from entering their critical region. III. There should be no assumptions about the speed or number of CPUs.
1.119. What is the negation of the predicate ?x y (p(y) ? q(x))?
1.120. Consider a single-issue processor with an in-order five-stage pipeline (IF, ID, EX, MEM, and WB) and with the following characteristics.
1.121. A hiker faces the 0/1 Knapsack problem. There are 7 items to be packed into the knapsack, each with value vi and weight wi as shown in the following table.
1.122. Amdahl’s Law pertains to the speedup achieved when running a program on parallel processors versus using a single serial processor. In this context, speedup is the ratio of original running time to improved running time. According to Amdahl’s Law, approximately how much speedup could we expect for an unlimited number of processors if 10 percent of a program is sequential and the remaining part is ideally parallel?
1.123. Let T(n) be defined by T(0) = T(1) = 4 and T(n) = T(?n/2?) + T(?n/4?) + cn for all integers n = 2, where c is a positive constant. What is the asymptotic growth of T(n)?
1.124. 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? I. C is a queue and D is a queue. II. C is a stack and D is a stack. III. C is a queue and D is a stack.
1.125. Which of the following problems is (are) known to be solvable in running time O(n3)? I. 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. II. 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. III. 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.
1.126. The Fibonacci sequence Fn is defined by F1 = 1, F2 = 1, and Fn = Fn-2 + Fn-1 for all integers n = 3. 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.e., F1 through F7) and then wraps around?
1.127. An algorithm takes a list of 2n numbers [a1, a2, …, a2n] and replaces it with [b1, b2, …, b2n-1] where 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?
1.128. Consider the following instruction sequence for a hypothetical RISC processor.
1.129. Consider the following three statements. I. If language L is recognized by a nondeterministic finite automaton, then L is recognized by a deterministic finite automaton. II. If language L is recognized by a nondeterministic pushdown automaton, then L is recognized by a deterministic pushdown automaton. III. 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?
1.130. 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 [1..10].
1.131. 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. I. x (S(x, b) ? y S(x, y)) II. x yS(x, y) ? y xS(x, y) III. x ( S(x, x) ? S(b, x)) Which of the following best describes the predicate logic statements?
1.132. 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?
1.133. 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?
1.134. If L1 is a decidable language and L2 is an undecidable language, then L1 L2, the union of L1 and L2, is
1.135. Suppose that a certain software product has a mean time between failures of 10,000 hours and has a mean time to repair of 20 hours. If the product is used by 100 customers, what is its availability?
1.136. The object-oriented paradigm includes which of the following properties? I. Encapsulation II. Inheritance III. Recursion
1.137. Which of the following algorithms has running time O(n2) in the worst case but O(n log n) on average?
1.138. Which of the following is the name of the data structure in a compiler that is responsible for managing information about variables and their attributes?
1.139. Consider the following pseudocode.
1.140. Suppose that P(x, y) means “x is a parent of y” and M(x) means “x is male”. If F(v, w) equals M(v) x y (P(x, y) P(x, v) (y v) P(y, w)), what is the meaning of the expression F(v, w)?
1.141. Which of the following represents a postorder traversal of T?
1.142. If T is a binary search tree with the smaller elements in the left subtree, which of the following nodes contains the fourth smallest element in T?
1.143. Which of the following statements about Ethernets is typically FALSE?
1.144. A k-ary tree is a tree in which every node has at most k children. In a k-ary tree with n nodes and height h, which of the following is an upper bound for the maximum number of leaves as a function of h, k, and n?
1.145. Which of the following is (are) true about virtual memory systems that use pages? I. The virtual address space can be larger than the amount of physical memory. II. Programs must be resident in main memory throughout their execution. III. Pages correspond to semantic characteristics of the program.
1.146. Let T(n) be defined by T(1) = 7 and T(n + 1) = 3n + T(n) for all integers n = 1. Which of the following represents the order of growth of T(n) as a function of n?
1.147. One approach to handling fuzzy logic data might be to design a computer using ternary (base-3) logic so that data could be stored as “true,” “false,” and “unknown.” If each ternary logic element is called a flit, how many flits are required to represent at least 256 different values?
1.148. Hash tables can contribute to an efficient average-case solution for all of the problems described below EXCEPT:
1.149. An invariant for the loop below is “z * xk = bn and k = 0”.
1.150. In the Internet Protocol (IP) suite of protocols, which of the following best describes the purpose of the Address Resolution Protocol?
1.151. A certain pipelined RISC machine has 8 general-purpose registers R0, R1, ..., R7 and supports the following operations. ADD Rs1, Rs2, Rd - Add Rs1 to Rs2 and put the sum in Rd. MUL Rs1, Rs2, Rd - Multiply Rs1 by Rs2 and put the product in Rd. An operation normally takes one cycle; however, an operation takes two cycles if it produces a result required by the immediately following operation in an operation sequence. Consider the expression AB + ABC + BC, where variables A, B, C are located in registers R0, R1, R2. If the contents of these three registers must not be modified, what is the minimum number of clock cycles required for an operation sequence that computes the value of AB + ABC + BC?
1.152. Below is a precedence graph for a set of tasks to be executed on a parallel processing system S. Efficiency is defined as the ratio between the speedup and the number of processors. The speedup is defined as the ratio of the time taken to perform a set of tasks on a single processor to the time taken to perform the same set of tasks on a parallel processor. System S has four processors (CPU’s). If each of the tasks T1, ..., T8 takes the same time, what is the efficiency of this precedence graph on S?
1.153. Let G = (V, E) be a finite directed acyclic graph with |E| > 0. Which of the following must be true? I. G has a vertex with no incoming edge. II. G has a vertex with no outgoing edge. III. G has an isolated vertex, that is, one with neither an incoming edge nor an outgoing edge.
1.154. During the execution of the loop, how many bytes will be written to memory if the cache has a write-through policy?
1.155. During the execution of the loop, how many bytes will be written to memory if the cache has a write-back policy?
1.156. According to the IEEE standard, a 32-bit, single-precision, floating-point number N is defined to be N = (-1)S × 1.F × 2E-127 where S is the sign bit, F the fractional mantissa, and E the biased exponent. A floating-point number is stored as S: E: F, where S, E, and F are stored in 1 bit, 8 bits, and 23 bits, respectively. What is the decimal value of the floating-point number C1E00000 (hexadecimal notation)?
1.157. Which of the following predicate calculus formulas must be true under all interpretations? I. ( xP(x) xQ(x))? x(P(x) Q(x)) II. x(P(x) Q(x))?( x(P(x) xQ(x)) III. ( xP(x) xQ(x))? x(P(x) Q(x))
1.158. Suppose that all parameters are passed by value. Which of the following values are output when procedure mystery is called?
1.159. Suppose that all parameters are passed by reference. Which of the following values are output when procedure mystery is called?
1.160. Let A and B be two sets of words (strings) from S*, for some alphabet of symbols S. Suppose that B is a subset of A. Which of the following statements must always be true of A and B? I. If A is finite, then B is finite. II. If A is regular, then B is regular. III. If A is context-free, then B is context-free.
1.161. A CPU has an arithmetic unit that adds bytes and then sets its V, C, and Z flag bits as follows. The V-bit is set if arithmetic overflow occurs (in two’s complement arithmetic). The C-bit is set if a carry-out is generated from the most significant bit during an operation. The Z-bit is set if the result is zero. What are the values of the V, C, and Z flag bits after the 8-bit bytes 1100 1100 and 1000 1111 are added?
1.162. Let k be an integer greater than 1. Which of the following represents the order of growth of the expression ki as a function of n?
1.163. Mergesort works by splitting a list of n numbers in half, sorting each half recursively, and merging the two halves. Which of the following data structures will allow mergesort to work in O(n log n) time? I. A singly linked list II. A doubly linked list III. An array
1.164. Consider the following function.
1.165. Which of the following statements about datagrams sent by a node in a network using IPv4 protocol is (are) true? I. Datagrams at the source must be the size of the smallest maximum transmission unit (MTU) of all the links on a path to the destination. II. Datagrams may be fragmented during routing. III. Datagrams are reassembled only at the destination.
1.166. Of the following problems concerning a given undirected graph G, which is currently known to be solvable in polynomial time?
1.167. Two processors, M-5 and M-7, implement the same instruction set. Processor M-5 uses a 5-stage pipeline and a clock cycle of 10 nanoseconds. Processor M-7 uses a 7-stage pipeline and a clock cycle of 7.5 nanoseconds. Which of the following is (are) true? I. M-7’s pipeline has better maximum throughput than M-5’s pipeline. II. The latency of a single instruction is shorter on M-7’s pipeline than on M-5’s pipeline. III. Programs executing on M-7 will always run faster than programs executing on M-5.
1.168. For the following code, the bias of each conditional branch in the code is labeled on the control flow graph below. For example, the Boolean expression if_condition evaluates to true on one-half of the executions of that expression.
1.169. Consider the following grammar. S?(S) S?x Which of the following statements is (are) true? I. The grammar is ambiguous. II. The grammar is suitable for top-down parsing. III. The grammar is suitable for bottom-up parsing.
1.170. A logic circuit has three input bits: x0, x1, and x2, where x0 is the least significant bit and x2 is the most significant bit. The output from the circuit is 1 when its input is any of the 3-bit numbers 1, 4, 5, or 6; otherwise, the output is 0. Which of the following expressions represents the output from this circuit?
1.171. Which of the following problems can be solved by a standard greedy algorithm? I. Finding a minimum spanning tree in an undirected graph with positive-integer edge weights II. Finding a maximum clique in an undirected graph III. Finding a maximum flow from a source node to a sink node in a directed graph with positive-integer edge capacities
1.172. If m is composite, what is the probability that in each of the k different executions the output of A is Yes?
1.173. Suppose that in each of the k different executions the output of A is No. What is the probability that m is composite?
1.174. In systems with support for automatic memory management, a garbage collector typically has the responsibility for reclaiming allocated memory objects whose contents cannot affect any future legal computation. Such objects are identified by determining that they cannot be reached from a root set. Which of the following is NOT part of the root set in a typical garbage collector?
1.175. For a connected, undirected graph G = (V, E), which of the following must be true? I. Sv?V degree(v) is even. II. |E| = |V|-1 III. G has at least one vertex with degree 1.
1.176. Which of the following conditions can be expressed by a Boolean formula in the Boolean variables p1, p2, p3, p4 and the connectives (without )? I. At least three of p1, p2, p3, p4 are true. II. Exactly three of p1, p2, p3, p4 are true. III. An even number of p1, p2, p3, p4 are true.
1.177. Consider the collection of all undirected graphs with 10 nodes and 6 edges. Let M and m, respectively, be the maximum and minimum number of connected components in any graph in the collection. If a graph has no self-loops and there is at most one edge between any pair of nodes, which of the following is true?
1.178. Consider the following pseudocode, where n is a nonnegative integer.
1.179. In order to find a solution x* to the equation f(x) = 0 for a polynomial f(x) of degree = 2 with derivative f'(x*) ? 0, Newton’s method does iterations of the form xt+1 = xt - f(xt)/f'(xt), starting with some initial value x0 ? x* sufficiently close to the desired solution x* to ensure convergence to x*. For fixed values of x0 and x*, which of the following represents the order of growth of the minimal number of iterations required to compute x* to b bits of accuracy as a function of b?
1.180. Which of the following statements about a remote procedure call is true?
1.181. Let M be a single-tape, deterministic Turing machine with tape alphabet {blank,0,1}, and let C denote the (possibly infinite) computation of M starting with a blank tape. The input to each problem below is M, together with a positive integer n. Which of the following problems is (are) decidable? I. The computation C lasts for at least n steps. II. The computation C lasts for at least n steps, and M prints a 1 at some point after the nth step. III. M scans at least n distinct tape squares during the computation C.
1.182. Which of the following is NOT a property of bitmap graphics?
1.183. In a pipelined RISC computer where all arithmetic instructions have the same CPI (cycles per instruction), which of the following actions would improve the execution time of a typical program? I. Increasing the clock cycle rate II. Disallowing any forwarding in the pipeline III. Doubling the sizes of the instruction cache and the data cache without changing the clock cycle time
1.184. Which of the following is the general step in the recurrence, where 1 = k = n?
1.185. What is the running time of the Floyd-Warshall algorithm?
1.186. A transaction schedule is serializable if its effect is equivalent to that of some serial schedule. Consider a bookkeeping operation consisting of two transactions - T1 and T2 - that are required to keep the sum A + B + C unchanged. Which of the following pairs of transactions will always result in a serializable schedule?
1.187. Which of the following is NOT a reasonable justification for choosing to busy-wait on an asynchronous event?
1.188. The Singleton design pattern is used to guarantee that only a single instance of a class may be instantiated. Which of the following is (are) true of this design pattern? I. The Singleton class has a static factory method to provide its instance. II. The Singleton class can be a subclass of another class. III. The Singleton class has a private constructor.
1.189. Assume that a target t is an integer value stored in some element of integer array x, which is sorted in nondecreasing order, and consider the following outline of a loop to search for t.
1.190. Assume that a debugger places a breakpoint at a load instruction at virtual address 0x77E81234 (hexadecimal notation) in a debugged process P. If the text segment of P begins at 0x77E80000 in P’s virtual address space and if the debugger has mapped this same text segment at 0x01000000 in its virtual address space, which of the following is the virtual address used by the debugger in its WRITE operation, along with a description of how the debugger has mapped the virtual memory page containing this address?
1.191. Company X shipped 5 computer chips, 1 of which was defective, and Company Y shipped 4 computer chips, 2 of which were defective. One computer chip is to be chosen uniformly at random from the 9 chips shipped by the companies. If the chosen chip is found to be defective, what is the probability that the chip came from Company Y?
1.192. An Euler circuit of an undirected graph is a circuit in which each edge of the graph appears exactly once. Which of the following undirected graphs must have an Euler circuit? I. A complete graph with 12 vertices II. A complete graph with 13 vertices III. A tree with 13 vertices
1.193. Consider the following two languages. L1 = {x {a, b}* | x has equally many a’s and b ’s} L2 = {x {a, b, c}* | x has equally many a’s, b’s, and c ’s} Which of the following is true about L1 and L2?
1.194. Consider the following possible data structures for a set of n distinct integers. I. A min-heap II. An array of length n sorted in increasing order III. A balanced binary search tree For which of these data structures is the number of steps needed to find and remove the 7th largest element O(logn) in the worst case?
1.195. Which of the following problems is (are) decidable? I. Given a (finite) string w, is w a prefix of the decimal expansion of p? II. Given a program and an input, is the program’s output the decimal expansion of p? III. Given a program that takes as input a prefix of the decimal expansion of p, is the program’s output always the same for every prefix?
1.196. Which of the following problems would have polynomial time algorithms if it is assumed that P # NP? I. Given a combinational circuit with n inputs and m outputs and n2 gates, where each gate is either AND, OR, or NOT, and given m values c1, ... , cm in {0, 1}, either find a string of n input values b1, ... , bn in {0, 1} that would produce c1, ... , cm as output or determine that c1, ... , cm is not a possible output of the circuit. II. Given an n by n matrix A with rational number entries, either find the exact inverse A-1 of A or determine that A-1 does not exist. Assume that each rational number is expressed as a pair a/b of integers (b # 0), where a and b are expressed in binary notation. III. Given a directed graph with nodes numbered 1, 2, ... , n, and given positive integer weights assigned to the edges, either find the length of a shortest path from node 1 to node n or determine that no such path exists. Here the length of a path is the sum of the lengths of the edge weights on the path.
1.197. Which of the following characteristics of a programming language is best specified using a context-free grammar?
1.198. Consider the following function.
1.199. Let T be a depth-first search tree of a connected undirected graph G. For each vertex v of T, let pre(v) be the number of nodes visited up to and including v during a preorder traversal of T, and post(v) be the number of nodes visited up to and including v during a postorder traversal of T. The lowest common ancestor of vertices u and v in T is a vertex w of T such that w is an ancestor of both u and v, and no child of w is an ancestor of both u and v. Let (u, v) be an edge in G that is not in T, such that pre(u) < pre(v). Which of the following statements about u and v must be true? I. post(u) < post(v) II. u is an ancestor of v in T. III. If w is the lowest common ancestor of u and v in T, then w = u.
1.200. Consider languages L and L1, each over the alphabet {a, b}, where L1 = {w | w contains some x L as a substring}. Which of the following must be true about L and L1? I. If L is regular, then L1 is regular. II. If L is context-free, then L1 is context-free. III. If L is recursive, then L1 is recursive.
1.201. For each nonnegative integer n, let Rn be the greatest possible number of regions into which the plane can be partitioned by n straight lines. For example, R0 = 1 and R1 = 2. Then Rn has order
1.202. Which of the following comes closest to being a perfectly secure encryption scheme?
1.203. Suppose Q and R are languages. Assuming P # NP, which of the following implies that R is not in P?
1.204. Let N be the set of all natural numbers. Which of the following sets are countable? I. The set of all functions from N to {0, 1} II. The set of all functions from {0, 1} to N III. The largest subset of N
1.205. Any set of Boolean operators that is sufficient to represent all Boolean expressions is said to be complete. Which of the following is NOT complete?
1.206. Which of the following decimal numbers has an exact representation in binary notation?
1.207. Bob writes down a number between 1 and 1,000. Mary must identify that number by asking "yes/no" questions of Bob. Mary knows that Bob always tells the truth. If Mary uses an optimal strategy, then she will determine the answer at the end of exactly how many questions in the worst case?
1.208. If x is a string, then xR denotes the reversal of x. If x and y are strings, then (xy)R =
1.209. A procedure that printed the following binary tree in postorder would produce as output
1.210. Which of the following is NOT a binary search tree?
1.211. Consider the following Pascal-like program fragment.
1.212. A starvation-free job-scheduling policy guarantees that no job waits indefinitely for service. Which of the following job-scheduling policies is starvation-free?
1.213. Consider a singly linked list of the following form where F is a pointer to the first element in the list and L is a pointer to the last element in the list. The time of which of the following operations depends on the length of the list?
1.214. For the program fragment below involving integers p, k, and n, which of the following is a loop invariant; i.e., true at the beginning of each execution of the loop and at the completion of the loop?
1.215. Consider an output-producing, deterministic finite state automaton (DFA) of the kind indicated in the figure below, in which it is assumed that every state is a final state. Assume that the input is at least four bits long. Which of the following is (are) true? I. The last bit of the output depends on the start state. II. If the input ends with "1100", then the output must end with "1". III. The output cannot end with "1" unless the input ends with "1100".
1.216. A particular BNF definition for a "word" is given by the following rules.
1.217. How many lines of output does the program produce?
1.218. Which of the following is the integer that best approximates the last number printed?
1.219. An integer c is a common divisor of two integers x and y if and only if c is a divisor of x and c is a divisor of y. Which of the following sets of integers could possibly be the set of all common divisors of two integers?
1.220. Consider the following grammar.
1.221. A particular parallel program computation requires 100 seconds when executed on a single processor. If 40 percent of this computation is "inherently sequential" (i.e., will not benefit from additional processors), then the theoretically best possible elapsed times for this program running with 2 and 4 processors, respectively, are
1.222. The lookup page table shown below is for a job in a paged virtual storage system with a page size of 1,024 locations. Each virtual address is in the form [p, d] where p and d are the page number and the displacement in that page, respectively. A virtual address of [0, 514] maps to an actual address of
1.223. If the expression ((2 + 3) * 4 + 5 * (6 + 7) * 8) + 9 is evaluated with * having precedence over +, then the value obtained is the same as the value of which of the following prefix expressions?
1.224. Let P be a procedure that for some inputs calls itself (i.e., is recursive). If P is guaranteed to terminate, which of the following statements must be true? I. P has a local variable. II. P has an execution path where it does not call itself. III. P either refers to a global variable or has at least one parameter.
1.225. Consider a computer design in which multiple processors, each with a private cache memory, share global memory using a single bus. This bus is the critical system resource. Each processor can execute one instruction every 500 nanoseconds as long as memory references are satisfied by its local cache. When a cache miss occurs, the processor is delayed for an additional 2,000 nanoseconds. During half of this additional delay, the bus is dedicated to serving the cache miss. During the other half, the processor cannot continue, but the bus is free to service requests from other processors. On average, each instruction requires 2 memory references. On average, cache misses occur on 1 percent of references. What proportion of the capacity of the bus would a single processor consume, ignoring delays due to competition from other processors?
1.226. In multiprogrammed systems it is advantageous if some programs such as editors and compilers can be shared by several users. Which of the following must be true of multiprogrammed systems in order that a single copy of a program can be shared by several users? I. The program is a macro. II. The program is recursive. III. The program is reentrant.
1.227. A particular disk unit uses a bit string to record the occupancy or vacancy of its tracks, with 0 denoting vacant and 1 denoting occupied. A 32-bit segment of this string has the hexadecimal value D4FE2003. The percentage of occupied tracks for the corresponding part of the disk, to the nearest percent, is
1.228. A program that checks spelling works in the following way. A hash table has been defined in which each entry is a Boolean variable initialized to false. A hash function has been applied to each word in the dictionary, and the appropriate entry in the hash table has been set to true. To check the spelling in a document, the hash function is applied to every word in the document, and the appropriate entry in the hash table is examined. Which of the following is (are) correct? I. true means the word was in the dictionary. II. false means the word was not in the dictionary. III. Hash table size should increase with document size.
1.229. The finite automaton below recognizes a set of strings of length 6. What is the total number of strings in the set?
1.230. Let S be the statement: for i :=1 to N do V[i] := V[i] +1 Which of the following perform(s) the same changes to V as S?
1.231. For the program fragment below, which of the following statements about the variables i and j must be true after execution of the fragment?
1.232. Each of the following is a regular expression that denotes a subset of the language recognized by the automaton below EXCEPT
1.233. If the rest of the program is as follows,
1.234. In another program written in a Pascal-like language with the same heading and type declaration, assume that a choice must be made between the following two options.
1.235. An XY flip-flop operates as indicated by the following table.
1.236. A black-and-white computer graphics display is divided up into an array of pixels as shown below. Each of the pixels can take on one of eight gray levels ranging from 0 (white) to 7 (black). In order to prevent sharp discontinuities of shade, the software system that causes pictures to be displayed enforces the rule that the gray levels of two adjacent pixels cannot differ by more than two. How many of the 64 possible assignments of gray levels to two adjacent pixels satisfy this rule?
1.237. A doubly linked list is declared as below where Fwd and Bwd represent forward and backward links to adjacent elements of the list. Which of the following segments of code deletes the element pointed to by X from the doubly linked list, if it is assumed that X points to neither the first nor the last element of the list?
1.238. Processes P1 and P2 have a producer-consumer relationship, communicating by the use of a set of shared buffers:
1.239. Which of the following instruction-set features is NOT generally considered an obstacle to aggressive pipelining of an integer unit?
1.240. Let A be the representation function from IntSet into "set of integers" such that, for each concrete object S of type IntSet, A(S) is the set of integers represented by S.A(S) can be written as
1.241. An advantage of choosing this implementation of "set of integers" is that adding an element to a set is a constant-time operation. Which of the following is a disadvantage of this implementation?
1.242. The following code fragment mutates concrete IntSet objects.
1.243. To compute the matrix product M1M2, where M1 has p rows and q columns and where M2 has q rows and r columns, takes time proportional to pqr, and the result is a matrix of p rows and r columns. Consider the product of three matrices N1N2N3 that have, respectively, w rows and x columns, x rows and y columns, and y rows and z columns. Under what condition will it take less time to compute the product as (N1N2)N3 (i.e., multiply the first two matrices first) than to compute it as N1(N2N3)?
1.244. Which of the following is usually NOT represented in a subroutine's activation record frame for a stack-based programming language?
1.245. Let A be a finite nonempty set with cardinality n. The number of subsets S A having odd cardinality is
1.246. A certain algorithm A has been shown to have running time O(N2.5), where N is the size of the input. Which of the following is NOT true about algorithm A?
1.247. A data structure is comprised of nodes each of which has exactly two pointers to other nodes, with no null pointers. The following C program is to be used to count the number of nodes accessible from a given node. It uses a mark field, assumed to be initially zero for all nodes. There is a statement missing from this code.
1.248. Of the following, which best characterizes computers that use memory-mapped I/O?
1.249. At lower multiprogramming levels, throughput increases as multiprogramming level increases. This phenomenon is best explained by the fact that as multiprogramming level increases
1.250. At intermediate multiprogramming levels, the rate of increase of throughput with multiprogramming levels decreases. This phenomenon is best explained by the fact that as multiprogramming level increases
1.251. If Tree1 and Tree2 are the trees indicated below, which traversals of Tree 1 and Tree2, respectively, will produce the same sequence of node names?
1.252. Let A be a finite set with in elements, and let B be a finite set with n elements. The number of distinct functions mapping A into B is
1.253. The "parsing automaton" below is for the context-free grammar with the productions indicated below. Each state includes certain "items," which are productions with dots in their right sides. The parser using this automaton, with X1X2...Xn on the stack, reduces by production A ? a if and only if there is a path, labeled X1X2...Xn from the start state to a state that includes the item A ? a. (note the dot at the right end). Which of the following stack contents causes the parser to reduce by some production?
1.254. Let k = 2. Let L be the set of strings in {0,1}* such that x L if and only if the number of 0's in x is divisible by k and the number of 1's in x is odd. The minimum number of states in a deterministic finite automaton (DFA) that recognizes L is
1.255. In the diagram below, the inverter and the AND-gates labeled 1 and 2 have delays of 9, 10, and 12 nanoseconds, respectively. Wire delays are negligible. For certain values of a and c, together with a certain transition of b, a glitch (spurious output) is generated for a short time, after which the output assumes its correct value. The duration of the glitch is
1.256. Of the following sorting algorithms, which has a running time that is LEAST dependent on the initial ordering of the input?
1.257. A certain well-known computer family represents the exponents of its floating-point numbers as "excess-64" integers; i.e., a typical exponent e6e5e4e3e2e1e0 represents the number e = -64 + 2iei . Two such exponents are input to a conventional 7-bit parallel adder. Which of the following should be accomplished in order to obtain a sum that is also in excess-64 notation?
1.258. Assume that N = 2M and FIFO is used. If the string p1,p2,…pN is repeated three times, then the number of page faults is
1.259. If the string of N requests is repeated many times, which of the following is (are) true? I. The fewest page faults occur when M = N. II. LRU and FIFO will always result in the same number of page faults. III. LIFO will always result in the fewest possible page faults.
1.260. The logic circuit below is used to compare two unsigned 2-bit numbers, X1 X0 = X and Y1 Y0 = Y, where X0 and Y0 are the least significant bits. (A small circle on any line in a logic diagram indicates logical NOT.) Which of the following always makes the output Z have the value 1?
1.261. It is known that the language L {a,b}* that consists of all strings that contain an equal number of a's and b's is context-free. Let M be the regular language a*b*. Which of the following is (are) true? I. L M is a context-free language. II. L M is a regular language. III. L M = {anbm | n is a positive integer less than integer m}.
1.262. Of the following, which gives the best upper bound for the value of f(N) where f is a solution to the recurrence f(2N + 1) = f(2N) = f(N) + log N for N = 1, with f(1) = 0?
1.263. Let I denote the formula: (q p) (p q) Let II denote the formula: (p q) q Which of the following is true?
1.264. Consider a data type whose elements are integers and whose operations are INSERT, DELETE, and FINDCLOSEST, with FINDCLOSEST(y) defined to be some element x in the current set such that |x – y| = |xi – y| for all xi in the current set. Let T = max(TINSERT, TDELETE, TFINDCLOSEST) where TOP denotes the worst-case time complexity for the given operation OP. Which of the following data structures would be best to use in order to minimize T?
1.265. A block of 105 words of memory is used for dynamic storage for objects of sizes 3 and 10 words. The operations supported by the storage are:
1.266. Languages with a structure that implements abstract data types (e.g., a C++ class) can prevent access to components of this structure by all operations except those that are part of this structure. However, definitions of such a structure often contain declarations of components of the structure (e.g., the header file for a C++ class may contain declarations of its private components). For such a language, an object's name could be bound at run time to stack storage for its component values (direct representation) or to a stack pointer referencing heap storage for its component values (indirect representation). Which of the following statements about comparisons between direct and indirect representations is (are) true? I. Indirect representation noticeably increases compilation time. II. Direct representation decreases the time needed to access components of a variable. III. When the storage size of some private component of a variable changes, indirect representation minimizes the number of recompilations of source modules that must be performed.
1.267. In a 2-ordered array of 2N elements, what is the maximum number of positions that an element can be from its position if the array were 1-ordered?
1.268. In an array of 2N elements that is both 2- and 3-ordered, what is the maximum number of positions that an element can be from its position if the array were 1-ordered?
1.269. Consider a queue between the two processes indicated below. N is the length of the queue; e, f, and b are semaphores.
1.270. Church's thesis equates the concept of "computable function" with those functions computable by, for example, Turing machines. Which of the following is true of Church's thesis?
1.271. Consider the following C code.
1.272. Let G = (V,E) be a connected, undirected graph, and let a and b be two distinct vertices in V. Let P1 be the problem of finding a shortest simple path between a and b, and let P2 be the problem of finding a longest simple path between a and b. Which of the following statements about P1 and P2 is true?
1.273. Let T denote a nonempty binary tree in which every node either is a leaf or has two children. Then n(T) denotes the number of non-leaf nodes of T (where n(T) = 0 if T is a leaf), h(T) denotes the height of T (where h(T) = 0 if T is a leaf), TL denotes the left subtree of T, and TR denotes the right subtree of T. If F is a function defined by
1.274. If DFA denotes "deterministic finite automata" and NDFA denotes "nondeterministic finite automata," which of the following is FALSE?
1.275. Which single node label of the tree below should be replaced so as to make the resulting tree a valid binary search tree?
1.276. The infix expression A - (B + C) * (D / E) is equivalent to which of the following postfix expressions?
1.277. Consider the following equations concerning a stack module that has the operations Push, Pop, Top, and IsEmpty. Which of the equations does NOT represent the conventional semantics of a stack?
1.278. Which of the following pairs of 8-bit, two's-complement numbers will result in overflow when the members of the pairs are added?
1.279. An internal hash table has 5 buckets, numbered 0, 1, 2, 3, 4. Keys are integers, and the hash function h(i) = i mod 5 is used, with linear resolution of collisions (i.e., if bucket h (i) is filled, the buckets h (i) + 1, h (i) + 2, . . . are tried successively with all bucket numbers computed modulo 5). If elements with keys 13, 8, 24, 10, and 3 are inserted, in that order, into an initially blank hash table, then the content of the bucket numbered 2 is
1.280. Which of the following sets of bit strings CANNOT be described with a regular expression?
1.281. Which of the following language features requires that stack-based storage allocation be used rather than static allocation?
1.282. The figure below shows a 4-bit, right-shift register and a NOR gate. If the register outputs {ABCD} at time 0 are 0110, then their values four clock pulses later are
1.283. How many nodes (including * nodes) are there in the trie for "do", "dog", "door", and "doors" ?
1.284. Which of the following statements about the implementation of tries is NOT true?
1.285. Of the following page-replacement policies, which is guaranteed to incur the minimum number of page faults?
1.286. Which of the following statements describe(s) properties of a purely segmented memory system? I. It divides memory into units of equal size. II. It permits implementation of virtual memory. III. It suffers from internal fragmentation.
1.287. In the tree below, some of the nodes n have an attribute Color(n). To determine a color for a given node n, the following pseudo-Pascal code is executed.
1.288. Consider the following procedure, where SetType is an implementation for sets. procedure Insert(s : SetType; i : integer); (* Precondition: i so, where so denotes the value of s *) (* Postcondition: s is the union of so and the singleton set {i} *) Which of the following statements is (are) true concerning the call Insert(s,i)? I. If the precondition is met, then, upon return from the call to Insert, the size of s will have increased by 1. II. The writer of any code that includes a call to Insert can assume i is not in s prior to the call. III. The writer of any code for the body of Insert can assume i is not in s upon entrance to the procedure.
1.289. In which of the following representations of numbers by 8-bit words is the addition of the integers 109 and -42 within range? I. One's complement. II. Two's complement. III. Sign and magnitude
1.290. Between points 1 and 2, system throughput increases because
1.291. Between points 2 and 3, system throughput decreases because
1.292. A product-of-sums expression for the function BD + CD is
1.293. An independent set I of nodes of a graph G is a collection of nodes of G such that no two nodes of I are adjacent in G. A maximal independent set M of a graph G is an independent set such that if x is any node of G that is not in M, then M {x} is not an independent set. Which of the following is a maximal independent set of the graph in the figure above?
1.294. A sequential circuit emits a 1 if and only if a 1 has just been received and the system has received an even number of 0's and an even number of l's since it was reset. The system resets on emitting a 1. Which of the following is a possible state diagram for this circuit, where A is the initial (start) state?
1.295. Which of the following statements about circuits is(are) true? I. Combinational circuits may have feedback; sequential circuits do not. II. Combinational circuits have a "memoryless" property; sequential circuits do not. III. Both sequential and combinational circuits must be controlled by an external clock.
1.296. What is the maximum possible number of directed edges in an n-node, simple, acyclic, directed graph?
1.297. What is the maximum possible number of edges in an n-node, simple, acyclic, undirected graph?
1.298. Suppose sharing of files in a multilevel directory structure is achieved with directory entries that are links pointing to a node containing information about a shared file. Information in this node includes (1) the owner of the file, (2) a count of the number of links to the file, and (3) the disk block numbers of the file. What is a primary drawback to this approach to sharing?
1.299. Which of the following considerations applies (apply) to choosing the page size in a paging system? I. An advantage of larger pages is that they lead to smaller page tables. II. An advantage of smaller pages is that they lead to less waste due to internal fragmentation. III. Normally, the dominant factor in disk access time is not dependent on page length, so longer pages can be used advantageously.
1.300. A switch is an element of the type that connects p and t to r and s. The connections may be either straight (p to r; t to s) or crossed (p to s; t to r). The network below is used to connect four processors, A, B, C, D, to four memories, W, X, Y, Z. Which of the following connections can be achieved by some combination of switch settings?
1.301. For a given problem with inputs of size n, two algorithms are run, one requiring time c*n and the other requiring time d*n2, where c and d are constants. Some measured running times of these algorithms are given below.
1.302. Carol, Ted, and Alice are three users of the system. Carol and Alice are in the same group. Ted is a Super User. Which of the following rights is INCONSISTENT with the given policies?
1.303. Which of the following pieces of security-policy information CANNOT be determined from an access-rights matrix?
1.304. Consider the following postcondition for a routine that is supposed to sort an array A[1...n] in nondecreasing order. "1 = i < n implies A[i] = A[i + 1]" Which of the following statements is true about this postcondition?
1.305. 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?
1.306. A 3-way, set-associative cache is
1.307. Which of the following best characterizes the language generated by the grammar S ? aSb | bSa | SS | ??
1.308. Which of the following statements is FALSE about memory reclamation based on reference counting?
1.309. Which of the following evaluation strategies must be defined in order to execute a logic program on a sequential machine? I. Evaluation order of rules. II. Evaluation order of clauses. III. Evaluation order of arguments in each clause.
1.310. Consider an object-oriented language in which all entities are objects. Two relationships arise: (1) the instance relationship, between an object and the class of which that object is a member, and (2) the subclass relationship, between a class and the superclass from which that class inherits properties. In such a language, when a message is sent to an object requesting execution of one of its methods (procedures), the method is located by following
1.311. Suppose it takes 1 second to factor a general 100 × 100 matrix using Gaussian elimination. Of the following, which is the best estimate of the number of seconds it will take to factor a 500 × 500 matrix based on the relative dimensions?
1.312. At time 0, five jobs are available for execution on a single processor, with service times of 25, 15, 5, 3, and 2 time units. Which of the following is the minimum value of the average completion time of these jobs?
1.313. Consider the representation of the array var A: array[L1..U1, L2..U2] of integer; on a word-addressable machine on which arrays are stored in row-major order and integers occupy one word. The location of A[I, J] can be calculated as follows. Loc(A[I, J]) = Loc(A[L1, L2]) + (I - L1)*Multiplier1+(J - L2)*Multiplier2 where Multiplieri is the number of words between elements whose subscripts differ by 1 in dimension i. The "origin" of an array is Loc(A[L1, L2]). To reduce the number of run-time subtractions, it is useful to calculate a "virtual origin," defined as Loc(A[0, 0]) (whether or not this element exists in the actual array). The virtual origin of the array var A: array[-3..2, 5..7] of integer is
1.314. Which of the following best indicates the maximum number of times that the assignment statement B[i, j] := true (marked 1 in the procedure) can be executed
1.315. The transitive closure of the graph G is an n × n matrix T such that
1.316. A compiler generates code for the following assignment statement. G := (A + B)* C - (D + E)* F The target machine has a single accumulator and a single-address instruction set consisting of instructions load, store, add, subtract, and multiply. For the arithmetic operations, the left operand is taken from the accumulator and the result appears in the accumulator. The smallest possible number of instructions in the resulting code is
1.317. Consider the following directed graph. This graph has six vertices (labeled A-F) and eleven directed edges AB, BC, BE, BF, CA, DB, EA, ED, EF, FC, and FD. Which of the following properties does this graph have? I. It has a planar embedding. II. It is strongly connected. III. It has a directed Hamiltonian path starting at C.
1.318. Which of the following statements is (are) true about binary search in a[1..N], where N is a large positive integer? I. If x is present in a[1..N], then x is always found within O(log N) comparisons. II. If x is not present in a[1..N], then failure is always reached within O(log N) comparisons. III. Searching for two different values of x, neither of which is present in a[1..N], always takes the same number of steps to determine failure.
1.319. Suppose that the first step in the binary search algorithm given above is changed to "Let M = (3L + R) div 4." What effect does this have on the worst-case number of comparisons for searching in a[1..N], where N is a large positive integer?
1.320. Which of the following statements about floating-point arithmetic is NOT true?
1.321. Consider the following functions written in a procedural language.
1.322. Assume that any assignment statement can be executed in unit time. If as many identical processors as needed are used, what is the minimum number of time units needed to execute the assignments
1.323. If a round-robin scheduling algorithm with a time slice of 10 milliseconds is assumed, then at approximately what time is Job 3 completed?
1.324. If a first-come-first-served scheduling algorithm is assumed, where ties are resolved in favor of the smaller-numbered job, what is the average (arithmetic mean) number of seconds that a job waits before being assigned to the processor?
1.325. A grammar is said to be "useless" if and only if it produces no terminal strings. If S is the start symbol, which of the following grammars is (are) "useless"?
1.326. What is the output of the program shown above if it is assumed that references to nonlocal variables are resolved using static scoping?
1.327. What is the output of the program shown above if it is assumed that references to nonlocal variables are resolved using dynamic scoping?
1.328. The set of five binary words shown as rows below is used as a code. Because of channel noise, any sequence of five bits could be received. A code is said to be able to correct all k-bit errors if no received word can have Hamming distance k or less from two different code words. (The Hamming distance between two binary words is the number of bit positions in which they differ.) A code is said to be able to detect all k-bit errors if no code word is at a Hamming distance of k or less from any other code word. Which of the following is true of the code below? 00011 01101 00101 11001 01111
1.329. How many times is the function X called when X(X(5)) is evaluated?
1.330. As a function of N, which of the following best describes the running time of this function when invoked with the call X(N)?
1.331. As a function of X(N), which of the following best describes the running time of this function when invoked with the call X(N)?
1.332. Which of the following conditions is (are) necessary to assure that program fragment C2 can replace program fragment C1 within an otherwise arbitrary program without changing what the surrounding program does? I. x is dead (its value will not subsequently be needed) on exit from the while loop. II. n = 1 on entry to the while loops. III. i is dead on exit from the while loops.
1.333. If p(x) is the minimal-degree interpolating polynomial for the real-valued function f(x) at the n + 1 distinct real numbers x0, ... , xn, what is the maximum possible degree of p(x)?
1.334. Magic memory has two operations: Read and Clear. Both are indivisible and mutually exclusive. Clear sets the magic memory to zero. Read returns a value that represents the number of Read operations since the last Clear operation. Which of the following is(are) true of "Magic memory"? I. It can provide the functionality of an atomic Test-and-Set. II. It can be used to coordinate processes running on a shared-memory multiprocessor. III. It is only useful on a multiprocessor.
1.335. Which of the following characterizes the nature of the formulas below? I. (P P) II. ((P P) or ( P P))
1.336. A multiplexor, shown below on the right, has six inputs, S0, S1, A, B, C, and D. The truth table on the left describes its function. It is desired to implement the function F = (X Y) Z using the multiplexor. If X is applied to S0 and Y is applied to S1, what inputs should be applied to A, B, C, and D to realize the function F?
1.337. Function signatures describe the types of the arguments to a function as well as the return value of the function. For instance, the addition function on reals has a signature of
1.338. If T(0) = T(1) = 1, each of the following recurrences for n = 2 defines a function T on the nonnegative integers. Which CANNOT be bounded by a polynomial function?
1.339. Which of the following sets of productions determine(s) an ambiguous context-free grammar?
1.340. The hit ratio of a cache memory is the percentage of accesses (reads and writes) for which data are found in the cache. Write-through is a policy whereby every write operation updates main memory. Write-back is a policy whereby a write operation to a line found in the cache does not affect main memory until the line is evicted from the cache. Write-allocation is a policy whereby a cache line is allocated and loaded on a write-miss. If it is assumed that write-allocation is always used, which of the following is true?
1.341. The 64k address space of a certain microcomputer is accessed by address signals A0, A1, ..., A14, A15 (where A0 is the least significant bit and A15 is the most significant bit) and is divided unequally among read-only memory (ROM), read-write memory (RAM), and input-output registers (I/O) by means of the decoder and gates shown above. Note that only the three high-order outputs of the decoder are used. Output i (0 = i = 7) of the decoder is 1 if and only if the binary value of the inputs A15A14A13 is i. Which of the following correctly indicates the beginning and ending hexadecimal addresses of the three portions of the address space?
1.342. Which of the following statements about horizontal versus vertical microarchitecture is (are) true? I. Programs for horizontal architectures require more time steps than those for vertical architectures. II. Horizontal microinstructions are unencoded. III. Horizontal microinstructions usually have a single opcode and multiple operand specifiers.
1.343. The Karnaugh map shown below illustrates a switching function f(A,B,C,D) that includes five "don't cares." Which of the following expressions is (are) valid representations of f?
1.344. As a generating function, 1/(1-2z) generates the sequence 1, 2, 4, 8, 16, .... Which of the following is the generating function for the sequence 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...?
1.345. Resolution theorem proving for showing that a formula of propositional logic is not satisfiable has which of the following properties? I. It is a sound proof system in the sense that there does not exist a proof of the unsatisfiability of a satisfiable formula of propositional logic. II. It is a complete proof system in the sense that there is a proof of unsatisfiability for every unsatisfiable formula of propositional logic. III. It is a succinct proof system in the sense that whenever an unsatisfiable formula F of propositional logic has a resolution proof, F also has a proof whose length is polynomial in the length of F.
1.346. A "strictly binary tree" is a binary tree in which every node that is not a leaf has two children. Suppose that for a class of strictly binary trees there exists c > 0 such that, for any tree in the class, the ratio of the lengths of any two root-to-leaf paths is bounded above by c. Which of the following best characterizes the height h of any tree in this class, where N is the number of nodes in the tree and N > 1?
1.347. If the cube root of 7 is approximated by applying Newton's method to the function f(x) = x3 - 7, with initial value x0 and successive approximations x1, x2, x3, ..., which of the following is(are) true?
1.348. For all strings x, the function xM is defined recursively as follows.
1.349. If all inputs to device D become available simultaneously, which output will be available last?
1.350. If all inputs to device D become available simultaneously, what is the delay before S2 must be valid?
1.351. If x = 3(564) mod 7 and y = 3(564) mod 9, which of the following is true?
1.352. Many cryptographic protocols base their security on assumptions about the computational difficulty of integer factorization. Integer factorization serves this purpose because we believe that
1.353. Consider the following grammars, each with start symbol S.
1.354. The figure below shows part of a CPU with parallel data paths A, B, F, G, and H. The information on these paths is interpreted as integers in two’s-complement notation. The four control signals x, y, z, and (the low-order carry-in) c0, come from a control unit and cause the boxes in the figure to implement the following functions: F = ?A ? xB; G = yB z; H = F + G + c0 where ? is bit-wise OR, is bit-wise exclusive OR, the bit-wise AND is denoted by juxtapositions, and + is arithmetic plus. Which of the following values of H CANNOT be realized by some combination of the control signals and c0?

 
   

Content Copyright Basandra Books 2011. All Rights Reserved.