Data Structures Final Review

A queue is a data structure that follows the First-In-First-Out (FIFO) principle, where elements are added to the rear and removed from the front. This means that the element that is added first will be the first one to be removed. It operates like a queue of people waiting in line, where the person who arrives first is the first one to be served and leaves the line first. The queue data structure is commonly used in various applications such as job scheduling, message passing, and breadth-first search algorithms.

The correct answer is "Dequeue" because to remove an element from the end of a queue, we need to dequeue it. Dequeuing means removing an element from the front of the queue. Since a queue follows the FIFO (First-In-First-Out) principle, the element that was added first will be removed first. Therefore, to remove an element from the end of the queue, we need to dequeue it.

The correct answer is PUSH(X) because the PUSH operation is used to insert an object X onto the stack. This operation adds the element to the top of the stack, making it the new top element.

Double hashing uses two hash functions to calculate the probe value. The first hash function is used to determine the initial position, and if that position is already occupied, the second hash function is used to calculate the next position to probe. This technique helps to resolve collisions and distribute the elements evenly in the hash table.

When a node is inserted into an AVL tree, it may cause the tree to become unbalanced, which in turn may change the height of the tree. This is because AVL trees are self-balancing binary search trees that maintain a balance factor for each node, which is the difference between the heights of its left and right subtrees. If the balance factor of a node becomes greater than 1 or less than -1, the tree needs to be rebalanced by performing rotations. This rebalancing process can change the height of the tree as nodes are shifted and rearranged to maintain the balance factor constraint. Therefore, inserting a node in an AVL tree can indeed change the height of the tree.

A red-black tree is a type of self-balancing binary search tree (B.S.T.) that maintains balance by ensuring that the tree height is always logarithmic. Therefore, all properties of a binary search tree, such as the left subtree containing nodes with smaller values and the right subtree containing nodes with larger values, still hold true for a red-black tree. Hence, the statement is true.

An enqueue operation adds an element to the end of a queue, while a dequeue operation removes an element from the front of the queue. On the other hand, a deque (double-ended queue) allows elements to be added or removed from both ends. Therefore, an enqueue operation is indeed the opposite of a dequeue operation, making the statement "An enque is the opposite of a deque" true.

Collision is the condition that occurs when two or more keys in a hash table produce the same hash location. In a hash table, each key is mapped to a specific index using a hash function. However, due to the limited number of possible hash locations, it is possible for different keys to map to the same index. This is known as a collision. Collisions need to be resolved in order to maintain the integrity and efficiency of the hash table.

Rehashing is the process of resolving a collision by computing a new hash location from a hash function that manipulates the original location rather than the element's key. This technique is used when two or more elements in a hash table have the same hash value, causing a collision. By applying a different hash function or modifying the original hash value, rehashing allows for the redistribution of elements to different locations in the hash table, reducing the likelihood of collisions and improving the efficiency of the data structure.

In a rooted tree, the root is the only vertex that has no incoming edges. It is the starting point of the tree and serves as the common ancestor for all other vertices. This unique vertex is responsible for giving the tree its hierarchical structure, as all other vertices are connected to it through edges. Therefore, the root is the correct answer for the given question.

The method "isStackEmpty()" returns a boolean indicating if the stack is empty. This means that when called, the method will check if there are any elements in the stack and return true if there are no elements, indicating that the stack is empty. Conversely, it will return false if there are elements in the stack, indicating that it is not empty.

The correct answer includes the methods Enqueue(X), Dequeue(), Size(), isQueueEmpty(), and Front(). These methods are commonly used in queue data structures. Enqueue(X) is used to add an element to the rear of the queue, Dequeue() is used to remove an element from the front of the queue, Size() returns the number of elements in the queue, isQueueEmpty() checks if the queue is empty, and Front() returns the element at the front of the queue without removing it.

A binary tree is an ordered tree where each vertex can have 0, 1, or 2 children. This means that each vertex in the tree can have either no children, one child, or two children. The term "binary" refers to the fact that each vertex has a maximum of two children. Therefore, the given answer "Binary Tree" accurately describes an ordered tree with these characteristics.

The in-order traversal is a method of traversing a binary tree where the left subtree is visited first, followed by the root node, and then the right subtree. In this case, the given sequence 6 13 17 27 33 42 48 represents the in-order traversal of a binary tree. The numbers are arranged in ascending order, indicating that the left subtree contains smaller values, while the right subtree contains larger values.

The given methods POP(), PUSH(X), SIZE(), isStackEmpty(), and TOP() are the stack methods. POP() is used to remove the top element from the stack, PUSH(X) is used to add an element X to the top of the stack, SIZE() is used to determine the number of elements in the stack, isStackEmpty() checks if the stack is empty, and TOP() returns the top element of the stack without removing it. These methods are commonly used in stack data structures to manipulate and retrieve data.

