DS SUMMER 2020 SOLUTION

Q1 (A) Difference between data types & data structures (3M)

ANS
Data Types Data Structures
Data type is a kind of variable or Data structure is the collection of
form of a variable which is being different kind of data. The entire
used throughout the program. It data can be represented using an
defines that the particular variable object and can be used throughout
will assign the values of the given the entire program
data type only
Implementation through data Implementation through data

z
types is a form of abstract structures is called concrete
implementation
Can hold values and not data so it
aa
implementation
Can hold a different kind and types
Aw
is data less of data within one single project
Values can directly be assigned to The data is assigned to the data
data type variables structure object using some set of
ut

algorithms and operations like

push pop and so on
gr

No problem of time complexity Time complexity comes into play

Ja

when working with data structure

Ex : int, float, double Ex : stacks, queue etc

Q1 (B) Answer the followings

a) Give examples of Linear and Non-Linear Data Structures.
b) What do you mean by Abstract Data Types? (4M)

ANS
a) Give examples of Linear & Non – Linear Data Structures
 Linear Data Structure : Stack & Queue
 Non Linear Data Structure : Tree & Graph

b) What do you mean by Abstract Data Types?

Click :Youtube Channel | Free Material | Download App

 The concept of abstraction is commonly found in computer
science. A big problem is never written as a monolithic piece of
program instead it is broken down in smaller modules(may be
called a function or procedure) and each module is developed
independently

When the programme is hierarchical organised as shown in

figure 1.3 then the main program utilises services at the
functions appearing at level 1. Similarly, functions return at
level 1 utilizes services of functions written at level 2. Main
program uses the services of the next level function without
knowing their implementation details. Thus a level of
abstraction is created. When an abstraction is created at any
level, are concern is limited to what it can do and not how it is
done

z
aa
Aw
ut
gr
Ja

Abstraction in case of data

Abstraction for primitive data types is provided by the compiler.
For example we use integer type data and also perform various
operations on them without knowing them
1) Representation
2) How various operations are performed on them

Example : int x, y, z ;
x = 13;
constant 13 is converted to 2’s complement & then stored in X.
Representation is handled by the complier
X=Y+Z

Click :Youtube Channel | Free Material | Download App

 Meaning of the operation ‘+’ is defined by the compiler and its
implementation details remain hidden from the user

Implementation details(representation) and how various

operations are implemented remain hidden from user. User is
only concerned about how to use these equations

Q1 (C) Discuss and write program to implement queue functions using

arrays (7M)

ANS

/* C program to implement a Queue using an array */

#include <stdio.h>
#include <stdlib.h>

z
#define MAX 50 aa
void insert( );
Aw

void delete( ) ;
void display( ) ;
int queue_array[MAX];
ut

int rear = - 1;
gr

int front = - 1;
main( )
Ja

{
int choice;
while(i)
{
printf(“1.Insert element to queue\n”);
printf(“2.Delete element to queue \n”);
printf(“3. Display all elements of queue\n”);
printf(“4. Quit \n”);
printf(“Enter your choice :”);
scanf(“%d”, &choice);
switch(choice)
{
case 1 :
insert( );

Click :Youtube Channel | Free Material | Download App

 break ;
case 2 :
delete( );
break ;
case 3 :
display( );
break ;
case 4 :
exit(1);
default;
printf(“Wrong choice \n”);
}
}
}
void insert( )

z
{ aa
int add_item
if(rear = = MAX – 1)
Aw

printf(“Queue Overflow \n”);

else
{
ut

if(front = = -1)
gr

/* If queue is initially empty*/

front = 0;
Ja

printf(“Insert the element in queue :”);

scanf(“T.D”, &add_item);
rear = rear + 1 ;
queue_array[rear] = add_item;
}
}
void delete( )
{
if(front = = - 1 ||front > rear)
{
printf(“Queue underflow \n”);
return ;
}
else

Click :Youtube Channel | Free Material | Download App

 {
printf(“Element deleted from queue is %d \n”, queue_array[front])
front = front + 1;
}
}
void display( )
{
int( );
if (front = - 1)
printf(“Queue is empty \n”);
else
{
printf(“Queue is : \n”);
for (i = front; i < = rear; i ++)
printf(“%d”, queue_array[i]);

z
printf(“\n”); aa
}
}
Aw

