Data Structure & Algorithms

What is the time complexity of the following code snippet?

for(i=0; i<n; i++) {
    for(j=0; j<i; j++) {
        int sum = i + j;
    }
}

Which type of traversal of binary search tree outputs the value in sorted order?

Suppose a circular queue of capacity $ (n-1) $ elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR=FRONT=0. The conditions to detect queue full and queue empty are

Which of the following data structures can be used for parentheses matching?

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?

What will be the postfix expression for the given infix expression: $ (a+b)*c-d $

What is the outcome of the prefix expression + - * 3 2 / 8 4 1 ?

Where will the new element be inserted in the linked list implementation of the queue?

Let us consider a list of numbers (34, 16, 2, 93, 80, 77, 51) and a hash table size of 10. What is the order of elements (from index 0 to size-1) in the hash table?

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

Why do we need an asymptotic notation? Explain the different asymptotic notations with definitions and examples.

Write the worst-case run time complexity of the following algorithms: linear search, bubble sort, merge sort, and push operation in the stack.

Write push() and pop() functions of a stack.

Evaluate the following postfix expression using STACK. Show all the steps. 8, 2, /, 3, *, 4, -, 6, 2, /, +

Write the algorithm to count the total elements in a singly linked list.

How a doubly linked list is better than a singly linked list? Explain deletion on a doubly linked list using an example.

The following values are to be stored in a hash table: 25, 42, 96, 101, 102, 162, 197. Describe how the values are hashed by using the division method of hashing with a table size of 7. Use chaining as the method of collision resolution.

Apply the merge sort on the following numbers: 10, 15, 50, 17, 20, 25, 30, 16, 70, 6.

Differentiate between stack and queue. Explain different types of queues with examples.

Write the properties of a binary search tree. Create a binary search tree using the following elements: 45, 15, 79, 90, 10, 55, 12, 20, 50.

Consider the in-order and pre-order traversal of a binary search tree are (1, 2, 3, 4, 5, 6, 8, 10, 25) and (4, 3, 1, 2, 10, 8, 5, 6, 25) respectively. Construct a unique binary search tree for the given in-order and pre-order traversals.

Explain the insertion in the AVL tree using an example.

Explain the Heap sort algorithm. Create a heap for the following elements and then sort them: 13, 102, 405, 136, 15, 105, 390, 432, 28, 444.

What is the time complexity of the following code snippet?

Which type of traversal of binary search tree outputs the value in sorted order?

Suppose a circular queue of capacity $(n-1)$ elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR=FRONT=0. The conditions to detect queue full and queue empty are

Which of the following data structures can be used for parentheses matching?

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?

What will be the postfix expression for the given infix expression: $(a+b)*c-d$

What is the outcome of the prefix expression + - * 3 2 / 8 4 1 ?

Where will the new element be inserted in the linked list implementation of the queue?

Let us consider a list of numbers (34, 16, 2, 93, 80, 77, 51) and a hash table size of 10. What is the order of elements (from index 0 to size-1) in the hash table?

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

Why do we need an asymptotic notation? Explain the different asymptotic notations with definitions and examples.

Write the worst-case run time complexity of the following algorithms: linear search, bubble sort, merge sort, and push operation in the stack.

Write push() and pop() functions of a stack.

Evaluate the following postfix expression using STACK. Show all the steps. 8, 2, /, 3, *, 4, -, 6, 2, /, +

Write the algorithm to count the total elements in a singly linked list.

How a doubly linked list is better than a singly linked list? Explain deletion on a doubly linked list using an example.

The following values are to be stored in a hash table: 25, 42, 96, 101, 102, 162, 197. Describe how the values are hashed by using the division method of hashing with a table size of 7. Use chaining as the method of collision resolution.

Apply the merge sort on the following numbers: 10, 15, 50, 17, 20, 25, 30, 16, 70, 6.

Differentiate between stack and queue. Explain different types of queues with examples.

Write the properties of a binary search tree. Create a binary search tree using the following elements: 45, 15, 79, 90, 10, 55, 12, 20, 50.

