Programming, Data Structures and Algorithms - Data Science & Artificial Intelligence Previous Year Questions

Consider performing depth-first search (DFS) on an undirected and unweighted graph \( G \) starting at vertex \( s \). For any vertex \( u \) in \( G \), \( d[u] \) is the length of the shortest path from \( s \) to \( u \). Let \( (u, v) \) be an edge in \( G \) such that \( d[u] < d[v] \). If the edge \( (u, v) \) is explored first in the direction from \( u \) to \( v \) during the above DFS, then \( (u, v) \) becomes a ______ edge.

Consider a hash table of size 10 with indices {0,1,…,9}, with the hash function
\(h(x) = 3x \ (\text{mod } 10)\),
where linear probing is used to handle collisions. The hash table is initially empty and then the following sequence of keys is inserted into the hash table: 1, 4, 5, 6, 14, 15. The indices where the keys 14 and 15 are stored are, respectively

Consider that the quick sort algorithm is used to sort an array of \(n\) distinct randomly ordered elements. In every call, the pivot is chosen as the first element of the current subarray.
Let \(T(n)\) denote the expected time to sort the array. Assume that the time to partition is linear in the size of the current subarray.
Which of the following recurrence relations correctly represents \(T(n)\) in this scenario?

Consider performing uniform hashing on an open address hash table with load factor \(\alpha = \frac{n}{m} < 1\), where n elements are stored in the table with m slots. The expected number of probes in an unsuccessful search is at most \(\frac{1}{1-\alpha}\). Inserting an element in this hash table requires at most ______ probes, on average.

Consider the following Python declarations of two lists.
A = [1, 2, 3]
B = [4, 5, 6]
Which one of the following statements results in A = [1, 2, 3, 4, 5, 6]?

Consider the given Python program.

def append_to_lst(val, lst=[]):
    lst.append(val)
    return lst
print(append_to_lst(1))
print(append_to_lst(2))
print(append_to_lst(3, []))

Which of the following is the correct output of this program?