TYPICAL QUESTIONS & ANSWERS

PART I

OBJECTIVE TYPE QUESTIONS

Each Question carries 2 marks.

Q.1 If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the expected number of collisions involving a particular key x is :

(A) less than 1. (B) less than n.

(C) less than m. (D) less than n/2.

Ans:A

Q.2 Let A be an adjacency matrix of a graph G. The entry in the matrix , gives

(A) The number of paths of length K from vertex Vi to vertex Vj.

(B) Shortest path of K edges from vertex Vi to vertex Vj.

(C) Length of a Eulerian path from vertex Vi to vertex Vj.

(D) Length of a Hamiltonian cycle from vertex Vi to vertex Vj.

Ans:B

Q.3 The OS of a computer may periodically collect all the free memory space to form contiguous block of free space. This is called

(A) Concatenation (B) Garbage collection

(C) Collision (D) Dynamic Memory Allocation

Ans:B

Q.4 What is the following code segment doing?

void fn( ){

char c;

cin.get(c);

if (c != ‘\n’) {

fn( );

cout.put(c);

}

}

(A) The string entered is printed as it is.

(B) The string entered is printed in reverse order.

(C) It will go in an infinite loop.

(D) It will print an empty line.

Ans:B

Q.5 You have to sort a list L consisting of a sorted list followed by a few “random” elements. Which of the following sorting methods would be especially suitable for such a task?

(A) Bubble sort (B) Selection sort

(C) Quick sort (D) Insertion sort

Ans:D

Q.6 B Trees are generally

(A) very deep and narrow (B) very wide and shallow

(C) very deep and very wide (D) cannot say

Ans:D

Q.7 A technique for direct search is

(A) Binary Search (B) Linear Search

(C) Tree Search (D) Hashing

Ans:D

Q.8 If a node having two children is deleted from a binary tree, it is replaced by its

(A) Inorder predecessor (B) Inorder successor

(C) Preorder predecessor (D) None of the above

Ans:B

Q.9 The searching technique that takes O (1) time to find a data is

(A) Linear Search (B) Binary Search

(C) Hashing (D) Tree Search

Ans:C

Q.10 A mathematical-model with a collection of operations defined on that model is called

(A) Data Structure (B) Abstract Data Type

(C) Primitive Data Type (D) Algorithm

Ans:B

Q.11 The number of interchanges required to sort 5, 1, 6, 2 4 in ascending order using Bubble Sort is

(A) 6 (B) 5

(C) 7 (D) 8

Ans:B

Q.12 The postfix form of the expression is

(A) (B)

(C) (D)

Ans: A

Q.13 The complexity of multiplying two matrices of order m*n and n*p is

(A) mnp (B) mp

(C) mn (D) np

Ans:A

Q.14 Merging 4 sorted files containing 50, 10, 25 and 15 records will take____time

(A) O (100) (B) O (200)

(C) O (175) (D) O (125)

Ans:A

Q.15 For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is equal to

(A) 2n (B) (2n-1)/2

(C) 2e (D) e²/2

Ans:C

Q.16 In worst case Quick Sort has order

(A) O (n log n) (B) O (n²/2)

(C) O (log n) (D) O (n²/4)

Ans:B

Q.17 A full binary tree with 2n+1 nodes contain

(A) n leaf nodes (B) n non-leaf nodes

(C) n-1 leaf nodes (D) n-1 non-leaf nodes

Ans:B

Q.18 If a node in a BST has two children, then its inorder predecessor has

(A) no left child (B) no right child

(C) two children (D) no child

Ans:B

Q.19 A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is known as

(A) full binary tree. (B) AVL tree.

(C) threaded tree. (D) complete binary tree.

Ans:A

Q.20 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 a

(A) queue. (B) stack.

(C) tree. (D) linked list.

Ans:A

Q.21 What is the postfix form of the following prefix expression -A/B*C$DE

(A) ABCDE$*/- (B) A-BCDE$*/-

(C) ABC$ED*/- (D) A-BCDE$*/

Ans:A

Q.22 A full binary tree with n leaves contains

(A) n nodes. (B) nodes.

(C) 2n –1 nodes. (D) nodes.

Ans:C

Q.23 A sort which relatively passes through a list to exchange the first element with any element less than it and then repeats with a new first element is called

