BITM Data Structure and Algorithms

Define computational complexity.

Why do we need ADT? Justify.

Define computational complexity.

Do we need to analyze the average case as asymptotic notation? Justify.

Why doubly linked list needs more memory?

Write an algorithm or function to add a node at the end of doubly linked list.

Distinguish between array list and linked list.

Write a Java function to delete first and last node of a circular linked list.

Write two major operations of stack.

Convert the infix expression \((X+Y)*Z\) into postfix expression.

Write an algorithm or function to pop an element from a stack.

What is part of pop operation in stack?

Evaluate \(32 + 6*4 -\) using stack.

List any two applications of queue.

List any one limitation of circular queue.

Write an algorithm or function to enqueue an element into a linear queue.

What is excessive recursion?

Write recursive function to find the GCD of two positive integers.

What is indirect recursion?

Write a recursive function to reverse the given integer.

Mention the worst case while creating BST.

Write a function to traverse a binary tree in Postorder.

Explain different cases of deleting a node from a binary tree.

Why do we need to balance BST? Support your statement with an example. Create a B-tree of order 5 from the given data: 7, 6, 1, 2, 11, 4, 8, 13, 10, 5, 19, 9, 18, 24.

Define binary tree.

Define max heap.

Construct AVL trees for 22, 27, 31, 10, 515.

Discuss about B – tree as a self-balancing tree.

Write an algorithm or function to search a data item in a Binary Search Tree.

Create a B-tree of order 5 with given data: 5, 8, 2, 7, 6, 15, 1, 12, 4, 13, 3.

What is the basic difference between tree and graph?

Define weighted graph.

How do you traverse a graph? Illustrate any one.

Find the shortest paths from vertex A to other vertices of the below graph using Dijkstra's algorithm:

List any one different between graph and tree.

Define spanning tree. Draw a minimum spanning tree using Kruskal’s algorithm and prims algorithm for the graph below:

Why do we need to sort the data?

Using quick sort, arrange the data 2, 1, 6, 10, 9, 4, 8, 7, 5 in ascending order.

What is the role of pivot element in quick sort?

Why we need to sort data? Trace it to sort the given data using heap sort algorithm: 12, 18, 16, 11, 20, 25, 13, 22, 21.

Define hash collision.

List the advantages of circular queue over linear queue. Insert 39, 55, 10, 29, 19, 15 into a Hash table of size 10 using division function. Use linear probing technique to resolve hash collision(if necessary).

Why do we need hashing?

Assume a 10-size hash table onto which insert 17, 19, 36, 7, 25, 6, 42 using quadratic probing.