HomeSubjectsUniversityBlogAbout

Non-Linear Data Structures

Topic in Data Structures & Algorithms

210 total MCQsShowing 30 with explanations10 Easy10 Medium10 Hard
Start Timed Quiz on Non-Linear Data StructuresBack to Data Structures & Algorithms

About This Topic

Non-linear data structures arrange elements hierarchically or as a network, so one element can link to several others, as in trees, heaps and graphs. Tree questions cover vocabulary such as root, leaf, sibling, height and depth, the fact that a tree with n nodes has n - 1 edges, and binary tree limits of two children per node. Binary search tree ordering, max-heaps and min-heaps with O(log n) insertion, and array-based heap storage follow. Graph items ask about directed versus undirected and weighted edges, self-loops, and the space trade-off between an adjacency matrix at O(V^2) and an adjacency list at O(V + E).

Below are 30 practice questions from a pool of 210 Non-Linear Data Structures MCQs, one of 12 topics in Data Structures & Algorithms. Each shows the correct answer with an explanation; when you are ready, take a timed quiz to test recall under exam conditions.

Practice Questions

Each question below shows the correct answer with a full explanation. Use these to build conceptual understanding before attempting a timed quiz.

Non-Linear Data StructuresEasy

Q1. What is a binary tree?

  1. A.A directed graph with no cycles at all
  2. B.A tree with exactly 2 total internal nodes
  3. C.A tree where each node has at most 2 children✓ Correct
  4. D.A tree where each node has at most 3 children

Explanation

A binary tree is a tree data structure where each node has at most two children, referred to as left and right child.

Report an error in this question

Non-Linear Data StructuresEasy

Q2. What is a graph in data structures?

  1. A.A chart used for data visualization
  2. B.A type of contiguous memory array
  3. C.A sequential linear data structure
  4. D.A collection of vertices and edges✓ Correct

Explanation

A graph is a non-linear data structure consisting of vertices (nodes) and edges (connections between vertices).

Report an error in this question

Non-Linear Data StructuresEasy

Q3. What is a heap?

  1. A.A type of directed graph with cycles
  2. B.A complete binary tree with heap property✓ Correct
  3. C.A sorted array-based storage structure
  4. D.A variant of a hash table with chains

Explanation

A heap is a complete binary tree where each node satisfies the heap property (max-heap: parent >= children, min-heap: parent <= children).

Report an error in this question

Non-Linear Data StructuresEasy

Q4. What is the root of a tree?

  1. A.The node with the most children
  2. B.The topmost node with no parent✓ Correct
  3. C.The node with no children at all
  4. D.The leftmost node in the tree

Explanation

The root is the topmost node in a tree that has no parent. All other nodes are descendants of the root.

Report an error in this question

Non-Linear Data StructuresEasy

Q5. What is the maximum number of nodes in a binary tree of height h?

  1. A.2^h - 1
  2. B.h^2
  3. C.2h
  4. D.2^(h+1) - 1✓ Correct

Explanation

A binary tree of height h can have at most 2^(h+1) - 1 nodes (when it is a complete/perfect binary tree, counting height from 0).

Report an error in this question

Non-Linear Data StructuresEasy

Q6. What is the degree of a vertex in an undirected graph?

  1. A.The assigned weight of the given vertex
  2. B.The number of edges incident to the vertex✓ Correct
  3. C.The total number of vertices in the graph
  4. D.The shortest path length from the vertex

Explanation

The degree of a vertex in an undirected graph is the number of edges connected to that vertex.

Report an error in this question

Non-Linear Data StructuresEasy

Q7. What is a leaf node?

  1. A.A node with two children
  2. B.A node with no children✓ Correct
  3. C.The root node itself
  4. D.A node with one child

Explanation

A leaf node (also called an external node) is a node that has no children.

Report an error in this question

Non-Linear Data StructuresEasy

Q8. What is a Binary Search Tree (BST)?

  1. A.A binary tree where left child > parent > right child
  2. B.A tree data structure with exactly two total nodes
  3. C.A binary tree where left child < parent < right child✓ Correct
  4. D.A balanced tree structure that is always complete

Explanation

In a BST, for each node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.

Report an error in this question

Non-Linear Data StructuresEasy

Q9. What is an undirected graph?

  1. A.A graph where edges have no direction✓ Correct
  2. B.A graph with no edges at all
  3. C.A hierarchical tree structure
  4. D.A graph where edges have direction

Explanation

In an undirected graph, edges have no direction; if there is an edge between A and B, you can traverse it in both directions.

