Deck 4: Loops

Question 1

Show the BST after inserting 45, 43, 100, 34, 23, and 3 into an empty BST.

Answer 1

Question 2

a.Suppose you need to store a list of elements, if the number of elements in the program is fixed, what data structure should you use? (array, ArrayList, or LinkedList)
b.If you have to add or delete the elements at the beginning of a list, should you use ArrayList or LinkedList?
c.If most of operations on a list involve retrieving an element at a given index, should you use ArrayList or LinkedList?

Answer 2

a. Array
b. LinkedList
c. ArrayList

Question 3

Assume the load factor threshold is 75%. Show the hash table of size 11 after inserting entries with keys 14, 3, 24, 35, using separate chaining. Show the hash table after removing 24.

Answer 3

Question 4

Assume the load factor threshold is 75%. Show the hash table of size 11 after inserting entries with keys 14, 3, 24, 35, using linear probing. Show the hash table after removing 24.

Question 5

For the AVL tree in the preceding figure, show the new AVL tree after adding element 50. Which node was unbalanced? What rotation did you perform in order to rebalance the tree?

Question 6

Add the elements 40, 135, 9, 11, 3, 102, into a heap in this order. Draw the final heap.

Question 7

Suppose that the text consists of characters a, b, c, d, e, f, g, h and frequency of these characters in the text is as follows:
a: 30
b: 25
c: 40
d: 9
e: 20
f: 3
g: 12
h: 23
Draw a Huffman tree to obtain the code for these characters.

Question 8

Given the following heap, show the resulting heap after removing 62 from the heap.

Question 9

Show the BST after deleting 60 from the following BST.

Question 10

Show the balance factor of each node in the following tree.

Question 11

Show the BST after deleting 15 from the following BST.

Question 12

Show the inorder, preorder, and postorder of the following BST.