Linked List and Stack Quiz

Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

• Insertion Sort

• Quick Sort

• Heap Sort

• Merge Sort

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

• log(2*n)

• n/2

• log(2*n) -1

• n

Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node Q from the list?

• O(n)

• O(log2 n)

• O(logn)

• O(1)

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order ?

• Θ(n)

• Θ(n log n)

• Θ(n2)

• Θ(1)

Consider the following conditions: (a)The solution must be feasible, i.e. it must satisfy all the supply and demand constraints. (b)The number of positive allocations must be equal to m1n21, where m is the number of rows and n is the number of columns. (c)All the positive allocations must be in independent positions. The initial solution of a transportation problem is said to be non-degenerate basic feasible solution if it satisfies:

• (a) and (b) only

• (a) and (c) only

• (b) and (c) only

• (a), (b) and (c)

Which of the following is true about linked list implementation of stack?

• In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.

• In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.

• Both of the above

• None of the above

Which one of the following is an application of Stack Data Structure?

• Managing function calls

• The stock span problem

• Arithmetic expression evaluation

• All of the above

The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is

• A

• B

• C

• D

Stack A has the entries a, b, c (with a on top). Stack B is empty. An entry popped out of stack A can be printed immediately or pushed to stack B. An entry popped out of the stack B can be only be printed. In this arrangement, which of the following permutations of a, b, c are not possible?

• b a c

• b c a

• c a b

• a b c

The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is

• A

• B

• C

• D