Data & File Structure Exam Overview
Uploaded by
Adhikari SushilData & File Structure Exam Overview
Uploaded by
Adhikari SushilCommon questions
Powered by AI2-3 trees differ from binary search trees by allowing nodes to contain two or three children and one or two keys, maintaining sorted order within nodes. This structure inherently guarantees balance, avoiding degradation to linked list forms as seen in unbalanced binary search trees. 2-3 trees restructure only when nodes exceed three children or keys, promoting efficient operations and ensuring balanced height and improved search times. Unlike AVL or Red-Black trees, 2-3 trees maintain balance through node key management rather than external re-balancing rotations .
A priority queue is most efficiently implemented using a heap structure due to its ability to maintain the order of elements according to priority with optimal time complexities for insertion and removal. An example usage is in task scheduling systems where higher-priority tasks are dequeued ahead of others regardless of their arrival times. Using a max-heap allows quick access to the highest-priority task, while a min-heap can provide the lowest-priority element. This implementation ensures efficient operations suited for dynamic datasets .
Fundamental file processing operations include opening, reading, writing, closing, and deleting files. Physical files refer to the actual storage of data on a hardware medium, while logical files represent the abstracted way users and programs interact with stored data. These operations abstract physical data handling into logical processes, making data manipulation intuitive and efficient for users and applications. Understanding this separation enables efficient file system management and data integrity across various storage media .
The primary advantage of linked lists over arrays is their dynamic sizing capability, allowing efficient insertions and deletions without resizing. Linked lists can save memory compared to fixed-size arrays due to this flexibility. However, linked lists have disadvantages such as higher memory usage per element because of the need to store pointers, and they often have slower access times due to non-contiguous memory storage, requiring traversal from the head to access a specific element, unlike direct indexing in arrays .
Sparse matrices can be represented using linked lists by creating a node for each non-zero element, which stores the element’s value, row, and column indices. Each node is linked sequentially according to row and column order. To add two sparse matrices represented as linked lists, traverse both lists comparing row and column indices. If indices match, add the values; if not, append the node from the matrix with the smaller index to the result list. Continue until both lists are exhausted. This method efficiently handles matrices with a large number of zero elements .
Divide and Conquer sorting involves recursively breaking down the dataset into smaller subsets until manageable units are obtained, each of which can be sorted simply. These units are then combined in a manner that results in a complete sorted dataset. Applying this to the sequence 13, 81, 92, 43, 65, 31, 57, 26, 26, 75, 0, the dataset is divided into halves, each sorted by further splits, with iterative merging leading to a completely sorted array. This technique is fundamental to algorithms like Merge Sort .
To restore the balance in an AVL tree after inserting or deleting a node, rotations are performed to maintain the height difference of no more than one between left and right subtrees. For insertion, a single or double rotation (left-right or right-left) is applied based on the imbalance pattern detected (left-left, left-right, etc.). Example: inserting a node causing left-right imbalance requires left rotation on the node's left child followed by right rotation on the root. Similarly, deletions causing imbalance undergo appropriate rotations depending on which side the additional node depth affects .
A double-ended queue (deque) allows insertion and deletion of elements at both ends, offering more flexibility compared to regular queues. This can be implemented using a linked list where nodes are added or removed at both the head and tail, maintaining efficient operations for operations that involve both ends. Deques support bidirectional iteration crucial for algorithms that require reversed processes, thus providing versatile solutions to symmetrical data processing tasks .
Data on magnetic tapes is organized sequentially, with blocks of data separated by inter-block gaps for proper data retrieval. The block factor (B.F) affects storage efficiency; a larger B.F reduces the number of gaps, minimizing wasted space. For instance, storing a large mailing list file with inter-block gaps of 0.3 inches requires precise calculations considering tape density and block sizes to appropriately size the necessary storage length. Efficient block usage maximizes data storage capability on accessible length of tape .
Infix to postfix conversion involves rearranging operators in relation to operands by following the precedence and associativity rules and utilizing a stack data structure. For (A-B/C)*(D*E-F), push operands directly to the output, push lower precedence operators from the stack when encountering a higher precedence one, and use a stack to maintain order for parentheses. The conversion steps for this expression result in: ABC/-DE*F-* when traced stepwise using a stack, ensuring operator precedence and correct associative handling .