S.Y. Diploma : Sem.

III
[CO/CM/IF/CW]
Data Structures Using ‘C’
Time: 3 Hrs.] Prelim Question Paper Solution [Marks : 70

Q.1 Attempt any FIVE of the following: [10]

Q.1(a) List any four operations on data structure. [2]
Ans.: Operations on data structure:
 Insertion
 Deletion
 Searching
 Sorting
 Traversing
 Merging

Q.1(b) Explain the concept of information, Next, Null pointer and empty [2]
list with respect to link list.
Ans.: Node: Each data element in a linked list is represented as a node. Node
contains two partsone is info (data) and other is next pointer (address). Info
part stores data and next pointer stores address of next node.

Next pointer: It is a pointer that holds address of next node in the list i.e.
next pointer points to next node in the list

Null pointer: It is a pointer that does not hold any memory address i.e. it is
pointing to nothing. It is used to specify end of the list. The last element of
list contains NULL pointer to specify end of list.

Empty list: Each linked list has a header node. When header node contains
NULL value, then that list is said to be empty list.

-1-
Vidyalankar : S.Y. Diploma  DS

Q.1(c) List any four applications of queue. [2]

Ans.:  In computer system to maintain waiting list for single shared resources
such as printer, disk, etc.
 It is used as buffers on MP3 players, iPod playlist, etc.
 Used for CPU scheduling in multiprogramming and time sharing systems.
 In real life, Call Center phone systems will use Queues, to hold people
calling them in an order, until a service representative is free.
 Handling of interrupts in real-time systems.
 Simulation

Q.1(d) Differentiate between stack and queue.(Any 2 points). [2]

Ans.:

Sr. Stack Queue

No.
(i) Stack is a data structure in Queue is a data structure in
which insertion and deletion which insertion and deletion
operations are performed at operations are performed at
same end. different ends.
(ii) In stack an element inserted In Queue an element inserted
last is deleted first so it is first is deleted first so it is
called Last In First Out list. called First In First Out list.
(iii) In stack only one pointer is In Queue two pointers are used
used called as stack top. called as front and rear.
(iv) Example: Stack of books Example: Students standing in a
line at fees counter
(v) Application: Application:
 Recursion  In computer system for
 Polish notation organizing processes.
 In mobile device for sending
receiving messages.
(vi) Representation: Using array Representation: Using array

Q.1(e) Define the terms: Linear data structure and non-linear data [2]
structure.
Ans.: Linear Data Structure: A data structure in which all data elements are
stored in a particular sequence is known as linear data structure.

-2-
 Prelim Question Paper Solution

Example: stack, queue

Non-Linear data structure: A data structure in which all data elements are
not stored in any particular sequence is known as nonlinear data structure.
Example: graph and tree.

Q.1(f) Explain time complexity and space complexity. [2]

Ans.: The analysis of the program requires two main considerations:
 Time complexity
 Space complexity

The time complexity of a program / algorithm is the amount of computer

time that it needs to run to completion. The space complexity of a
program/algorithm is the amount of memory that it needs to run to
completion.

Time Complexity
While measuring the time of an algorithm, we concentrate on developing only
the frequency count for all key statements (statements that are important
and are the basic instructions of an algorithm). This is because, it is often
difficult to get reliable timing figure because of clock limitations and the
multiprogramming or the sharing environment.
Consider the algorithm given below:

ALGORITHM a=a+1
A

for x = 1 to n step 1
ALGORITHM a=a+1
B Loop

for x = 1 to n step 1
ALGORITHM for y = 1 to n step 1
C a=a+1
Loop

In the algorithm A we may find that the statement a = a + 1 is independent

and is not contained within any loop. Therefore, the number of times shall be
executed is 1. We can say that the frequency count of algorithm A is 1.

In the second algorithm, i.e. B, the key statement out of three statements is
the assignment operation a = a + 1. Because this statement is contained

-3-
Vidyalankar : S.Y. Diploma  DS

within a loop, the number of times it is executed is n, as the loop runs for n
times. The frequency count for this algorithm is n.

According to the third algorithm, the frequency count for the statement
a = a + 1 is n2 as the inner loop runs n times, each time the outer loop runs,
the outer loop also runs for n times. n2 is said to be different in increasing
order of magnitude just like 1, 10, 100 depending upon the n.

Space Complexity
The space needed by the program is the sum of following components:

Fixed space requirement

This includes the instruction space, for simple variables, fixed size
structured variables and constants.

Variable space requirement

This consists of space needed by structured variables whose size depends on
particular instance of variables. It also includes the additional space
required when the function uses recursion.

Q.1(g) Write any four applications of data structure. [2]

Ans.: Following are some real world applications of Data Structures:
(i) Mostly, Dictionaries are built using a Hash Table Data Structure. Hash
Tables are also used for caches, database indexing, fast data lookup -
symbol table for compilers.
(ii) Trees helps to build File System, Parsers.
(iii) B-Trees helps to build Database Design.
(iv) BSP tree is used in 3D computer graphics.
(v) Radix tree is used in IP routing table.
(vi) Stack : Real word applications like Java virtual machine, expression
evaluation, UNDO\REDO operation in word processors etc.
(vii) Queues : Operating systems often maintain a queue of processes that are
ready to execute or that are waiting for a particular event to occur.
(ix) Priority queues : process scheduling in the kernel.
(x) Heap is used in Dynamic memory allocation in lisp.
(x) Graphs are used in Connections/relations in social networking sites,
Routing, networks of communication, data organization etc.

Q.2Attempt any THREE of the following: [12]

Q.2(a) Explain the working of Binary search with an example. [4]
Ans.: Binary search is performed only on sorted array. Search method starts with
calculating mid position from an array and compare the mid position element

-4-
 Prelim Question Paper Solution

with the search element. If a match is found then the search process ends
otherwise divide the i/p list into 2 parts. First part contains all the numbers
less than mid position element and second part contains all the numbers
greater than mid position element. Then select one of the part depending on
search element is less or greater than mid position element and calculate mid
position for selected part. Again compare mid position element with search
element. The binary search performs comparison and division task the
element is found or division of list gives one element for comparison.

To calculate mid element perform (lower + upper) / 2.

lower-lower index position of an array(initially 0)
upper-upper index position of an array(initially size-1)

Example:
Consider Input list 0, 1, 2, 9, 10, 11, 15, 20, 46, 72
Search element: 11

Iteration 1
Lower = 0 Upper = 9 mid = (lower + upper)/2 = (0 + 9/2) = 4.5

Iteration 2
Lower = 5 Upper = 9 mid = (Lower + Upper)/2 = (5 + 9) /2 = 7

Iternation 3
Lower = 5 Upper = 6 mid = (Lower + Upper)/2 = (5 + 6)/2 = 5.5

-5-
Vidyalankar : S.Y. Diploma  DS

Q.2(b) Explain stack overflow and underflow conditions with example. [4]
Ans.: Stack Overflow: Sometimes when a new data is to be inserted into a stack
but there is no available space, then this situation is known as Stack
Overflow.
Example: If a stack has maximum capacity of 3 elements, and these three
are already occupied and the programmer tries to push in a fourth element,
then it will lead to overflow.

Stack Underflow: Sometimes when one wants to delete data from a stack
but the stack is already empty, then this situation is known as Stack
Underflow.
Example: If a stack is empty and a programmer tries to execute the POP
operation on it, then it will cause the Underflow error.

Q.2(c) Describe the concept of linked list with the terminologies : node, [4]
next pointer, null pointer and empty list.
Ans.: Node: Each data element in a linked list is represented as a node. Node
contains two parts one is info (data) and other is next pointer (address).
Info part stores data and next pointer stores address of next node.

Next pointer: It is a pointer that holds address of next node in the list i.e.
next pointer points to next node in the list

Null pointer: It is a pointer that does not hold any memory address i.e. it is
pointing to nothing. It is used to specify end of the list. The last element of
list contains NULL pointer to specify end of list.

Empty list: Each linked list has a header node. When header node contains
NULL value, then that list is said to be empty list.

-6-
 Prelim Question Paper Solution

Q.2(d) Write an algorithm to insert a node in between in a link list. [4]

Ans.: Algorithm to insert an element at the beginning of linked list:
1. Start
2. Create the node pointer *temp
Struct node * temp
3. Allocate address to temp using malloc
temp = malloc(sizeof(struct node));
4. Check whether temp is null, if null then
Display “Overflow”
Else
temp-> info=data
temp-> next=start
5. Start=temp
6. stop

Algorithm to insert an element at the end of linked list:

1. Start
2. Create two node pointers *temp, *q
struct node * temp, *q;
3. q = start
4. Allocate address to temp using malloc
temp = malloc(sizeof(struct node));
5. Check whether temp is null, if null then
Display “Overflow”
else
temp-> info=data
temp-> next=null
6. While(q->next!=null)
q= q-> next
7. q->next= temp
8. stop

Q.3Attempt any Three of the following: [12]

Q.3(a) Write an algorithm for inorder traversal of binary tree. [4]
Ans.: Inorder Traversal : C-B-A-D-E is the inorder traversal i.e. first we go
towards the leftmost node i.e C so print that node C. Then go back to the
node B and print B. Then root node A then move towards the right sub-tree
print D and finally E. Thus we are following the tracing sequence of LDR. This
type of traversal is called inorder traversal. The basic principal is to traverse
left subtree then root and then the right subtree.

-7-
Vidyalankar : S.Y. Diploma  DS

Fig.: Inorder traversal

Q.3(b) For the following directed graph : A B [4]

(i) Give adjacency matrix representation.
(ii) Give adjacency list representation.
Ans.: Adjacency List: C D
A: B
B: D
C: A,D
D: A

Adjacency Matrix:
A B C D
A 0 1 0 0
B 0 0 0 1
C 1 0 0 1
D 1 0 0 0

Q.3(c) Evaluate the following postfix expression: [4]

5, 6, 2, +, *, 12, 4, /,  Show diagrammatically each step of
evolution using stack.
Ans.:
Scanned Operand 1 Operand 2 Value Stack
Symbol Content
5 5
6 5, 6
2 5,6,2
+ 6 2 8 5,8
* 5 8 40 40
12 40, 12
4 40,12,4
/ 12 4 3 40,3
- 40 3 37 37

Result of above postfix expression evaluation- 37

-8-
 Prelim Question Paper Solution

Q.3(d) Write ‘c’ program for deletion of an element from an array. [4]
Ans.: #include <stdio.h>
int main( )
{
int array[100], position, c, n;
print(“Enter number of elements in array\n”);
scanf(“%d”, &n);
printf(“Enter %d elements\n”, n);
for (c = 0; c< n; c++)
scanf(“%d”, &array[c]);
print(“Enter the location where you wish to delete element\n”);
scanf(“%d”, &position);
if (position > = n + 1)
printf(“Delection not possible.\n”);
else
{
for (c = position – 1; c < n – 1; c++)
array[c] = array[c + 1];

printf(“Resultant array;\n”);

for (c = 0; c < n – 1; c++)

}
Return 0;
}

Q.4 Attempt any THREE of the following: [12]

Q.4(a) Construct a binary search tree for following elements: [4]
30, 100, 90, 15, 2, 25, 36, 72, 78, 10 show each step of
construction of BST.
Ans.: Stepwise construction of Binary search tree for following elements:
30,100,90,15,2,25,36,72,78,10 is as follows:

-9-
Vidyalankar : S.Y. Diploma  DS

Q.4(b) Explain the concept of double ended queue. [4]

Ans.: Double Ended Queue :
(i) A double-ended queue or dequeue is an abstract data structure that
implements a queue for which elements can only be added to or removed
from the front (head) or back (tail).
(ii) It is also often called a head-tail linked list.
(iii) Dequeue is a special type of data structure in which insertions and deletions
will be done either at the front end or at the rear end of the queue.
(iv) The operations that can be performed on dequeues are
(a) Insert an item from front end

- 10 -
 Prelim Question Paper Solution

(b) Insert an item from rear end

(c) Delete an item from front end
(d) Delete an item from rear end
(e) Display the contents of queue
Rear Front

Front Rear

Q.4(c) Draw the tree structure of the following expressions: [4]

(i) (2a + 5b)3 * (x – 7y)4 (ii) (a – 3b) * (2x  7)3
Ans.: (i) (2a + 5b)3 * (x – 7y)4

(ii) (a – 3b) * (2x  7)3

Q.4(d) Write an algorithm to delete a node from the beginning of a [4]

circular linked list.
Ans.: Algorithm to delete a node from the beginning of a circular linked list
Consider the function delatbeg()
(i) Start
(ii) Declare struct node *tmp,*q;
(iii) Set q=last->link;
(iv) While (q! = last)
Do
tmp = q; // Identifies beginning node of Circular Linked List
last->link=q->link; // Set the address field before deleting identified
node
free(tmp); // Delete the beginning node
End of While

- 11 -
Vidyalankar : S.Y. Diploma  DS

(v) last=NULL; // Set last= NULL if only one node is present in the Circular
Linked List
(vi) End of function

Q.4(e) Describe circular linked list with suitable diagram. Also state [4]
advantage of circular linked list over linear linked list.
Ans.: Circular Linked List
A circular linked list is a variation of linked list in which the last element is
linked to the first element. This forms a circular loop.

A circular linked list can be either singly linked or doubly linked.

 for singly linked list, next pointer of last item points to the first item
 In doubly linked list, prev pointer of first item points to last item as
well.
We declare the structure for the circular linked list in the same way as
follows:
Struct node
{
Int data;
Struct node *next;
};
Typedef struct node *Node;
Node *start = null;
Node *last = null;

For example:

Advantages of Circular Linked Lists:

(i) Any node can be a starting point. We can traverse the whole list by
starting from any point. We just need to stop when the first visited
node is visited again.
(ii) Useful for implementation of queue. Unlike this implementation, we don’t
need to maintain two pointers for front and rear if we use circular linked

- 12 -
 Prelim Question Paper Solution

list. We can maintain a pointer to the last inserted node and front can
always be obtained as next of last.
(iii) Circular lists are useful in applications to repeatedly go around the list.
For example, when multiple applications are running on a PC, it is common
for the operating system to put the running applications on a list and
then to cycle through them, giving each of them a slice of time to
execute, and then making them wait while the CPU is given to another
application. It is convenient for the operating system to use a circular
list so that when it reaches the end of the list it can cycle around to the
front of the list.
(iv) Circular Doubly Linked Lists are used for implementation of advanced
data structures like Fibonacci Heap.

Q.5 Attempt any TWO of the following: [12]

Q.5(a) For given binary tree write in-order, pre-order and post-order [6]
traversal.

Ans.: Inorder Traversal: Q, E, F, R, D, H, B, A, I, J, K, C, L, P

Preorder Traversal: A, B, D, E, Q, F, R, H, C, I, J, K, L, P
Postorder Traversal: Q, R, F, E, H, D, B, K, J, I, P, L, C, A

Q.5(b) Write an algorithm to count numbers of nodes in singly linked list. [6]
Ans.: Step 1: Count = 0. SAVE = FIRST.
Step 2: Repeat step 3 while SAVE != NULL.
Step 3: Count= Count + 1. SAVE=SAVE->LINK.
Step 4: Return Count.

Q.5(c) Consider the graph given in Figure. A D [6]

Find its adjacency matrix and
adjacency link representation.

B C

- 13 -
Vidyalankar : S.Y. Diploma  DS

Ans.:
A D

B C

Adjacency Matrix
A B C D A D C B
A 0 1 0 1  A 0 1 0 1 
   
A = B 1 0 0 0 OR D 0 0 0 0
   
C 1 1 0 1  C 1 1 0 1 
   
D  0 0 0 0  B  1 0 0 0 

Adjacent nodes can contain two or three fields.

START

A X

B X

C X

D X X

Q.6.Attempt any TWO of the following: [12]

Q.6(a) Create a Singly Linked List using data fields 10, 20, 30, 40, 50. [6]
Search a node 40 from the SLL and show procedure step-by-step
with the help of diagram from start to end.
Ans.: Step 1:

Step 2:

- 14 -
 Prelim Question Paper Solution

Step 3:

Step 4:

Result: Value was found in the linked list. The pointer points to the node
having the value.

Q.6(b) Describe breadth first search traversal in a graph with example. [6]
Ans.: Algorithm for BFS:
(i) Initialize all nodes to ready state.
(ii) Insert starting node in a queue and change its state to waiting state.
(iii) Repeat steps 4 to 6 till the queue becomes empty.
(iv) Remove front node N from queue 2 change its status to visit.
(v) Insert all adjacent nodes of N at the rear end of the queue and change
their status to ‘waiting state’.
(vi) From the origin find path from source node to destination node or from
the queue element list find all nodes that are reachable.
(vii) Stop.

Example :
Front of the queue is set to ‘0’
Rear of the queue is set to ‘0’
Queue is used to indicate elements of the A
graph which are visited.
F C B
Origin is used to keep track of origin of each node.
D E G

J K

Find all nodes reachable from ‘A’

1) Insert A into a queue.
A
Front=1 Rear=1
Queue=A Origin=0