(A) insertion sort. (B) selection sort.

(C) heap sort. (D) quick sort.

Ans:D

Q.24 Which of the following sorting algorithms does not have a worst case running time of ?

(A) Insertion sort (B) Merge sort

(C) Quick sort (D) Bubble sort

Ans:B

Q.25 An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components?

(A) O (n) (B) O (e)

(C) O (e+n) (D) O

Ans:C

Q.26 Consider a linked list of n elements. What is the time taken to insert an element after an element pointed by some pointer?

(A) O (1) (B) O

(C) O (n) (D) O

Ans:A

Q.27 The smallest element of an array’s index is called its

(A) lower bound. (B) upper bound.

(C) range. (D) extraction.

Ans:A

Q.28 In a circular linked list

(A) components are all linked together in some sequential manner.

(B) there is no beginning and no end.

(C) components are arranged hierarchically.

(D) forward and backward traversal within the list is permitted.

Ans:B

Q.29 A graph with n vertices will definitely have a parallel edge or self loop of the total number of edges are

(A) more than n (B) more than n+1

(C) more than (n+1)/2 (D) more than n(n-1)/2

Ans: D

Q.30 The minimum number of multiplications and additions required to evaluate the polynomial

P = 4x³+3x²-15x+45 is

(A) 6 & 3 (B) 4 & 2

(C) 3 & 3 (D) 8 & 3

Ans: C

Q.31 The maximum degree of any vertex in a simple graph with n vertices is

(A) n–1 (B) n+1

(C) 2n–1 (D) n

Ans: A

Q.32 The data structure required for Breadth First Traversal on a graph is

(A) queue (B) stack

(C) array (D) tree

Ans: A

Q.33 The quick sort algorithm exploit _________ design technique

(A) Greedy (B) Dynamic programming

(C) Divide and Conquer (D) Backtracking

Ans: C

Q.34 The number of different directed trees with 3 nodes are

(A) 2 (B) 3

(C) 4 (D) 5

Ans: B

Q.35 One can convert a binary tree into its mirror image by traversing it in

(A) inorder (B) preorder

(C) postorder (D) any order

Ans:C

Q.36 The total number of companions required to merge 4 sorted files containing 15, 3, 9 and 8 records into a single sorted file is

(A) 66 (B) 39

(C) 15 (D) 3

Ans: 33 (option is not available)

Q.37 In a linked list with n nodes, the time taken to insert an element after an element pointed by some pointer is

(A) 0 (1) (B) 0 (log n)

(C) 0 (n) (D) 0 (n 1og n)

Ans:A

Q.38 The data structure required to evaluate a postfix expression is

(A) queue (B) stack

(C) array (D) linked-list

Ans:B

Q.39 The data structure required to check whether an expression contains balanced parenthesis is

(A) Stack (B) Queue

(C) Tree (D) Array

Ans:A

Q.40 The complexity of searching an element from a set of n elements using Binary search algorithm is

(A) O(n) (B) O(log n)

(C) O(n²) (D) O(n log n)

Ans:B

Q.41 The number of leaf nodes in a complete binary tree of depth d is

(A) 2^d (B) 2^d–1+1

(C) 2^d+1+1 (D) 2^d+1

Ans:A

Q.42 What data structure would you mostly likely see in a nonrecursive implementation of a recursive algorithm?

(A) Stack (B) Linked list

(C) Queue (D) Trees

Ans:A

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

(A) Bubble Sort (B) Insertion Sort

(C) Selection Sort (D) Quick Sort

Ans:A

Q.44 A B-tree of minimum degree t can maximum _____ pointers in a node.

(A) t–1 (B) 2t–1

(C) 2t (D) t

Ans:D

Q.45 The process of accessing data stored in a serial access memory is similar to manipulating data on a

(A) heap (B) queue

(C) stack (D) binary tree

Ans:C

Q.46 A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are

(A) greater than n–1 (B) less than n(n–1)

(C) greater than n(n–1)/2 (D) less than n²/2

Ans:A

Q.47 A BST is traversed in the following order recursively: Right, root, left

The output sequence will be in

(A) Ascending order (B) Descending order

(C) Bitomic sequence (D) No specific order

Ans:B

Q.48 The pre-order and post order traversal of a Binary Tree generates the same output. The tree can have maximum

