Model QUESTION PAPER – 2

As per the New Model Curriculum designed Under

[NEP]Applicable to BCA course of Bangalore
University & Bangalore City University
I. Answer any four questions each carry 2 mark (4*2=8)

1. How to measure the complexity of an algorithm?

Algorithm analysis refers to the task of determining the computing time and storage space
requirement of an algorithm. It is also known as performance analysis or efficiency of an
algorithm which enables us to select an efficient algorithm.
We can measure an algorithm by two ways:
 By checking the correctness of an algorithm
 By measuring time and space complexity of an algorithm
2. What is an abstract data type?give an example.
Abstract data type is a specification of set of data and set of operation that can be performed on
the data that is associated with its operation but representation is hidden
Example:

overflow

4
3
2
1

stack

3. Explain overflow and underflow conditions in stack.

The array size is already declared, it may be possible that sometimes there cannot be the place
for an item to be pushed (added). This condition is termed as ‘stack overflow’. For this we need
to always check the value of TOP with the size of the array prior to the operation.
Sometimes it may be possible that there is no item in the stack to POP(delete). If there
is no element in the stack, the POP value will be ‘-1’. This condition is popping from an empty
stack is termed as ‘stack underflow’. For this we need to always check the value of TOP before
deleting the item.
Consider a stack – array ‘s’ of size 20 which means that the maximum number of elements
that can be held by the stack (called MAXSTK) is 20 and let the item 14,23,1,4,45 are need to be
pushed into the stack. It can be represented as:
14 23 1 04 45
S[0] [1] [2] [3] [4] [19]

Top=4
 From the above representation, the stack items are,
S[0]=14;S[1]=23;S[2]=01;S[3]=04;S[4]=45 and MAXSTK=20.
The value of TOP is 4 and it increments by 1 from -1 for every PUSH operation and number of
such PUSH operation is 5.
4. What is a binary search tree? give an example.
A binary search tree, also known as an ordered binary tree, is a variant of binary trees in which
nodes are arranged in an order. In a binary search tree, all the nodes in the left sub-tree have a
value less than that of the root node. Correspondingly, all the nodes in the right sub-tree have a
value either equal to or greater than the root node.
Example:

50

30 80

75 90
20 40

85 100
15 45

Binary search tree with numeric data.

5. Mention any two types of graphs.

a) Directed graph : it is a pair G=(V,E) where v is set whose elements are called vertices, and E
is a set of ordered pair of element of V. Vertices are also called nodes. Elements of E are
arcs.

1 2

3 4 5

6 7
Directed graph

b) Undirected graph: An undirected graph is a pair G=(V,E),where V is a set whose elements

are called vertices, and E is a set of unordered pairs of distinct elements of V vertices are
nodes. Elements of E are called edges. Each edge considered as a subset of V containing two
elements.

1 2

3 4 5

6 7
 Undirected graph.

6. What do you mean by chaining in collision Resolution?

Collision resolution by chaining combines linked representation with hash table. When two or
more records hash to the same location, these records are constituted into a singly-linked list
called a chain.
In the chain method, a chain of elements is maintained which have the same hash
address. Each location in the hash table stores a pointer to the linked list, which contains all the
key elements that were hashed to that location.
Example: The location 5 in the hash table points to the key values that hashed to location 5.if
no key value hashes to location 5, then in the case location 5 will contain NULL.

II. Answer any 4 questions. Five marks questions (4*5=20)

7. Define sparse matrix. Write a C program to check whether given matrix is SPARSE or
NOT.
Matrix which contains high number of zero entries are called sparse matrices. In simple terms, a
matrix which contains more zero elements than non-zero elements are referred as sparse
matrix.
- Program to check whether given matrix is sparse matrix are not.
#include<stdio.h>
#include<conio.h>
int main( )
{
int matrix[10][10];
clrscr();
int i,j,m,n;
int sparse_counter=0;
printf(“Enter the order of the matrix:\n”);
scanf(“%d %d”,&m,&n);
printf(“\n Enter the elements of the matrix:\n”);
for(i=0;i<m;++i)
{
for(j=0;j<n;++j)
{
scanf(“%d”,&matrix[i][j]);
if(matrix[i][j]==0)
++sparse_counter;
}
}
if(sparse_counter > ((m*n)/2))
printf(“The given matrix is sparse Matrix !!! \n”);
else
printf(“The given matrix is not sparse Matrix \n”);
printf(“There are %d number of zeros.”, sparse_counter);
 getch();
}

