Advance Computer Science

Data Structures and Algorithms

50,000+ Questions

Previous Year Papers

Detailed Solutions

Hindi & English

MEDIUM

Consider a graph with 10 nodes (N), 15 edges (E), and 2 connected components (P). What is the Cyclomatic Complexity of this graph?

Explanation

🌟 Quick Verification

Direct Answer: The correct answer is 9.
Core Concept: The Cyclomatic Complexity is a software metric used to indicate the complexity of a program.

🧠 Concept Blueprint

Formula: The formula is M = E - N + 2P.
Calculation:
- E (Edges) = 15
- N (Nodes) = 10
- P (Connected Components) = 2
- M = 15 - 10 + 2(2) = 5 + 4 = 9.

📊 Fact Spotlight

Metric	Definition	Significance
Cyclomatic Complexity	M = E - N + 2P	Measures independent paths
Spanning Tree	V-1 edges	Connects all nodes without cycles
Hamiltonian Path	Visits every vertex once	NP-Complete problem

💡 Exam Strategy & Trivia

Tip

Common Pitfall: For a single connected component (P=1), the formula simplifies to E - N + 2. Always check the number of components (P) provided in the question.

Memorable Trivia: Higher cyclomatic complexity indicates a higher risk of bugs and more difficult testing requirements.

Karnataka PSC Comp. Sci. Teacher 16.10.2017

MEDIUM

In a linear search:

Search starts at the middle and goes to left or right depending on the case

Search starts at the beginning of the list and checks every element in the list until either the search is successful or the list ends

Computes a hash value and compares

Search is randomly carried out

Explanation

In linear search, we check every element sequentially.

MEDIUM

Match the following formulas with their corresponding array addressing techniques:

List I (Technique)	List II (Formula)
A. 1D Array	1. Base + W * (j * M + i)
B. RMO (0-based)	2. Base + W * (i - LB)
C. CMO (0-based)	3. Base + W * (i * N + j)

Select the correct matching code:

A-2, B-3, C-1

A-1, B-2, C-3

A-2, B-1, C-3

A-3, B-2, C-1

Explanation

🌟 Quick Verification

Direct Answer: The correct answer is A-2, B-3, C-1.
Core Concept: Addressing Formula Mapping.

🧠 Concept Blueprint

1D Array: Uses the simple linear formula Base + W * (i - LB).
RMO (Row-Major): Stores row-by-row. The offset is calculated by skipping full rows ( $i \times N$ ) and adding the column offset ( $j$ ). Formula: Base + W * (i * N + j).
CMO (Column-Major): Stores column-by-column. The offset is calculated by skipping full columns ( $j \times M$ ) and adding the row offset ( $i$ ). Formula: Base + W * (j * M + i).

📊 Fact Spotlight

Technique	Primary Multiplier	Offset Logic
RMO	Number of Columns ( $N$ )	Row-first traversal
CMO	Number of Rows ( $M$ )	Column-first traversal

💡 Exam Strategy & Trivia

Tip

Memory Aid: In RMO, the row index $i$ is multiplied by the column count $N$ . In CMO, the column index $j$ is multiplied by the row count $M$ . Always look for the 'opposite' dimension in the multiplier.

MEDIUM

Assertion (A): An Adjacency List is preferred over an Adjacency Matrix for representing sparse graphs.
Reason (R): Adjacency Matrices consume significant memory by storing zeros for all non-existent connections between vertices.

Both A and R are true and R is the correct explanation of A

Both A and R are true but R is not the correct explanation of A

A is true but R is false

A is false but R is true

Explanation

🌟 Quick Verification

Direct Answer: The correct answer is Both A and R are true and R is the correct explanation of A.
Core Concept: Space complexity trade-offs in graph storage.

🧠 Concept Blueprint

Reasoning:
- The assertion is true because sparse graphs have very few edges relative to the potential maximum number of edges ( $n^2$ ).
- The reason is also true because an adjacency matrix must allocate memory for every possible pair of vertices ( $n^2$ cells), filling non-existent edges with 0. This results in wasted memory, which the adjacency list avoids by only storing actual connections.