(A) Three nodes (B) Two nodes

(C) One node (D) Any number of nodes

Ans:C

Q.49 The postfix form of A*B+C/D is

(A) *AB/CD+ (B) AB*CD/+

(C) A*BC+/D (D) ABCD+/*

Ans:B

Q.50 Let the following circular queue can accommodate maximum six elements with the following data

front = 2 rear = 4

queue = _______; L, M, N, ___, ___

What will happen after ADD O operation takes place?

(A) front = 2 rear = 5

queue = ______; L, M, N, O, ___

(B) front = 3 rear = 5

queue = L, M, N, O, ___

(C) front = 3 rear = 4

queue = ______; L, M, N, O, ___

(D) front = 2 rear = 4

queue = L, M, N, O, ___

Ans:A

Q.51 A binary tree of depth “d” is an almost complete binary tree if

(A) Each leaf in the tree is either at level “d” or at level “d–1”

(B) For any node “n” in the tree with a right descendent at level “d” all the left descendents of “n” that are leaves, are also at level “d”

(C) Both (A) & (B)

(D) None of the above

Ans:C

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

(A) linked list (B) node list

(C) primitive list (D) None of these

Ans:A

Q.53 Representation of data structure in memory is known as:

(A) recursive (B) abstract data type

(C) storage structure (D) file structure

Ans:B

Q.54 If the address of A[1][1] and A[2][1] are 1000 and 1010 respectively and each element occupies 2 bytes then the array has been stored in _________ order.

(A) row major (B) column major

(C) matix major (D) none of these

Ans:A

Q.55 An adjacency matrix representation of a graph cannot contain information of :

(A) nodes (B) edges

(C) direction of edges (D) parallel edges

Ans:D

Q.56 Quick sort is also known as

(A) merge sort (B) heap sort

(C) bubble sort (D) none of these

Ans:D

Q.57 One of the major drawback of B-Tree is the difficulty of traversing the keys sequentially.

(A) True (B) False

Ans:A

Q.58 O(N) (linear time) is better than O(1) constant time.

(A) True (B) False

Ans:B

Q.59 An ADT is defined to be a mathematical model of a user-defined type along with the collection of all ____________ operations on that model.

(A) Cardinality (B) Assignment

(C) Primitive (D) Structured

Ans:C

Q.60 An algorithm is made up of two independent time complexities f (n) and g (n). Then the complexities of the algorithm is in the order of

(A) f(n) x g(n) (B) Max ( f(n),g(n))

(C) Min (f(n),g(n)) (D) f(n) + g(n)

Ans:B

Q.61 The goal of hashing is to produce a search that takes

(A) O(1) time (B) O(n² ) time

(C) O(log n ) time (D) O(n log n ) time

Ans:A

Q.62 The best average behaviour is shown by

(A) Quick Sort (B) Merge Sort

(C) Insertion Sort (D) Heap Sort

Ans:A

Q.63 What is the postfix form of the following prefix *+ab–cd

(A) ab+cd–* (B) abc+*–

(C) ab+*cd– (D) ab+*cd–

Ans:A

Q.64 Time complexities of three algorithms are given. Which should execute the slowest for large values of N?

(A) (B)

(C) (D) None of these

Ans:B

Q.65 How does an array differ from an ordinary variable?

Ans.

Array Vs. Ordinary Variable

Array is made up of similar data structure that exists in any language. Array is set of similar data types. Array is the collection of similar elements. These similar elements could be all int or all float or all char etc. Array of char is known as string. All elements of the given array must be of same type. Array is finite ordered set of homogeneous elements. The number of elements in the array is pre-specified.

An ordinary variable of a simple data type can store a single element only.

For example: Ordinary variable: - int a

Array: - int a[10]

Q.66 What values are automatically assigned to those array elements which are not explicitly

initialized?

Ans.

Garbage values are automatically assigned to those array elements that are not explicitly initialized. If garbage class is auto then array is assumed to contain garbage values. If storage class were declared static or external then all the array elements would have a default initial value as zero.

Q.67 A stack is to be implemented using an array. The associated declarations are:

int stack [100];

int top = 0;

Give the statement to perform push operation.

Ans.

Let us assume that if stack is empty then its top has value –1.

Top ranges from 0 – 99. Let item be the data to be inserted into stack

int stack [100];

int top = 0;

int item ;

If (top == 99)

Printf (“stack overflow”);

Else

stack[top++] = item;

Q.68 Assume that a queue is available for pushing and popping elements. Given an input sequence a, b, c, (c be the first element), give the output sequence of elements if the rightmost element given above is the first to be popped from the queue.

Ans.

A

B

C

Front Rear

c b a

Q.69 A two dimensional array TABLE [6] [8] is stored in row major order with base address 351. What is the address of TABLE [3] [4]?

Ans.

TABLE [6] [8]

Base address 351

Let us assume that TABLE[6] [8] is of type integer.

The formula for row major form to calculate address is

Loc(a[ i ] [j] ) = base (a) + w [n (i –lbr) + ( j-lbc)]

where

n no. of column in array

w no of bytes per storage location

lbr lower bound for row index

lbc lower bound for column index.

Loc(TABLE[3] [4]) = 351 + 2[8(3-0) + (4-0)]

= 351 +2[24+4]

= 351 + 56

=407

Q.70 Which sorting algorithm is best if the list is already sorted? Why?

Ans.

Insertion sort as there is no movement of data if the list is already sorted and complexity is of the order O(N)

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

Ans.

Time complexity of merge sort is O(N log₂ N)

Time complexity of heap sort is O(nlog₂n)

Sort	Worst Case	Average Case	Best Case
Merge Sort	O(nlog n)	O(nlog n)	O(nlog n)
Heap Sort	O(nlog n)	O(nlog n)	O(nlog n)

Q.72 What is the maximum possible number of nodes in a binary tree at level 6?

Ans.

2⁶ = 2 x 2 x 2 x 2 x 2 x 2 = 64

Q.73 A queue is a,

(A) FIFO (First In First Out) list. (B) LIFO (Last In First Out) list.

(C) Ordered array. (D) Linear tree.

Ans. (A)

Q.74 Which data structure is needed to convert infix notation to postfix notation?

(A) Branch (B) Queue

(C) Tree (D) Stack

Ans. (D)

Q.75 Which of the following operations is performed more efficiently by doubly linked list than

by singly linked list?

(A) Deleting a node whose location in given

(B) Searching of an unsorted list for a given item

(C) Inverting a node after the node with given location

(D) Traversing a list to process each node

Ans. (A)

Q.76 The extra key inserted at the end of the array is called a,

(A) End key. (B) Stop key.

(C) Sentinel. (D) Transposition.

Ans. (C)

Q.77 The prefix form of A-B/ (C * D ^ E) is,

(A) -/*^ACBDE (B) -ABCD*^DE

(C) -A/B*C^DE (D) -A/BC*^DE

Ans. (C)

Q.78 Consider that n elements are to be sorted. What is the worst case time complexity of Bubble sort?

(A) O(1) (B) O(log₂n)

(C) O(n) (D) O(n²)

Ans. (D)

Q.79 A characteristic of the data that binary search uses but the linear search ignores is the___________.

(A) Order of the elements of the list.

(B) Length of the list.

(C) Maximum value in list.

(D) Type of elements of the list.

Ans. (A)

Q.80 In Breadth First Search of Graph, which of the following data structure is used?

(A) Stack. (B) Queue.

(C) Linked List. (D) None of the above.

Ans. (B)

Q.81 The largest element of an array index is called its

(A) lower bound. (B) range.

(C) upper bound. (D) All of these.

Ans. (C)

Q.82 What is the result of the following operation

Top (Push (S, X))

(A) X (B) null

(C) S (D) None of these.

Ans. (A)

Q.83 How many nodes in a tree have no ancestors.

(A) 0 (B) 1

(C) 2 (D) n

Ans. (B)

Q.84 In order to get the contents of a Binary search tree in ascending order, one has to traverse it in

(A) pre-order. (B) in-order.

(C) post order. (D) not possible.

Ans. (B)

Q.85 Which of the following sorting algorithm is stable

(A) insertion sort. (B) bubble sort.

(C) quick sort. (D) heap sort.

Ans. (D)

Q.86 The prefix form of an infix expression is

(A) . (B) .

(C) . (D) .

Ans. (C)

Q.87 Which data structure is used for implementing recursion?

(A) Queue. (B) Stack.

(C) Arrays. (D) List.

Ans. (B)

Q.88 In binary search, average number of comparison required for searching an element in a list if n numbers is

(A). (B) .

(C) n. (D) n – 1.

Ans. (A)

Q.89 In order to get the information stored in a Binary Search Tree in the descending order, one should traverse it in which of the following order?

(A) left, root, right (B) root, left, right

(C) right, root, left (D) right, left, root

Ans. (C)

Q.90 The equivalent prefix expression for the following infix expression (A+B)-(C+D*E)/F*G is

(A) -+AB*/+C*DEFG (B) /-+AB*+C*DEFG