Output:
Enter the order of the matrix: 3 3
Enter the elements of the matrix
120
000
011
The given matrix is sparse matrix !!!
There are 5 number of zeros.
8. Write an algorithm for ENQUEUE and DEQUEUE operations.
Algorithm for ENQUEUE or Qinsert (Q, front, rear, N, item)
Step 1: [overflow check]
If REAR=N-1
Then write (‘overflow’)
Return
Step 2: [Increment rear pointer]
REAR=REAR+1
Step 3: [insert the item]
Q[REAR]=ITEM
Step 4: return.

Algorithm for DEQUEUE or Qdelete (Q, front, rear ,N, Item)

Step 1: [overflow check]

if REAR=FRONT-1
Then write(‘underflow’)
return(0)
Step 2: [delete the item]
ITEM=Q[FRONT]
Step 3: if FRONT=REAR[when there is only one item]
FRONT=0, REAR=-1
else
FRONT=FRONT+1
Step 4: return
9. What is Recursion? Write a program to print Fibonacci series using Recursion function.
Recursion is a process of calling the function repeatedly in terms of itself. The repeated calling
is terminated by the specified condition.
Program:
#include<stdio.h>
#include<conio.h>
fibon(int N)
{
if((N==0)) || (N==1))
return(0);
else if (N==2)
return(1);
 else
return(fibon(N-1)+fibon(N-2);
}
void main( )
int N;
clrscr( );
int i=0;
printf(“Enter the number to generate Fibonacci series: \n”);
scanf(“%d”,&N);
while(i<N)
{
++I;
printf(“%d”, fibon(i));
}
Printf(“\n %dth element of the series is: %d \n”, i, fibon(i));
Getch( );
}
10. Write pre order, in order, post-order, Traversal for the given Tree.

B C
B
D E F

G
H I

Preorder : ABDCEGFHI
Inorder : BDAGECHFI
Postorder : DBGEHIFCA
11. Write an algorithm for insertion sort. Give the analysis for insertion sort.
Algorithm:
A is an array of n elements.
Step 1: Repeat step 2 to 5 for pass=1 to n – 1
Step 2: Set K=A[pass]
Step 3: repeat step 4 for j = pass -1 to 0
Step 4: if (k < A[j])
A[j+1]=A[j]
Step 5: A[j+1]=K
Step 6: Exit.
 The process of inserting each element in proper place is at shown below
Pass 0 : A(0) is already sorted because of only one element.
Pass 1 : A[1] is inserted before or after A[0] So A[0] and A[1] are sorted.
Pass 2 : A[2] is inserted before A[0], or after A[1] or in between A[0] and A[1]. So A[0] , A[1] and
A[2] are sorted.
Pass 3 : A[3] inserted into its proper place in A[0] A[1] A[2] So A[0], A[1], A[2] and A[3] are
sorted
Pass N-1: A[N-1] is inserted into its proper place in A[0], A[1].………A[N - 2]
so A[0], A[1] ,A[2] ………... A [N-1] are sorted.
 Any element to be inserted in between the ith element and i+1th element is possible only
When, element> = 1th element and
element<=(i+1)th element.
12. Write a note on
i. Adjacency matrix
ii. Adjacency list
i. In adjacency matrix is a matrix with ‘n’ rows and ‘n’ columns. Which entry in the matrix
represents 1, if there exists an edge (i,j) between vertex i and vertex j and 0 when there is
no edge. Therefore, the adjacency matrix contains only 0’s and 1’s for both undirected and
directed graphs.

Advantages and disadvantages of adjacency matrix :

 Adjacency matrices are helpful when we need to quickly check if two nodes have a direct
edge or not. however, the main disadvantage is its large memory complexity
 The adjacency matrix is most helpful in cases where the graph doesn’t contain a large
number of nodes. Also, when the graph is almost complete using adjacency matrices might
be a good solution.
 Adding new nodes in an adjacency matrix is a difficult task, as the size of the matrix needs
to be changed and existing nodes may have to be reordered.
ii. In adjacency list representation, the adjacency information is stored in the form of linked
list. For each vertex in the graph, a linked is created to stored all the adjacent vertices.

Advantages and disadvantages of adjacency list :

 Adjacency list are a great option when we need to continuously access all the neighbors
of some node u. in the case, we’ll only be iterating over the required nodes. Adjacency
list limitations show when we need to check of two nodes have a direct edges or not.
 If is often for storing graphs that have small-to-,moderate number of edges. That is, an