Q2 (A) Difference between Stack & Queue (3M)

ut

ANS
gr

Stack Queue
Ja

A linear list which allows A linear list which allows insertion

insertion and deletion of an at one end & deletion at another
element at one end only end is called Queue
Since insertion & deletion of Since insertion & deletion of
element are performed at one element are performed at opposite
end of stack elements can only end of queue elements can be
be removed in opposite order of removed in same order of insertion
insertion
Stack is called as Last in First Out Queue is called as First in First Out
(LIFO) list (FIFO) list
The most and least accessible Insertion of element is performed at
elements are called as TOP and FRONT end & deletion of element is
BOTTOM of stack performed from REAR end

Click :Youtube Channel | Free Material | Download App

 Example of stack is arranging Example is ordinary queue in
plates in one above one provisional store
Insertion operation is referred as Insertion operation is referred as
PUSH and deletion operation is ENQUEUE and deletion operation is
referred as POP referred as DEQUEUE
Function calling in any languages Task Scheduling by operating system
uses Stack uses Queue

Q2 (B)What is top of stack? Why stack is called LIFO list? (4M)

ANS

 Stack : top ( ) function is an inbuilt function in C++ STL, which is

defined in <stack>. header.file top( ) is used to access element at top
of stack container. In stack, top element is element that is inserted at

z
last or most recently inserted element
Syntax : stack_name.top( );
aa
 Stack is basic data structure where insertion & deletion of data takes
Aw

place at one end called top of stack. It follow LIFO (Last In First Out)
principle where element can be added or removed from top end of
ut

stack
gr

Q2 (C) What is circular queue? How do you check queue full condition?
Ja

Write an algorithm to count nodes in circular queue? (7M)

ANS
Circular Queue
 A more suitable method of representing excessive use of memory is
to average elements Q[1], Q[2] …. Q[n] in circular fashion with Q[I]
following Q[n] this is called Circular Queue
 In standard queue data structure re – buffering problem occurs for
each dequeue operation. To solve this problem by joining front and
rear ends of queue to make queue as circular queue
 Circular queue is linear data structure. It follows FIFO principle
 In circular queue last node is connected back to first node to make
queue

Click :Youtube Channel | Free Material | Download App

  Circular linked list follow First in First Out principle (FIFO)
 Elements are added at rear end & elements are deleted at front end
of queue
 Both front & rear pointer points to beginning of array
 It is also called as ‘Ring Buffer’

z
To check whether queue is FULL
aa
Check ((rear = = SIZE – 1 && front = 0) ||(rear = = front – 1))
If it is full then display Queue is full. If queue is not full then check if
Aw
(rear = = SIZE – 1 && front! = 0). If it is true then set rear = 0 & insert
element
ut

Algorithm to count nodes in circular queue

gr

void count_node(node * head)

Ja

{
node * temp = head;
int count = 0;
if (temp = = NULL)
count < < “List is Empty”;
do
{
count ++;
temp = temp → next;
}
while(temp ! = head)
count << “The total number of nodes” << count;
}

Click :Youtube Channel | Free Material | Download App

OR
Q2(C) Explain creation, insertion & deletion of doubly linked list with
example (7M)

ANS

Creation of doubly linked list :

A double linked list is complex version of singly linked list where each node
contains a pointer to its previous node as well as next node. Each node in
doubly linked list has three parts : the first part points to previous node,
middle part contains data & last part points to next node

z
aa
Aw
ut

Insertion in doubly linked list

gr

1. Adding node at beginning in Doubly Linked List

Point next pointer of new node to first node & point previous pointer
Ja

of current first node to new node. Point previous of new node to

NULL. The new node is now first node of linked list

void insertAtBegin(node * new)

{
New → next = head;
head previous = new;
head = new;
}

Click :Youtube Channel | Free Material | Download App

2. Adding node at end in Doubly Linked List
To add node in last position, point next pointer of last node to new
node & point previous pointer of new node to current last node.
Point next node to null

void AddatEnd(node * new)

{
while(last → next ! = NULL)
last = last → next;

z
last → next = new;
new → previous = last;
new → next = NULL;
aa
Aw
}

3. Adding node at specific position in Doubly Linked List

ut