- 15 -
Vidyalankar : S.Y. Diploma  DS

2) Remove front element A and insert adjacent nodes of a in queue.

F C B
Queue=A front=1
Origin=O, A, A, A rear=3

3) Remove element F and insert its adjacent nodes in the queue.

C B D
Queue=A, F, C, B, D front=2
Origin=O, A, A, A, F rear=4

4) Remove front element C and insert its adjacent nodes in the queue
(F is already visited)
B D
Queue=A, F, C, B, D front=3
Origin=O, A, A, A, F rear=4

5) Remove front element B and insert adjacent nodes

D G
Queue=A, F, C, B, D, G front=4
Origin=O, A, A, A, F, B rear=5

6) Remove front element D and insert adjacent nodes (C is already visited)

G
Queue=A, F, C, B, D, G front=5
Origin=O, A, A, A, F, B, G rear=5

7) Remove front element G and insert adjacent nodes

E
Queue=A, F, C, B, D, G, E front=6
Origin=O, A, A, A, F, B, G rear=6

8) Remove front element E and insert its adjacent nodes (D is already a

visited node)
J
Queue=A, F, C, B, D, G, E, J
Origin=O, A, A, A, F, B, G, E

9) Remove J

Queue = A, F, C, B, D, G, E, J
All nodes readable from A-A, F, C, B, D, G, E, J
Origin= O, A, A, A, F, B, G, E, J

- 16 -
 Prelim Question Paper Solution

Q.6(c) Create a singly linked list using data fields 90, 25, 46, 39, 56. [6]
Search a node 40 from a SLL and show procedure step-by-step
with the help of diagram from start to end.
Ans.: (i) With given data fields, singly linked list is created as follows.

(ii) Operation : Search a node 22 from the above SLL

 Initially q = start where q is a pointer of type struct node used for
traversing a linked list.

 q ! = Nuk and pos = 1

q  data  key value
i.e. is  22
 q = q  next and pos++

 q! = NULL and pos = 2

q data  key value
i.e. 20  22
 q = q  next and pos = 3

q! = NULL and pos = 3 q

q data = = key value
i.e. 22 = 22
 node 22 is located at position 3 search is successful.



- 17 -