CSC 231 Final Review

Review for all material covered in CSC 231

The Python function id(x) returns what?

the memory address of the variable x as an integer

instruction memory

memory that holds the code instructions in bytecode. Python interprets this code.

heap memory

memory that Python uses for storing data, like strings, ints, lists, etc

call stack

memory that Python uses to keep track of what it has executed

If id(x) == id(y) is true, then which of the following statements are true? Select all that apply.

x == y, x and y point to the same address in memory, type(x) == type(y)

The hex() function converts an integer into hexadecimal.

True

All data takes up the same amount of memory

False

Consider the following code:

food = 'cheese,franks,beans'
x = food.split(',')
y = x[1]

What is the value of y after the code executes?

franks

What is the type of x after the following code executes?

x = 'My name is mud'.split()

list

Consider the following code:

lst = []
lst.append('Bob')

You know that append must be:

a method on the list class

Which of the following methods is the class constructor of Python classes?

__init__

The first parameter of every Python method is always 

self

Complete the sentence below using the correct terms.

Given the code x = Student(), we say that x is a/an instance of class Student.

instance, class

Suppose that you are working with a Python class called LibraryBook that has class instance variables named title, author, and year.

Suppose the variable books is a list of LibraryBook objects. What code goes on the blank line to print out the authors of all the books in the list:

for b in books:
    print(________)

b.author

In algorithm analysis, we say that an efficient algorithm is one that  ___________.

executes quickly

The efficiency of an algorithm is determined by which of the following?

the number of steps in the algorithm, the size of the input to the program

Which of the following are O(1), or constant time, operations in Python?

indexing of a Python list[], e.g, mylist[0], math operators like +, -, *, variable assignment

Big-O notation refers to the rate of growth. In other words, how quickly an algorithm's time increases as the size of the input increases.

True

Put the following O(f(n)) values in order from best (fastest) or worst (slowest):

O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)

ADT

an abstract concept consisting of operations and data that solve a common computing problem

data type

an implementation of an ADT in a specific language such as Python

data structure

the internal storage and organization of how data items are kept in memory

Python's list[] data type is implemented using a/an ____________________________ data structure

ArrayList

Deque ADT lets you do addition and removal at both ends

True

Python lists[] implement the Unordered List ADT.

True

O(f(n)) of x = lst.pop()

O(1)

O(f(n)) of x = lst.pop(index)

O(n)

O(f(n)) of x = lst[index ]

O(1)

O(f(n)) of lst.append(x)

O(1)

O(f(n)) of lst.remove(x)

O(n)

O(f(n)) of lst.insert(index, x)

O(n)

In a Queue ADT conceptually speaking, data is enqueued at the ____ of the queue.

rear

n a Queue ADT conceptually speaking, data is dequeued at the ____ of the queue.

front

Identify the O(f(n)) of each Queue operation. Assume that you use Python's list[] to implement a queue. Assume that the front of the queue is end of the list.: q.enqueue('val')

O(n)

Identify the O(f(n)) of each Queue operation. Assume that you use Python's list[] to implement a queue. Assume that the front of the queue is end of the list.: x = q.dequeue()

O(1)

Identify the O(f(n)) of each Queue operation. Assume that you use Python's list[] to implement a queue. Assume that the front of the queue is end of the list.: q.is_empty()

O(1)

Identify the O(f(n)) of each Queue operation. Assume that you use Python's list[] to implement a queue. Assume that the front of the queue is end of the list.: q.size(x)

O(1)

In a Stack ADT, the addition and removal of data always occurs at the ______ of the stack.

top

Identify the O(f(n)) of each Stack operation. Assume that you use Python's list[] to implement a stack. Assume that the top of the stack is end of the list.: stack.push('val')

O(1)

Identify the O(f(n)) of each Stack operation. Assume that you use Python's list[] to implement a stack. Assume that the top of the stack is end of the list.: x = stack.pop()

O(1)

Identify the O(f(n)) of each Stack operation. Assume that you use Python's list[] to implement a stack. Assume that the top of the stack is end of the list.: x = stack.peek()

O(1)

Identify the O(f(n)) of each Stack operation. Assume that you use Python's list[] to implement a stack. Assume that the top of the stack is end of the list.: stack.is_empty()

O(1)

Identify the O(f(n)) of each Stack operation. Assume that you use Python's list[] to implement a stack. Assume that the top of the stack is end of the list.: stack.size(x)

O(1)

Identify the O(f(n)) of each Stack operation. Assume that you use Python's list[] to implement a stack. Assume that the top of the stack is beginning of the list (index 0).: stack.push('val')

O(n)

Identify the O(f(n)) of each Stack operation. Assume that you use Python's list[] to implement a stack. Assume that the top of the stack is beginning of the list (index 0).: x = stack.pop()

O(n)

Identify the O(f(n)) of each Stack operation. Assume that you use Python's list[] to implement a stack. Assume that the top of the stack is beginning of the list (index 0).: x = stack.peek()

O(1)

Identify the O(f(n)) of each Stack operation. Assume that you use Python's list[] to implement a stack. Assume that the top of the stack is beginning of the list (index 0).: stack.is_empty()

O(1)

Identify the O(f(n)) of each Stack operation. Assume that you use Python's list[] to implement a stack. Assume that the top of the stack is beginning of the list (index 0).: stack.size(x)

O(1)

LIFO

last-in first-out meaning the most recently added item will be removed first in the stack.

FIFO

