Which of the following best describes an array?

The process of removing an element from stack is called

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

A linear collection of data elements where the linear node is given by means of pointer is called

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?

With what data structure can a priority queue be implemented?

What is the functionality of the following piece of code?

public void fun(int x) {
    q1.offer(x);
}

In a max-heap, element with the greatest key is always in which of the following nodes?

What is the specialty about the in-order traversal of a binary search tree?

Which of the following is not an application of priority queue?

Explain array implementation of priority queues and list implementations of priority queues.

Differentiate between row major and column major array index notations. How is index calculated in both? Explain your answer by using the example of an integer array $a[10][10]$ and the element $a[2][5]$ is to be accessed.

What is doubly linked list? What are its applications? Explain how an element can be deleted from the list using appropriate pseudocode.

Consider two strings $X = x_1, x_2, \dots, x_n$ and $Y = y_1, y_2, \dots, y_n$, where $x_i, 1 \le i \le n$ and $y_j, 1 \le j \le m$ are the members of finite set symbols. Write an algorithm to generate a string by taking 1 element from each list. When any one string is exhausted, the output string should store rest of the elements of other string.

What do you understand by 'garbage'? Explain how garbage collection method is used for allocating and freeing memory storage.

Suppose the following eight numbers are inserted in order into an empty binary search tree: $T : 50, 33, 44, 22, 77, 35, 60, 40$ Draw the tree T.

Discuss pre-order and post-order tree traversal techniques. Write the pseudo-code for these two traversal methods.

Write the algorithms for insertion sort and merge sort with examples and discuss their complexities.

Write an algorithm to perform breadth first search (BFS). Compare the BFS and DFS search techniques.

Explain the working of merge sort on the following data: ${10, 15, 0, 17, 20, 25, 30, 16, 70, 6}$ Show all intermediate steps. Also, mention its time complexity.

What is meant by a spanning tree of a graph? Give an algorithm to find a spanning tree. What is the complexity of your algorithm?

What do you mean by tree traversal? Give a recursive algorithm for tree traversal. Determine the complexity of your algorithm.

Algorithm A requires $n^2$ days and algorithm B requires $n^3$ sec to solve a problem. Which algorithm would you prefer for a problem instance with $n = 10^6$?

Assume the recurrence relation $T(n) = 2T(n/2) + n, n \ge 2$ with boundary condition $T(1) = 0$. What is the time complexity?

Write short notes on the following:

How many number of interchanges are required to sort 5, 1, 6 in ascending order using Bubble sort?

What is the postfix form of the expression $(A + B) * (C * D - E) * F / G$?

How many leaf nodes are present in a full binary tree with $2n+1$ nodes?

A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as .............

What is LIFO?

What are the minimum number of multiplications and additions required to evaluate the given polynomial $P=4x^3+3x^2-15x+45$?

Which of the following sorting methods would be most suitable for sorting a list which is almost sorted?

What values are automatically assigned to those array elements which are not explicitly initialized?

What is the time complexity of Merge sort and Heap sort algorithms?

What is complete binary Tree?

What is Binary Search Tree (BST)? Make a BST for the following sequence of numbers. 45, 36, 76, 23, 89, 115, 98, 39, 41, 56, 69, 48 Traverse the tree in Preorder, Inorder and Postorder.

What is an algorithm? What are the characteristics of a good algorithm?

What is a sparse matrix? How is it stored in the memory of a computer?

Describe about the doubly linked list with an example. Write the advantages of linked list over array.

Show the various passes of bubble sort on an unsorted list 11, 15, 2, 13, 6

Define a stack. Describe ways to implement stack.

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

Describe insertion sort with a proper algorithm. What is the complexity of insertion sort in worst case?

Write an algorithm to insert a node in the beginning of the linked list.

For the given Binary Search Tree, perform the following sequence of operations: (A) Delete 44 (B) Delete 75 (C) Delete 25

Write down the applications of stack and queue data structures.