Consider the in-order and pre-order traversal of a binary search tree are (1, 2, 3, 4, 5, 6, 8, 10, 25) and (4, 3, 1, 2, 10, 8, 5, 6, 25) respectively. Construct a unique binary search tree for the given in-order and pre-order traversals.

Explain the insertion in the AVL tree using an example.

Explain the Heap sort algorithm. Create a heap for the following elements and then sort them: 13, 102, 405, 136, 15, 105, 390, 432, 28, 444.

• Circular Queue
• Adjacency matrix
• Depth first search
• B tree

In a stack, if a user tries to remove an element from empty stack it is called:

Consider the binary max-heap implemented using an array. Which one of the following array represents the heap:

A hash function is defined as h(key) = key mod 7, with linear probing used to insert keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?

If the number of values to be sorted is already partially sorted, then ______ sorting can be efficient.

The time complexity of merge sort is:

State true or false: A: Binary search is used for searching in a sorted array. B: The time complexity of binary search is $ O(\log n) $.

In a circular linked list organization, insertion of a record involves modification of:

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

An Abstract Data Type (ADT) is:

How many distinct BSTs can be constructed with 3 distinct keys?

Explain different asymptotic notations (Big-O, $ \Omega $, $ \Theta $) used for comparing the time complexity of an algorithm with neat figures.

The run time of an algorithm is represented by the recurrence relation $ T(n) = 2T(n/2) + n $; $ n \ge 2 $ and with boundary condition $ T(1) = 0 $. What is the time complexity (in terms of $ \Theta $ notation).

Discuss pre-order, in-order and post-order traversal techniques of binary tree. Write a C function for non-recursive pre-order traversal.

The pre-order traversal sequence of a Binary Search Tree (BST) is 30, 20, 10, 15, 25, 23, 39, 35, 42. Write step by step process to derive the BST and find post-order traversal also.

Consider a circular queue of capacity n-elements implemented with an array. Write C functions for insertion and deletion operations.

Convert the given infix expression into postfix using stack: $ A + B / C * (D + E) - F $. For each input symbol clearly mention the action taken and status of the stack during conversion.

Write a C function to delete last node from a singly linked list.

Create a max-heap by inserting following keys in the given order. Show each insertion step with clear illustration: 25, 35, 18, 9, 46, 70, 48.

Write an algorithm for merge sort and discuss space and time complexity.

Define collision in hashing. Explain briefly different methodologies to resolve collision.

Write algorithm to count leaf nodes in binary tree. What is the complexity of your algorithm?

Compare BFS and DFS traversal techniques for graph. Write an algorithm to perform BFS using queue.

Differentiate between system defined data types and abstract data types with suitable examples.

What is doubly linked list? What are its applications? Explain how a node can be added as last node using appropriate pseudo code.

AVL Rotations

Open Addressing & Chaining

B-Tree

Priority Queue

In a stack, if a user tries to remove an element from empty stack it is called:

Consider the binary max-heap implemented using an array. Which one of the following array represents the heap:

A hash function is defined as h(key) = key mod 7, with linear probing used to insert keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?

If the number of values to be sorted is already partially sorted, then ______ sorting can be efficient.

The time complexity of merge sort is:

State true or false: A: Binary search is used for searching in a sorted array. B: The time complexity of binary search is $ O(\log n) $.

In a circular linked list organization, insertion of a record involves modification of:

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

An Abstract Data Type (ADT) is:

How many distinct BSTs can be constructed with 3 distinct keys?

Explain different asymptotic notations (Big-O, $ \Omega $, $ \Theta $) used for comparing the time complexity of an algorithm with neat figures.

The run time of an algorithm is represented by the recurrence relation $ T(n) = 2T(n/2) + n $; $ n \ge 2 $ and with boundary condition $ T(1) = 0 $. What is the time complexity (in terms of $ \Theta $ notation).

Discuss pre-order, in-order and post-order traversal techniques of binary tree. Write a C function for non-recursive pre-order traversal.

The pre-order traversal sequence of a Binary Search Tree (BST) is 30, 20, 10, 15, 25, 23, 39, 35, 42. Write step by step process to derive the BST and find post-order traversal also.

Consider a circular queue of capacity n-elements implemented with an array. Write C functions for insertion and deletion operations.