adjacency list is preferred for representing sparse graphs in the computer’s memory;
otherwise, an adjacency matrix is a good choice.
 Adding new nodes in graphs is easy and straightforward when graph is represented
using an adjacency list.

III. Answer any four questions. Eights marks for each (4*8=32)

13. a) Explain different asymptotic notations. (5m)

b) write an algorithm to insert an element into an array. (3m)

a) - Big –oh notation(O)

f(n) = 0(g(n)) such that there exists two positive Constants 'c' and ‘no’ n with constraint that.
| f(n) | < c |g(n)| n > no .
it is often useful to think of g as some given function and f as the function to analyse. The
important point is that f is bounded above by some Constant multiple of g (n) for all large
Values of n. let us assume that n is real number.
the notation O(g(n)) is usually called “ big oh of g of n”. in this notation f(n) grows no more
than g(n)
 c.g(n)

f(n)

no

F(n)=0(g(n))

- Omega notation (Ω)

f(n)= Ω(g(n))
if and only if there exists two positive constants c and no with the constraint that
| f(n) | ≤ c | g(n) |∀n ≥ no
Here c is some positive constant. Thus g is a lower bound on the value of f for all suitably
large n.

f(n)

c.g(n)

no

f(n)=Ω(g(n))

- Theta notation (⊖)

F(n)= ⊖(g(n))
If and only if there exists three positive constants c1, c2, and no with the constant that
C1| g(n) | ≤ | f(n) |≤ c2 |g(n) | ∀n ≥ no
 C2.g(n)

f(n)

C1.g(n)

no n

f(n)= ⊖(g(n))

b) Here A is linear array with N element. LOC is the location where ITEM is to be inserted.
Step 1: set I=N [Initialize counter]
Step 2: Repeat while ( I >= LOC )
Step 3: Set A[I +1]= A[I] [Move elements to next locations ]
Step 4: Set I = I – 1 [Decrease counter by 1]
[end of while loop]
Step 5: Set A[loc] = ITEM [Insertion element at LOC position]
Step 6: set N=N + 1 [Increment N by 1]

14. a) Mention and explain the type of linked list in brief. (4m)
b) Explain tower of Hanoi problem with an algorithm.

a) linked list are classified into 4 types

1) Singly linked list

2) Circular linked list
3) Doubly linked list
4) Header linked list
1) Singly linked list: a singly linked list is a collection of zero or more nodes where each node
has two or more field and only one link field which contains address of the next node.
Representation

Start

10 20 30 40 null
node 1 node 2 node 3 node 4
 2) Circular linked list: circular linked list are typically Intimented using a single linked list
structure that means each node in the list is connected to the next node via pointer the last
node in the list is then connected back to the first node by creating a ring like structure.

Representation

10 20 30 40

A Circular List can be used as a stack or Q to implement their Data Structure be required the
following function.
 Insert_front: to insert an element at the front end of the list
 Insert_rare: to insert an element at the rare and of the list
 Delete_front: to delete an element at the front end of the list
 Delete_rare: to delete an element at the rare and of the list
 Display: to display all the constants of the list.

Advantages of circular linked list

 Circular linked list can be travel to any node from any node.
 All the notes linked address will have valid addresses instead of null pointer.
 One can start at any node in the list and travels the whole list
 A node can be represented to insert or delete from any position of a linked list.

3) Doubly linked list: Double linked list of singly linked list is a data structure that contains a
set of a singly linked list, each of which is doubly linked list. it is used to store data in a way
that allows for fast insertion and deletion of element.
There are 2 parts which are called head and tail.

Representation
HEAD NEXT NEXT NEXT NEXT

A B C D
NULL PREV PREV PREV NULL

The Representation can be determined by the following:

 Pointer to the previous node/back field.

 Information field.
 Pointer to the next field/forward field.
 BACK is a pointer which points the previous node in the list.
 Forward is a pointer which points the next node of the list.
 Information failed contains the data or information.

Advantages :
 Doubly linked list can be traversed forward or backward direction.
  Doubly linked list is used to represent that trees effectively.
 This simplify the management

4) Header linked list: Header linked list is a linked list in which always information contains a
special node called the header node at the beginning of the list. The information field of
such header node generally contains the Global information of the entire list.
There are 2 kinds of header linked list
 Grounded header linked list
 Circular header linked list
