Advertisement
Only the second half from what someone posted on the facebook group. If anyone has the data for the first half all on one thing, lmk
43. Which of the following are advantages of the first-child / next-sibling representation of trees?
o A: faster execution
o B: promotes family values
o C: unlimited number of children
o D: saves memory
o E: C and D
C is true because first-child / next-sibling in effect gives each node a lin thus the number of children is unlimited. D is true because each node contains only 2 links, making it use less storage than a representation that stores a link for each child if there can be more than 2 children per node.
44. What is the Big O of finding an item in a balanced BST?
o B: O(log n)
o D: O(n log n)
o E: O(n2)
A BST, or Binary Search Tree, is ordered so that all descendants to the left of a node have a key value that is less, and all descendants to the right of a node have a key value that is greater. Thus, a search can discard half the tree at each step, giving a O(log n) search time.
45. What kind of tree is most similar to our directory tree?
o A: Binary tree
o B: n-ary tree
o D: First-child / next-sibling
o E: Implicit tree
The directory tree used in the class notes, p. 132, is like a first-child / next-sibling tree because each node has a linked list of its children.
50. Why do binary search trees need to be balanced?
o A: saves search time
o B: saves memory
o C: easier to draw
o D: unbalanced trees may cause errors
o E: A, B, and C
Balancing of a BST is important to give the desired O(log n) search time. If the tree is unbalanced, search time could be as bad as O(n). While O(n) is not always bad, we expect a lookup table to have a time of O(1) or O(log n) because lookup is done frequently, often in a loop. (Unless the table is known to be small, in which O(n) is okay.)
51. What would the branching factor b need to be for a tree with n = 1,000,000,000 elements at the bottom to have a height (depth) d of 3?
Our formula for trees is n = b d.
Thus, we have 1,000,000,000 = b3, which gives b = 1,000.
A large branching factor, as found in B-trees, allows a desired record to be found in a large database with a small number of (slow) disk accesses. If the first 2 levels of this tree are kept in memory (1,000 + 1,000,000 items), any record in the billion-record database can be gotten with a single disk access.
52. About how long does it take to read a record from a disc drive?
o A: 10 microseconds (0.00001 second)
o B: 100 microseconds (0.0001 second)
o C: 1 millisecond (0.001 second)
o D: 10 milliseconds (0.01 second)
o E: 100 milliseconds (0.1 second)
Disk access takes around 10 milliseconds, 1/100 of a second. While this seems fast, a computer can execute millions of instructions in this amount of time. Thus, disk access can easily become a bottleneck, which is why it takes so long to boot up your computer.
53. If we divide a 1 TB disc drive equally among all possible social security numbers, how many bytes are there per SSN?
o D: 10,000
o E: 100,000
A terabyte is 1012 bytes. There are 9 digits in a SSN, hence 109 possible SSN's. Dividing gives 103 bytes per SSN.
If we compute a disk address directly from the SSN, we can access the record for any SSN with one (slow) disk access.
Although not all SSN's are valid, disk space is cheap, so it is okay to waste some of it.
54. What is the value of (list(&a&) == list(&a&))
o B: false
o D: error
o E: could be true or false
Today's Zen question: What is the meaning of == ?
The meaning of the == for reference types (any Capital-letter type in Java such as String) is: exact equivalance of pointer values, i.e. same location in memory.
Any call to cons(), list(), or new allocates brand-new storage, different from any existing storage that might be pointed to. Since there are two calls to list(), each one gets its own brand-new storage, and they are guaranteed to be in different locations.
55. What is the value of
(subst 'crazy 'beauty '(beauty is as beauty does))
o A: (crazy is as crazy does)
o C: (crazy is as beauty does)
o D: (beauty is as beauty does)
o E: (beauty is as crazy does)
(subst x y z) means &substitute x for y in z&. It replaces all occurrences.
56. What is the value of
(sublis '((z 4) (y 3) (x 2)) '(* x y))
o A: error
o B: (* x y)
o C: (* x 3)
o E: (* 2 3)
sublis makes a copy of its second argument, replacing variables with their values as given in the association list that is the first argument.
57. What is the value of (list(&a&).equals(list(&a&)))
o B: false
o D: error
o E: could be true or false
In general, .equals() compares the values of two reference types (as opposed to ==, which compares locations, or exact identity). Since these two objects have equal values, .equals() returns true.
58. What is the value of
(match '(- ?x ?y) '(- w 3)) ?
o A: ((?y 3))
o C: false
o E: ((?y 3) (?x w))
(match pattern input ) compares the pattern and input, returning a binding list or association list of variable substitutions that, if made, would cause the pattern to be equal to the input (or null if there is no such substitution).
The rules for match are:
Constant values and structure in the pattern must match exactly. Variables (beginning with ?) will match anything, but they must do so consistently.
59. What is the value of
(match '(- ?x ?x) '(- w 3)) ?
o A: ((?x w))
o C: false
o E: ((?x 3) (?x w))
The pattern does not match the input, because to do so would require ?x to match both w and 3.
The @ Answer returned is null, which can be of the specified return type, Cons. (false is type boolean, so it would cause a compiler error.)
60. What is not true of .hashCode() in Java?
o A: there is a default .hashCode() for any Object
o B: returns an int
o C: must be the same for objects that are .equals()
o D: could be negative
o E: is usually a prime
We often use a prime number as the size of a hash table and compute the hash value modulo that prime. The .hashCode(), though, is any int and usually will not be a prime.
61. Keeping the load factor (fullness) λ & 0.7 in a hash table:
o A: means there usually are no collisions
o B: keeps the number of collisions fairly small on average
o C: wastes between 1 / 3 and 1 / 2 the table space
o D: requires use of quadratic probing
o E: B and C
With λ & 0.7 there will be some collisions (about 1 on average), but this can be considered to be constant-time. Keeping the table less than 0.7 full means we are wasting 0.3 of the space at least, basically between 1 / 3 and 1 / 2.
62. What is the Big O of hashing when λ & 0.7 ?
o B: O(log n)
o D: O(n log n)
o E: O(n2)
Although we expect some collisions (about 1 on average), this can be considered to be constant-time.
63. What is an advantage of hashing with buckets, compared to ordinary hashing?
o A: faster Big O
o B: don't need to expand the table
o C: simpler code: no collisions
o D: A and B
o E: B and C
Hashing with buckets uses an an array of pointers to an extra structure, such as a linked list, to store all entries that hash to a given value.
The extra structure means we don't have to worry about collisions (there are none) or expanding the table. The Big O, formally, may be worse: O(n) instead of O(1) because it takes O(n) time to search
with a fairly large table to hash into, though, this can be made small in practice.
64. What is the Big O of hashing with buckets?
o B: O(log n)
o C: O(n) but you can make it very fast
o D: O(n log n)
o E: O(n2)
The formal @ Answer is O(n) due to the time to search linearly through the linked list that is used for a bucket.
In reality, though, the average time is n / (2 * nb) where nb is the number of buckets. By making the number of buckets large enough, say n / 10, we can make the search time small enough to be considered constant.
65. Suppose that items are inserted into a min priority queue with the order and priorities: ((A, 2), (B, 3), (C, 1), (D, 2), (E, 1))
In what order are the items removed from the queue?
o A: A, B, C, D, E
o B: C, E, A, D, B
o C: B, A, D, C, E
o D: E, C, D, A, B
o E: C, E, D, A, B
After the insertions, the queue will contain:
The priority 1 items will be processed in order, followed by Priority 2 and 3.
66. What are advantage(s) of a heap for storing a priority queue, compared to an AVL tree?
o A: faster Big O
o B: simpler code
o C: uses less memory
o D: A and B
o E: B and C
A heap involves relatively simple code, compared to the complex code to handle an AVL tree. The heap also saves memory: whereas the AVL tree has two pointers and a balance code for each node, the heap uses an array and can compute pointer thus it uses no storage for pointers.
67. What is the data structure used for a heap?
o A: a hash table
o B: a linked list
o C: an AVL tree
o D: an array that we think of as a tree
o E: a list that we think of as an array
Answer is D
68. What is not true about Insertion Sort?
o A: stable
o B: O(n log n)
o C: on-line
o D: in-place
o E: good when input is almost sorted
Insertion Sort is O(n2), but is good when the input is almost sorted. It is also stable (does not change the relative position of equal keys), on-line (able to accept new items one at a time and process them efficiently), and in-place (does not need large extra storage).
69. What is true about Quicksort?
o A: stable
o B: always O(n log n)
o C: on-line
o D: in-place
o E: best for small input
Quicksort is usually great. But it is not stable (it swaps items), can be O(n2) in the worst case, is not on-line (accepting a new item means sorting the whole set again), and is not that good for small input (recursive function calls are relatively expensive for the small cases). It is in-place, sorting within the original array.
70. What is true about Heapsort?
o A: stable
o B: always O(n log n)
o C: on-line
o D: in-place
o E: B and D
Answer is E
71. The number of possible graphs with n nodes is:
Whoa! This is huge. There are 65,536 possible graphs with 4 nodes, and 33,554,432 possible graphs with 5 nodes.
If we think about the adjacency matrix representation of a graph, there is an n × n matrix with a 0 or 1 in position [i][j] iff there is an arc from i to j. Since there are n2 bits, the number of values of all possible matrices of bits is 2n2
72. Suppose that each user of Facebook has 1000 friends.
Is that graph:
o A: sparse
o B: dense
o C: acyclic
o D: planar
o E: k-chromatic
A graph is sparse if the number of edges is O(v2) where v is the number of vertices. All real-world graphs are sparse unless they are small.
In this question, the number of edges is O(1000 * v); that is O(v) even though 1000 is a big number.
73. Consider a family tree (ancestry) as a graph, with links from parents to their children.
Is that graph:
o A: sparse
o B: dense
o C: acyclic
o D: directed
o E: A, C, and D
The graph is sparse (people don't have many children), acyclic (nobody is their own ancestor), and directed (from parents to children).
74. What does Prim's algorithm guarantee?
o A: Distance between any two cities is no more than twice the shortest path between them
o B: If two cities have a direct edge connecting them, the path between them will use it
o C: Total distance to connect all nodes is minimized
o D: Total distance between pairs of nodes is minimized
o E: Nodes that are too far away are not connected
Answer is C
75. What does Dijkstra's algorithm produce?
o A: Shortest paths from one node to all other nodes
o B: Shortest path between any pair of nodes
o C: Shortest path from one node to one goal node
o D: Minimum total distance of all paths
o E: Minimum average distance between any pair of nodes
76. What advantage might A* have over Dijkstra's Algorithm?
o A: Lower-cost route than Dijkstra
o B: Finds same
Answer as Dijkstra for one goal with less work
o C: Gets @ Answers nearly as good but runs faster
o D: Finds paths between more pairs of nodes
o E: Has a stronger guarantee of optimality
@ Answer: B
For some applications (e.g. driving directions) a path to one goal is all that is needed.
77. What does A* assume that Dijkstra does not?
o A: sum of all edge costs is to be minimized
o B: no one-way links
o C: limited number of edges per node
o D: routes to many destinations are needed
o E: a heuristic estimate of cost from a node to goal
A* takes advantage of a heuristic function to search faster. While a heuristic of 0 could be used, that would be the same as Dijkstra.
78. What is true of heuristic functions for A*?
o A: must be within a factor of 2 of true cost
o B: even an inaccurate heuristic can be useful
o C: cannot underestimate cost
o D: must obey the Pythagorean theorem
o E: always nonzero
Even a crude and inaccurate heuristic can still reduce search time significantly.
79. What kind of problem is MapReduce good for?
o A: large matrix calculations
o B: O(2n) algorithms
o C: combining bits of data from many diverse sources
o D: simple calculations over massive amounts of data
o E: all of the above
MapReduce isn't good for everything. The key to using MapReduce for an application is to conceptualize the application as one or a sequence of simple operations, perhaps over massive data. Handling massive data with many computers is where MapReduce excels.
Please allow access to your computer&s microphone to use Voice Recording.
Having trouble?
We can&t access your microphone!
Click the icon above to update your browser permissions above and try again
Reload the page to try again!
Press Cmd-0 to reset your zoom
Press Ctrl-0 to reset your zoom
It looks like your browser might be zoomed in or out. Your browser needs to be zoomed to a normal size to record audio.
or to use Voice Recording.
For more help, see our .
Your microphone is muted
For help fixing this issue, see .
Star this term
You can study starred terms together
NEW! Voice Recording
Keep me logged in
Need an account?}