If you want to add node at nth position, point next pointer of new
node to (n + 1) node & point to previous pointer of new node to (n -
gr

1) node . After that, point next of (n – 1)th node & previous of (n +

Ja

1)th node of new node

void AddAtPosition(node * new, node * prev)

{
new → new = prev → next;
new → previous = prev;
(previous → next) → previous = new;
prev → next = new;
}

Click :Youtube Channel | Free Material | Download App

Deletion in Doubly Linked List
1. Delete node at beginning of Doubly Linked List
Point next pointer of first node & previous pointer of second node to
null

void DeleteAtFirst( )
{
Node * temp = *head;
head = temp → next ;
head → previous = NULL;

z
free(temp);
}
aa
Aw
2. Delete node at end of Doubly Linked List
Point next pointer of second last node & previous pointer of last node
to null
ut
gr
Ja

void DeleteAtLast( )
{
Node * ptr, *ptr1;
ptr = head;
while (ptr → next ! = NULL)
{
ptr1 = ptr;
ptr = ptr → next;
}
ptr1 → next = NULL;
free ptr;
}

Click :Youtube Channel | Free Material | Download App

 3. Delete node at any position in Doubly Linked List
If you want to delete node at nth position, point next of (n – 1)th to
(n + 1)th node & point to previous of (n + 1)th node to (n – 1)th node.
Point previous & next of nth node to null

void DeleteAtPosition(int, pos)

z
{
struct node *ptr, *ptr1;
ptr = head;
aa
Aw
for(i = 0; i < pos; i ++)
{
ptr1 = ptr;
ut

ptr = ptr → next;

}
gr

ptr1 → next = ptr → next;

Ja

ptr1 → next → previous = ptr1;

free(ptr);
}

Q3(A) What are binary trees? Mention different types of binary trees with
example (3M)
ANS

 A binary tree is a tree – type non linear data structure with maximum
of two children for each parent.
 Every node in binary tree has a left & right reference along with data
element
 The node at top of hierarchy of tree is called Root Node
 The nodes that hold other sub – nodes are parent nodes

Click :Youtube Channel | Free Material | Download App

  A parent node has two child nodes : left child & right child
 Hashing routing data for network traffic, data compression, preparing
binary heaps & binary search trees are some of applications that use
a binary tree

z
aa
Types of Binary Tree
Aw
There are various types of binary trees & each of these binary tree
types has unique characteristics. Here are each of binary tree types in
detail
ut
gr

1. Full Binary Tree

 It is special kind of binary tree that has either zero children or
Ja

two children. It means that all nodes in that binary tree should
either have two child nodes of its parent node or parent node is
itself leaf node or external node
 In other words, a full binary tree is unique binary tree where
every node expect external node has two children. When it
holds single child, such binary tree will not be full binary tree.
Here quantity of leaf nodes is equal to number of internal
nodes plus one. Equation : L = l + 1, where L is number of leaf
node and l is number of internal nodes

Click :Youtube Channel | Free Material | Download App

2. Complete Binary Tree
 A complete binary tree is another specific type of binary tree
where all tree levels are filled entirely with nodes except lowest
level of tree. Also in last or lowest level of this binary tree, every
node should possibly reside on left side. Here is structure of
complete binary tree :

3. Perfect Binary Tree

 A binary tree is said to be ‘perfect’ if all internal nodes have

z
strictly two children & every external or leaf node is at same
aa
level or same depth within tree. A perfect binary tree having
height ‘h’ has 2h – 1 node. Here is structure of perfect binary
Aw

tree
ut
gr
Ja

4. Balanced Binary Tree

 A binary tree is said to be balanced if tree height is O(logN)
where N is number of nodes. In balanced binary tree height of
left & right subtrees of each node should vary by most one. An
AVL Tree & Red – Black Tree are some common examples of
data structure that can generate balance binary search tree

Click :Youtube Channel | Free Material | Download App

 5. Degenerate Binary Tree
 A binary tree is said to be degenerate binary tree pathological
binary tree or pathological binary tree if every internal node has
only one single child. Such tree are similar to linked list
performance

z
aa
Aw
ut

Q3(B) What is graph? Explain various representation of graphs (4M)

gr

ANS
Ja

Graph
 Graph is data structure that consists of following two components
