QUESTION BANK

SHORT QUESTIONS
1. What is data structure? Define Abstract data type.
2. Define stack and queue with examples.
3. Given one dimensional array A [100] in which each memory location of
size 16 bytes. Find the address of A [20] when the base address is 10000.
4. Define row major order and column major order
5. Suppose an array A [10] having contains elements from index 0 to 5. How
can we insert a new item at index 2 without disturbing the linear order of
elements in array?
6. Define sparse matrix with a suitable example
7. Define sparse matrix with a suitable example. The following sequence of
operations are performed on an empty stack: PUSH (1), PUSH (0), PUSH
(0), PUSH (1), POP, POP, PUSH (1), PUSH (0), POP? Write the sequence
of the popped out items.
8. Find out the PREFIX expression for the given infix: (B *C ^ D) using
mathematical process of conversion.
9. Convert the following infix expression (C * D ^ E) into postfix using
STACK
[Link] out different common operations we apply on a 1D array.
11. Write the steps to count the number of nodes of a single linked list.
[Link] the difference between linear search and binary search.
[Link] is linked stack?
[Link] are the advantages of linked list over array?
[Link] is linked Queue?
[Link] the difference between single linked list and circular single linked
list?
[Link] the algorithm steps for finding the middle position node in a single
linked list when we know the total no. of nodes are 11.
[Link] the procedure to count the no. of leaf nodes in a binary tree.
[Link] is Balance Factor?
[Link] terms: skew binary tree, strictly binary tree
[Link] to find the height of a tree? Give an example.
[Link] the difference between a Tree and a cyclic Graph.
[Link] a binary tree when the sequence of nodes given as:
In order : 10, 20, 25, 30, 35, 50, 60, 70, 90
Preorder : 50, 20, 10, 30, 25, 35, 70, 60, 90
24.A sequence of elements given below. Construct a Binary Search Tree.
70, 20, 10, 40, 60, 90, 75, 49, 65, 95
[Link] binary tree:

What are the terminal nodes?

What are the internal nodes?
How many NULL pointers exist?
What are the nodes available at level 2?
[Link] is max heap tree? How to construct it?
[Link] a Max-Heap Tree for a given list of elements: 20, 30, 10, 50, 90,
70
[Link] a Min-Heap tree for a given list of elements: 80,60,30,40,20,10
[Link] is the adjacency matrix of the graph given below:

[Link] out the traversal methods of a graph? State the operational difference
between them
[Link] is the adjacency matrix of the graph given below?

[Link] the in-degree and out-degree of each vertex of the graph given below:

LONG –QUESTIONS
1. List out the standard notations of algorithm.
2. Write an algorithm to test a number is prime or not.
3. Write an algorithm to find largest and smallest element present in an array
4. Given a matrix Q [7][8] in which the size of each memory location is 4
bytes. Find the address of Q [5][2] when the base address is 5000 and the
memory is occupied in row major order.
5. Using stack demonstrate how to generate equivalent postfix expression of
the infix expression
(A + B - (C * D / E))
6. Briefly elaborate the evaluation process of given postfix expression P = 2,
3, 15, 10, 2, /, -, *, +, 4, + using stack
7. Write down the algorithm to test a matrix is sparse or not and if sparse
store the non-zero information into another 3-column matrix.
8. Write a program to input elements into a 4X4 matrix and display the sum
of individual row elements using UDF.
9. Write down the algorithm to evaluate the postfix expression using stack
also apply it on the given postfix expression: 2, 100, 2, /, 20, -, *, 10, -
[Link] the postfix expression of given infix: (Q-W*E/(R+T*Y)-U) using
stack. Also write down the algorithm for infix to postfix conversion using
stack.
[Link] a program using C to create a stack of numbers and perform using
UDF:
(i) push operation (ii) pop operation (iii) display operation
[Link] an algorithm for selection sort. Explain the process with an
example.
[Link] an algorithm for bubble sort. Explain it with suitable example.
[Link] down the algorithm for performing push and pop operations in a
linked stack.
[Link] and design the algorithm for searching for an item and then delete
that item.
[Link] down the algorithm for performing insertion and deletion operations
in a linked queue.
[Link] down the algorithms for linear search and binary search operations
and state the difference.
[Link] is a Binary Search Tree? Write the steps of algorithm for inserting
an element into a BST.
[Link] elaborate the memory representation of a binary tree and their
types with suitable example.
[Link] down the algorithm for Inorder traversal for a binary tree. When an
inorder and preorder sequence of nodes given then how to construct a
binary tree.
[Link] to construct a binary tree when inorder and post order sequence of
node given? Also write down the algorithm for preorder traversal of a
binary tree
[Link] down all the 3 different recursive traversal methods for traversing
nodes of a binary tree.
[Link] a sequence of
elements:70,20,10,30,40,50,60,25,35,45,75,95,10,52,92
Construct an AVL tree by inserting each element
[Link] an infix expression (A+B/C-D^E*F-G)
Find its equivalent postfix notation and then using stack.
[Link] is Heap Tree and its types? Explain the procedure for construction
of Max heap Tree and Min Heap Tree both with suitable example.
[Link] Warshall’s algorithm to find the path matrix of a graph.
[Link] is path matrix? Write down adjacency matrix and incidence matrix
of the following graph. Also represent the linked concept for memory
representation of below graph.

[Link] the algorithm for BFS on a directed graph and write down the
explanation.

[Link] the algorithm for Depth First Search of a graph. Write down the
DFS order of the graph given below.
[Link] the path matrix? State the difference by writing down adjacency
matrix and incidence matrix of the following graph. Also represent the
linked concept for memory representation of below graph.