- Grounded header linked list : It is referred as singly header linked list where the
last node LINK field contains the NULL point. The first node is the header node and
START is pointing to the header node. The information field of the header contains
the number of nodes in the linked list. The information of the header load contains
the address of the last node.

START

NULL

START
2002

03 10 20 30 NULL
2002 2010 2050 2020

START
2002

2020 10 20 30 NULL
2002 2010 2050 2020

Header node

Circular header linked list: A linked list in which the last node points the header node is
called circular header linked list.

Head is the pointer which contains the address of the header node and last is the
pointer which contains address of the last node.

Head last
 2002 2004 2006 2008
10 20 30 40

b) Tower of Hanoi :

Tower of an Hanoi problem is a game where a disk is to be moved from one source
pillar to destination pillar using a temporary pillar.so, there will be a total of three pillars and
the disks. consider ‘S’ and ‘D’ are the source and destination pillars and ‘T’ be the temporary
pillar. And ‘n’ be the number of disks. Before solving this problem, we have to follow to
conditions that are to be checked for each moment. they are :

- Only one disk can be moved, at one time, from one pillar to another.
- A large disk cannot be placed on a smaller disk.
- Only the top disc on any pillar may be moved to any other pillar.
So if n=1, i.e., number of disks is ‘1’.
Algorithm for tower of Hanoi :
def tower_of_hanoi (n,source,target,auxiliary)
Parameters:
- n: Number of disks
- source: Source rod
- target: Target rod
- auxiliary: Auxiliary rod
Step 1: if n > 0:
Step 2: (Move n-1 disks from source to auxiliary rod)
tower_of_hanoi(n-1, source, auxiliary, target)
Step 3: (Move the nth disk from source to target rod)
print(f"Move disk {n} from {source} to {target}")
Step 4: (Move the n-1 disks from auxiliary to target rod)
tower_of_hanoi(n-1, auxiliary, target, source)
15. a) Explain underflow and overflow with respect to queues. (3)
b) Convert the following infix notation expression to postfix notation. (5)
Q=A+B*C+(D*E+F)*G (this expression is not from the model paper )
a) Queue overflow:
- Definition: Queue overflow occurs when you try to enqueue and element into a queue that is
already full meaning it has reached its maximum capacity.
-Scenario: if the capacity of the queue is, for example, 5 elements, and you try to enqueue a 6th
element when the queue is already full, a queue overflow condition is encountered.
-implications: overflow conditions need to be handled to prevent data loss or corruption. you
may choose to reject the enqueue operation, resize the queue, or implement a more Complex
data structure that dynamically adjust its sizes.
Queue underflow:

- Definition: Queue underflow occurs when you try to dequeue and element from an element
from an empty queue, meaning there are no elements to dequeue.

-Scenario: if you attempt to dequeue an element from an empty queue (one that has no
elements), a queue underflow condition is encountered.

- Implications: attempting to dequeue from an empty queue might result in undefined behavior
or errors. It is essential to check whether the queue is empty before attempting to dequeue an
element.

b) let us start the process with an empty stack. First, as per step 1,PUSH the left
parenthesis”(“on to the stack and right parenthesis”)” at the end of Q.

i.e., Q=A+B*C+(D*E*F)*G)

as per step 2,scan the expression from left to right. here, the operands ‘A’ is encountered first.
So add it to ‘P’

A
P

Now, the operator + is encountered. So according to step 5, as no operators are there on the top
of the stack, '+' is just pushed on to the stack.

A
+ P

Now, the operand B is encountered. So it is directly added to ‘P' and then the operator '*' is
encountered. As the top of the stack ' +’ is not of equal precedence or higher precedence than
the encountered operator '*', no popping is done and '*' is pushed on to the stack.
 AB
P
*

Now, the operand 'C' is directly added to P (step 3) and then the operator '+' is encountered. So
according to step 5, the top of the stack '*' is of higher precedence than the encountered
operator '+'. So ‘*’ is popped from the stack and added to the 'P'. Similarly as the * is added to
the stack, the ‘+’ operator which is now the top of the stack is of same precedence to the
encountered operator '+'.

