Axis Institute of Technology & Management
Unit 1 Introduction:
short
1. How can you represent a sparse matrix in memory?
2. List the various operations on linked list
3. Give some applications of stack
4. Explain Tail recursion. With example
5. Define time space trade off.
6. Array vs, linked list.
long
1. What are the merits and demerits of array? Given two arrays of integers
in ascending order, develop an algorithm to merge these arrays to form a
third array sorted in ascending order.
2. What is doubly linked list? What are its applications? Explain how an
element can be deleted from doubly linked list using C program
3. Define the following terms in brief:
(i) Time complexity (iii) Space complexity
(ii) Asymptotic Notation (iv) Big O Notation
4. Consider a multi-dimensional Array A[90] [30] [40] with base addressstarts at 1000.
Calculate the address of A[10] [20] [30] in row major order and column major order.
Assume the first element is storedat A[2][2][2] and each element take 2 byte.
5. Consider the two dimensional lower triangular matrix (LTM) of order N ,Obtain the
formula for address calculation in the address of row major and column major order for
location LTM[j][k], if base address is BA and space occupied by each element is w byte.
6. Write a C program to insert a node at kth position in single linked list.
Unit2 Stacks:
short
1. Define priority queue. Given one application of priority queue.
2. Write full and empty condition for circular queue.
Long
1. Write algorithm for Push and Pop operations in stack. Transform the
following expression into its equivalent postfix expression using stack:
A + (B * C – (D / E ↑ F) * G) * H
2.
(i) Differentiate between iteration and recursion.
(ii) Write the recursive solution for Tower of Hanoi problem.
3. Discuss array and linked representation of queue data structure. What is
dequeue?
4. Evaluate the following postfix expression using stack.
2 3 9 * + 2 3 ^ - 6 2 / + , show the contents of each and every steps. also find the
equivalent prefix form of above expression. Where ^ is an exponent operator.
SABIYA FATIMA, ASSISTANT PROFESSOR, CSE
Axis Institute of Technology & Management
5. Convert the following infix expression to reverse polish notationexpression using stack.
6. Write a C program to implement stack using single linked list.
Unit3 Searching, sorting, Hashing:
1. How does bubble sort work? Explain
2. Examine the minimum number of interchanges needed to convert thearray 90, 20,
41,18, 13, 11, 3, 6, 8,12, 7, 71, 99 into a maximum heap.
3. Differentiate sequential search and binary search.
4. Write short notes on min heap.
Long
1. How binary search is different from linear search? Apply binary search
to find item 40 in the sorted array: 11, 22, 30, 33, 40, 44, 55, 60, 66, 77,
80, 88, 99. Also discuss the complexity of binary search
2. Why is quick sort named as quick? Show the steps of quick sort on the
following set of elements:25, 57, 48, 37, 12, 92, 86, 33
Assume the first element of the list to be the pivot element
3. What is hashing? Give the characteristics of hash function. Explain
collision resolution technique in hashing.
4. Explain any three commonly used hash function with the suitableexample? A hash
function H defined as H(key) =key%7, with linear probing, is used to insert the key
37,38,72,48,98,11,66 into a table indexed from 0 to 6. what will be the location of key
11? Justify your answer, also count the total number of collisions in this probing.
5. Write an algorithm for merge sort and apply on following elements
45,32,65,76,23,12,54,67,22,87.
6. Write a C program for Index Sequential Search.
Unit 4 Trees:
short
1. Define extended binary tree, full binary tree, strictly binary tree and
complete binary tree
2. Explain threaded binary tree.
3. What is the importance of threaded binary tree?
Long
1. What is the difference between a binary search tree (BST) and heap? For
a given sequence of numbers, construct a heap and a BST.
34, 23, 67, 45, 12, 54, 87, 43, 98, 75, 84, 93, 31
SABIYA FATIMA, ASSISTANT PROFESSOR, CSE
Axis Institute of Technology & Management
2. Can you find a unique tree when any two traversals are given? Using the
following traversals construct the corresponding binary tree:
INORDER: H K D B I L E A F C M J G
PREORDER: A B D H K E I L C F G J M
Also find the Post Order traversal of obtained tree
3. What is a B-Tree? Generate a B-Tree of order 4 with the alphabets
(letters) arrive in the sequence as follows:
agfbkdhmjesirxclntup
4. If the in order of a binary tree is B,I,D,A,C,G,E,H,F and its post order is
I,D,B,G,C H,F,E,A then draw a corresponding binary tree with neat and
clear steps from above assumption.
5. Write Short notes of following
(a) Extended Binary Trees (b) Complete Binary Tree
(c) Threaded Binary Tree.
6. Insert the following sequence of elements into an AVL tree, starting
with empty tree 71,41,91,56,60,30,40,80,50,55 also find the minimumarray
size to represent this tree.
Unit 5 Graphs:
1. What is Minimum cost spanning tree? Give its applications
2. Compare adjacency matrix and adjacency list representations of graph
3. Compute the Transitive closure of following graph.
4. Write short notes on adjacency multi list representation a Graph
Long
1. Find the minimum spanning tree in the following graph using Kruskal’s
algorithm:
SABIYA FATIMA, ASSISTANT PROFESSOR, CSE
Axis Institute of Technology & Management
2. Explain warshall’s algorithm with the help of an example.
3. Describe the Dijkstra algorithm to find the shortest path. Find the
shortest path in the following graph with vertex ‘S” as source vertex.
4. Write an algorithm for Breadth First search (BFS) and explain with thehelp of
suitable example.
5. Describe Prim`s algorithm and find the cost of minimum spanning treeusing
Prim`s Algorithm.
6. Apply the Floyd warshall’s algorithm in above mentioned graph (i.e. in Q.no 6a)
SABIYA FATIMA, ASSISTANT PROFESSOR, CSE