(C) -/+AB*+CDE*FG (D) -+AB*/+CDE*FG

Ans. (A)

Q.91 The time required to delete a node x from a doubly linked list having n nodes is

(A) O (n) (B) O (log n)

(C) O (1) (D) O (n log n)

Ans. (C)

Q.92 Ackerman’s function is defined on the non-negative integers as follows

a (m,n) = n+1 if m=0

= a (m-1, 1) if m0, n=0

= a (m-1, a(m, n-1)) if m0, n0

The value of a (1, 3) is

(A) 4. (B) 5.

(C) 6. (D) 7.

Ans. (B)

Q.93 The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is

(A) 600. (B) 350.

(C) 650. (D) 588.

Ans. (B)

Q.94 The worst case of quick sort has order

(A) O(n²) (B) O(n)

(C) O (n log₂ n) (D) O (log₂ n)

Ans. (A)

Q.95 For an undirected graph G with n vertices and e edges, the sum of the degrees of each vertex is

(A) ne (B) 2n

(C) 2e (D) eⁿ

Ans. (C)

Q.96 The time required to delete a node x from a doubly linked list having n nodes is

(A) O (n) (B) O (log n)

(C) O (1) (D) O (n log n)

Ans. (C)

PART II

DESCRIPTIVES

Q.1 What is an algorithm? What are the characteristics of a good algorithm? (4)

