Prashnikaप्रश्निका

Data structures - ISC Class 12 Computer Science Questions with Answers, Page 3

87 past-paper questions on Data structures from ISC Class 12 Computer Science papers (2026-2017), newest first, in full. Questions 41-60 are on this page, 20 to a page. Tap "Show answer" under a question to see its answer.

Practise these questions with filters
2023 · 5 marks · Case basedOpen: Holder is a kind of data structure which can store elements with the…

Answer the questions on the class described below.

Holder is a kind of data structure which can store elements with the restriction that an element can be added from the rear end and removed from the front end only. The details of the class Holder is given below:
Class name:Holder
Data members/instance variables:
Q[ ]:array to hold integers
cap:maximum capacity of the holder
front:to point the index of the front end
rear:to point the index of the rear end
Methods / Member functions:
Holder(int n ):constructor to initialize cap=n, front= 0 and rear=0
void addint( int v ):to add integers in the holder at the rear end if possible, otherwise display the message “ HOLDER IS FULL ”
int removeint( ):removes and returns the integers from the front end of the holder if any, else returns −999
void show( ):displays the elements of the holder
(i)[4.0]
Specify the class Holder giving details of the functions void addint(int) and int removeint( ). Assume that the other functions have been defined. The main( ) function and algorithm need NOT be written.
(ii)[1.0]
Name the entity described above and state its principle.
Show answer

Answer (i)

AI
void addint(int v)
{
    if (rear == cap)
        System.out.println("HOLDER IS FULL");
    else
    {
        Q[rear] = v;
        rear++;
    }
}

int removeint()
{
    if (front == rear)
        return -999;
    else
    {
        int val = Q[front];
        front++;
        return val;
    }
}
Explanation: addint() checks whether rear has reached the capacity cap (holder full) before storing v at index rear and advancing rear; otherwise it prints "HOLDER IS FULL". removeint() checks whether the holder is empty (front==rear), returning -999 in that case; otherwise it returns the element at front and advances front, so elements always leave from the front in the order they were added (verified logically against the given constructor, which sets front=rear=0).

Answer (ii)

AI
The entity described is a Queue (Linear Queue). It works on the principle of FIFO (First In First Out) - the element added first (at the rear) is the element removed first (from the front).
2023 · 3 marks · Binary treeOpen: Answer the following questions from the diagram of a Binary Tree given below…

Answer the following questions from the binary tree.

Answer the following questions from the diagram of a Binary Tree given below:
(a)[1.0]
Write the in-order traversal of the above tree structure.
(b)[1.0]
Name the children of the nodes B and G.
(c)[1.0]
State the root of the right sub tree.
Show answer

Answer (a)

AI
From the figure: A is the root with children B (left) and F (right); B has left child D only; F has right child G only; G has children E (left) and H (right). In-order (Left, Root, Right): D, B, A, F, E, G, H

Answer (b)

AI
Node B has only one child: D (its left child); B has no right child. Node G has two children: E (left child) and H (right child).

Answer (c)

AI
The root of the right subtree (of A) is F.
2023 · 2 marks · ConversionOpen: Convert the following infix notation to postfix form.

Answer the following.

Convert the following infix notation to postfix form. $( P / Q - R ) * ( S + T )$
Show answer

Answer

AI
$(P/Q-R)*(S+T)$ Converting $(P/Q-R)$: push $($, output $P$, push $/$, output $Q$ (so far $PQ$), on seeing $-$ pop $/$ to output ($PQ/$) then push $-$, output $R$ ($PQ/R$), on $)$ pop $-$ ($PQ/R-$). Converting $(S+T)$: output $ST+$. Combine with $*$: $PQ/R- \;\; ST+ \;\; *$ Postfix: $PQ/R-ST+*$
2023 · 4 marks · ProgramOpen: A double ended queue is a linear data structure which enables the user to add…

Answer the following.