first-in first-out meaning the first time added will be removed first in the stack.

A linked list and an array-based list are two data structures that can each be used to implement the UnorderedList ADT.

True

Which of the following are always True regarding a Linked List?

if the list has a tail, tail.next will always be None, the head and the tail of the list may refer to the same node, the head of the list must always be the first node in the list, if the list is empty, self.head must be None

Like an ArrayList, the nodes of a linked list must be stored in a contiguous block of memory.

False, linked lists can be stored non-contiguously.

Which of the following Linked List operations require you to traverse the list?

search(), remove(), pop()

Suppose you have a correctly-implemented LinkedList. Consider the code below:

lst = LinkedList()
lst.append('Alice')
lst.add('Bob')
lst.add('Charlie')

Which of the following statements are True after the code executes? Select all that apply.

Charlie is at the head, Alice is at the tail, self.head.next points to Bob's node

Suppose you have a linked list of the following form:

(Head)  'Alice' -> 'Bob' -> 'Charlie' -> 'Dave' -> 'Emma' (Tail)

What will be the returned value from calling pop(4) on this list be?

'Emma'

Consider the following Doubly Linked List.

(Head)  'Alice' <-> 'Bob' <-> 'Charlie' (Tail)

Which of the following expressions yields Charlie's node? Select all that apply.

self.head.next.next, self.tail.prev.next, self.tail.prev.prev.next.next

Consider the following implementation of the add method in a LinkedList class that has both head and tail variables.

    def add(self, item):
        """
        adds item to the beginning of the list. This method does not return anything.
        :param item: the data item to add to the beginning of the list
        """
        node = Node()
        node.data = item
        node.next = self.head
        self.head = node
        self.size += 1

Under which circumstances will the following code incorrectly update the list? Select all that apply.

when the list is empty. The code functions just fine for adding a node to the list at the head. The problem is that the tail also needs to be set if calling add() on an empty list.

Which of the following singly Linked List method calls are constant time ((O(1))? Select all that apply.

add('Joe'), append('Joe'), pop(0)

Suppose we implement a Linked List method called get_by_index(pos) to allow programmers to access the Linked List by index, just as you can do with a regular Python array-based list, e.g., lst[5].

1. What must the O(f(n)) (Big-O) for the new method be?

2. And why?

The logic of this method would require you to "walk or traverse the list", starting at the head, index number of times. This would require a loop as in the pop(pos) method of the LinkedList. In the worst case, you would walk to the end of the list, which is n times.

Suppose that you want to implement deque and have a choice between using ArrayLists, Linked Lists and Doubly Linked Lists for the underlying data structure.

1. Which data structure would be the most efficient in this case?

2. And why?

Deques need to do operations such as add and remove both at the end and beginning. Doubly linked lists allow you to perform add, append, remove at index 0 and end all in O(1).

Binary search is an example of a _________________ algorithm.

divide-and-conquer

Why would you not use a binary search on a Python list[]? Select all that apply.

the list elements cannot be sorted, the cost of keeping the list ordered outweighs the benefits of binary search

Suppose you have a Linked List of 10,000 elements that are sorted in ascending order. Which search algorithm will yield the best performance when searching this list? And why?

• You cannot perform binary search on a linked list and have it be O(logn). To be, O(logn)the binary search algorithm requires that you can access any index of the list, e.g., lst[1254], in O(1) time. Accessing indexes of a linked list is a O(n) operation (think of pop()).

• While sequential search and smart sequential search are both O(n), you will see slightly better performance when searching for something not int the list with a smart sequential search, as was demonstrated in the search_experiment.py.

A hash function, H(x), that takes an arbitrary value as input and transforms it into a new value (a hash) that is part of a smaller set of values, like a fixed range of integers.

True

Python's dictionary {} data type uses a hash table for its data structure.

True

Python's dictionary data type is an implementation of the ______________ ADT.

Map

Consider the following Python code:

    plates = {}
    plates['NC-112233'] = "Vito Vitorelli"
    plates['MD-887123'] = "Harry Hamlin"
    plates['MD-887123'] = "Mary Manson"
    x = plates['MD-887123']

What is the value of x after the code completes?

"Mary Manson"

Consider the following Python code:

    plates = {}
    plates['NC-112233'] = "Vito Vitorelli"
    plates['MD-887123'] = "Harry Hamlin"
    plates['MD-887123'] = "Mary Manson"
    x = "Mary Manson" in plates

What is the value of x after the code executes?

False

A problem solved with recursion can also be solved using iteration.

True

What is the output of the following code?

def some_func(n):
   if n <= 1:
       return n
   else:
       return(some_func(n-1) + some_func(n-2))

print(some_func(4))

3

What is the problem with the following recursive function?

def x(lst):
    if lst == []:
        return False
    else:
        return x(lst)

it does not make progress toward the base case

Some lists simply cannot be sorted. Why? Select TWO (2) answers.

the list elements have no natural ordering, the list elements cannot be compared to one another

bubble sort

O(n²)

selection sort

O(n²)

insertion sort

O(n²)

merge sort

O(n log n)

quicksort

O(n log n)

A binary search tree is one in which each data value is greater than all of its ____ descendants.

left

A binary search tree is one in which each data value is less than all of it's ___ descendants.

right

What is the depth of node 'LA'?

2 (with margin: 0)

What is the height of the tree below?

4 (with margin: 0)

In the tree below, how many nodes are visited in the search for 'HI'?

3 (with margin: 0)