ABC*+
p
+
(

So this operator '+' is also popped from the stack and added to P. And finally, the encountered
operator '+' is pushed to the stack. Now left parenthesis "(" is encountered. So push it on to the
stack (according to step 4). Then the operand 'D' is directly added to 'P'.

ABC*+D
P
(

+
(

Next, the operator* is encountered. As the top of the stack"("can be popped / removed only
when")" parenthesis is encountered (step 4). Therefore* is pushed on to the stack. Then the
operand "E" is directly added to P.

ABC*+DE*
+ P

(
+
(
Then, the operator '+' is encountered. The top of the stack '*' is of higher precedence than the
encountered operator '+'. So '*' is popped from the stack and added to P. And the encountered
operator '+' is pushed on to the stack (Step 5)

ABC*+DE*
* P

(
+
(

Now, the operand ‘F' is directly added to P. Then the right parenthesis “)” is encountered. So
according to step 6, popping is to done from the stack until the left parenthesis is encountered
and is added to 'P'. So, here '+' is popped and added to 'P'. Also, the left parenthesis "(" is then
removed from the stack and is not added to "P".

ABC*+DE*F+
P
+
(

STACK

Then, the operator '*' is encountered. As the TOP of the stack'+' is not of same
precedence/higher precedence to the encountered operator*, according to step 5. The
encountered operator '*' is pushed on to the stack.

ABC*+DE*F
P
*

+
(

STACK
 Now, the operand ‘G’ is directly added to P.

ABC*+DE*F+G
P
*

+
(

STACK

Finally, the right parenthesis ")" that is added according to step 1, is encountered. So according
to step 6, all the items from the stack are popped and added to 'P' one-by-one from TOP until
the left parenthesis " (“ is reached. And this left parenthesis "(" is removed from the stack and
not added to 'P'.

ABC*+DE*F+G*+

STACK

The stack now becomes empty and the final postfix expression is obtained. Stopping of scan is
done as the empty stack is obtained (step 2)

The postfix conversion of

A+B+C+(D*E+F)*G ABC*+DE*F+G*+
Is

16. Explain heap sort method for given set of elements (8m)
(Elements are not the same from modelpaper)
13 86 48 38 54 23 08 63
17. a) Define hashing. Explain hash table and hash function with an example. (6m)
b) List any two probing methods. (2m)

a) Hashing is the process of mapping keys to their appropriate locations in the Hash table. It is the most

Hashing in a data structure is a two-step process.

1. The hash function converts the item into a small integer or hash value. This integer is used as
an index to store the original data.

2. It stores the data in a hash table. We can use a hash key to locate data quickly.

Hash table:

Hash Table is a data structure which stores data in an associative manner. In a hash table, data
is stored in an array format, where each data value has its own unique index value. Access of
data becomes very fast if we know the index of the desired data.

index value
0 value_1
1 value_2
2 value_3
3 value_4

We know that the main principle of hashing is 'conversion of the key in to the array index'. The
function of converting the key into the table/array index is called Hash function. It is usually
denoted by 'H’ . A hash function is a mathematical formula which, when applied to a key,
produces an integer which can be used as an index for the key in the hash table.

Example :Let us understand hashing in a data structure with an key value pair. Imagine we need
to store some items (arranged in a key-value pair) inside a hash table with 30 cells.

The values are: (3,22) (1,65) (40,89) (5,36) (11,55) (15,29) (18,1) (16,75) (38,50)

Let the hash function be h(k) = k mod 30

key hash Array index value

3 3%30=3 3 22
1 1%30= 1 1 65
40 40%30=10 10 89
5 5%30=5 5 36
11 11%30=11 11 55
15 15%30=15 15 29
18 18%30=18 18 1
16 16%30=16 16 75
38 38%30=8 8 50

b) The two probing methods are

Linear probing : This hashing technique find the hash key (or) generated address value through
Hash Function and maps the key on particular position in the Hash table. In case if the key has
same hash address then it will find the next empty position in the Hash table.
 Quadratic probing: Linear probing has the disadvantage of clustering. In order to minimize the
clustering problem, quadratic probing can be used. Suppose hash generating address is ‘a’ then
in the case of Collision linear problems the location a,a+1,a+2….. so the location where the
insertion and searching takes place is(a+i)(for i=0,1,2…..)but in quadratic probing, the location
of insertion and search takes place in(a+i2)(for=0,1,2…).

18. Construct binary tree. Given inorder and postorder traversals. (8m)
Inorder: 6 + 2 5 * 8 – 9 4 1 2 10 6
Post order: 6 2 5 + 8 9 1 4 10 2 - * (given order are same from the modelpaper)

Inorder: 6 + 2 5 * 8 – 9 4 1 2 10 6

Postorder: : 6 2 5 + 8 9 1 4 10 2 - *