CSCI 340 – Final Exam Study Guide

What is the load factor of a hashing table?


Give this one a try later!


The ratio of the number of elements in the hash table compared to the total
hash table size.

Note how the ideal case is a load factor of 1 (since 1 means a full table). A
load factor of more than 0.7 (ie. 70 percent) should signal for rehashing.

,What is the written order of a postorder traversal?


Give this one a try later!


-> left
-> right
-> node


Note! How in all of the orders left node always goes before right. The only
thing that changes is when we visit the parent.




What structure require the root to be the minimum value and requires that all levels
be filled completely.


Give this one a try later!


Heap




Does the implementation of a list need to be known in order to work with it?


Give this one a try later!


No.




What type of collision handling uses linked lists for elements that hash to the same
value?


Give this one a try later!

, Separate chaining

Note how this is problematic since time complexity depends on how much
data is being traversed in each list.




True/False


Keys in a BTree can be in no particular order.


Give this one a try later!


False

Keys in a Btree are sorted in ascending order for each node




Which of the following is(or are) the least efficient?


- insertion sort
- selection sort
- quick sort
- heap sort
- merge sort
- bubble sort


Give this one a try later!


- insertion sort
- selection sort
- quick sort
- bubble sort

, What is the written order of an inorder traversal?


Give this one a try later!


-> left
-> node
-> right




What is the best case time complexity of a hashing table?


Give this one a try later!


O( 1 )

This is constant time, therefore the most efficient.




How would you declare an empty set of doubles?


Give this one a try later!


set<double> myset;




True/False


All external nodes in a Red-Black tree do not necessarily have to be equal black
depth.


Give this one a try later!