Ans:

An algorithm is “a step-by-step procedure for accomplishing some task'' An algorithm can be given in many ways. For example, it can be written down in English (or French, or any other ''natural'' language). However, we are interested in algorithms which have been precisely specified using an appropriate mathematical formalism--such as a programming language.

Every algorithm should have the following five characteristics:
1.Input: The algorithm should take zero or more input.
2. Output: The algorithm should produce one or more outputs.
3. Definiteness: Each and every step of algorithm should be defined unambiguously.
4. Effectiveness: A human should be able to calculate the values involved in the procedure of the algorithm using paper and pencil.
5. Termination: An algorithm must terminate after a finite number of steps.

Q.2 How do you find the complexity of an algorithm? What is the relation between the time and space complexities of an algorithm? Justify your answer with an example. (5)

Ans:

Complexity of an algorithm is the measure of analysis of algorithm. Analyzing an algorithm means predicting the resources that the algorithm requires such as memory, communication bandwidth, logic gates and time. Most often it is computational time that is measured for finding a more suitable algorithm. This is known as time complexity of the algorithm. The running time of a program is described as a function of the size of its input. On a particular input, it is traditionally measured as the number of primitive operations or steps executed.

The analysis of algorithm focuses on time complexity and space complexity. As compared to time analysis, the analysis of space requirement for an algorithm is generally easier, but wherever necessary, both the techniques are used. The space is referred to as storage required in addition to the space required storing the input data. The amount of memory needed by program to run to completion is referred to as space complexity. For an algorithm, time complexity depends upon the size of the input, thus, it is a function of input size ‘n’. So the amount of time needed by an algorithm to run to its completion is referred as time complexity.

The best algorithm to solve a given problem is one that requires less memory and takes less time to complete its execution. But in practice it is not always possible to achieve both of these objectives. There may be more than one approach to solve a same problem. One such approach may require more space but takes less time to complete its execution while the other approach requires less space but more time to complete its execution. Thus we may have to compromise one to improve the other. That is, we may be able to reduce space requirement by increasing running time or reducing running time by allocating more memory space. This situation where we compromise one to better the other is known as Time-space tradeoff.

Q.3 Compare two functions and for various values of n. Determine when second becomes larger than first. (5)

