Data Structures and Algorithms

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.

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.

An extended binary tree (also called a full binary tree or proper binary tree) is defined as a binary tree where every node has either 0 or 2 children - never just 1 child. A complete binary tree fills all levels except possibly the last, which must be left-filled. A binary search tree is ordered by key values, not by child count. Option C is correct.

Arrays are designed to store homogeneous data elements - all elements must be of the same type. Records can store heterogeneous data (different types), pointers store addresses (not data elements per se), and 'None' is incorrect. Therefore Arrays is the correct answer.

Records are designed to store heterogeneous data elements - fields can be of different types (e.g., name:string, age:integer, salary:decimal). Arrays require homogeneous elements. Pointers store addresses. Therefore Records is the correct answer.

Linear arrays are indexed structures because they allow direct access to any element using its index in constant time O(1). The index is used to calculate the memory address directly. Linked lists are sequential structures that require traversal from the head to access a specific element, making them non-indexed.

Binary search requires the search space/list to be sorted and allows random access to the middle element to achieve logarithmic time complexity. It does not require a mechanism to insert or delete elements; in fact, binary search is often performed on static arrays.

Binary search has O(log n) time complexity, which remains efficient even for large datasets. The efficiency depends on the logarithmic growth rate, not on a fixed number like 1000. Options A, B, and C are actual limitations: binary search requires sorted data and direct access to the middle element, which can be expensive to maintain with frequent insertions/deletions.

Two-dimensional arrays are commonly referred to as both tables (for tabular data representation) and matrices (especially in mathematical contexts involving rows and columns). Both terms describe the same conceptual structure of data arranged in a grid format with rows and columns.

The address of any array element is calculated as: Base Address + (Index - Lower Bound) × Word Size. For the 5th element, this is LOC(Array[5]) = Base(Array) + w(5 - lower bound), where w represents bytes per memory cell. Options B and C are incorrect because they omit the word size multiplier or use wrong bounds.

A deque (double-ended queue) specifically allows insertion and deletion at both ends. Stacks only allow operations at one end (LIFO), queues restrict insertion to rear and deletion to front (FIFO), and linked lists allow insertion/deletion anywhere but not with the same efficiency at both ends as a deque.