Exam 5 MC Review

update time: 12/4/2016

For a minHeap implementation, assume we use the 0th index of the array to store the root (instead of index 1). Given an element at position $$i$$ , what would be the position of its parent (assume $$i \neq 0$$ )?

• a. None of other options
• b. $\frac{i-1}{2}$
• c. $\lceil \frac{i-1}{2} \rceil$
• d. $\lfloor \frac{i}{2} \rfloor$
• e. $\lfloor \frac{i-1}{2} \rfloor$

For a minHeap implementation, assume we use the 0th index of the array to store the root (instead of index 1). Given an element at position $$i$$ , what would be the position of its left child (if one exists)?

• a. 2i + 1
• b. 2i
• c. 2i + 2
• d. None of other options
• e. 2i - 1

Consider the following array-based representation of a disjoint set:

index: 0   1  2  3  4  5  6   7  8
element: 1  -5  1  2  2  6  7  -4  6

The operations Find(3), Union(Find(4), Find(8)) and Find(5) are performed using union-by-size and path compression. How many times is node 2 traversed during the operations?

• a. None of these is correct
• b. 1
• c. 3
• d. 2
• e. 0

The std::map in C++ is:

• a. Abstract Data Type
• b. None of the options is correct
• c. Iterator
• d. Abstract Base Class
• e. Operator

There are several factors that affect the efficiency of lookup operations in a hash table. Which of the following is not one of those factors?

• a. Quality of the hash function
• b. Size of elements stored in the hash table
• c. All of these factors affect the efficiency of hash table lookups
• d. Number of elements stored in the hash table
• e. Number of buckets in the hash table

In our uptree disjoint sets implementation, suppose we employ union-by-size and no path compression. The running times of the relevant functions are:

• a. O(n) for setUnion and O(1) for Find
• b. O(\log n) for setUnion and O(\log n) for Find
• c. O(n) for setUnion and O(n\log n) for Find
• d. O(1) for setUnion and O(\log n) for Find
• e. None of the other answers

What is the worst case running time of removeMin on a heap? In answering this question you should assume the best possible implementation given the constraints, and also assume that every array is sufficiently large to handle all items (unless otherwise stated). The variable $$n$$ represents the number of items.

• a. None of the other options
• b. O(n)
• c. O(1)
• d. O(n^2)
• e. O(\log n)
• f. O(n\log n)

The Priority Queue (PQ) ADT implements the functions removeMin and insert. Suppose you use a sorted, singly linked list with a tail pointer and with keys arranged largest to smallest to implement a PQ. Which of these is the tightest bound on the running times for removeMin and insert for this implementation on a PQ containing $$n$$ keys?

• a. O(n) for removeMin and O(n) for insert
• b. None of the other options
• c. O(1) for removeMin and (\log n) for insert
• d. O(n) for removeMin and O(\log n) for insert
• e. O(1) for removeMin and O(n) for insert

Suppose you implement a hash table with separate chaining, where instead of a linked list, you use an AVL Tree. What is the worst case running time for inserting 1 element into the hash table of size $$n$$ if resizing is set to occur every time any of the binary trees reach a size of $$m$$ ( $$m$$ nodes are present in the binary tree).

• a. O(m)
• b. O(\log m)
• c. O(n)
• d. None of the other options
• e. O(n \log m)
• f. O(m + n)

Suppose you are given a list of size $$n$$ and another list of size $$m$$ , where $$m \gt n$$ . You want to determine if all elements that are in the size $$m$$ list are present in the list of size $$n$$ . What is the best time complexity of CREATING a hashtable such that you will be able to solve the problem even with duplicate elements.

• a. None of the other options
• b. O(mn)
• c. O(n)
• d. O(m \log n)
• e. O(n + m)
• f. O(m)

Suppose your goal is determine whether or not a graph contains a vertex that is connected to no other vertices. How long does the best possible algorithm take if the graph is implemented using adjacency lists? an adjacency matrix? (As always, assume there are $$n$$ vertices and $$m$$ edges.)

• a. O(1) for lists and O(n) for the matrix.
• b. O(deg(v)) for lists and O(n) for the matrix
• c. O(n) for lists and O(n^2) for the matrix.
• d. O(m) for lists and O(n^2) for the matrix.
• e. None of these answers is correct.

What is the best definition of a collision in a hash table?

• a. Two entries are identical except for their keys.
• b. Two entries with dierent data have the exact same key.
• c. Two entries with dierent keys have the same exact hash value.
• d. Two entries with the exact same key have dierent hash values.
• e. None of the above is correct.

Which of the following expressions represents the load factor for a hash table of size $$m$$ containing $$n$$ keys?

• a. m+n
• b. m*n
• c. m/n
• d. n/m
• e. None of these is the load factor.

Suppose $$T$$ is a min-heap storing $$n$$ keys. Your task is to design an algorithm for reporting all keys in $$T$$ that are less than or equal to a query key $$x$$ (which is not necessarily in $$T$$ ). Your algorithm should run in time $$O(k)$$ , where $$k$$ is the number of keys in $$T$$ whose value is less than or equal to $$x$$ . Which of the following algorithms would you adapt to complete this task?

• a. RemoveMin
• b. PreOrder tree traversal
• c. Union of disjoint sets
• d. Find in BST
• e. None of these solves the problem.

Which of the following array-based representations of a forest of up-trees could not possibly result from a sequence of union and find operations if union-by-size and path compression are employed?

• a.

• b.

• c.

• d.

• e. All of these are valid forests of up-trees.

Suppose we run breadth first search on a connected, undirected graph with $$n$$ vertices and $$5n + 2$$ edges. How many edges will be labelled "back" edges?

• a. n-1
• b. 4n+1
• c. 4n+3
• d. 5n+2
• e. The answer cannot be determined from the information given.

Depth first search, when run on the following graph, beginning at node A, classifies edge $$(c, f)$$ as __. Assume that the edge iterators are set up to process adjacent vertices in the (left to right) order given in this adjacency list representation of the graph.

• a. "back"
• b. "cross"
• c. "discovery"
• d. "predecessor"
• e. None of these is the correct choice.

Suppose we implement an algorithm to determine whether or not a simple undirected graph is connected using a modification of a graph algorithm we saw in class. What is the tightest worst case asymptotic running time of the best algorithm to do this?

• a. O(n^2)
• b. O(n+m)
• c. O(n \log n + m \log n)
• d. O(n)

Consider two vertices $$x$$ and $$y$$ that are simultaneously on the queue during execution of BFS from vertex $$s$$ in an undirected graph. Which of the following is/are true?

I. The number of edges on the shortest path from $$> s >$$ to $$> x >$$ is at most one more than the number of edges on the shortest path from $$> s >$$ to $$> y >$$ . II. The number of edges on the shortest path from $$> s >$$ to $$> x >$$ is at least one less than the number of edges on the shortest path from $$> s >$$ to $$> y >$$ . III. There is a path from $$> x >$$ to $$> y >$$ .

• a. Only one of these statements is true.
• b. Items I. and II. are true.
• c. Items I. and III. are true.
• d. Items II. and III. are true.
• e. All three statements are true.