Computer Science I Jeopardy

Hash Tables

100

What arithmetic operation do you use to make sure the hash function returns an index that is not out of bounds for the size of a table?

modulo

200

What happens when two different keys generate the same hash code for a hash table?

A collision

300

What would be the index of the word 'rat' if it was the string of the following hash function? def hash( string ) return ( string * 2 )

There would be an error

400

Which of these statements is true: Entries in a hash table are sorted Elements in a hash table cannot be removed A key can be any kind of object

A key can be any kind of object

500

Look at the following function hash function: def hash( string ): return len( string ) How many collisions would there be if we put the following words in a hash table and we resolve them with open addressing: cat, dog, raccoon, mole, goat

3

Linked Lists (Mostly T or F)

100

True or False: (If you get it wrong, the other team gets it by default) Appending and element in the beginning of an array list is faster than in a linked list

False!

200

True or False: (If you get it wrong, the other team gets it by default) A linked list must always contain at least one node.

False, an empty linked list just contains a None

300

Fill in the blanks: class Node (rit_object): __slots__ = ("data", "next") _types = ( ______, _______ )

object, 'Node'

400

True or False: (If you get it wrong, the other team gets it by default) Accessing an element in a linked list is faster than in an array list

False

500

True or False: (If you get it wrong, the other team gets it by default) Searching for an element in a sorted array list and linked list takes the same time: O(n)

False, in the event the list is sorted, you could do binary search on the array list, making it slightly faster

Queues and Stacks

100

Which of the following acronyms best describes a stack? FIFO FOFI LIFO LOFI

Last in, first out LIFO

200

Which of the following acronyms best describes a queue? FOFI LIFO FAFI LOFI FIFO

FIFO First in, first out

300

Which of this objects would work best to implement a stack? string array list node rit_object

Node

400

Using the following definition, how would you push the value 6 to a stack named my_stack? def push( node, data): return Node( data, node)

my_stack = push( my_stack, 6 )

500

Create an empty queue named 'my_queue' class Queue(rit_object): __slots__ = ('front', 'back', 'size') _types = (object, object, int )

my_queue = Queue( None, None, 0)

Classes

100

Name one benefit of using the rit_object

Easier printing Less error-prone code Enforced types

200

Change Garfield's age to 7 class Cat (rit_object): __slots__ = ("name", "age") _types = (str, int) my_cat = Cat( "Garfield", 6 )

my_cat.age = 7

300

What are the two slots and their types of a hash table?

list/array/anything indicative of a list and size types: list and integer

400

Make a class named Person, whose attributes are name and age on the board

class Person (rit_object): __slots__ = ('name', 'age') _types = (str, int)

500

Create and store a dog named Lazy in a variable named 'my_dog' using the following class definition. The age and height can be anything class Dog (rit_object): __slots__ = ('name', 'age', 'height') _types = (str, int, float)

my_dog = Dog("Lazy", 7, 3.4)

Big-O of:

100

Insertion Sort

O(n^2)

200

Finding the location of an object in a hash map if there's no collisions:

O( 1 )

300

Searching for a value in a sorted list using binary search:

O( log(n) )

400

Remove an element from an array list:

O( n )

500

Adding an element in the head of a linked list:

O( 1 )