u4

Question 1

median of a list of n numbers

Answer 1

can be found by sorting the listand picking the middle value if nis odd or calculating the mean of the two middle values if nis even

Question 2

Hashing

Answer 2

• Data items are placed in a series of indexed slots in a linear structure called a hash table.
• The ratio of the number of occupied slots to the size of the table is known as the load factor.
• The mapping of an item to a slot index is performed by means of a hash function.

Question 3

The folding method

Answer 3

Divide the digits of the item into equal size pieces (except possibly the last). Then, add the pieces together and take the remainder when the total is divided by the number of slots.

Question 4

The mid-square method

Answer 4

Square the item. Then, extract the middle digit or middle two digits, depending on whether the number of digits of the squared item is odd or even.Finally, take the remainder when this number is dividedby the number of slots.

Question 5

open addressing

Answer 5

if a collision occurs, the item is placed in another slot

Question 6

Linear probing

Answer 6

searches sequentially for the next open slot

Question 7

Quadratic probing

Answer 7

avoids clustering by adding successive square numbers to the index

Question 8

chaining

Answer 8

each slot may contain a collection of items, all having the same hash value

Question 9

Binary search trees

Answer 9

A binary tree (not necessarily complete), such that for every node p, all the keys within p’s left subtree are less than the key of p; and all the keys withinp’s right subtree are greater than the key of p.

Question 10

Insert to BST

Answer 10

• If the tree is empty, replace it with a tree consisting of a single node with the new key.
• Otherwise, if the new key is less than the key of the root, then insert into the left subtree of the root, else insert into the right subtree of the root.

Question 11

Delete from BST

Answer 11

• Find the node N to be deleted.
• If N has no children, remove it.
• If N has one child, replace N with the child.
• If N has two children, find N’s successor, M, in N’s right subtree. M is a leaf. Replace N’s content with M’s content and delete M.

Question 12

AVL trees

Answer 12

A self-balancing binary search tree.

Question 13

height of a tree

Answer 13

number of edges on the longest path from the tree’s root to a leaf, if the tree is non-empty, and −1 otherwise.

Question 14

A balanced BST

Answer 14

a BST for which the difference in height between any node’s left and right subtree doesn’t exceed 1.

Question 15

balance factor

Answer 15

calculated by subtracting the height of the node’s right subtree from the height of its left subtree