A Red-Black tree is a type of binary search tree (BST) that has additional properties and rules for maintaining balance and ensuring efficient operations. It follows the properties of a BST, such as having a left child with a smaller value and a right child with a larger value. Therefore, the statement "A Red-Black tree is a BST tree" is true because a Red-Black tree is a specific implementation of a BST.

The given statement accurately describes the characteristics of a queue. In a queue, elements are added at one end (rear) and removed from the other end (front) in a first-in-first-out (FIFO) manner. This means that the element that is added first will be the first one to be removed. Therefore, the statement is true.

Enqueue is the correct answer because it refers to the operation of adding an element to the rear of a queue. In a queue, elements are added at the rear and removed from the front, following the First-In-First-Out (FIFO) principle. Therefore, Enqueue accurately describes the action of inserting an element at the rear of the queue. Dequeue, on the other hand, refers to removing an element from the front of the queue, so it is not the appropriate choice for this scenario.

The term "child" is used to describe a node that is connected to a higher node via edges. In a hierarchical structure, such as a tree, the child node is located below and is directly connected to its parent node. The child node is dependent on the parent node and is considered to be at a lower level in the hierarchy.

A perfect binary tree is a type of full binary tree in which all leaves have the same depth. In other words, every level of the tree is completely filled with nodes, and all leaf nodes are at the same level. This means that every parent node has exactly two children, except for the leaf nodes. Therefore, a perfect binary tree satisfies the given condition of having all leaves at the same depth.

LIFO structure stands for "Last In First Out". This means that the last item that is added to the structure will be the first one to be removed. It follows a stack-like behavior where the most recently added element is the first one to be accessed or processed. This concept is commonly used in data structures such as stacks, where the last item pushed onto the stack is the first one to be popped off.

A hash function is used to manipulate the key of an element in a list in order to identify its location in the list. A hash function takes an input, typically the key of the element, and applies a mathematical algorithm to generate a unique hash value. This hash value is then used as an index to store or retrieve the element in the list. The purpose of a hash function is to efficiently distribute the elements across the list, reducing the time complexity for operations like insertion, deletion, and search.

The statement is true because "Insert," "Append," "Delete," and "Next" are all commonly used operations when working with lists. "Insert" is used to add an element at a specific position in the list, "Append" is used to add an element at the end of the list, "Delete" is used to remove an element from the list, and "Next" is used to access the next element in the list. Therefore, all four operations mentioned are valid list operations.

The correct answer is "parent" because in a hierarchical structure, a node connected via edges to a lower node is typically referred to as the parent node. The parent node is the one that is higher in the hierarchy and has a connection to one or more lower nodes. It provides a way to organize and structure the relationship between nodes in a hierarchical manner.

The given statement is a property of all trees. In a tree, the number of edges is always one less than the number of nodes. This can be explained by considering that each edge connects two nodes, so if we have n nodes in a tree, there will be n-1 edges connecting them. Therefore, the correct answer is #Edges = #Nodes - 1.

A hash table is a data structure that allows for efficient storage and retrieval of key-value pairs. It uses a hash function to map keys to specific indexes in an array, which allows for constant time complexity for insertion, deletion, and retrieval operations on average. Compared to an array, linked list, or balanced binary search tree (B.S.T.), a hash table generally has better performance in terms of both time and space efficiency. This is because the hash function allows for direct access to the desired element, eliminating the need for traversal or sorting operations. Therefore, the statement "A hash table tends to perform better overall (both time and space) than an array, linked list, or balanced B.S.T." is true.

Pre order

In a normal (double linked) binary tree, each node has two pointers assigned to it. These two pointers are used to connect the node to its left child and its right child. This allows for efficient traversal and manipulation of the tree structure.

The function POP() is used to remove the top object of the stack and return it. This operation is commonly referred to as "popping" an element from the stack. It is an essential method in stack data structures as it allows for the retrieval and removal of the most recently added element, maintaining the LIFO (Last-In-First-Out) principle of stacks.

Hashing is a technique used for inserting and accessing elements in a list in a relative constant time by manipulating the key to identify its location in the list. It involves applying a hash function to the key, which generates a unique hash value. This hash value is then used as an index to store or retrieve the element in the list. By using this technique, the time complexity for insertion and retrieval operations becomes constant, regardless of the size of the list.

A node at level X in a binary tree refers to its position or height within the tree. The depth of a node also represents its position or height within the tree. Therefore, it is correct to say that a node at level X is also said to be at a depth of X.

The term "depth" refers to the length of the path from the root of a tree to a specific vertex of interest. In a tree structure, each vertex has a level or depth assigned to it, indicating how many edges are traversed from the root to reach that vertex. Therefore, the answer "Depth" accurately describes the length of the path from the root to the vertex of interest in a tree.

