Computer Data Structure and Algorithm 2(TTA)

When new data are to be inserted into a data structure, but there is no available space, this situation is usually called "overflow." Overflow occurs when the data structure reaches its maximum capacity and cannot accommodate any more data. This can happen in various data structures such as arrays or queues. When an overflow occurs, it indicates that the data structure is full and cannot accept any additional data until some space is freed up.

Recursion is the correct answer because an algorithm that calls itself, either directly or indirectly, is known as a recursive algorithm. In recursion, a problem is divided into smaller subproblems, and the solution to each subproblem is obtained by solving smaller instances of the same problem. This process continues until a base case is reached, which allows the algorithm to terminate. Recursion is commonly used in programming to solve problems that can be broken down into smaller, similar subproblems.

Arrays cannot store non-homogeneous data elements because they require all elements to be of the same data type. In an array, each element occupies a fixed amount of memory space, and the data type determines the size of that space. Therefore, if non-homogeneous data elements were allowed, it would be difficult to allocate the appropriate amount of memory for each element. In contrast, records and pointers can store non-homogeneous data elements because they allow for different data types to be stored within a single structure or variable.

Queues are a type of data structure that allows deleting data elements from the front and inserting new elements at the rear. In a queue, the first element that is inserted is the first one to be removed, following the First-In-First-Out (FIFO) principle. This makes queues suitable for scenarios where elements need to be processed in the order they arrive, such as handling requests or tasks in a computer system. Stacks, on the other hand, follow the Last-In-First-Out (LIFO) principle, where the last element inserted is the first one to be removed. Deques and binary search trees do not have the specific functionality of deleting from the front and inserting at the rear.

In a binary search tree, the in-order traversal will yield a sorted listing of elements. This is because the in-order traversal visits the left subtree first, then the root, and finally the right subtree. Since the elements in a binary search tree are arranged in a specific order where all elements in the left subtree are smaller than the root, and all elements in the right subtree are greater than the root, the in-order traversal will produce a sorted listing of the elements. Therefore, the correct answer is binary search trees.

The situation when in a linked list START=NULL is referred to as underflow. This means that the linked list is empty and there are no elements present in it. In a linked list, the START pointer points to the first node of the list. When START=NULL, it indicates that there are no nodes in the list, resulting in underflow.

The correct answer is "both e begins at u and ends at v and u is processor and v is successor". This answer combines both conditions mentioned in the question. It states that e begins at u and ends at v, indicating the direction of the edge. Additionally, it states that u is the processor and v is the successor, implying the relationship between the two vertices in terms of their roles or positions in a system or network.

The name "FIFO lists" does not relate to stacks because stacks follow the LIFO (Last-In, First-Out) principle, while FIFO (First-In, First-Out) is the principle followed by queues. Stacks are a data structure where the last element added is the first one to be removed, while queues are a data structure where the first element added is the first one to be removed. Therefore, "FIFO lists" is not a name that relates to stacks.

Binary search algorithm cannot be applied to a sorted linked list because binary search requires random access to elements, which is not possible in a linked list. Binary search relies on dividing the search space in half at each step, but in a linked list, accessing elements in the middle of the list is not efficient. In contrast, binary search can be applied to sorted binary trees, sorted linear arrays, and pointer arrays because these data structures allow for efficient random access to elements.

A graph is said to be complete if every node in the graph is adjacent to every other node in the graph. This means that there is an edge connecting every pair of distinct nodes in the graph. In other words, there are no missing edges in a complete graph. Therefore, the given answer "complete" accurately describes the property of a graph where every node is adjacent to every other node.

A variable P is called a pointer if it contains the address of an element in DATA. This means that P is able to store the memory address of a specific element within the DATA. A pointer does not necessarily point to the address of the first element in DATA, nor does it store the entire DATA and its address. Its main purpose is to hold the address of a specific element within the DATA.

