Data Structures and Algorithms

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.

Algorithm efficiency is measured by counting the number of key operations (like comparisons, assignments, etc.). Counting microseconds is machine-dependent, making it unreliable for comparing algorithms across different platforms.

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.

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.

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.