Convert the given infix expression into postfix using stack: $ A + B / C * (D + E) - F $. For each input symbol clearly mention the action taken and status of the stack during conversion.

Write a C function to delete last node from a singly linked list.

Create a max-heap by inserting following keys in the given order. Show each insertion step with clear illustration: 25, 35, 18, 9, 46, 70, 48.

Write an algorithm for merge sort and discuss space and time complexity.

Define collision in hashing. Explain briefly different methodologies to resolve collision.

Write algorithm to count leaf nodes in binary tree. What is the complexity of your algorithm?

Compare BFS and DFS traversal techniques for graph. Write an algorithm to perform BFS using queue.

Differentiate between system defined data types and abstract data types with suitable examples.

What is doubly linked list? What are its applications? Explain how a node can be added as last node using appropriate pseudo code.

AVL Rotations

Open Addressing & Chaining

B-Tree

Priority Queue

Choose the correct answer of the following (any seven) :

Answer the following:

Answer the following:

Insert the following numbers, in the given sequence, in an empty B tree of order 5 and display the tree at every split : 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. Now delete the following elements from the tree, in the given sequence, and display the tree at every merge.

Insert the following numbers, in the given sequence, in an empty B+ tree of order 3 and display the tree at every split : 10, 20, 30, 90, 80, 60, 70, 40, 50, 66, 16, 84, 21, 76. Now delete the following elements from the tree, in the given sequence, and display the tree at every merge.

Answer the following:

Differentiate between the following :

Explain in detail the Kruskal's and Prim's algorithms for constructing minimum spanning tree. For the weighted undirected graph given below, construct the minimum cost spanning tree for the given graph using Kruskal's algorithm and Prim's algorithm when the starting vertex is R1 :

Define the following :

Which of the following is time complexity of the given code?
$ int\ a=0; $
$ for(i=0; i< N; i++) \{ $
$ \quad for(j=N; j>i; j--) \{ $
$ \quad \quad a = a + i + j; $
$ \quad \} $
$ \} $

Which of the following is time complexity of the given code?
$ int\ i,\ j,\ k=0; $
$ for(i=n/2; i<=n; i++) \{ $
$ \quad for(j=2; j<=n; j=j*2) \{ $
$ \quad \quad k = k + n/2; $
$ \quad \} $
$ \} $

Which of the following cases does not exist in complexity theory?

The operation of processing each element in the list is known as

Arrays are best data structures

Each array declaration needs not give, implicitly or explicitly the information about

In general, the binary search method needs not more than

State True or False:
A. Binary search is used for searching in a sorted array.
B. The time complexity of binary search is O(logn).

Which of the following is non-linear data structure?

Which is the correct output for the following sequence of operations? push(5), push(8), pop, push(2), push(5), pop, pop, pop, push(1), pop

Analyse the time complexity of the given function and also write the recurrence relation of the function:
$ int\ DoSomething(int\ n) \{ $
$ \quad if(n<=2)\ return\ 1; $
$ \quad else\ return\ (DoSomething(floor(sqrt(n))) + n); $
$ \} $

Consider the following postfix expression : 873-/6254+*+-
The above expression is evaluated using stack. Show the content of stack after each step.

What are the different notations for comparing the time complexity of an algorithm? Explain each of them with neat figures.

Explain the queue and circular queue with examples. Also, write the differences between the two.

Let a and b be positive integers. Suppose a function F is defined recursively as follows:
$ F(a,b) = \begin{cases} 0 & \text{if } a < b \\ F(a-b,b) + 1 & \text{if } b \le a \end{cases} $
Find the values of the following: (a) $ F(2,3) $ (b) $ F(14,3) $

Write the algorithm of prefix evaluation with example.

Write prefix notation of the following infix notation: $ A+B*C+D $

What do you mean by ADT? Explain the ADT stack with test cases for both pop and push.

Hashing

Circular linked list

Adjacency list

AVL tree

Which of the following is time complexity of the given code?
$ int\ a=0; $
$ for(i=0; i< N; i++) \{ $
$ \quad for(j=N; j>i; j--) \{ $
$ \quad \quad a = a + i + j; $
$ \quad \} $
$ \} $

