Introduction to Algorithms

Final exam, $2024\mathrm{.}06\mathrm{.}17$: $14\mathrm{.}00-16\mathrm{.}00$

Name: $q,$

$26.$ What is the primary purpose of the color$-$flip

Student ID:

operation in the insertion process of a left$-$leaning red$-$

a$)5$

black BST$?$

b$)1$

a$)$ To pass red links up the tree.

c$)2$

b$)$ To balance the tree after an insertion.

c$)$ To ensure that all red links lean left.

d$)$ To maintain the symmetric order of the tree.

$27.$ What kind of insertion pattern results in a perfectly balanced left$-$leaning red$-$black BST$?$

a$)$ Random order.

d$)10$

b$)$ Ascending order.

c$)$ Descending order.

d$)$ None of the above.

$28.$ What is the approximate average height of a red$-$black BST containing $N$ nodes?

a$)1\mathrm{.}00lgN$

b$)1\mathrm{.}39lgN$

c$)2lgN$

d$)lgN$

$29.$ Which of the following is NOT a key issue in hashing?

a$)$ Sorting the keys in the hash table

b$)$ Computing the hash function

c$)$ Collision resolution

d$)$ Equality test

$30.$ Which of the following is a good hash code for phone numbers?

a$)$ The last three digits

b$)$ The first three digits

c$)$ The area code

d$)$ The country code

$31.$ In Java, what does the hashCode$()$ method return?

a$)$ A $32-$bit integer

b$)$ A string representation of the object

c$)$ A Boolean value indicating equality

d$)$ The memory address of the object

$32.$ What is the purpose of the $"31x+y"$ rule in hash code design?

a$)$ To combine multiple fields into a single hash code

b$)$ To ensure that all keys hash to the same value

c$)$ To make the hash code more difficult to compute

d$)$ To prevent collisions from occurring

$33.$ What is the typical choice for the load factor $()$ in a separate chaining hash table? separate chaining hash table?

$34.$ Which of the following is a potential drawback of resizing a hash table?

a$)$ It requires rehashing all the keys

b$)$ It can cause the hash function to become less efficient

c$)$ It can increase the number of collisions

d$)$ It can make the hash table less space$-$efficient

$35.$ Which graph representation is typically used in practice due to its efficiency with sparse graphs?

a$)$ Adjacency$-$list representation

b$)$ Set$-$of$-$edges representation

c$)$ Adjacency$-$matrix representation

d$)$ union$-$find data structure

$36.$ What is the primary goal of depth$-$first search $($DFS$)?$

a$)$ To systematically search through a graph

b$)$ To find the shortest path between two vertices

c$)$ To find all vertices connected to a given source vertex

d$)$ To identify connected components

$37.$ Which data structure is used in Breadth$-$First Search $($BFS$)?$

a$)$ Stack

b$)$ Queue

c$)$ Tree

d$)$ Set

$38.$ What is a connected component in a graph?

a$)$ A set of vertices that are all connected to a single source vertex

b$)$ A set of vertices that are all reachable from each other

c$)$ A set of vertices that have the same degree

d$)$ A set of vertices that are all part of a cycle

$39.$ In an undirected graph, what does the degree of a vertex represent?

a$)$ The number of vertices adjacent to the vertex

b$)$ The number of edges incident to the vertex

c$)$ The length of the longest path starting from the vertex

d$)$ The number of connected components the vertex belongs to

$40.$ What is a self$-$loop in an undirected graph?

a$)$ An edge connecting two different vertices