n	n^2	2^n/4
1 2 3 4 5 6 7 8 9 10	1 4 9 16 25 36 49 64 81 100	0.5 1 2 4 8 16 32 64 128 256

When n=8, the value of n² and 2ⁿ/4 is same. Before that n² >2ⁿ/4, and after this value n²< 2ⁿ/4.

Q.4 Explain an efficient way of storing a sparse matrix in memory. Write a module to find the transpose of a sparse matrix stored in this way. (10)

Ans:

A matrix in which number of zero entries are much higher than the number of non zero entries is called sparse matrix. The natural method of representing matrices in memory as two-dimensional arrays may not be suitable for sparse matrices. One may save space by storing only nonzero entries. For example matrix A (3*3 matrix) represented below

0 2 0

5 0 0

0 6 9

can be written in sparse matrix form as:

3 3 4

0 1 2

1 0 5

2 2 6

2 3 9

where first row represent the dimension of matrix and last column tells the number of non zero values; second row onwards it is giving the position and value of non zero number.

A function to find transpose of a sparse matrix is:

void transpose(x,r,y)

int x[3][3],y[3][3],r;

{

int i,j,k,m,n,t,p,q,col;

m=x[0][0];

n=x[0][1];

t=x[0][2];

y[0][0]=n;

y[0][1]=m;

y[0][2]=t;

if(t>0)

{

q=1;

for (col=0;col<=n;col++)

for(p=1;p<=t;p++)

if(x[p][1]==col)

{

y[q][0]=x[p][1];

y[q][1]=x[p][0];

y[q][2]=x[p][2];

q++;

}

}

return;

}

Q.5 Explain an efficient way of storing two symmetric matrices of the same order in memory. (4)

Ans:

A n-square matrix array is said to be symmetric if a[j][k]=a[k][j] for all j and k. For a symmetric matrix, we need to store elements which lie on and below the diagonal or those on and above the diagonal. Two symmetric matrix of A and B of same dimension can be stored in an n*(n+1) array C where c[j][k]=a[j][k] when j≥k but c[j][k-1]=b[j][k-1] when j<k.

a₁₁ b₁₁ b₁₂ b_{13 …} b_1,n-1 b_1n

a₂₁ a₂₂ b₂₂ b_{23 …} b_2,n-1 b_2n

a₃₁ a₃₂ a₃₂ b_{33 …} b_3,n-1 b_3n

…………………………………………………

………………………………………………….

a_n1 a_n2 a_n3 a_{n4 …} a_n,n b_nn

Q.6 Write an algorithm to evaluate a postfix expression. Execute your algorithm using the following postfix expression as your input : a b + c d +*f . (7)

Ans:

To evaluate a postfix expression:

clear the stack

symb = next input character

while(not end of input)

{

if (symb is an operand)

push onto the stack;

else

{

pop two operands from the stack;

result=op1 symb op2;

push result onto the stack;

}

symb = next input character;

}

return (pop (stack));

The given input as postfix expression is:- ab+cd+*f^

Symb Stack Evaluation

a a

b a b

+ pop a and b (a + b)

Push (a + b)

c (a + b) c

d (a + b) c d

+ pop c and d (c + d)

Push (c + d)

* pop (a + b) and (c + d) (a + b) * (c + d)

f (a + b) * (c + d) f

^ pop (a + b) * (c + d) and f (a + b) * (c + d) ^ f

The result of evaluation is ((a + b) * (c + d)) ^ f

Q.7 What are circular queues? Write down routines for inserting and deleting elements from a circular queue implemented using arrays. (7)

Ans:

Circular queue: Static queues have a very big drawback that once the queue is FULL, even though we delete few elements from the "front" and relieve some occupied space, we are not able to add anymore elements as the "rear" has already reached the Queue's rear most position.

The solution lies in a queue in which the moment "rear" reaches its end; the "first" element will become the queue's new "rear". This type of queue is known as circular queue having a structure like this in which, once the Queue is full the "First" element of the Queue becomes the "Rear" most element, if and only if the "Front" has moved forward;

Circular Queue using array:-

insert(queue,n,front,rear,item)

This procedure inserts an element item into a queue.

1. If front = 1 and rear = n, or if front = rear + 1, then:

Write: overflow, and return

2. [find new value of rear]

If front = NULL , then : [queue initially empty.]