A double ended queue is a linear data structure which enables the user to add and remove integers from either ends i.e., from front or rear. The details of the class deQueue are given below:
Class name:deQueue
Data members/ instance variables:
Qrr[ ]:array to hold integer elements
lim:maximum capacity of the dequeue
front:to point the index of the front end
rear:to point the index of the rear end
Methods / Member functions:
deQueue(int l):constructor to initialise $lim = l$, $front = 0$ and $rear = 0$
void addFront(int v):to add integers in the dequeue at the front end if possible, otherwise display the message “OVERFLOW FROM FRONT”
void addRear(int v):to add integers in the dequeue at the rear end if possible, otherwise display the message “OVERFLOW FROM REAR”
int popFront( ):removes and returns the integers from the front end of the dequeue if any, else returns -999
int popRear( ):removes and returns the integers from the rear end of the dequeue if any, else returns -999
void show( ):displays the elements of the dequeue
Specify the class deQueue giving details of the functions void addFront(int) and int popFront( ). Assume that the other functions have been defined. The main( ) function and algorithm need NOT be written.
Show answer

Answer

AI
class deQueue
{
    int Qrr[];   // array holding the elements
    int lim;     // maximum capacity
    int front;   // front end index
    int rear;    // rear end index

    deQueue(int l)
    {
        lim = l;
        front = 0;
        rear = 0;
        Qrr = new int[lim];
    }

    // adds v at the front end if there is room before front
    void addFront(int v)
    {
        if (front > 0)
        {
            Qrr[front] = v;
            front--;
        }
        else
            System.out.println("OVERFLOW FROM FRONT");
    }

    // removes and returns the element at the front end, or -999 if empty
    int popFront()
    {
        if (front == rear)
            return -999;
        front++;
        return Qrr[front];
    }
}
The elements occupy positions front + 1 to rear, so the dequeue is empty when front == rear (both start at 0, as the constructor sets). addFront() stores the value at index front and moves front one step left; when front is 0 there is no room at the front, so it reports overflow. popFront() moves front one step right and returns the element there, or -999 if the dequeue is empty. (addRear() correspondingly does rear++ then Qrr[rear] = v while rear < lim - 1.) Tested with the other functions filled in: after addRear(10), addRear(20), addRear(30), popFront() returned 10 and then 20; addFront(15) then put 15 in front of 30; popFront() gave 15, 30 and then -999.
2023 · 1 mark · Short answerOpen: What is a linked list?

Answer the following.

What is a linked list?
Show answer

Answer

AI
A linked list is a linear, dynamic data structure made up of a sequence of nodes, where each node holds a data item and a reference (pointer/link) to the next node in the sequence. Unlike an array, its elements need not occupy contiguous memory locations, and the list can grow or shrink at run time.
2023 · 2 marks · ProgramOpen: A linked list is formed from the objects of the class: class Node { int num…

Write the program described below.

A linked list is formed from the objects of the class: 
class Node
{
    int num;
    Node next;
}
Write an Algorithm OR a Method to insert a node at the beginning of an existing linked list. The method declaration is as follows: 
void InsertNode( Nodes  starPtr, int n )
Show answer

Answer

AI
Assuming a class-level Node reference start holds the head of the linked list, and startPtr is the current head passed into the method:
void InsertNode(Node startPtr, int n)
{
    Node temp = new Node();
    temp.num = n;
    temp.next = startPtr;
    start = temp;
}
A new node temp is created and its data field is set to n; its next is made to point to the current first node (startPtr), and the class-level head pointer start is then updated to this new node, thereby inserting it at the beginning of the list.
2022 · 4 marks · ProgramOpen: A Queue is a linear data structure in which the operations are performed based…

Write the program described below.

A Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out). Define a class Queue with the following details: Class name: Queue Data member/instance variable: dat[]: array to hold the integer elements cap: stores the maximum capacity of the queue front: to point the index of the front rear: to point the index of the rear Member functions/methods: Queue(int max): constructor to initialize the data member cap = max, front = rear = 0 and create the integer array void add_dat(int v): to add integers from the rear index if possible else display the message (“Queue full”) int pop_dat(): to remove and return elements from front, if any, else returns -999 void display(): to display elements of the queue Specify the class Queue giving the details of void add_dat(int) and int pop_dat(). Assume that the other functions have been defined. The main() function and algorithm need NOT be written.
Show answer

Answer

AI
void add_dat(int v)
{
    if (rear < cap)
    {
        dat[rear] = v;
        rear++;
    }
    else
        System.out.println("Queue full");
}