1. A finite set of vertices also called as Nodes
2. A finite set of ordered pair of form(u, v) called as edge. The pair
is ordered because (u, v) is not same as (v, u) in case of a
graph(di – graph). The pair of form (u, v) indicates that there is
edge from vertex u to vertex v. The edges may contain weight/
value

 Graphs are used to represent many – real life applications : Graphs are
used to represent networks. The networks may include paths in a city
or telephone network or circuit network. Graphs are also used in social
networks like LinkedIn, Facebook. For eg : in Facebook, each person is

Click :Youtube Channel | Free Material | Download App

 represented with vertex (or node). Each node is structure & contains
information like person id, name, gender & locate

 EG : Undirected graph with 5 vertices

Representation of Graphs
 The following two are most commonly used representations of graph
1. Adjacency Matrix
2. Adjacency List

z
There are other representations also like Incidence Matrix &
aa
Incidence List. The choice of graph representation is situation –
specific. It totally depends on type of operations to be performed and
Aw

ease of use
 Adjacency Matrix
ut

Adjacency Matrix is 2 – D array of size V × V where V is number of

vertices in graph. Let 2D array be adj [ ] [ ], a slot adj [i] [j] = 1
gr

indicates that there is an edge from vertex i to vertex j . Adjacency

Ja

Matrix for undirected graph is always symmetric . Adjacency Matrix is

also used to represent weighted graphs.If adj [i] [j] = W, then there is
an edge from vertex i to vertex j with weight W

Adjacency Matrix for above example graph is

Pros : Representation is easier to implement & follow. Removing an

edge takes O(1) time. Queries like whether there is an edge from
‘vertex u’ to ‘vertex v’ are efficient & can be done O(1)

Click :Youtube Channel | Free Material | Download App

 Cons : Consumes more space O(V2). Even if graph is sparse contains
less number of edges it consumes same space. Adding a vertex is
O(V2) time

 Adjacency List
An array of lists is used. The size of array is equal to number of
vertices. Let array be an array[ ]. An entry array [i] represents list of
vertices adjacent to ith vertex. This representation can also be used to
represent weighted graph. The weights of edges can be represented
as lists of pairs. Following is adjacency list representation of above
graph

z
aa
Aw
ut
gr

Q3(C) Write an algorithm to add node in binary search tree (7M)

Ja

ANS

Algorithm
1) Create new binary search tree node & assign values to it
2) Insert (node, key)
i) If root = NULL
return the new node to calling function
ii) if root → data < key

Click :Youtube Channel | Free Material | Download App

 call insert function with root → right & assign return value in
root → right
root → right = insert(root → right, key)
iii)if root → data > key
call insert function with root → left & assign return value in
root → left
root → left = insert(root → left, key)
3) Finally, return original root pointer to calling function

OR
Q3(A) What is B – Tree of order m? Draw a B – tree of order 3 (3M)

ANS
 B – Tree or Multiway Search Tree is M – way tree which can have
maximum of M children

z
 M – way tree contains multiple keys in node
aa
 This leads to reduction in overall height of tree
 If node of M – way tree holds k keys then it will have k + 1 children
Aw

 Following properties
 Root can have 1 to M – 1 keys
ut

 All nodes (except Root) have (M – 1)/2 to (M – 1) keys

 All leaves are at same level
gr

 If a node has ‘t’ number of children then it must have ‘t – 1’

Ja

keys
 Keys of nodes are stored in ascending order

 3 – way search tree

Click :Youtube Channel | Free Material | Download App

OR
Q3(B) Construct binary tree having following traversal sequences :
Preorder Traversal : ABCDEFGHI
Postorder Traversal : BCAEDGHFI (7M)

ANS

z
aa
Aw
ut
gr
Ja

Click :Youtube Channel | Free Material | Download App

OR
Q3(C) Discuss algorithm of Breadth First Search (BFS) traversal for graph.
Explain with example (7M)

ANS

 This method starts from vertex V0

 V0 is marked as visited. All vertices adjacent to V0 are V1, V2, V3
 V1, V2, V3 are marked visited
 All unvisited vertices adjacent to V1, V2, V3 are visited next
 The method continuous until all vertices are visited
 Algorithm for BFS has to maintain list of vertices which have been
visited but not explored for adjacent vertices. The vertices which
have not been visited but not explored for adjacent vertices can be

