| | |
In the binary search tree given below, show the three states of the tree after the Hibbard deletion (using successors) of nodes corresponding to keys X, O, and D, in that order, respectively.
deleting X:
|
+--M--------+
| |
+--------------J- +-----S--------+
| | |
+--D--------+ -O--+ +-----W-
| | | |
-B- +-----H--+ -R- -U--+
| | |
-F--+ -I- -V-
|
-G-
deleting O:
|
+--M-----+
| |
+--------------J- +--S--------+
| | |
+--D--------+ -R- +-----W-
| | |
-B- +-----H--+ -U--+
| | |
-F--+ -I- -V-
|
-G-
deleting D:
|
+--M-----+
| |
+-----------J- +--S--------+
| | |
+--F-----+ -R- +-----W-
| | |
-B- +--H--+ -U--+
| | |
-G- -I- -V-
A heap of $120$ elements is represented as an array whose value at index $0$ is null. Answer the following questions:
null but we still wanted to treat the array as a heap (such as we do in heapsort), at what index would the left child of the element at index $13$ now be?
During heap insertion, which action(s) may be needed to correct heap order -- a "sink", a "swim", both, or neither?
The element inserted (as the last non-null element in the array) may need to "swim" to a higher/smaller-indexed position in the tree/array to accomplish correct heap order.
Can the below tree serve as a heap? Explain your answer.
No. The tree is not "complete" given that $M$ has no children, but $N$ does.
The heapsort algorithm is applied to the array {'O','N','P','I','L','E','S'} in order to sort the characters contained therein alphabetically. Show the state of the array after each sink (or exchange-and-sink) applied.
Order before heapsort application: O N P I L E S 0 1 2 3 4 5 6 --------------------- O N S I L E P S N P I L E O P N O I L E S O N E I L P S N L E I O P S L I E N O P S I E L N O P S E I L N O P S Order after heapsort application: E I L N O P S
Complete the rotateLeft() method shown by filling in each blank below with a single statement, so that rotateLeft() can be used (in combination with appropriate other methods) to insert elements into a red-black tree:
private Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
______________________;
______________________;
h.color = RED;
x.size = h.size;
h.size = 1 + size(h.left) + size(h.right);
return x;
}
x.left = h; x.color = h.color;
Trace the state of an initially empty red-black tree as keys 'D', 'W', 'A', 'T', 'R', 'Z', and 'Y' are added to it in that order. That is to say, draw the tree after each letter has been added. Use a double-line to indicate a "red" link and a single line for "black" links. (Unimportant, but fun fact: Dwa-Trzy means "2-3" in Polish!
inserting D:
|
-D
inserting W:
|
+==W
‖
-D
inserting A:
|
+--D--+
| |
-A -W
inserting T:
|
+--D-----+
| |
-A +==W
‖
-T
inserting R:
|
+=====T--+
‖ |
+--D--+ -W
| |
-A -R
inserting Z:
|
+=====T-----+
‖ |
+--D--+ +==Z
| | ‖
-A -R -W
inserting Y:
|
+-----T-----+
| |
+--D--+ +--Y--+
| | | |
-A -R -W -Z
Interpret the following as a red-black tree (double lines indicate "red" links, and single lines indicate "black" links). Draw the related 2-3 tree.
Recalling that x.hashCode() returns a 32-bit integer, what is the purpose of the "x.hashCode() & 0x7fffffff" in the below hash() method?
private int hash(Key x) {
return (x.hashCode() & 0x7fffffff) % M;
}
It forces the leading bit of the hash code produced to be 0, thus producing a positive integer.
You may find the following table of ASCII values, a calculator, and the largest positive int value of $2147483647$ helpful as you answer this question:
$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c}
A&B&C&D&E&F&G&H&I&J&K&L&M\\\hline
65&66&67&68&69&70&71&72&73&74&75&76&77\\\hline\hline
N&O&P&Q&R&S&T&U&V&W&X&Y&Z\\\hline
78&79&80&81&82&83&84&85&86&87&88&89&90
\end{array}$$
The strings "SUP", "ERC", "ALI", "FRA", and "GIL" have been added to an initially empty hash table of size $16$ that uses linear probing to resolve collisions and resizes by doubling in size before insertions when half full. The result is shown below:
$${\small \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\\hline
-- & -- & -- & -- & -- & \texttt{FRA} & \texttt{ERC} & -- & -- & -- & \texttt{GIL} & -- & -- & -- & \texttt{ALI} & \texttt{SUP}\\\hline\\\\
\end{array}}$$
"IST".hashCode()."IST" appear in the array if it is added next?"FRA" is then deleted from the hash table, how many strings must be re-hashed?"A", "AB", "ABC", "ABCD", ..., and so on. Which is the first such string to have a negative hash code?
In an initially empty hash table of size $4$ that uses separate chaining to resolve collisions (and never resizes), the keys {'F', 'O', 'U', 'R', 'C', 'H', 'A', 'I', 'N', 'S'} are added. The respective values of hashCode() are given below:
$$\begin{array}{c|c|c|c|c|c|c|c|c|c}
F & O & U & R & C & H & A & I & N & S\\\hline
70 & 79 & 85 & 82 & 67 & 72 & 65 & 73 & 78 & 83
\end{array}$$
Show the resulting hash table that results. (Note, draw the chains so they run horizontally with their "head" being the left-most element.)
0 : H 1 : I->A->U 2 : N->R->F 3 : S->C->O
Which of the following are good things to do when overriding the hashCode() method of a class (indicate all that apply)?
One should...
1 than bits of 0hashCode() methods of the instance variables of that class to build the return value for the hashCode() method being written
All of these are good things to do in this context.
Hash tables and red-black trees are often used as symbol tables (i.e., "dictionaries"). Should the keys for any symbol table be mutable or immutable? Explain.
Keys of a symbol table (i.e., "dictionary") should always be immutable. If this were not the case, a key might change its value after being inserted into table -- which depending on the implementation of the symbol table can cause significant problems. For example, if the symbol table was implemented with a binary search tree, the tree might no longer be in symmetric order. As another example, changing the key associated with a value would invariably change the hash code to find the value in a hash table.
Given the following adjacency list, draw the graph so described, and then give the edges of the breadth-first paths tree found with source 0, in the order they are added to the tree. Finally, give the shortest path, as found by the breadth-first traversal in question between 0 and 6.
7 vertices, 10 edges 0: 5 1 1: 4 0 2: 5 6 4 3 3: 5 2 4: 6 2 1 5 5: 0 2 3 4 6: 4 2
Edges of Breadth-first Paths Tree: 0-5 0-1 5-2 5-3 5-4 2-6 Shortest path between vertices 0 and 6: 0-5-2-6
Given the following adjacency list, draw the graph so described, and then give the edges of the depth-first paths tree found with source 0, in the order they are added to the tree.
7 vertices, 10 edges 0: 2 1 4 1: 0 5 3 2: 0 6 4 3: 1 4 4: 0 6 2 3 5: 6 1 6: 5 2 4
Edges of Depth-first Paths Tree: 0-2 2-6 6-5 5-1 1-3 3-4