UGC NET Computer Science Data Structures and Algorithms Syllabus

Data Structures and Algorithms syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Data Structures and Algorithms in UGC NET Computer Science, not a summary of it.

1. 1

   Data Structures

   11 topics

   • Arrays and their Applications
   • Sparse Matrix
   • Stacks
   • Queues
   • Priority Queues
   • Linked Lists
   • Trees
     • Binary Tree
     • Threaded Binary Tree
     • Binary Search Tree
     • AVL Tree
     • B Tree
     • B+ Tree
     • B* Tree
   • Forest
   • Data Structure for Sets
   • Graphs
   • Sorting and Searching Algorithms
     • Hashing
2. 2

   Performance Analysis of Algorithms and Recurrences

   3 topics

   • Time and Space Complexities
   • Asymptotic Notation
   • Recurrence Relations
3. 3

   Design Techniques

   5 topics

   • Divide and Conquer
   • Dynamic Programming
   • Greedy Algorithms
   • Backtracking
   • Branch and Bound
4. 4

   Lower Bound Theory

   2 topics

   • Comparison Trees
   • Lower Bounds through Reductions
5. 5

   Graph Algorithms

   5 topics

   • Breadth-First Search
   • Depth-First Search
   • Shortest Paths
   • Maximum Flow
   • Minimum Spanning Trees
6. 6

   Complexity Theory

   2 topics

   • P and NP Class Problems
   • NP-completeness and Reducibility
7. 7

   Selected Topics

   4 topics

   • Number Theoretic Algorithms
   • Polynomial Arithmetic
   • Fast Fourier Transform
   • String Matching Algorithms
8. 8

   Advanced Algorithms

   3 topics

   • Parallel Algorithms for Sorting, Searching and Merging
   • Approximation Algorithms
   • Randomized Algorithms

Data Structures and Algorithms flashcards for UGC NET Computer Science

19 of 69 cards from the Data Structures and Algorithms deck — real questions with worked answers.

1. What is the time complexity to access an element by index in an array, and why?

   O(1). Arrays store elements in contiguous memory, so the address of element i is computed directly as base + i × element_size.

2. What is a sparse matrix, and what are two common compact storage formats for it?

   A matrix in which most elements are zero. Common storage formats: the triplet/coordinate form (row, column, value lists) and linked-list representation; compressed forms include CSR (Compressed Sparse Row) and CSC.

3. What principle governs a stack, and what are its two primary operations?

   LIFO (Last In, First Out). Primary operations: push (add to top) and pop (remove from top), both O(1); often with peek/top.

4. What principle governs a queue, and what are its two primary operations?

   FIFO (First In, First Out). Primary operations: enqueue (add at rear) and dequeue (remove from front), both O(1).

5. What is a circular queue and what problem does it solve?

   A queue implemented on a fixed array where the rear wraps around to the front using modulo arithmetic. It solves the wasted-space problem of a linear array queue where dequeued slots cannot be reused.

6. What is a priority queue, and what data structure typically implements it efficiently?

   An abstract structure where each element has a priority and the highest- (or lowest-) priority element is served first. Typically implemented with a binary heap giving O(log n) insert and extract-min/max, and O(1) find-min/max.

7. In a binary min-heap stored in an array (1-indexed), what are the indices of the parent and children of node i?

   Parent = floor(i/2); left child = 2i; right child = 2i+1.

8. What is the difference between a singly linked list and a doubly linked list?

   A singly linked list node has one pointer (to the next node), allowing forward traversal only. A doubly linked list node has two pointers (next and previous), allowing both forward and backward traversal at the cost of extra memory.

9. What is the time complexity to insert a node at the head of a singly linked list versus at the tail (no tail pointer)?

   Insert at head: O(1). Insert at tail without a tail pointer: O(n) because you must traverse to the last node.

10. Define a binary tree and a complete binary tree.

    A binary tree is a tree where each node has at most two children. A complete binary tree is one in which all levels are completely filled except possibly the last, which is filled from left to right.

11. What is the maximum number of nodes in a binary tree of height h (root at height 0)?

    2^(h+1) − 1 nodes.

12. What property defines a Binary Search Tree (BST)?

    For every node, all keys in its left subtree are smaller and all keys in its right subtree are larger than the node's key (no duplicates), making in-order traversal yield sorted order.

13. What is an AVL tree and what is its balance condition?

    A self-balancing BST in which, for every node, the heights of the left and right subtrees differ by at most 1 (balance factor ∈ {−1, 0, +1}). Rotations restore balance, keeping height O(log n).

14. What are the three depth-first tree traversals and their node-visit orders?

    Preorder: Root, Left, Right. Inorder: Left, Root, Right. Postorder: Left, Right, Root.

15. What is a forest in graph/tree terminology?

    A forest is a disjoint collection (set) of trees, i.e., an acyclic graph that may be disconnected. Removing the root of a tree yields a forest of its subtrees.

16. What is the Union-Find (Disjoint Set) data structure used for, and what two optimizations make it near-constant time?

    It maintains a partition of elements into disjoint sets supporting union and find operations. Optimizations: union by rank/size and path compression, giving near-O(α(n)) amortized time (inverse Ackermann).

17. What is the difference between the adjacency matrix and adjacency list representations of a graph?

    Adjacency matrix uses O(V²) space with O(1) edge lookup; good for dense graphs. Adjacency list uses O(V+E) space and is efficient for sparse graphs but edge lookup is O(degree).

18. State the relationship between the sum of vertex degrees and the number of edges in an undirected graph (Handshaking Lemma).

    The sum of all vertex degrees equals twice the number of edges: Σ deg(v) = 2E. Consequently the number of odd-degree vertices is always even.

19. What is the worst-case and average-case time complexity of Quicksort?

    Average case: O(n log n). Worst case: O(n²), occurring when the pivot is consistently the smallest or largest element (e.g., already-sorted input with a poor pivot).

See more Data Structures and Algorithms flashcards →

Planning Data Structures and Algorithms for UGC NET Computer Science

Data Structures and Algorithms (UGC NET Computer Science) FAQ