📊 Fact Spotlight

Graph Density	Recommended Representation
Dense (Edges ≈ V²)	Adjacency Matrix
Sparse (Edges ≈ V)	Adjacency List

💡 Exam Strategy & Trivia

Tip

Common Pitfall: Do not assume Adjacency Lists are always better. For very dense graphs, the overhead of pointers in a linked list might actually make the Adjacency Matrix more efficient.

Memorable Trivia: The term Sparse usually implies that the number of edges is proportional to the number of vertices, not the square of vertices.

MEDIUM

Which traversal technique is most appropriate for deleting a tree structure from memory to ensure all children are processed before their parents?

Pre-order traversal

In-order traversal

Post-order traversal

Level-order traversal

Explanation

🌟 Quick Verification

Direct Answer: Post-order traversal
Core Concept: Post-order Traversal Application.

🧠 Concept Blueprint

Why Post-order?: In post-order traversal, the sequence is Left Sub-tree → Right Sub-tree → Root. This ensures that both children are visited and deleted before the parent node is deleted.
Risk of others: If you delete the root first (Pre-order), you lose the pointers to the children, causing memory leaks.

📊 Fact Spotlight

Traversal	Best Use Case
Pre-order	Copying/Cloning Tree
In-order	Sorting (BST)
Post-order	Deleting/Postfix Expression

💡 Exam Strategy & Trivia

Tip

Common Pitfall: Always remember that 'Post' means the root is processed 'after' the children.

Memorable Trivia: Post-order traversal is also used to evaluate mathematical expressions represented as trees (Postfix/Reverse Polish Notation).

No credit card required

EASY

Consider a tree where each node has at most 2 children. Which of the following statements is true regarding the terminology of such a tree?

An internal node is a node with no child nodes.

A leaf node is a node with at least one child.

A binary tree is a tree where each element has at most 2 children.

A general tree is a tree where each node has exactly 2 children.

Explanation

🌟 Quick Verification

Direct Answer: A binary tree is a tree where each element has at most 2 children.
Core Concept: Binary Tree Definition.

🧠 Concept Blueprint

Terminology Clarification:
- Binary Tree: Defined by the constraint of having a maximum of 2 children per node.
- Internal Node: Defined as a node having at least one child.
- Leaf Node: Defined as a node having zero children (terminal node).
- General Tree: Allows a node to have zero or more children (no limit of 2).

📊 Fact Spotlight

Term	Definition
Internal Node	Degree >= 1
Leaf Node	Degree = 0
Binary Tree	Max Degree = 2

💡 Exam Strategy & Trivia

Tip

Common Pitfall: Confusing 'General Tree' with 'Binary Tree'. General trees have no limit on the number of children.

Memorable Trivia: The binary tree is the most widely used tree structure in computer science due to its simplicity and efficiency in searching.

GPSC Asst. Prof. 30.06.2016

MEDIUM

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

Heap

Binary Tree

Array

Stack

Explanation

In serial access memory, data is read sequentially, which is similar to the operations of a stack (or queue).

MEDIUM

A complete binary tree with n leaf nodes has ____

n + 1 nodes

2n - 1 nodes

2n + 1 nodes

\frac{n(n-1)}{2}

nodes

Explanation

In a full binary tree (where every node has 0 or 2 children), if there are $n$ leaf nodes, the total nodes are $2n-1$ .

MEDIUM

In a min heap

minimum value of stored

child nodes have less value than parent nodes

parent nodes have less value than child nodes

maximum value is contained by the root node

Explanation

In a Min Heap, the value of each parent node is less than or equal to the values of its child nodes.

Karnataka PSC Comp. Sci. Teacher 16.10.2017

MEDIUM

In linked list representation, graph is stored in:

Edge list

Vertex list

Adjacency list

None of the above

Explanation

Graphs are commonly stored using linked lists in the form of an adjacency list.

Full Mock Tests

Take Full-Length Mock Tests

Test your complete preparation with timed mock tests. Get detailed analytics and compare scores with other aspirants.

Explore Test Series

ISRO Scientist/Engineer 2007

MEDIUM

Selection sort algorithm design techniques is an example of