int pop_dat()
{
    if (front == rear)
        return -999;
    int v = dat[front];
    front++;
    return v;
}
Elements are added at index rear while rear is less than cap; otherwise "Queue full" is displayed. Elements are removed from index front, and -999 is returned when the queue is empty (front equals rear).
2022 · 2 marks · ConversionOpen: Convert the following infix notation to postfix notation:

Convert the following notation as directed.

Convert the following infix notation to postfix notation: $A * (B + C / D) - E / F$
Show answer

Answer

AI
Postfix: $A B C D / + * E F / -$ Working: C/D gives CD/; B+CD/ gives BCD/+; A*(...) gives ABCD/+*; E/F gives EF/; the subtraction gives ABCD/+*EF/-.
2020 · 5 marks · ProgramOpen: Circular Queue is a linear data structure in which the operations are performed…

Write the program described below.

Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. Define a class Cqueue with the following details: Class name : Cqueue Data member/instance variable: ele[ ] : array to hold the integer elements cap : stores the maximum capacity of the array front : to point the index of the front rear : to point the index of the rear. Member functions/methods: Cqueue(int max) : constructor to initialize the data member cap = max, front = rear = 0 and create the integer array void insert(int v) : to add integers from the front index if possible else display the message(“full from rear”) int delete( ) : to remove and return elements from rear, if any, else returns -999 void display() : to display elements of circular queue Specify the class Cqueue giving the details of void insert(int) and int delete( ). Assume that the other functions have been defined. The main( ) function and algorithm need NOT be written.
Show answer

Answer

AI
void insert(int v)
{
    if ((front + 1) % cap == rear)
        System.out.println("full from rear");
    else
    {
        ele[front] = v;
        front = (front + 1) % cap;
    }
}

int delete()
{
    if (front == rear)
        return -999;
    int v = ele[rear];
    rear = (rear + 1) % cap;
    return v;
}
Explanation: As given in the question, elements are added at the front index and removed from the rear end, and front and rear both start at 0, so front == rear means the queue is empty. insert() checks whether moving front one step forward (with wrap-around using % cap) would meet rear; if so the queue is full and the message full from rear is shown (one position is kept unused to tell a full queue from an empty one). Otherwise the value is stored at ele[front] and front moves circularly. delete() returns -999 if the queue is empty; otherwise it returns the element at rear and moves rear forward circularly, so the element inserted first is removed first (FIFO). Tested with cap = 4: three inserts were accepted, the fourth printed full from rear, deletes returned the values in FIFO order and a delete on the empty queue returned -999.
2020 · 2 marks · ProgramOpen: A linked list is formed from the objects of the class Node. The class structure…

Write the program described below.

A linked list is formed from the objects of the class Node. The class structure of the Node is given below: 
class Node
{
    int n;
    Node next;
}
Write an Algorithm OR a Method to find the product of the integer numbers from an existing linked list. The method declaration is as follows: void Product_Node( Node str )
Show answer

Answer

AI
void Product_Node(Node str)
{
    if (str == null)
    {
        System.out.println("The list is empty");
        return;
    }
    int p = 1;
    Node t = str;
    while (t != null)
    {
        p = p * t.n;
        t = t.next;
    }
    System.out.println("Product = " + p);
}
Explanation: p starts at 1 and a temporary reference t starts at the first node str. The loop multiplies p by the number stored in each node (t.n) and moves t to the next node until t becomes null, i.e. the end of the list. The product is then displayed. Tested: for the list 2, 3, 7 the output is Product = 42.
2020 · 2 marks · DifferentiateOpen: State the difference between a Binary Tree structure and a single Linked List.

Differentiate between the following.

State the difference between a Binary Tree structure and a single Linked List.
Show answer

Answer

AI
Binary tree: a non-linear, hierarchical data structure with a root; every node can have up to two children (left and right), so each node holds two links. Data is reached by moving down from the root through a path, and in a binary search tree searching is fast (about $O(\log n)$ for a balanced tree). Single linked list: a linear data structure; each node holds one link (next) to the following node, so the nodes form a single chain from the first node to the last. Elements can be reached only sequentially, so searching takes $O(n)$.
2020 · 1 mark · Binary treeOpen: Write the post order traversal of the tree.