An input-restricted deque is a data structure that allows deletions at both ends of the list but only allows insertion at one end. This means that elements can be removed from either the front or the back of the list, but new elements can only be added to one end of the list, typically the front. This restriction on insertion allows for efficient removal operations while maintaining a specific order of elements in the list.

A connected graph T without any cycles is called a tree graph because it resembles a tree structure, with a single root node and branches extending outwards. It is also referred to as a free tree because it is free from any loops or cycles. Therefore, all of the given options - tree graph, free tree, and a tree - are correct descriptions for this type of graph.

A deque, or double-ended queue, is a data structure that allows elements to be added or removed at both ends. This means that elements can be added or removed at either end, but not in the middle. Linked lists, stacks, and queues also allow elements to be added or removed, but they do not have the capability to do so at both ends. Therefore, the correct answer is deque.

In a binary tree, certain null entries are replaced by special pointers called "thread" which point to nodes higher in the tree for efficiency. This allows for faster traversal of the tree as it eliminates the need to backtrack or navigate through unnecessary null entries. By using threads, the tree structure becomes more compact and efficient in terms of memory usage and traversal operations.

The inorder traversal of a binary tree visits the left subtree, then the root, and finally the right subtree. In this case, the inorder traversal resulted in E A C K F H D B G. The preorder traversal visits the root first, then the left subtree, and finally the right subtree. Therefore, the correct preorder traversal would be FAEKCDHGB.

An extended binary tree is a binary tree in which every node has either zero or two children. This means that there are no nodes with only one child in an extended binary tree. Therefore, the given answer is correct.

Quick sort is a sorting algorithm that follows the divide-and-conquer approach. It works by selecting a pivot element and partitioning the array into two sub-arrays, one with elements smaller than the pivot and the other with elements larger than the pivot. This process is recursively applied to the sub-arrays until the entire array is sorted. Therefore, Quick sort is the correct answer as it exemplifies the divide-and-conquer type of sorting algorithm.

The correct answer is "all of these" because each data item in a record may indeed be a group item composed of sub-items, which are called elementary items. Additionally, indecomposable items are also referred to as atoms, and scalars are another term used to describe these items. Therefore, all three options are correct and applicable in this context.

A priority queue is suitable for representing a hierarchical relationship between elements. In a priority queue, each element is assigned a priority value, and the elements are organized in such a way that the element with the highest priority value is always at the front of the queue. This allows for efficient retrieval of the highest priority element, making it suitable for representing a hierarchical relationship where certain elements have higher priority than others. A deque (double-ended queue) does not inherently have a notion of priority, and therefore may not be suitable for representing a hierarchical relationship.

All the options given in the question - Strings, Lists, and Stacks - are linear data structures because they organize data in a sequential manner. However, the correct answer is "None of these" because all the options mentioned are linear data structures, and the question asks for a non-linear data structure. Non-linear data structures, such as trees and graphs, do not organize data in a sequential manner and allow for more complex relationships between data elements.

Records are a data structure that store homogeneous data elements. Unlike arrays, which store elements of the same data type, records can store elements of different data types. Records are often used to represent a collection of related data fields, such as a person's name, age, and address. Therefore, records are the correct answer for this question.

None of the options provided is a two way list. A two way list, also known as a doubly linked list, is a type of linked list where each node contains references to both the previous and next nodes in the list. However, none of the given options mention this characteristic.

None of the given options (Strings, Lists, Stacks) are linear data structures. Strings are a sequence of characters and not a data structure. Lists and Stacks are both examples of linear data structures, but they are not the only types. Other linear data structures include arrays, queues, and linked lists. Therefore, the correct answer is "None of these" as there are other linear data structures besides the ones mentioned in the options.

The terms "push" and "pop" are commonly used in the context of stacks. In a stack, elements are added or removed from one end only. The "push" operation adds an element to the top of the stack, while the "pop" operation removes the top element from the stack. Arrays, lists, and stacks are all data structures, but the specific operations of "push" and "pop" are typically associated with stacks.