Which of the following is time complexity of the given code?
$ int\ i,\ j,\ k=0; $
$ for(i=n/2; i<=n; i++) \{ $
$ \quad for(j=2; j<=n; j=j*2) \{ $
$ \quad \quad k = k + n/2; $
$ \quad \} $
$ \} $

Which of the following cases does not exist in complexity theory?

The operation of processing each element in the list is known as

Arrays are best data structures

Each array declaration needs not give, implicitly or explicitly the information about

In general, the binary search method needs not more than

State True or False:
A. Binary search is used for searching in a sorted array.
B. The time complexity of binary search is O(logn).

Which of the following is non-linear data structure?

Which is the correct output for the following sequence of operations? push(5), push(8), pop, push(2), push(5), pop, pop, pop, push(1), pop

Analyse the time complexity of the given function and also write the recurrence relation of the function:
$ int\ DoSomething(int\ n) \{ $
$ \quad if(n<=2)\ return\ 1; $
$ \quad else\ return\ (DoSomething(floor(sqrt(n))) + n); $
$ \} $

Consider the following postfix expression : 873-/6254+*+-
The above expression is evaluated using stack. Show the content of stack after each step.

What are the different notations for comparing the time complexity of an algorithm? Explain each of them with neat figures.

Explain the queue and circular queue with examples. Also, write the differences between the two.

Let a and b be positive integers. Suppose a function F is defined recursively as follows:
$ F(a,b) = \begin{cases} 0 & \text{if } a < b \\ F(a-b,b) + 1 & \text{if } b \le a \end{cases} $
Find the values of the following: (a) $ F(2,3) $ (b) $ F(14,3) $

Write the algorithm of prefix evaluation with example.

Write prefix notation of the following infix notation: $ A+B*C+D $

What do you mean by ADT? Explain the ADT stack with test cases for both pop and push.

Hashing

Circular linked list

Adjacency list

AVL tree

If the number of records to be sorted is small, then ______ sorting can be efficient.

Which of the following is not a limitation of binary search algorithm?

The complexity of the merge sort is

Which of the following is a hash function?

In simple hashing, what is the search complexity?

In simple chaining, what data structure is appropriate?

Which is not true about insertion sort?

Which of the below mentioned sorting algorithms is not stable?

A pivot element to partition unsorted list is used in

Which one of the following is divide and conquer approach?

Write down breadth-first traversal and depth-first traversal of given graph taking 1 as source vertex.

Construct a B-tree with minimum degree t as 3 and a sequence of integers 10, 20, 30, 40, 50, 60, 70, 80 and 90 in an initially empty B-tree. Show each step.

Write a function to perform merge sort on array of element mentioned. Also write recurrence relation for time complexity of algorithm.

What is AVL tree? Describe deletion operation in AVL tree with example.

Apply bubble sort on given array of integers: 26, 45, 13, 23, 12, 7, 38, 42. Show the content of array after every pass.

Write the algorithm to count leaf node in binary tree and check whether the tree is balanced or not.

What is hash table? How can we use this structure to find all anagrams in a dictionary?

Write a function that inserts a given element in a binary search tree. If the element is already present, throw an exception 'duplicate value'.

Linear and non-linear data structures

How to implement stack using queue

Heapsort

C++ STL

If the number of records to be sorted is small, then ______ sorting can be efficient.

Which of the following is not a limitation of binary search algorithm?

The complexity of the merge sort is

Which of the following is a hash function?

In simple hashing, what is the search complexity?

In simple chaining, what data structure is appropriate?

Which is not true about insertion sort?

Which of the below mentioned sorting algorithms is not stable?

A pivot element to partition unsorted list is used in

Which one of the following is divide and conquer approach?

Write down breadth-first traversal and depth-first traversal of given graph taking 1 as source vertex.

Construct a B-tree with minimum degree t as 3 and a sequence of integers 10, 20, 30, 40, 50, 60, 70, 80 and 90 in an initially empty B-tree. Show each step.

Write a function to perform merge sort on array of element mentioned. Also write recurrence relation for time complexity of algorithm.

What is AVL tree? Describe deletion operation in AVL tree with example.