Creating a Binary Search Tree (B.S.T.) requires sorting data. This is because in a B.S.T., the left child node of a parent node must have a smaller value, while the right child node must have a larger value. To maintain this property, the data needs to be sorted before inserting it into the tree. If the data is not sorted, the B.S.T. may not function correctly, leading to incorrect search or traversal operations. Therefore, sorting the data is necessary in order to create a valid B.S.T.

Clustering refers to the tendency of elements to become unevenly distributed in a hash table. It occurs when multiple elements hash to the same location, causing the formation of clusters. This can lead to performance issues as it increases the likelihood of collisions and can result in longer search times. To mitigate clustering, various techniques can be used such as rehashing, resizing the hash table, or using alternative collision resolution methods like chaining or linear probing.

The correct answer is "Right Child" because in a binary tree, each vertex can have at most two children - a left child and a right child. The name "Right Child" refers to the child of a vertex that is located on the right side when looking at the tree structure. This child is connected to the vertex through its right branch.

Random probing is a technique used to resolve hash collisions by generating pseudorandom hash values in successive applications of the rehash function. Instead of linearly probing through the hash table, random probing selects a random offset to probe for an empty slot when a collision occurs. This helps to distribute the collided keys more evenly throughout the hash table, reducing the chances of further collisions and improving the overall performance of the hash table.

The statement is true because in postfix notation, negative numbers are represented by using the minus sign (-) as a binary operator to subtract a number from another. Therefore, negative numbers themselves cannot be directly represented in postfix notation.

Linear probing is not a good solution for clustering because it can lead to clustering, where consecutive elements are stored in close proximity to each other. This can result in poor performance and increased search time as the number of elements increases. Additionally, linear probing does not handle collisions efficiently, as it simply looks for the next available slot in the hash table, which can further contribute to clustering. Other collision resolution techniques, such as chaining or quadratic probing, are generally considered better options for handling clustering in hash tables.

A binary tree is a type of ordered tree in which each vertex can have either no children, one child, or two children. In a binary tree, each vertex is called a node and it can have at most two children, referred to as the left child and the right child. This means that every node in a binary tree can have either 0, 1, or 2 children, making it different from other types of ordered trees where a node can have more than two children. Therefore, the given answer, "Binary Tree," accurately describes the characteristics of an ordered tree with these specific child constraints.

A post order traversal is a way of traversing a binary tree where the left subtree is visited first, then the right subtree, and finally the root node. This traversal can be used to evaluate an arithmetic expression because it ensures that the operands of an operator are visited before the operator itself. This allows for the expression to be evaluated in the correct order, following the rules of arithmetic. Therefore, the statement "A post order traversal may be used to evaluate an arithmetic expression" is true.

Linear probing is a method used to resolve hash collisions in a hash table. When a collision occurs, linear probing involves sequentially searching the hash table starting from the location returned by the hash function. It checks the next available slot in the table until an empty slot is found, allowing the collided item to be placed there. This process helps to avoid clustering, where multiple items are clustered together in the table, and instead distributes the items more evenly across the table.

The length of the longest path from a vertex to a leaf that is a descendant of the vertex is referred to as the height of the vertex. The height of a vertex represents the maximum number of edges that need to be traversed to reach a leaf node starting from that vertex. It is important to note that the height of a tree is determined by the height of its root node.

The TOP() method returns the top object of the stack without removing it. This means that it allows us to access the element that is currently at the top of the stack without modifying the stack itself.

The statement is true because a stack is indeed an abstract data type. An abstract data type refers to a data structure that is defined by its behavior and not by its implementation. A stack follows the Last-In-First-Out (LIFO) principle, where the last element added to the stack is the first one to be removed. This behavior is independent of how the stack is actually implemented in a programming language or system. Therefore, a stack can be considered an abstract data type.

^worst case

Pre-order traversal is a method used in tree traversal algorithms, where the root node is visited first, followed by the left subtree, and then the right subtree. In the context of reading a book, starting from the cover and going through each page until the end can be considered as a pre-order traversal. The cover represents the root node, and each subsequent page represents the left and right subtrees. Therefore, reading a book from cover to cover aligns with the concept of pre-order traversal, making the answer "True".

The DIR command in DOS utilizes a post order traversal of the directory tree structure. In a post order traversal, the algorithm visits the left subtree, then the right subtree, and finally the root node. This means that the command will first list the files and folders in the left subtree, then in the right subtree, and finally the current directory. This order allows for the sizes of all files and folders to be accurately calculated and displayed.

4

3

A descendant refers to a child, grandchild, great-grandchild, or any subsequent generation of a specific vertex. It signifies the lineage or offspring that can be traced back to a particular vertex. This term is commonly used in genealogy or family trees to describe the relationship between different generations.