Test #2

Question 1

Why do we want the initial data of a BST to come in randomly?

Answer 1

so the BST fills in instead of becoming a linked list

Question 2

What is an AVL tree?

Answer 2

BST that remains balanced upon insertion or deletion

Question 3

What does AVL stand for?

Answer 3

Adelson, Velskii, and Landis whom are the inventors

Question 4

Why do we want to balance a tree?

Answer 4

peak efficiency: makes O(log n) instead of worst case being O(n)

Question 5

What is a splay tree?

Answer 5

a BST that moves each node that is accessed into the root node

Question 6

What does the word splay mean in general?

Answer 6

spead out or scatter

Question 7

Why do we want to splay a tree?

Answer 7

because 90% of the accesses of a BT occur on only 10% of the data.

Question 8

What is the 90/10 rule?

Answer 8

When 90% of the accesses of a BST occur on only 10% of the data

Question 9

AVL tree vs splay tree uses

Answer 9

splay : fast lookup on recently used items
AVL : if lookup is a lot more common than insertion/deletion

Question 10

Hashing definition

Answer 10

technique that maps a key to its corresponding hash value

Question 11

When and why do we want to use hashing as compared to binary search trees?

Answer 11

Best and avg case of O(1)

Question 12

What are some common applications that use hashing?

Answer 12

Password verification, part lookup

Question 13

What constitutes a good hashing function?

Answer 13

Load Factor (% of slots in use) is kept under 50% to minimize collisions and to have more wiggle room. Once 50% is reached, double size of table and rehash.

Question 14

What is a collision?

Answer 14

when two keys are hashed to the same location

Question 15

What is a perfect hash function?

Answer 15

no collisions

Question 16

Linear probing

Answer 16

algorithm looks for the next available slot in the hash table to store the collided key.

Question 17

What is clustering?

Question 18

Quadratic probing

Question 19

Chaining

Answer 19

way to handle collisions using an array of pointers out to a linked list of all keys that hash to that location

Question 20

Folding (be able to implement in different ways)

Answer 20

when a key which is a string is converted into an integer for hashing

Question 21

What is this?

Answer 21

used to reference both the data members and member functions of an object

Question 22

Does this mean the same thing as this does in java?

Answer 22

has the same usage however in c++ it is a pointer, so u must de reference

Question 23

The differences between structs and unions

Answer 23

Unions only hold one active value

Question 24

What are the advantages of unions?

Answer 24

memory efficiency since only one field contains data at a time

Question 25

What is a variant record and why is it used?

Answer 25

record type that can have different sets of fields. example: personnel with names, integers for ids

Question 26

What is namespace scope?

Answer 26

provides a scope to the identifiers. used to prevent name collisions

Question 27

Why do you need the using directive with a given namespace?

Answer 27

using provides access to all namespace qualifiers and the scope operator

Question 28

What scope do cin and cout belong to?

Answer 28

std

Question 29

Balanced BST vs Hashing ( BST )

Answer 29

built using dynamic memory worst/average case runtime to insert or search for n items: O n log n can easily obtain a sorted listing of all elements, find a minimum or maximum, or search for a range of values

Question 30

Balanced BST vs Hashing ( Hashing )

Answer 30

fixed overhead for array representing table worst case runtime to insert or search for n items is O n^2 avg case run time is O(1) for searches/insertions cannot get a sorted list or find the minimum or maximum element

Question 31

what happens when you declare a class inside another class as a friend?

Answer 31

Classes declared as friends to any other class will have all the member functions as friend functions to the friend class

Question 33

Secondary Clustering

Answer 33

Unable to add an element in quadratic probing because the index calculated is never empty