Apply bubble sort on given array of integers: 26, 45, 13, 23, 12, 7, 38, 42. Show the content of array after every pass.

Write the algorithm to count leaf node in binary tree and check whether the tree is balanced or not.

What is hash table? How can we use this structure to find all anagrams in a dictionary?

Write a function that inserts a given element in a binary search tree. If the element is already present, throw an exception 'duplicate value'.

Linear and non-linear data structures

How to implement stack using queue

Heapsort

C++ STL

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

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

What is the functionality of the following code?
$ public\ void\ function(Node\ node)\ \{ $
$ \quad if(size==0)\ head=node; $
$ \quad else\ \{ $
$ \quad \quad Node\ temp,\ cur; $
$ \quad \quad for(cur=head; (temp=cur.getNext())! $ $=null; cur=temp); $
$ \quad \quad cur.setNext(node); $
$ \quad \} $
$ \quad size++; $
$ \} $

What is the space complexity for deleting a linked list?

The situation when in a linked list START=NULL is

What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list?

What kind of linked list is best to answer question like "What is the item at position n"?

A variation of linked list is circular linked list, in which the last node in the list points to first node of the list. One problem with this type of list is

Each node in a linked list must contain at least

A linear list in which the last node points to the first node is

In a linked list, insertion can be done at

What is a Hash Table, and what is the average case and worst-case time for each of its operations? How can we use this structure to find all anagrams in a dictionary?

Describe insertion in max heap tree with example from the following list of numbers: 33, 42, 67, 23, 44, 49, 74

Sort the given values using quicksort and write time complexity of algorithm: 65, 70, 75, 80, 85, 60, 55, 50, 45

Insert the following sequence of elements into an AVL tree, starting with an empty tree: 10, 20, 15, 25, 30, 16, 18, 19

Delete 30 in the AVL tree that you got.

Write algorithm for quicksort and mention time and space complexity in each case.

Define collision in hashing. What are the different methodologies to resolve collision? Explain briefly.

Construct binary search tree and write pre- and post-order traversals of this tree: 8, 3, 1, 10, 6, 14, 4, 7, 13, 22, 5

Write algorithm to count leaf node in binary tree and check whether tree is balanced or not.

Write a recursive and iterative version of insertion sort algorithm and mention time complexity.

BFS

DFS

Binary search tree

Balance factor

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

What is the functionality of the following code?
$ public\ void\ function(Node\ node)\ \{ $
$ \quad if(size==0)\ head=node; $
$ \quad else\ \{ $
$ \quad \quad Node\ temp,\ cur; $
$ \quad \quad for(cur=head; (temp=cur.getNext())! $ $=null; cur=temp); $
$ \quad \quad cur.setNext(node); $
$ \quad \} $
$ \quad size++; $
$ \} $

What is the space complexity for deleting a linked list?

The situation when in a linked list START=NULL is

What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list?

What kind of linked list is best to answer question like "What is the item at position n"?

A variation of linked list is circular linked list, in which the last node in the list points to first node of the list. One problem with this type of list is

Each node in a linked list must contain at least

A linear list in which the last node points to the first node is

In a linked list, insertion can be done at

What is a Hash Table, and what is the average case and worst-case time for each of its operations? How can we use this structure to find all anagrams in a dictionary?

Describe insertion in max heap tree with example from the following list of numbers: 33, 42, 67, 23, 44, 49, 74

Sort the given values using quicksort and write time complexity of algorithm: 65, 70, 75, 80, 85, 60, 55, 50, 45

Insert the following sequence of elements into an AVL tree, starting with an empty tree: 10, 20, 15, 25, 30, 16, 18, 19

Delete 30 in the AVL tree that you got.

Write algorithm for quicksort and mention time and space complexity in each case.

Define collision in hashing. What are the different methodologies to resolve collision? Explain briefly.

Construct binary search tree and write pre- and post-order traversals of this tree: 8, 3, 1, 10, 6, 14, 4, 7, 13, 22, 5

Write algorithm to count leaf node in binary tree and check whether tree is balanced or not.

Write a recursive and iterative version of insertion sort algorithm and mention time complexity.

BFS

DFS

Binary search tree

Balance factor