z
stored in queue
 Initially queue contains starting vertex aa
 In every iteration a vertex is removed from queue & its adjacent
Aw
vertices which are not visited as yet are added to queue
 Algorithm terminates when queue becomes empty
ut
gr
Ja

Procedure : BFS(Vertex ‘V’)

This procedure traverse graph G in BFS manner. V is starting vertex to be
explored. Q is queue, visited [ ] is array which tells you whether particular
vertex is visited or not. W is adjacent node of vertex v
1. Initialize Q
2. [Marks visited of V as 1]
Visited[V] ← 1
3. [Add vertex V to Q]
Insert Queue(V)
4. [Repeat while Q is not empty]
Repeat while Q is not empty

Click :Youtube Channel | Free Material | Download App

 V ← RemoveFromQueue( )
for all vertices W adjacent to V
if visited[W] is 0
then visited [W] ← 1
InsertQueue(W)

Q4(A) Explain Sequential File Organization & list its advantages &
disadvantages (3M)

ANS
 It is the most common type of file
 A fixed format is used for record
 All records are of the same length
 Position of each file in record and length of field is fixed

z
 aa
Records are physically ordered on the value of one of the fields called
ordering field
Aw
ut
gr
Ja

Some blocks of an ordered(sequential) file of students records with

Roll. No as ordering field

 Advantages of Sequential File over Unordered File

 Reading of records in order of the ordering key is extremely
efficient
 Finding the next record in order of the ordering key usually
doesn’t require additional block access. Next record may be
found in the same block
 Searching operation on ordering key is must faster. Binary
search can be utilised. A Binary search will require log2b block
address where b is total number of blocks in file

Click :Youtube Channel | Free Material | Download App

  Disadvantages of Sequential File over Unordered File
 Sequential file does not give any advantage when searching
operation is to be carried out on non – ordering field
 Inserting a record is an expensive operation. Insertion of a new
record requires finding of place of insertion and then all records
are ahead of it must be moved to create space for record to be
inserted. This could be very expensive for large fields
 Deleting a record is an expensive operation. Deletion too
requires movement of records
 Modification of field value of ordering key could be time
consuming. Modifying the ordering field means the record can
change its position. This requires deletion of the old record
followed by the insertion of modified record

z
Q4(B) How access of record is performed in Multi – Key File Organization
(4M) aa
ANS
Aw

Multikey File Organization

 When a file records are made accessed based on more than one key
ut

are called Multikey File Organization. This file organization is needed

gr

many times. EG : in banking system we keep records of accounts in

file. Now account holder needs account information which can be
Ja

access through account no, while loan officer needs account records
with the given value of overdue limit. So we need to provide to
access path to record based on different need. Generally these files
are index sequential file in which file is stored sequentially based on
primary key & more than one index table are provided based on
different keys. Basically there are 2 approaches for implementing
multi key organization
1. Inverted File Organization
 In this file organization keys inversion index contains all of the
values that the key presently has in records of data file. Each
key – value entry in inversion index points to all of the data
records that have corresponding value. The data file is said to
be inverted on that key. Inverted files are sorted on inversion
index so that binary search can be applied to find out index of

Click :Youtube Channel | Free Material | Download App

 record. Whenever records is added in data file its corresponding
entry has to be made in inverted file
2. Multi List File Organization
 In this file organization the index contains all values that
secondary key has in data file same as inverted file but
difference is that entry in multi index for secondary key value
pointer to first record with that key value. That data record
contains pointer to second record having same key. Thus there
is linked list of data records for each value of secondary key.
Multi list chains usually are bidirectional & occasionally are
circular to improve update operation
Sequential Data File Sorted on primary key A/C No

z
aa
Aw
Inverted Index File for secondary key A/C value
ut
gr

Multi List File for secondary key A/C value

Ja

Click :Youtube Channel | Free Material | Download App

Q4(C) Describe various collision resolution techniques in Hashing (7M)

ANS
Collision Resolution Technique
 When one or more hash values, compete with single hash table slots,
collisions occur. To resolve this, next available empty slot is assigned
to current hash value. The most common methods are open
addressing chaining, probabilistic hashing, perfect hashing &
coalesced hashing technique

Chaining
 This technique implements linked list & is most popular collision
resolution techniques. Below is an example of chaining process