Answer the following questions from the binary tree.

Write the post order traversal of the tree.
Show answer

Answer

AI
Post-order traversal (left, right, root): left subtree of A gives D B (B has only a right child D), right subtree gives E G F C (C has left child E and right child F; F has left child G), then the root A. Post-order: D B E G F C A
2020 · 2 marks · ProgramOpen: A linked list is formed from the objects of the class Node. The class structure…

Write the program described below.

A linked list is formed from the objects of the class Node. The class structure of the Node is given below: 
class Node
{
    int num;
    Node next;
}
Write an Algorithm OR a Method to insert a node at the beginning of an existing linked list. The method declaration is as follows: void InsertNode( Node starPtr, int n )
Show answer

Answer

AI
void InsertNode(Node starPtr, int n)
{
    Node t = new Node();
    t.num = n;
    t.next = starPtr;
    start = t;
}
Explanation: starPtr is the reference to the first node of the existing list and start is the class-level reference that holds the head of the list (starPtr = start when the method is called). A new node t is created and the number n is stored in it. Its next reference is made to point to the old first node (starPtr), and start is then made to point to t, so the new node becomes the first node. This also works for an empty list (starPtr is null), where the new node becomes the only node. Tested: inserting 30, 20 and 10 in turn gives the list 10 20 30.
2020 · 1 mark · Binary treeOpen: Name the Root and the leaves of the tree.

Answer the following questions from the binary tree.

Name the Root and the leaves of the tree.
Show answer

Answer

AI
Root of the tree: A. Leaves (nodes with no children): D, E and G.
2020 · 1 mark · DifferentiateOpen: How is a linear queue structure different from a circular queue structure?

Differentiate between the following.

How is a linear queue structure different from a circular queue structure?
Show answer

Answer

AI
In a linear queue, insertion is at the rear and deletion is at the front, and once the rear reaches the last position no more elements can be added even if the front positions have become empty after deletions, so that space is wasted. In a circular queue the last position is connected back to the first position, so rear can wrap around and reuse the vacated positions at the front; the space is used efficiently.
2020 · 4 marks · ProgramOpen: Specify the class CirQueue giving details of the functions void push(int) and…

Write the program described below.

Specify the class CirQueue giving details of the functions void push(int) and int pop( ). Assume that the other functions have been defined. The main function and algorithm need NOT be written.
Show the case
A Circular queue is a linear data structure which works on the principle of FIFO, enables the user to enter data from the rear end and remove data from the front end with the rear end connected to the front end to form a circular pattern. Define a class CirQueue with the following details: Class name : CirQueue Data members / instance variables: cq[ ] : array to store the integers cap : stores the maximum capacity of the array front : to point the index of the front end rear : to point the index of the rear end Member functions: CirQueue (int max) : constructor to initialize the data member cap=max, front=0 and rear=0 void push(int n) : to add integer in the queue from the rear end if possible, otherwise display the message “QUEUE IS FULL” int pop( ) : removes and returns the integer from the front end of the queue if any, else returns -9999 void show( ) : displays the queue elements
Show answer

Answer

AI
void push(int n)
{
    if ((rear + 1) % cap == front)
        System.out.println("QUEUE IS FULL");
    else
    {
        cq[rear] = n;
        rear = (rear + 1) % cap;
    }
}

int pop()
{
    if (front == rear)
        return -9999;
    int v = cq[front];
    front = (front + 1) % cap;
    return v;
}
Explanation: front and rear both start at 0, so front == rear means the queue is empty. push() checks whether advancing rear (with wrap-around using % cap) would meet front; if so the queue is full and the message QUEUE IS FULL is shown (one position is kept unused to tell a full queue from an empty one). Otherwise the number is stored at cq[rear] and rear moves to the next position circularly. pop() returns -9999 when the queue is empty; otherwise it returns the element at front and moves front forward circularly. Tested with cap = 4: three pushes were accepted, the fourth printed QUEUE IS FULL, pops returned the elements in FIFO order, and a pop on the empty queue returned -9999.

Questions on other pages on Data structures

Other Computer Science chapters