Greedy method

Divide-and-conquer

Dynamic Programming

Backtracking

Explanation

In selection sort, we choose the smallest element at each step, which is a greedy approach.

MEDIUM

Which one of below mentioned is linear data structure?

queue

stack

arrays

all of these

Explanation

Queue, stack, and arrays are all linear data structures.

HARD

A strictly binary tree has 15 internal nodes. How many leaf nodes does it have?

Explanation

🌟 Quick Verification

Direct Answer: 16
Core Concept: Strictly Binary Tree Property.

🧠 Concept Blueprint

The Rule: In a strictly binary tree (where every non-leaf node has exactly 2 children), the number of leaf nodes (n) and internal nodes (I) are related by the formula I = n - 1.
Calculation: Given I = 15, we solve for n: 15 = n - 1, which gives n = 16.

📊 Fact Spotlight

Property	Formula
Total Nodes	2n - 1 (where n = leaves)
Internal Nodes	n - 1 (where n = leaves)
Leaf Nodes	I + 1 (where I = internal nodes)

💡 Exam Strategy & Trivia

Tip

Common Pitfall: Do not confuse this with a general binary tree, where the number of internal nodes and leaves can vary significantly.

Memorable Trivia: This property is a specific case of the more general rule that in any binary tree, the number of nodes with two children is one less than the number of leaf nodes.

MEDIUM

A 2D array A[0...2][0...2] has a base address of 1000 and each element occupies 4 bytes. Calculate the address of A[1][1] using Column-Major Order (CMO).

1016

1020

1012

1024

Explanation

🌟 Quick Verification

Direct Answer: The correct answer is 1016.
Core Concept: CMO Calculation.

🧠 Concept Blueprint

Given: Base = 1000, W = 4, $LB_r = 0, LB_c = 0$ .
Total Rows ( $N_r$ ): $UB_r - LB_r + 1 = 2 - 0 + 1 = 3$ .
Formula: $Base + W \times [(j - LB_c) \times N_r + (i - LB_r)]$ .
Calculation: $1000 + 4 \times [(1 - 0) \times 3 + (1 - 0)] = 1000 + 4 \times [3 + 1] = 1000 + 4 \times 4 = 1000 + 16 = 1016$ .

📊 Fact Spotlight

Variable	Value	Role
$j$	1	Column index
$N_r$	3	Total rows (multiplier)
$i$	1	Row index

💡 Exam Strategy & Trivia

Tip

Common Pitfall: In CMO, the column index $j$ is multiplied by the total number of rows $N_r$ . Do not use $N_c$ (columns) as the multiplier here.

GPSC Asst. Prof. 30.06.2016

MEDIUM

What is meant by physical size in a dynamic array?

The size allocated to elements

The size extended to add new elements

The size of the underlying array at the back-end

The size visible to users

Explanation

The physical size is the capacity of the underlying array, not the number of elements currently filled.

MEDIUM

Assertion (A): Inserting an element at the front of a linked list (given the head pointer) takes O(1) time.
Reason (R): This operation only involves creating a new node and updating the head pointer, without requiring traversal of the list.

Select the correct option:

Both A and R are true and R is the correct explanation of A

Both A and R are true but R is not the correct explanation of A

A is true but R is false

A is false but R is true

Explanation

🌟 Quick Verification

Direct Answer: Both A and R are true and R is the correct explanation of A.

🧠 Concept Blueprint

Linked List Insertion: When the head pointer is provided, inserting at the front is an O(1) constant time operation because we simply point the new node to the current head and update the head pointer.
Contrast: Inserting at the rear of a linked list typically requires traversing the entire list to find the last node, making it an O(n) operation.

📊 Fact Spotlight

Operation	Time Complexity (Linked List)
Insert at Front	O(1)
Insert at Rear	O(n)
Access Element	O(n)

💡 Exam Strategy & Trivia

Tip

Exam Trap: Always check if the 'tail' pointer is provided. If a tail pointer is provided, insertion at the rear also becomes O(1).

MEDIUM

Which of the following statements regarding Binary Search is correct?

It is applicable only in Linked Lists.