z
aa
Aw
ut
gr

Here, since one slot has 3 elements {50, 85, 92}, a linked list is
assigned to include other 2 items {85, 92}. When you use chaining
Ja

technique, inserting or deleting of items with hash table is fairly

simple & high performing. Likewise a chain hash table inherits pros &
cons of linked list. Alternatively, chaining can use dynamic arrays
instead of linked list

Open Addressing
 This technique depends on space usage and can be done with Linear
or Quadratic probing techniques. As name says, their technique tries
to find on available slot to store record. It can be done in 3 ways
1) Linear Probing : Here, next probe interval is fixed to 1. It supports
best caching but miserably fails at clustering
2) Quadratic Probing : The probe distance is calculated based on
quadratic equation. This is considerably better option as it balances
clustering & caching

Click :Youtube Channel | Free Material | Download App

 3) Double Hashing : Here the probing interval is fixed for each record
by second hashing function. This technique has poor cache
performance though it does not have clustering issues

Below are some of hashing techniques that can help in resolving

collision
Probabilistic Hashing
 This is memory based hashing that implements caching. When
collision occurs either old record is replaced by new or new record
may be dropped. At though this scenario has risk of losing data it is
still preferred due to its case implementation and high performance
Perfect Hashing
 When slots are uniquely mapped, there is very less chances of
collision. However, it can be done where there is lot of space memory
Coalesced Hashing

z
 This technique is a combo of open addressing & chaining methods. A
aa
chain of items are stored in table when there is collision. The next
Aw
available items to prevent collision
ut

OR
Q4(A) Explain indexed sequential file structure (3M)
gr
Ja

ANS

Indexed Sequential File Structure

 An indexed sequential file consists of records that can be accessed
sequential. Direct access is also possible. It consists of 2 parts :
1) Data File : Contains records in sequential scheme
2) Index File : Contains primary key & its in address in data file
 Following are key attributes of sequential file organization
 Records can be read in sequential order just like in sequential
file organization
 Records can be accessed randomly if primary key is known.
Indexed file is used to get address of record & then record is
fetched from data file
 Sorted index is maintained in this file system which relates key
value to position of reward in file

Click :Youtube Channel | Free Material | Download App

  Alternate index can also be created to fetch records
 Syntax
INPUT – OUTPUT SECTION
FILE CONTROL
SELECT file_name ASSIGN TO dd-name-jcl
ORGANIZATION IS INDEXED
RECORD KEY IS primary_key
ALTERNATE RECORD KEY IS rec_key
OR
Q4(B) Explain minimum spanning tree (4M)

ANS
Minimum Spanning Tree
 A minimum spanning tree is special kind of tree that minimizes

z
lengths or weights of edges of tree. An example is cable company
aa
wanting to lay line to multiple neighbourhoods by minimizing amount
of cable laid, cable company will save money
Aw

 A tree has one path joins any two vertices

 A spanning tree of graph in tree that :
 Contains all original graphs vertices
ut

 Reaches out to (spans) all vertices

gr

 Is acyclic. In other words, graph doesn’t have any nodes which

loop to itself
Ja

 A few popular algorithm for finding minimum distance include :

Kruskal’s Algorithm, Prim’s Algorithm & Boruvka’s algorithm

Click :Youtube Channel | Free Material | Download App

 Kruskal’s Algorithm
1) Find the edge with least weight and highlight it. For this example
graph II ve highlighted top edge (from A to C) in red it has lowest
weight(of 1)

Find next edge with lowest weight & highlight it

z
aa
Continue selecting lowest edges until all nodes in same tree
2) Be careful not to complete cycle(route one node back to itself). If
Aw

your choice completes a cycle, discard your choice move onto next
largest weight
ut
gr
Ja

OR
Q4(C) What is Hashing? What are qualities of good hash function? Explain
any two hash functions in short (7M)

ANS

Hashing
 A function that converts a given big phone number to small practical
integer value. The mapped integer value is used as an index in hash
table. In simple terms, hash function maps big number or string to
small integer that can be used as index in hash table

Click :Youtube Channel | Free Material | Download App

Characteristics of good hash function
1) Efficiently computable
2) Should uniformly distribute keys (Each table position equally likely
for each key)

Hash Function
 The two heuristic methods are Hashing by Division & Hashing by