Report an error in this question

Non-Linear Data StructuresHard

Q10. What is the time complexity of building a heap from an unsorted array of n elements?

  1. A.O(n log n)
  2. B.O(n)✓ Correct
  3. C.O(log n)
  4. D.O(n^2)

Explanation

Using the bottom-up heapify approach (Floyd's algorithm), a heap can be built in O(n) time, as most nodes are near the leaves.

Report an error in this question

Non-Linear Data StructuresHard

Q11. What is the time complexity of deleting the root from a max-heap of n elements?

  1. A.O(n log n)
  2. B.O(n)
  3. C.O(1)
  4. D.O(log n)✓ Correct

Explanation

Deleting the root involves replacing it with the last element and performing heapify-down, which takes O(log n).

Report an error in this question

Non-Linear Data StructuresMedium

Q12. What is the worst-case time complexity of search in an unbalanced BST?

  1. A.O(log n)
  2. B.O(n^2)
  3. C.O(1)
  4. D.O(n)✓ Correct

Explanation

An unbalanced BST can degrade to a linked list (skewed tree), making search O(n) in the worst case.

Report an error in this question

Non-Linear Data StructuresMedium

Q13. In a max-heap, where is the maximum element?

  1. A.At the root✓ Correct
  2. B.At the last level
  3. C.At a leaf node
  4. D.It could be anywhere

Explanation

In a max-heap, the maximum element is always at the root because every parent is greater than or equal to its children.

Report an error in this question

Non-Linear Data StructuresHard

Q14. What is a threaded binary tree?

  1. A.A tree where null pointers become in-order links✓ Correct
  2. B.A binary tree with multiple root nodes
  3. C.A tree with thread-safe atomic operations
  4. D.A tree used in multithreading concurrency

Explanation

In a threaded binary tree, null left/right pointers are replaced with pointers to the in-order predecessor/successor, enabling efficient traversal without a stack.

Report an error in this question

Non-Linear Data StructuresHard

Q15. In a directed graph with V vertices, what is the maximum number of edges?

  1. A.V^2
  2. B.V
  3. C.V(V-1)✓ Correct
  4. D.V(V-1)/2

Explanation

In a directed graph without self-loops, each pair of vertices can have two directed edges (one in each direction), giving V(V-1) maximum edges.

Report an error in this question

Non-Linear Data StructuresEasy

Q16. How is a graph typically represented?

  1. A.Using adjacency matrix or list✓ Correct
  2. B.Using singly linked lists only
  3. C.Using stack data structures
  4. D.Using simple arrays only

Explanation

Graphs are commonly represented using an adjacency matrix (2D array) or an adjacency list (array of lists).

Report an error in this question

Non-Linear Data StructuresHard

Q17. What is a B-tree of order m?

  1. A.A tree data structure with m distinct roots
  2. B.A self-balancing tree with at most m children✓ Correct
  3. C.A binary tree with exactly m total levels
  4. D.A graph with m connected components total

Explanation

A B-tree of order m is a self-balancing search tree where each node can have at most m children, commonly used in databases and file systems.

Report an error in this question

Non-Linear Data StructuresMedium

Q18. What type of graph has edges with associated weights?

  1. A.Weighted graph✓ Correct
  2. B.Directed graph
  3. C.Bipartite graph
  4. D.Complete graph

Explanation

A weighted graph assigns a numerical weight (cost, distance, etc.) to each edge.

Report an error in this question

Non-Linear Data StructuresHard

Q19. What is a bipartite graph?

  1. A.A graph divisible into two disjoint vertex sets✓ Correct
  2. B.A fully connected complete graph structure
  3. C.A graph with exactly two vertices in total
  4. D.A graph with exactly two connected components

Explanation

A bipartite graph's vertices can be partitioned into two sets such that every edge connects a vertex from one set to the other. It contains no odd-length cycles.

Report an error in this question

Non-Linear Data StructuresMedium

Q20. What is the space complexity of an adjacency matrix for a graph with V vertices?

  1. A.O(V)
  2. B.O(V + E)
  3. C.O(E)
  4. D.O(V^2)✓ Correct

Explanation

An adjacency matrix uses a V × V 2D array, requiring O(V^2) space regardless of the number of edges.

Report an error in this question

Non-Linear Data StructuresMedium

Q21. What is the in-order traversal of a BST with values 4, 2, 6, 1, 3, 5, 7 (root=4)?

  1. A.1, 2, 3, 4, 5, 6, 7✓ Correct
  2. B.4, 2, 1, 3, 6, 5, 7
  3. C.4, 2, 6, 1, 3, 5, 7
  4. D.1, 3, 2, 5, 7, 6, 4

Explanation

In-order traversal of a BST visits nodes in sorted (ascending) order: left, root, right.

Report an error in this question

Non-Linear Data StructuresHard

Q22. How many distinct BSTs can be formed with n distinct keys?

  1. A.2^n (powers of two)
  2. B.n^2 (square of n)
  3. C.C(n) the Catalan number✓ Correct
  4. D.n! (factorial of n)

Explanation

The number of structurally distinct BSTs with n keys is the n-th Catalan number: C(n) = (2n)! / ((n+1)! * n!).

Report an error in this question

Non-Linear Data StructuresMedium

Q23. What is the space complexity of an adjacency list for a graph with V vertices and E edges?

  1. A.O(E)
  2. B.O(V^2)
  3. C.O(V + E)✓ Correct
  4. D.O(V)

Explanation

An adjacency list stores V lists (one per vertex) with a total of E entries across all lists, giving O(V + E) space.

Report an error in this question

Non-Linear Data StructuresHard

Q24. What is the minimum number of nodes in an AVL tree of height h?

  1. A.N(h) = N(h-1) + N(h-2) + 1✓ Correct
  2. B.2^(h+1) - 1
  3. C.2^h
  4. D.h + 1

Explanation

The minimum number of nodes follows the recurrence N(h) = N(h-1) + N(h-2) + 1, similar to Fibonacci numbers.

Report an error in this question

Non-Linear Data StructuresMedium

Q25. What is the time complexity of searching in a balanced BST?

  1. A.O(log n)✓ Correct
  2. B.O(n log n)
  3. C.O(1)
  4. D.O(n)

Explanation

In a balanced BST, the height is O(log n), so search operations take O(log n) time.

Report an error in this question

Non-Linear Data StructuresMedium

Q26. What is a full binary tree?

  1. A.A tree with the maximum number of nodes
  2. B.A tree where every level is completely filled
  3. C.A tree where every node has 0 or 2 children✓ Correct
  4. D.A tree where all leaves are at same depth

Explanation

A full (or proper/strict) binary tree is one where every node has either 0 or 2 children, never just 1.

Report an error in this question

Non-Linear Data StructuresMedium

Q27. What is the time complexity of inserting an element into a max-heap?

  1. A.O(n)
  2. B.O(1)
  3. C.O(log n)✓ Correct
  4. D.O(n log n)

Explanation

Insertion into a heap involves placing the element at the end and bubbling up, which takes O(log n) due to the tree height.

Report an error in this question

Non-Linear Data StructuresMedium

Q28. What is a complete binary tree?

  1. A.A tree where every node has exactly 2 children always
  2. B.A tree where all leaf nodes are at the same level
  3. C.A tree with the maximum possible depth for its nodes
  4. D.A tree with all levels full except possibly the last level✓ Correct

Explanation

A complete binary tree has all levels fully filled except possibly the last level, which is filled from left to right.

Report an error in this question

Non-Linear Data StructuresHard

Q29. What is a Red-Black tree's maximum height for n nodes?

  1. A.n/2
  2. B.n
  3. C.log n
  4. D.2 log(n+1)✓ Correct

Explanation

A Red-Black tree guarantees height at most 2 log(n+1), ensuring O(log n) operations.

Report an error in this question

Non-Linear Data StructuresHard

Q30. What is the difference between a strongly connected and weakly connected directed graph?

  1. A.Strongly connected means directed paths exist between all pairs; weakly only without directions✓ Correct
  2. B.There is no meaningful difference between strongly and weakly connected directed graphs
  3. C.Strongly connected graphs always contain more edges than weakly connected directed graphs
  4. D.Weakly connected graphs always have more vertices and edges than strongly connected ones

Explanation

A strongly connected directed graph has a directed path between every pair of vertices. A weakly connected graph is connected only when edge directions are ignored.

Report an error in this question

More Data Structures & Algorithms Topics

Foundations of DS & Algorithms

Practice MCQs with explanations

Linear Data Structures

Practice MCQs with explanations

Searching Algorithms

Practice MCQs with explanations

Sorting Algorithms

Practice MCQs with explanations

Hashing

Practice MCQs with explanations

Tree Algorithms

Practice MCQs with explanations

Ready to test yourself on Non-Linear Data Structures?

Take a timed quiz drawn from 210+ questions on this topic. No signup required — your progress saves in your browser.

Start Non-Linear Data Structures Quiz