### Welcome to Data Structure Quiz, Entry Level !!

Question 1. Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

n(X + Y)

3Y + 2X

n(X + Y)-X

Y + 2X

Question 2. The best data structure to check whether an arithmetic expression has balanced parentheses is a

queue

stack

tree

list

Question 3. Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?

s + m

s - m

m * s

m / s

Question 4. In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

O(nlogn)

O(n)

O(logn)

O(1)

Question 5. A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?

rear node

front node

not possible with a single pointer

node next to front

Question 6. Level order traversal of a rooted tree can be done by starting from the root and performing

preorder traversal

in-order traversal

depth first search

Question 7. Which one of the following in place sorting algorithms needs the minimum number of swaps?

Quick sort

Insertion sort

Selection sort

Heap sort

Question 8. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

7 5 1 0 3 2 4 6 8 9

0 2 4 3 1 6 5 9 8 7

0 1 2 3 4 5 6 7 8 9

9 8 6 4 2 3 0 1 5 7

Question 9. In a binary max heap containing n numbers, the smallest element can be found in time

0(n)

O(logn)

0(loglogn)

0(1)

Question 10. The running time of the following algorithm
Procedure A(n)
If n <= 2 return(1) else return A();
is best described by

O(n)

O(log n)

O(1og log n)

O(1)