Multiplication
1) Hashing by Division (The mod method) :
 In this method for creating hash functions table by taking
remainder of key divided by table – size. That is, hash function is
h(key) = key mod table_size
i.e key % table = size
 Since, it requires only single decision operation, hashing by
division is quite fast

z
 When using division method, we usually avoid certain values of
aa
table size should not be power of number. Suppose r since if
table_size = r ^ p, then h(key) is just p lowest order bits of key.
Aw

Unless we know that all low – order p bit patterns are equally
likely, we are better off designing hash functions to depend on
all bits of key
ut

 It has been found that best results with division method are
gr

achieved when table size is prime. However even if table_size is

prime, an additional restriction is called for. If r is number of
Ja

possible character codes on computer & if table size is prime

such that r % table size = 1 then hash function h(key) = key %
table size is simply sum of binary representation of characters in
key mod table size
 Example :
Suppose r = 256 and table_size = 17 in which r % table_size i.e
256 % 17 = 1
So for key = 37599, its hash is 37599 % 17 = 12
But for key = 573, its hash function is also 573 % 17 = 12
Hence it can be seen that by this hash function many keys can
have same hash called collision
A prime not too close to an extent power of 2 is often good
choice for table_size

Click :Youtube Channel | Free Material | Download App

2) The Multiplication Method
 In multiplication method we multiply key k by c constant real
number C in range 0 < C < 1 & extract fractional part of k * c
 Then we multiply this value by table_size n & take floor of
result. It can be represented as
h(k) = floor(m * (k * c mod 1))
OR
h(k) = floor(m * frac(k * c))
where function floor(x) available in standard library math. h
yields integer part of real number X and frac(X) yields fractional
part [frac(X) = X = floor(X)]
 An advantage of multiplication method is that value of m is not
defined we typically choose it to be power of 2(m = 2 for some
integer p), Since we can then easily implement function on
most computers

z
 Suppose that word size of machine is W bits & that key fits into
aa
single word
 We restrict c to be function of form : S/(2w), where S is integer
Aw

in range 0 < S < 2w

 Referring to figure we first multiply key w – bit integer S = C *
2w, result is a 2w – bit
ut

r1 * 2w+r0
gr

where r1 = high – order word of product

r0 = lower – order word of product
Ja

 Although this method works with any value of constant c, it

works better with some values than others
C ~ (sqrt(5) – 1)/2 = 0.618033988… is likely to work reasonably
well
Suppose, k = 123456, p = 14, m = 214 = 16384 and w = 32
Adapting Knuth’s suggestion c to be function to be form s/232
Then key *s = 32770602297664 = (76300 * 232) + 17612864
So r1 = 76300 and r0 = 17612864
 Then 14 most significant bits of two yield value h(key) = 67

Click :Youtube Channel | Free Material | Download App

Q5(A) Define Topological Sort 3M)

ANS
Topological Sort
 Topological Sorting for Directed Acyclic Graph (DAG) is linear ordering
of vertices such that for every directed edge u, v vertex u comes
before v in ordering. Topological Sorting for graph is not possible if
graph is not DAG
 For example a topological sorting of following graph is “5 42310”.
There can be more than one topological sorting for graph. For
example, another topological sorting of following graph is “4 5 2 3 1
0”.The first vertex in topological sorting is always vertex with in
degree as 0 (a vertex with no incoming edges)

z
aa
Aw
ut

Time complexity : O(V + E)

gr

Auxiliary space : O(V)

 Applications
Ja

 Mainly used for scheduling jobs from given dependencies

among jobs
 In computer science, applications are of this type ordering of
formula cell
 Logic synthesis, data resolution and resolving symbolic
dependencies in linkers

Click :Youtube Channel | Free Material | Download App

Q5(B) Compare sequential searching with binary searching in detail (4M)

ANS

Sequential Search Binary Search

Time Complexity is O(n) Time Complexity is O(logn)
Finds key present at first position Finds key present at center
in constant time position in constant time
Sequence of elements in container Elements must be sorted in
does not affect container
Arrays & Linked Lists can be used It cannot be implemented
to implement this directly into linked list. We
need to change basic roles of
list to implement this
Algorithm is iterative in nature Algorithm technique is Divide