Set front = 1 and rear=1.

Else if rear = n, then:

Set rear=1.

Else:

Set rear = rear + 1.

[end of structure.]

3. Set queue[rear] = item. [this inserts new element.]

4.Return .

delete(queue,n,front,rear,item)

This procedure deletes an element from a queue and

assigns it to the variable item.

1. [queue already empty?]

If front = NULL , then:

Write: underflow, and return.

2. Set item = queue[front].

3. [find new value of front]

If front = rear , then : [queue has only one element to start].

Set front = NULL and rear = NULL.

Else if front = n, then:

Set front=1.

Else:

Set front = front + 1.

[end of structure.]

4. Return .

Q.8 Given a set of input representing the nodes of a binary tree, write a non recursive algorithm that must be able to output the three traversal orders. Write an algorithm for checking validity of the input, i.e., the program must know if the input is disjoint, duplicated and has a loop. (10)

Ans:

Pre-order Traversal

The process of doing a pre-order traversal iteratively then has the following steps(assuming that a stack is available to hold pointers to the appropriate nodes):

1. push NULL onto the stack

2. start at the root and begin execution

3. write the information in the node

4. if the pointer to the right is not NULL push the pointer onto the stack

5. if the pointer to the left is not NULL move the pointer to the node on the left

6. if the pointer to the left is NULL pop the stack

7. repeat steps 3 to 7 until no nodes remain

In-order Traversal

This process when implemented iteratively also requires a stack and a Boolean to prevent the execution from traversing any portion of a tree twice. The general process of in-order traversal follows the following steps:

1. push a NULL onto the stack.

2. beginning with the root, proceed down the left side of the tree. As long as there is another left node following the current node, push the pointer to the current node onto the stack and move to the left node which follows it.

3. when there are no more left nodes following the current node, process the current node.

4. check to see if the last left node has a right node(it obviously doesn’t have a left node).

5. if there is a right node then there is subtree to the right. This should be processed in following steps 2 to 4.

6. if there is no right node then pop the last node from the stack (back up one node). Process this node and since this node has a left subtree that has already been processed, move to the right of the node and begin looking for a left and right subtree again.

Post-order Traversal

This can be done both iteratively and recursively. The iterative solution would require a modification of the in-order traversal algorithm.

Q.9 Two linked lists contain information of the same type in ascending order.

Write a module to merge them to a single linked list that is sorted. (7)

Ans:

merge(struct node *p, struct node *q, struct **s)

{

struct node *z;

z = NULL;

if((x= =NULL) && (y = =NULL))

return;

while(x!=NULL && y!=NULL)

{

if(*s= =NULL)

{

*s=(struct link *)malloc(sizeof(struct node *z));

z=*s;

}

else

{

z-->link=(struct link *)malloc(sizeof(struct node *));

z=z-->link;

}

if(x-->data < y-->data)

{

z-->data=x-->data;

x=x-->link;

}

else if(x-->exp > y-->exp)

{

z-->data=y-->data;

y=y-->link;

}

else if(x-->data= =y-->data)

{

z-->data=y-->data;

x=x-->link;

y=y-->link;

}

}

while(x!=NULL)

{

zàlink = struct link *malloc(sizeof(struct node *));

z=zàlink;

z-->data=x-->data;

x=x-->link;

}

while(y!=NULL)

{

zàlink = struct link *malloc(sizeof(struct node *));

z=zàlink;

z-->data=y-->data;

y=y-->link;

}

z-->link=NULL;

}

Q.10 What is a 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. (8)

Ans:

A binary search tree B is a binary tree each node of which satisfies the following conditions:

1. The value of the left-subtree of ‘x’ is less than the value at ‘x’

2. The value of the right-subtree of ‘x’ is greater than value at ‘x’

3. the left-subtree and right-subtree of binary search tree are again binary search tree.

Preorder:-

23, 36, 39, 41, 45, 48, 56, 69, 76, 89, 98, 115

Inorder:-

45, 36, 23, 39, 41, 76, 56, 48, 69, 89, 115, 98

Postorder:-

23, 41, 39, 36, 48, 69, 56, 98, 115, 89, 76

Q.11 What are expression trees? Represent the following expression using a tree. Comment on the result that you get when this tree is traversed in Preorder, Inorder and postorder. (a-b) / ((c*d)+e) (6)