Construct a binary tree whose nodes on inorder and preorder are given as follows: Inorder: 10, 15, 17, 18, 20, 25, 30, 35, 38, 40, 50 Preorder: 20, 15, 10, 18, 17, 30, 25, 40, 35, 38, 50

What do you mean by hashing? Explain any three popular hash functions.

Write short notes on following (any two):

There are 8, 15, 13 and 14 nodes in four different trees. Which one of them can form a full binary tree?

Which data structure is used to perform recursion and why?

List out the areas in which data structures are applied extensively.

Sorting is not possible by using which of the following methods and why? Insertion, Selection, Exchange, Deletion

What is FIFO?

What is a postfix expression?

Differentiate between linear and non-linear data structures.

How do you insert a new item in a binary search tree?

Differentiate between stack and array.

What is an AVL tree?

Write binary search algorithm and trace to search element 91 in the following list: 13, 30, 62, 73, 81, 88, 91

What are the limitations of binary search?

Draw a binary tree from its inorder and preorder traversal sequences given as follows: Inorder: d b g e h a c n f Preorder: a b d e g h c f n

What is stack? How can stack be used to check whether an expression is correctly parenthesized or not? [Hint: () is correct but (( or )()( is not]

Convert the following infix expression into a postfix expression (show steps): $A * (B+D) / E - F(G + H/k)$

How do you find the complexity of an algorithm? What is the relation between the time and the space complexities of an algorithm?

Write an algorithm to create a singly linked list. Explain the steps to do the following operations:

Arrange the given list of elements in ascending order using quick sort: 44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66

Define an array. How does an array differ from an ordinary variable? How are arrays represented in the memory?

Define hashing. Describe any two commonly used hash functions. Describe one method of collision resolution.

Write down the procedure for inserting and deleting elements from a circular queue implemented using arrays.

What is a height balanced tree? Explain how the height is balanced after addition/deletion of nodes in it.

Write short notes on any two the following:

If the sequence of operations—push(1), push(2), pop, push(1), push(2), pop, pop, pop, push(2), pop are performed on a stack, the sequence of popped out values is

Queue can be used to implement

The number of binary trees with 3 nodes which when traversed in post-order gives the sequence A, B, C is

A binary tree has $n$ leaf nodes. The number of nodes of degree 2 in this tree is

Sparse matrices have

The postfix expression for $*+ab-cd$ is

The memory address of the first element of an array is called

The memory address of fifth element of an array can be calculated by the formula

Which of the following data structures are indexed structures?

Which of the following is not the required condition for binary search algorithm?

What is a data structure? What is the need of data structures?

Explain Big-Oh notation with the help of example.

Write suitable array declaration for the following:

• 100 items of integer type
• A string of 25 characters
• An integer matrix of order $5 \times 4$ Can an array be initialized? If yes, how?

Write a program that sorts a given list of numbers using quicksort.

Explain overflow and underflow conditions of a stack with examples.

What are priority queues? Write their applications.

Write a program that travels a linked list consisting of nodes of the following struct type:

struct student {
    char name[15];
    int roll;
    struct student *next;
};

While traversing, it counts the number of nodes in the list. Finally, the count is printed.

Explain the merits and demerits of static and dynamic memory allocation techniques.

Define the following terms: (i) Root (ii) Leaf nodes (iii) Empty tree (iv) Sub-tree

What are heap trees? Discuss a minheap and a maxheap tree with the help of examples. What are the operations that can be performed on a heap tree?

Explain the following graph theory terms: (i) Node (ii) Undirected graph (iii) Edge (iv) Connected graph (v) Directed graph (vi) Disconnected graph

Write the Warshall's algorithm.

Write an explanatory note on AVL rotations.

Write an algorithm for inserting a key K in a B-tree.

What is a sparse matrix? What are the methods to represent a sparse matrix?

Use a stack to convert the following infix arithmetic expression into a postfix expression: $(A-B)*(C/D)+E$ Show the changing status of the stack in tabular form.