DS Quiz

Which of the following is not a stable sorting algorithm in its typical implementation

• Insertion sort

• Merge sort

• Quick sort

• Bubble sort

Which of the following sorting algorithms in its typical implementation gives best performance when applied on an array which is sorted or almost sorted(maximum 1 or two elements are misplaced).

• Quick sort

• Heap sort

• Merge sort

• Insertion sort

The average number of key comparisons done in a successful sequential search in a list of length n is

• log n

• (n-1)/2

• n/2

• (n+1)/2

What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree for a skewed tree?

• O(n) for all

• O(log n)for all

• O(log n)for search and insert, and O(n) for delete

• O(log n)for search, and O(n)for insert and delete

Which searching technique takes O(1) time complexity for searching the data?

• Binary search

• Linear Search

• AVL Tree Search

• Hashing

Which of the following algorithms can be used to most efficiently determine the presence of a cycle in a given graph?

• Breadth first search

• Depth first search

• Prim's minimum spanning tree algorithm

• Kruskal' minimum spanning tree algorithm

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

• {u,v} must be an edge in G, and u is a descendant of v in T

• {u,v} must be an edge in G, and v is a descendant of u in T

• If {u,v} is not an edge in G then u is a leaf in T

• If {u,v} is not an edge in G then u and v must have the same parent in T

Which of the following points is/are true about Linked List data structure when it is compared with array?

• Arrays have better cache locality that can make them better in terms of performance.

• It is easy to insert and delete elements in Linked List

• Random access is not allowed in a typical implementation of Linked Lists

• All of the above

What does the following function do for a given Linked List with first node as head?

void fun1(struct node* head)

{

if(head == NULL)

return;

fun1(head->next);

printf("%d ", head->data);

}

• Prints all nodes of linked lists

• Prints all nodes of linked list in reverse order

• Prints alternate nodes of Linked List

• Prints alternate nodes in reverse order

How many stacks are needed to implement a queue. Consider the situation where no other data structure like arrays,linked list is available to you.

• 1

• 2

• 3

• 4