List of top Programming and Data Structures Questions on Searching, Sorting and Hashing

Suppose that insertion sort is applied to the array \( [1, 3, 5, 7, 9, 11, x, 15, 13] \) and it takes exactly two swaps to sort the array. Select all possible values of \( x \).

For which of the following inputs does binary search take time \( O(\log n) \) in the worst case?

Consider game trees Tree-1 and Tree-2 as shown. The first level is a MAX agent and the second level is a MIN agent. The value in the square node is the output of the utility function.

For what ranges of \( x \) and \( y \), the right child of node B and the right child of node E will be pruned by the alpha-beta pruning algorithm?

The state graph shows the action cost along the edges and the heuristic function \( h \) associated with each state. Suppose the A algorithm is applied on this state graph using a priority queue to store the frontier. In what sequence are the nodes expanded?

The pseudocode of a function \( fun() \) is given below:

fun(int A[0, ..., n-1]) {
    for i = 0 to n-2
        for j = 0 to n - i - 2
            if (A[j] > A[j+1])
                then swap A[j] and A[j+1]
}

Let \( A[0, \ldots, 29] \) be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function \( fun() \) is called with \( A[0, \ldots, 29] \) as argument, is __________ (Answer in integer).