Data Structures Final Review
-
______ is a data structure in which elements are added to the rear and removed from the front. A First-In-First-Out (FIFO) structure
About This Quiz
The 'Data Structures Final Review' quiz assesses understanding of fundamental data structures like stacks and queues. It covers concepts such as LIFO and FIFO principles, abstract data types, and performance of operations in linked lists, essential for efficient programming and computer science education.
(167).webp "Data Structures Final Review - Quiz")
Quiz Preview
- 2.
To remove an elemnt from the end (queue)
-
Enqueue
-
Dequeue
Correct Answer
A. DequeueExplanation
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.Rate this question:
-
- 3.
In Stack Methods: ____ Inserts object X onto the stack.
-
PUSH(X)
-
POP()
-
SIZE()
-
IsStackEmpty()
-
TOP()
Correct Answer
A. PUSH(X)Explanation
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.Rate this question:
-
- 4.
______ hashing uses 2 hash funtions to calculate the probe value
Correct Answer
doubleExplanation
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.Rate this question:
- 5.
Inserting a node in an AVL tree will sometimes change the height of the tree
-
True
-
False
Correct Answer
A. TrueExplanation
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.Rate this question:
-
- 6.
A red-black tree is also a B.S.T.
-
True
-
False
Correct Answer
A. TrueExplanation
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.Rate this question:
-
- 7.
An enque is the opposite of a deque
-
True
-
False
Correct Answer
A. TrueExplanation
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.Rate this question:
-
- 8.
___ is the condition resulting when two or more keys produce the same hash location
Correct Answer
collisionExplanation
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.Rate this question:
- 9.
_____ is resolving a collison by computing a new hash location from a hash function that manipulates the original location rather than the elements key
Correct Answer
rehashingExplanation
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.Rate this question:
- 10.
The unique vertex in a rooted tree
Correct Answer
rootExplanation
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.Rate this question:
- 11.
In Stack Methods: ____ Returns a boolean inidcating if the stack is empty.
-
PUSH(X)
-
POP()
-
SIZE()
-
IsStackEmpty()
-
TOP()
Correct Answer
A. IsStackEmpty()Explanation
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.Rate this question:
-
- 12.
Which are the Queue Methods
-
Enqueue(X), Dequeue(), Size(), isQueueEmpty(), Front()
-
POP(), PUSH(X), SIZE(), isStackEmpty(), TOP()
-
Size(), Front(), Push(X), Pop()
Correct Answer
A. Enqueue(X), Dequeue(), Size(), isQueueEmpty(), Front()Explanation
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.Rate this question:
-
- 13.
An ordered tree in which each vertex has 0, 1, or 2 children
Correct Answer
Binary TreeExplanation
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.Rate this question:
- 14.
What is the In Order Traversal:
Correct Answer
6 13 17 27 33 42 48Explanation
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.Rate this question:
- 15.
Which are the Stack Methods
-
Enqueue(X), Dequeue(), Size(), isQueueEmpty(), Front()
-
POP(), PUSH(X), SIZE(), isStackEmpty(), TOP()
-
Size(), Front(), Push(X), Pop()
Correct Answer
A. POP(), PUSH(X), SIZE(), isStackEmpty(), TOP()Explanation
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.Rate this question:
-
- 16.
A Red-Black tree is an BST tree
-
True
-
False
Correct Answer
A. TrueExplanation
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.Rate this question:
-
- 17.
A queue is and ADT in which elemets are added and removed from one end only; first-in-first-out (FIFO) structure.
-
True
-
False
Correct Answer
A. TrueExplanation
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.Rate this question:
-
- 18.
To insert an element at the rear (queue)
-
Enqueue
-
Dequeue
Correct Answer
A. EnqueueExplanation
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.Rate this question:
-
- 19.
A node connected via edges to a higher node
Correct Answer
ChildExplanation
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.Rate this question:
- 20.
A Full Binary Tree in which all leaves have the same depth
-
Perfect Binary Tree
-
Full Binary Tree
Correct Answer
A. Perfect Binary TreeExplanation
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.Rate this question:
-
- 21.
LIFO structire stands for...
-
Last In Furthest Out
-
Least In First Out
-
Last In First Out
Correct Answer
A. Last In First OutExplanation
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.Rate this question:
-
- 22.
A _____ function used to manipulate the key of an element in a list to identify its location in the list
Correct Answer
hashExplanation
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.Rate this question:
- 23.
Insert, Append, Delete, and Next are all valid list operations.
-
True
-
False
Correct Answer
A. TrueExplanation
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.Rate this question:
-
- 24.
A node connected via edges to a lower node
Correct Answer
parentExplanation
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.Rate this question:
- 25.
Property of all trees
-
#Edges = #Nodes - 1
-
#Nodes = #Edges - 1
Correct Answer
A. #Edges = #Nodes - 1Explanation
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.Rate this question:
-
- 26.
A hash table tends to perform better overall (bot time and space) than an array, linked list, or balanced B.S.T.
-
True
-
False
Correct Answer
A. TrueExplanation
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.Rate this question:
-
- 27.
Reading a book (cover to cover) is an example of Post Order Traversal
-
True
-
False
Correct Answer
A. FalseExplanation
Pre orderRate this question:
-
- 28.
For a normal (double linked) binary tree, __ pointers are assigned to each node
Correct Answer
2Explanation
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.Rate this question:
- 29.
In Stack Methods: ____ removes the top object of the stack and returns it.
-
PUSH(X)
-
POP()
-
SIZE()
-
IsStackEmpty()
-
TOP()
Correct Answer
A. POP()Explanation
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.Rate this question:
-
- 30.
____ is the 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
Correct Answer
hashingExplanation
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.Rate this question:
- 31.
A node at level X is also said to be a depth of X
-
True
-
False
Correct Answer
A. TrueExplanation
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.Rate this question:
-
- 32.
The length of the path from the root to the vertext of interst
Correct Answer
DepthExplanation
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.Rate this question:
- 33.
The process of creating a B.S.T. (requires/does not require) sorting data.
-
Requires
-
Does Not Require
Correct Answer
A. RequiresExplanation
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.Rate this question:
-
- 34.
The tendency of elements to become unevenly distributed in the hash table
-
Clustering
-
Bucket
-
Linear Probing
-
Chain
Correct Answer
A. ClusteringExplanation
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.Rate this question:
-
- 35.
The name of the second child of a vertex on a binary tree
Correct Answer
Right ChildExplanation
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.Rate this question:
- 36.
_____ probing resolving a hash collision by generating pseudorandom hash values in successive applications of the rehash function
Correct Answer
randomExplanation
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.Rate this question:
- 37.
Postfix notation may not contain negative numbers
-
True
-
False
Correct Answer
A. TrueExplanation
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.Rate this question:
-
- 38.
Linear probing is not a good solution for clustering
-
True
-
False
Correct Answer
A. TrueExplanation
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.Rate this question:
-
- 39.
An ordered tree in which each vertex has either no children, one child, or two children
-
Sub Tree
-
Ordered Tree
-
Binary Tree
Correct Answer
A. Binary TreeExplanation
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.Rate this question:
-
- 40.
A post oder traversal may be used to evaluate an arithmetic expression
-
True
-
False
Correct Answer
A. TrueExplanation
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.Rate this question:
-
- 41.
Resolving a hash collision by sequentially searching a hash table beginning at the location returned by the hash function
-
Clustering
-
Bucket
-
Linear Probing
-
Chain
Correct Answer
A. Linear ProbingExplanation
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.Rate this question:
-
- 42.
The length of the longest path from a vertex to a leaf that is a descendent of the vertex
-
Height
-
Depth
Correct Answer
A. HeightExplanation
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.Rate this question:
-
- 43.
In Stack Methods: ____ returns the top object of the stack without removing it.
-
PUSH(X)
-
POP()
-
SIZE()
-
IsStackEmpty()
-
TOP()
Correct Answer
A. TOP()Explanation
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.Rate this question:
-
- 44.
Stack is an Abstract Data Type
-
True
-
False
Correct Answer
A. TrueExplanation
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.Rate this question:
-
- 45.
The "best case" search time for a B.S.T. is O(n). (where n = the number of nodes in the tree)
-
True
-
False
Correct Answer
A. FalseExplanation
^worst caseRate this question:
-
- 46.
Reading a book (cover to cover) is an example of Pre Order Traversal
-
True
-
False
Correct Answer
A. TrueExplanation
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".Rate this question:
-
- 47.
The DIR command in DOS (which returns fil/folder sizes) untilizes a ___ order traversal of the directory tree structure
Correct Answer
postExplanation
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.Rate this question:
- 48.
For a normal (double-linked) binary tree, 8 pointers are assigned to each node.
-
True
-
False
Correct Answer
A. FalseExplanation
4Rate this question:
-
- 49.
The minimum height of a 14-node B.S.T. is 5
-
True
-
False
Correct Answer
A. FalseExplanation
3Rate this question:
-
.png "What is the In Order Traversal:")
Quiz Review Timeline (Updated): Mar 4, 2024 +
Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.
-
Current Version
-
Mar 04, 2024Quiz Edited by
ProProfs Editorial Team -
Apr 26, 2011Quiz Created by
JererermyG
Back to top