Ans:

The leaves of an expression tree are operands, such as constants or variable names, and the other nodes contain operators. This particular tree happens to be binary, because all of the operations are binary, and although this is the simplest case, it is possible for nodes to have more than two children. It is also possible for a node to have only one child, as is the case with the unary minus operator. We can evaluate an expression tree, T, by applying the operator at the root to the values obtained by recursively evaluating the left and right subtrees.

The expression tree for the expression: (a – b ) / ( ( c * d ) + e))

The traversal of the above expression tree gives the following result:-

Preorder:- ( / - a b + * c d e)

This expression is same as the “prefix notation” of the original expression.

Inorder:- ( a – b) / ((c * d) + e )

Thus the inorder traversal gives the actual expression.

Postorder:- ( a b – c d * e + / )

Thus the postorder traversal of this gives us the “posfix notation” or the “Reverse Polish notation” of the original expression.

Q.12 How do you rotate a Binary Tree? Explain right and left rotations with the help of an example. (8)

Ans:

Rotations in the tree:

If after inserting a node in a Binary search tree, the balancing factor (height of left subtree - height of right subtree) of each node remains 0, 1 and -1 then there is no need of modification of original tree. If balancing factor of any node is either +2 or -2, the tree becomes unbalanced. It can be balanced by using left rotation or right rotation or a combination of both.

For example

1. In the following tree, after inserting node 70 , the balance factor of tree at the root node (2) so the tree is rotated left to have a height balanced tree shown by (a) to (b):

(b)

2. In the following tree, after inserting 10 the balance factor of tree at root node is +2 so the tree is rotated right to have height balanced tree as shown by(a) to (b) below:

(a)

(b)

Q.13 Taking a suitable example explains how a general tree can be represented as a Binary Tree. (6)

Ans:

Conversion of general trees to binary trees:

A general tree can be converted into an equivalent binary tree. This conversion process is called the natural correspondence between general and binary trees.

The algorithm is as follows:

(a) Insert edges connecting siblings from left to right at the same level.

(b) Delete all edges of a parent to its children except to its left most offspring.

(c) Rotate the resultant tree 45⁰ to mark clearly left and right subtrees.

A general tree shown in figure (a) converted into a binary tree shown in (b)

Q.14 What are the different ways of representing a graph? Represent the following graph using those ways. (6)

Ans:

The different ways of representing a graph is:

Adjacency list representation: This representation of graph consists of an array Adj of |V| lists, one for each vertex in V. For each uεV, the adjacency list Adj[u] contains all the vertices v such that there is an edge (u,v)ε E that is Adj[u] consists of all the vertices adjacent to u in G. The vertices in each adjacency list are stored in an arbitrary order. The adjacency list representation of given graph is depicted in the following figure:

Adjacency Matrix representation: This representation consists of |V|*|V| matrix A= (a_ij) such that

1 if(i,j)ε E

a_ij =

0 otherwise

The adjacency matrix representation of given graph is given below:

A B C D E

A

B

C

D

E

Q.15 Show the result of running BFS and DFS on the directed graph given below using vertex 3 as source. Show the status of the data structure used at each stage. (8)

Ans:

Depth first search (DFS):

Depth first search (DFS) starting from vertex 3 as source and traversing above adjacency list one by one, we get following result:

3-7-2-8-6-5-4-1

Breath First Search(BFS):

Q

Elements are inserted from rear and deleted from front. Before removal of an element, insert its element in the queue. So result of BFS in the given graph is:

3-7-2-8-6-5-4-1

Q.16 Write an algorithm for finding solution to the Tower’s of Hanoi problem. Explain the working of your algorithm (with 4 disks) with diagrams. (5)

Ans:

void Hanoi(int n, char initial, char temp, char final)

{ if(n==1)

{ printf(“move disk 1 from peg %c to peg%c\n”,initial,final);

return;

}

Hanoi(n-1,initial, final, temp);

printf(“move disk %d from peg %c to peg%c\n”, n, initial, final);

Hanoi(n-1,temp,initial,final);

}

For n=4, let A, B and C denotes the initial, temp and final peg. Using above algorithm, the recursive solution for n=4 disks consists of the following 15 moves:

A B A C B C A B

C A C B A B