14. A red-black BST is balanced when all paths from __________ links to the root

Question

14.
A red-black BST is balanced when all paths from __________ links to the root have __________ nodes.
A) external; the same number of red
B) external; the same number of black
C) internal; the same number red
D) internal; the same number black
E) any; consecutive red

15.
Worst-case performance for a standard BST algorithm can occur with:
A) large numbers of duplicate keys.
B) files already in order.
C) files in reverse order.
D) all of the above.
E) none of the above.

16.
Linear probing performance is based on the:
A) number of unique keys.
B) percentage of occupied table positions.
C) distance of a key from the first table item.
D) average number of items per list.
E) total number of items per list.

17.
Performing extra work in one stage to avoid more work in later is known as:
A) optimization.
B) balancing.
C) amortization.
D) randomization.
E) rationalization.

18.
A suffix tree uses string indexing and works with:
A) binary search trees.
B) Patricia tries.
C) TSTs.
D) existence tables.
E) any algorithm that can use variable-length keys.

19.
Performance bugs in a hashing implementation commonly result from:
A) an improper data type conversion.
B) an incorrectly populated hash table.
C) a non-terminated recursion.
D) missing clusters in linear probing.
E) null links in separate chaining.

20.
Extendible hashing search uses elements of:
A) multiway tries.
B) hashing.
C) sequential-access search.
D) all of the above.
E) none of the above.

21.
Patricia tries allow a search for:
A) N keys in lg N nodes.
B) N keys in N nodes.
C) N keys in N2 nodes.
D) N keys in N/2 nodes.
E) N2 keys in N nodes.

22.
In Java, tries do not work well with strings because:
A) Java's String class hides low-level information.
B) Java's strings are character arrays and tries work best with linked lists.
C) Java's Unicode strings require excessive space.
D) Java does not allow casting of String class data to integers.
E) none of the above.

23.
The worst-case cost of a search using a BST is directly related to the tree's:
A) number of external nodes.
B) number of internal nodes.
C) internal path length.
D) height.
E) width.

24.
A B tree with k nodes has ________ keys.
A) k+1
B) k/2
C) k-1
D) 2k
E) between 2 and k

25.
Problems can occur with extendible hashing if:
A) too many items have duplicate keys.
B) keys are random.
C) items are removed.
D) a search requires multiple probes.
E) keys are inserted out of order

Explanation / Answer

14. b 15. d 16. B 17. C 18. C 19. B 20. dunno 21. B/D not sure: when you insert into patricia tree, it dpends on your algo how you sore your key, either each letter in separate node or not. On average you can get N/2 Nodes to represent N keys if you have duplicates etc) 22. E 23. C 24. D 25. A

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.