z
Algorithm is easy to implement &
aa
& Conquer
Algorithm is slightly complex.
Aw
requires less amount of code It takes more amount of code
to implement
N number of comparison are log n number of comparison
ut

required for worst case are sufficient in worst case

gr

Q5(C) Examine algorithm for Insertion Sort & sort following array :
Ja

77, 33, 44, 11, 88, 22, 66, 55 (7M)

ANS

Algorithm for Insertion Sort

1) If element is first element, assume that it is already sorted.
Return 1
2) Pick next element & store it separately in key
3) Now compare key with all elements in sorted array
4) If element in sorted array is smaller than current element, then
move to next element. Else, shift greater elements in array
towards right
5) Insert value
6) Repeat until array is sorted

Click :Youtube Channel | Free Material | Download App

 Insertion :

z
aa
Aw
Therefore 11, 22, 33, 44, 55, 66, 77, 88 is sorted
OR Q5(A) What do you mean by internal & external sorting (3M)
ut

ANS
Internal Sorting
gr

 Internal Sorting are type of sorting which is used when entire

Ja

collection of data is small enough that sorting can take place within
main memory. There is no need for external memory for execution of
sorting program
 It is used when size of input is small
 Example : Bubble Sort, Insertion Sort, Quick Sort, Heap Sort

External Sorting
 External Sorting refers to sorting algorithms that are suitable for large
files of records stored on disk that do not fit entirely in main memory
such as most database files
 Also called External Merge Sort Algorithm which is k – way merge
algorithm. It sorts chunks that each fit in RAM, then merges sorted
chunks together. Algorithm first sorts M items at time & puts sorted
list back into internal memory

Click :Youtube Channel | Free Material | Download App

OR Q5(B) Write an algorithm for Quick Sort (4M)
ANS
Algorithm : Quick (A [0…. n – 1], low, high)
/* Problem Description : This algorithm performs sorting of elements
given in Array [0…. n – 1]
Input : An array A[0… n – 1] in which unsorted elements are given. The low
indicates leftmost element in list
Output : Creates subarray which is sorted in ascending order */
if (low < high) then
//split array into two sub arrays
m ← partition (A [low… high])
//m is mid of array
Quick(A[low …. m – 1])
Quick (A[mid + 1 ……… high])

z
Algorithm : Partition (A [low … high])
aa
/* Problem Description : This algorithm partition subarray using first
Aw

element as pivot element

Input : A subarray A with low as left most index of array & high as
rightmost index of array
ut

Output : The partitioning of array A is done & pivot occupies its proper
gr

position and rightmost index of list is returned */

pivot ← A [low]
Ja

i ← low
j ← high + 1
while(i < = j) do
{
while(A[i] < = pivot) do
i←i+1
while(A[j] > = pivot) do
j←j+1
if(i < = j) then
swap(A[i] , A[j])
}
swap(A[low], A[j])
//when i crosses j swap A[low] and A[j] return j
// rightmost index of list

Click :Youtube Channel | Free Material | Download App

OR Q5(C) What is Binary Search Tree? Construct a BST for
following elements : 21, 16, 24, 18, 22, 25, 26, 27, 29, 33 (7M)

ANS

Binary Search Tree

 A binary search tree follows same order to arrange elements. In a
binary search tree, value of left node must be smaller than parent
node & value of right node must is greater than parent node. This
role is applied recursively to left & right subtree of root

z
aa
 In above figure, we can observe that root node is 40 & all nodes of
Aw
left subtree are smaller than root node & all nodes of right subtree
are greater than root node
 Similarly, we can see left child of node is greater than its left child &
ut

smaller than its right child. So also satisfies property of binary search
gr

tree. Therefore we can say tree in above is binary search tree

 Suppose, if we change 35 to 55 then we see than node 30 than on
Ja

left side. 25 is smaller than it. So satisfy but 55 on right side it does
not satisfy property of binary search tree

 Advantages of Binary Search Tree

 Searching an element in binary search tree is easy as always
have hint that which subtree has desired element
 As compared to array & linked list insertion & deletion
operations are faster in BST

Click :Youtube Channel | Free Material | Download App

 Construct BST with elements :
21, 16, 24, 18, 22, 25, 26, 27, 29, 33

z
aa
Aw
ut
gr
Ja

Click :Youtube Channel | Free Material | Download App