It is applicable in Arrays and AVL trees.

It is a greedy algorithm.

It requires the data to be unsorted.

Explanation

🌟 Quick Verification

Direct Answer: The correct answer is It is applicable in Arrays and AVL trees.
Core Concept: Binary Search is an efficient search algorithm that finds the position of a target value within a sorted structure.

🧠 Concept Blueprint

Requirements: Binary Search requires the data to be sorted and accessible in a way that allows efficient middle-element calculation (like arrays) or hierarchical traversal (like AVL trees).
Why Other Options are Incorrect:
- It is not suitable for standard Linked Lists (O(n) access time).
- It is a Divide and Conquer algorithm, not a greedy one.
- It strictly requires sorted data.

📊 Fact Spotlight

Search Type	Structure	Complexity
Linear Search	Any	O(n)
Binary Search	Sorted Array/AVL	O(log n)

💡 Exam Strategy & Trivia

Tip

Common Pitfall: Students often think Binary Search works on all data structures. It specifically requires random access or tree-based navigation.

Memorable Trivia: AVL trees are self-balancing, which ensures that the search time remains logarithmic even after multiple insertions and deletions.

MEDIUM

Arrange the following steps in the correct sequence for reconstructing a binary tree from In-order and Pre-order traversals:

Recursively apply the logic to build the left and right sub-trees.
Identify the root node from the Pre-order sequence.
Locate the identified root node in the In-order traversal.
Split the In-order traversal into left and right sub-tree elements.

2 -> 3 -> 4 -> 1

3 -> 2 -> 4 -> 1

2 -> 4 -> 3 -> 1

1 -> 2 -> 3 -> 4

Explanation

🌟 Quick Verification

Direct Answer: 2 -> 3 -> 4 -> 1.
Core Concept: Reconstruction Algorithm.

🧠 Concept Blueprint

Step-by-Step Process:
- First, you must identify the root (always the first in Pre-order).
- Second, find that root in the In-order list to determine the boundaries.
- Third, split the In-order list into left and right components.
- Finally, recurse on those components.

📊 Fact Spotlight

Step	Action
Root Identification	Pre-order sequence (first element).
Partitioning	In-order sequence (split by root).

💡 Exam Strategy & Trivia

Tip

Common Pitfall: Trying to split the tree before identifying the root. You must identify the root first to know where to split the In-order sequence.

UPSC Poly. Lect. 10.03.2019

MEDIUM

A model which is used to understand the design of a data structure to indicate an implementation-independent view of the data structure is:

Linear data type

Non-linear data type

Abstract data type

Primitive data type

Explanation

Abstract Data Type (ADT) provides an implementation-independent view of a data structure.

MEDIUM

Linked list are not suitable data structure for which one of the following problems?

insertion sort

binary search

radix sort

polynomial manipulation

Explanation

Binary search requires random access, which a linked list does not provide.

Free Forever

Track Your Progress

You're Doing Great! 🎯

Unlimited PYQs Progress Tracking Mock Tests

✨ Free forever • No credit card • 2 sec signup with Google

Full Mock Tests

Take Full-Length Mock Tests

Test your complete preparation with timed mock tests. Get detailed analytics and compare scores with other aspirants.

Explore Test Series

All Chapters

Advance Computer Science

Fundamentals of Computer

513+ questions

Word Processing (MS Word)

457+ questions

Spreadsheet Software (MS Excel)

147+ questions

Presentation Software (MS PowerPoint)

162+ questions

DBMS Software (MS Access)

224+ questions

C and C++ Programming

Artificial Intelligence and Machine Learning

175+ questions

Python Programming

92+ questions

Blockchain Technology

83+ questions

Principles of Programming and OOPs

630+ questions

Data Structures and Algorithms

288+ questions

Current 14

Computer Organization and Operating System

302+ questions

Communication and Network Concepts

627+ questions

Network Security

97+ questions

Database Management System

223+ questions

System Analysis and Design

226+ questions

Internet of Things and its Application

318+ questions

Major Developments in IT

103+ questions

Pedagogy of Computer Science

119+ questions

Digital Logic Systems

268+ questions