Data Structures and Algorithms Quiz

Merge sort has O(n log n) complexity because it divides the array in half log n times (the divide step) and merges n elements at each level (the conquer step). This gives n × log n operations.

Quick sort is a classic divide-and-conquer algorithm that works by selecting a pivot element and partitioning the array around it, then recursively sorting the sub-arrays. Bubble sort and insertion sort are incremental comparison-based sorts. Option D is incorrect because not all sorting algorithms use divide-and-conquer.

Recursion is when an algorithm calls itself directly or indirectly to solve a problem by breaking it down into smaller instances of the same problem. Option A is not a standard term. Option C is a notation for writing expressions. Option D is a type of algorithm for visiting nodes in a data structure, not a general concept.

In a threaded binary tree, null pointers are replaced with 'threads' that point to predecessor or successor nodes in the in-order traversal sequence. This allows efficient traversal without recursion or a stack. Option A (leaf) is a node with no children. Option B (branch) is not standard terminology. Option C (path) refers to a sequence of nodes.

In-order traversal of a binary search tree visits nodes in ascending order of their keys because of the BST property: left child < parent < right child. This is a fundamental property of BSTs. Option A is incorrect because regular binary trees have no ordering property. Option C is incorrect because heaps have different ordering properties.

Strings, lists, and stacks are all linear data structures where elements are arranged sequentially. Option D 'None of above' is correct because the question asks for a NON-linear data structure, but all options A, B, and C are linear types. Examples of non-linear structures would be trees, graphs, or heaps.

Strings, lists, and queues are all linear data structures where elements are accessed in sequential order. Linear structures have a single path to access elements (first-to-last or last-to-first). Since all three options (A, B, C) are linear data structures, option D 'All of above' is correct.

The depth of a complete binary tree is the number of levels from root to deepest leaf. For n nodes, the depth equals ⌊log₂n⌋ + 1 because a tree of depth d can hold at most 2^d - 1 nodes. This logarithmic relationship reflects how nodes double at each level in a perfect binary tree.

When representing an algebraic expression as a binary expression tree (2-tree), operands become external/leaf nodes and operators become internal nodes. This structure preserves evaluation order: children are evaluated before their parent operator, matching post-order traversal semantics.

Converting a binary tree to a 2-tree (extended binary tree) requires replacing every null child reference with an external node (leaf placeholder). This creates a strictly binary tree where every internal node has exactly two children, making path length analysis more tractable.

When extending a binary tree by adding external nodes for missing children, all original nodes become internal nodes of the extended tree. This is by definition: internal nodes have children (original or null placeholders), while new external nodes are the added leaf placeholders.

Given post-order DEBFCA of a binary tree, the root is A (last visited). From preorder ABDECF, A's left subtree is B-D-E and right is F-C. Post-order shows left subtree post-order is D-E-B, meaning B is root of left subtree with D and E as children. This uniquely determines the structure yielding preorder ABDECF.

In a min-heap or max-heap, the key property is that each node's value is greater than (max-heap) or less than (min-heap) all values in its subtree. This parent-child relationship must hold down the entire tree, not just comparing with one subtree or sibling.

In an undirected graph with edge e=[u,v], u and v share multiple relationships: they are the endpoints of edge e, they are adjacent vertices (connected by an edge), and they are neighbors (terms often used interchangeably in graph theory). All descriptions are correct.

A connected acyclic graph is the fundamental definition of a tree in graph theory. Such graphs are called trees, free trees (to distinguish from rooted trees), or tree graphs interchangeably. All terms refer to the same structure - minimally connected, maximally acyclic.

In a directed graph, edge e=(u,v) represents an ordered pair where u is the tail (start/predecessor) and v is the head (end/successor). This directionality means u is adjacent to v, but v is not adjacent to u in directed graphs (unless there's a reverse edge).

A complete graph is defined as a graph where every vertex is connected to every other vertex by a unique edge. If G has n vertices and every vertex is adjacent to all n-1 others, the graph is complete. This contrasts with isolated (no edges), finite (limited vertices), or strongly connected (directed graph concept).

A queue is a FIFO (First-In-First-Out) data structure where deletions occur only at the front and insertions only at the rear. This is fundamental to queue behavior - elements are processed in arrival order. Stacks use LIFO, deques allow operations at both ends, and BSTs don't enforce positional insertion/deletion.

An input-restricted deque allows deletions from both ends but restricts insertions to only one end. This is a specialized deque variant - unlike standard deques (full operations at both ends) or output-restricted deques (opposite restriction). Priority queues use different ordering principles entirely.

Trees are the standard data structure for representing hierarchical relationships because each node can have multiple children, forming a parent-child hierarchy. Deques (double-ended queues) are linear structures for adding/removing from both ends, not hierarchies. Priority queues are for ordered access by priority, not hierarchy. Option C is correct.