# Data Structures Final Review

Approved & Edited by ProProfs Editorial Team
The editorial team at ProProfs Quizzes consists of a select group of subject experts, trivia writers, and quiz masters who have authored over 10,000 quizzes taken by more than 100 million users. This team includes our in-house seasoned quiz moderators and subject matter experts. Our editorial experts, spread across the world, are rigorously trained using our comprehensive guidelines to ensure that you receive the highest quality quizzes.
| By JererermyG
J
JererermyG
Community Contributor
Quizzes Created: 1 | Total Attempts: 110
Questions: 81 | Attempts: 110

Settings

• 1.

### Stack is an Abstract Class

• A.

True

• B.

False

B. False
Explanation
The statement "Stack is an Abstract Class" is incorrect. A stack is a data structure that follows the LIFO (Last In, First Out) principle, where elements are added and removed from only one end. In programming, a stack can be implemented using an array or a linked list. It is not an abstract class itself, but rather a concept that can be implemented using different programming languages and paradigms.

Rate this question:

• 2.

### Stack is an Abstract Data Type

• A.

True

• B.

False

A. True
Explanation
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:

• 3.

### Pez Dispenser Anaolgy

• A.

Queue

• B.

Stack

• C.

Array

B. Stack
Explanation
The given options, "Queue", "Stack", and "Array", are all data structures. A stack is a data structure that follows the Last-In-First-Out (LIFO) principle, meaning the last element added to the stack will be the first one to be removed. This analogy is similar to a Pez dispenser, where the last candy added is the first one to be dispensed. On the other hand, a queue follows the First-In-First-Out (FIFO) principle, and an array is a collection of elements stored in contiguous memory locations. Therefore, the correct answer is "Stack" as it best aligns with the Pez dispenser analogy.

Rate this question:

• 4.

### LIFO structire stands for...

• A.

Last In Furthest Out

• B.

Least In First Out

• C.

Last In First Out

C. Last In First Out
Explanation
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:

• 5.

### A queue is and ADT in which elemets are added and removed from one end only; first-in-first-out (FIFO) structure.

• A.

True

• B.

False

A. True
Explanation
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:

• 6.

### The running time of RETREIVE call on a linked list is O(1) = constant

• A.

True

• B.

False

B. False
Explanation
The statement is false because the running time of a RETRIEVE call on a linked list is not constant or O(1). In a linked list, we need to traverse through the list from the beginning until we find the desired element. This process takes linear time, which means the running time is O(n), where n is the number of elements in the linked list.

Rate this question:

• 7.

### Insert, Append, Delete, and Next are all valid list operations.

• A.

True

• B.

False

A. True
Explanation
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:

• 8.

### An enque is the opposite of a deque

• A.

True

• B.

False

A. True
Explanation
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:

• 9.

### A node at level X is also said to be a depth of X

• A.

True

• B.

False

A. True
Explanation
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:

• 10.

### Postfix notation may not contain negative numbers

• A.

True

• B.

False

A. True
Explanation
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:

• 11.

### An ordered tree in which each vertex has 0, 1, or 2 children

Binary Tree
Explanation
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:

• 12.

### The name of the second child of a vertex on a binary tree

Right Child
Explanation
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:

• 13.

### A node connected via edges to a higher node

Child
Explanation
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:

• 14.

### The unique vertex in a rooted tree

root
Explanation
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:

• 15.

### A node connected via edges to a lower node

parent
Explanation
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:

• 16.

### If "X" is a descendent of "Y", then "Y" is a __________ of "X".

Ancestor
Explanation
If "X" is a descendant of "Y", it means that "Y" is higher in the family tree and "X" is lower. Therefore, "Y" is an ancestor of "X". An ancestor is a person, animal, or plant from which one is descended or originates.

Rate this question:

• 17.

### A child (grandchild, great-grand-child, etc...) of a specific vertext.

Descendant
Explanation
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.

Rate this question:

• 18.

### The length of the path from the root to the vertext of interst

Depth
Explanation
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:

• 19.

### Any non-leaf vertext

Internal
Explanation
The correct answer is "Internal". In a tree structure, a non-leaf vertex refers to any node that is not a leaf node, meaning it has at least one child node. An internal node is another term used to describe a non-leaf vertex in a tree. Therefore, the correct answer is "Internal".

Rate this question:

• 20.

### All the descendents of a vertex

Sub Tree
Explanation
The correct answer is "Sub Tree." In graph theory, a sub tree is a portion of a tree that is formed by selecting a vertex and all its descendants. Therefore, all the descendants of a vertex can be considered as a sub tree.

Rate this question:

• 21.
• A.

A

• B.

B

• C.

Neither

B. B
• 22.

### The length of the longest path from a vertex to a leaf that is a descendent of the vertex

• A.

Height

• B.

Depth

A. Height
Explanation
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:

• 23.

### All parents have the same depth, but not necessarily the same height

• A.

True - parents

• B.

False - siblings

B. False - siblings
Explanation
This statement is false because it states that all parents have the same depth, but not necessarily the same height. However, in a family tree, parents are at a higher level than siblings, so they have a greater depth. Siblings, on the other hand, are at the same level and therefore have the same depth.

Rate this question:

• 24.

### Property of all trees

• A.

#Edges = #Nodes - 1

• B.

#Nodes = #Edges - 1

A. #Edges = #Nodes - 1
Explanation
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:

• 25.

### An ordered tree in which each vertex has either no children, one child, or two children

• A.

Sub Tree

• B.

Ordered Tree

• C.

Binary Tree

C. Binary Tree
Explanation
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:

• 26.

### Every vertex has two children or is a leaf

• A.

Perfect Binary Tree

• B.

Full Binary Tree

B. Full Binary Tree
Explanation
A full binary tree is a type of binary tree in which every vertex has either two children or is a leaf node. In other words, there are no vertices with only one child. This means that every level of the tree is completely filled, except possibly for the last level, which is filled from left to right. Therefore, a full binary tree satisfies the given condition that every vertex has two children or is a leaf.

Rate this question:

• 27.

### A Full Binary Tree in which all leaves have the same depth

• A.

Perfect Binary Tree

• B.

Full Binary Tree

A. Perfect Binary Tree
Explanation
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:

• 28.

### What is the In Order Traversal:

6 13 17 27 33 42 48
Explanation
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:

• 29.

### Prior to inserting intoa B.S.T., you must sort the tree

• A.

True

• B.

False

B. False
Explanation
^search not sort

Rate this question:

• 30.

### The "best case" search time for a B.S.T. is O(n). (where n = the number of nodes in the tree)

• A.

True

• B.

False

B. False
Explanation
^worst case

Rate this question:

• 31.

### A Red-Black tree is an BST tree

• A.

True

• B.

False

A. True
Explanation
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:

• 32.

### A BST tree is always balanced

• A.

True

• B.

False

B. False
Explanation
AVL

Rate this question:

• 33.

### All AVL trees are BST

• A.

True

• B.

False

A. True
Explanation
AVL trees are a type of binary search tree (BST) that is balanced, meaning the heights of the left and right subtrees differ by at most 1. Since AVL trees are a subset of BSTs and satisfy the additional balancing condition, it can be concluded that all AVL trees are also BSTs. Therefore, the correct answer is true.

Rate this question:

• 34.

### For a normal (double-linked) binary tree, 8 pointers are assigned to each node.

• A.

True

• B.

False

B. False
Explanation
4

Rate this question:

• 35.

### Inserting a node in an AVL tree will sometimes change the height of the tree

• A.

True

• B.

False

A. True
Explanation
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:

• 36.

### A splay tree is also an AVL

• A.

True

• B.

False

B. False
Explanation
B.S.T.

Rate this question:

• 37.

### A red-black tree is also a B.S.T.

• A.

True

• B.

False

A. True
Explanation
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:

• 38.

### Red-Black trees are tree that have been restrctured with a heuristic similar to a self-organizing list

• A.

True

• B.

False

B. False
Explanation
Splay trees

Rate this question:

• 39.

### A hash table tends to perform better overall (bot time and space) than an array, linked list, or balanced B.S.T.

• A.

True

• B.

False

A. True
Explanation
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:

• 40.

### Linear probing is not a good solution for clustering

• A.

True

• B.

False

A. True
Explanation
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:

• 41.

### Double hashing requires more "computational overhead" than linear probing.

• A.

True

• B.

False

B. False
Explanation
Rehashing

Rate this question:

• 42.

### Rehashing guarentees a reduction in clustering

• A.

True

• B.

False

B. False
Explanation
Rehashing does not guarantee a reduction in clustering. Rehashing is a technique used in hash tables to resolve collisions by finding a new position for an element when a collision occurs. While it can help distribute the elements more evenly, it does not guarantee a reduction in clustering, which refers to the tendency of elements to cluster in specific positions within the hash table. Other techniques like resizing the hash table or using more advanced collision resolution methods may be needed to reduce clustering.

Rate this question:

• 43.

### Linear probing uses the numer of times the rehash function has been applied as a value in the hash formula

• A.

True

• B.

False

A. True
Explanation
Linear probing is a collision resolution technique in hashing where if a collision occurs, the algorithm looks for the next available slot in the hash table by incrementing the index until an empty slot is found. In linear probing, the number of times the rehash function has been applied is used as a value in the hash formula to determine the next index to probe. This helps in avoiding clustering of elements and ensures a more even distribution of values in the hash table. Therefore, the given statement is true.

Rate this question:

• 44.

### What is a disadvantage of using buckets for collision resolution? Choose all that apply

• A.

The search is long

• B.

It takes longer to walk down

• C.

Wasted space

• D.

Not knowing how big the bucket is

• E.

The return time

B. It takes longer to walk down
C. Wasted space
D. Not knowing how big the bucket is
Explanation
Using buckets for collision resolution can have several disadvantages. Firstly, it takes longer to walk down the bucket list, as each element in the bucket needs to be checked before finding the desired item. Secondly, using buckets can result in wasted space, as some buckets may remain empty while others become overcrowded. Lastly, not knowing how big the bucket is can be a disadvantage as it may lead to inefficient memory allocation and potential performance issues.

Rate this question:

• 45.

### Choose two ways to resolve problems following a deletion in a list using linear probing. Choose all that apply

• A.

Use recursion

• B.

Using chain down the list

• C.

Shift Everything

• D.

Insert null in deleted vairable

C. Shift Everything
D. Insert null in deleted vairable
Explanation
To resolve problems following a deletion in a list using linear probing, two possible approaches are shifting everything and inserting null in the deleted variable. Shifting everything involves moving all the elements in the list after the deleted element to fill the empty space. This ensures that the list remains contiguous and maintains the order of elements. Inserting null in the deleted variable means marking the deleted element as null, indicating that it is no longer a valid value. This allows for efficient searching and avoids potential errors when accessing the deleted element.

Rate this question:

• 46.

### All ordered trees are binary trees

• A.

True

• B.

False

B. False
Explanation
Not all ordered trees are binary trees because an ordered tree can have any number of children at each node, while a binary tree can have at most two children at each node. Therefore, it is possible for an ordered tree to have more than two children at a node, making it not a binary tree.

Rate this question:

• 47.

### Reading a book (cover to cover) is an example of Pre Order Traversal

• A.

True

• B.

False

A. True
Explanation
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:

• 48.

### A post oder traversal may be used to evaluate an arithmetic expression

• A.

True

• B.

False

A. True
Explanation
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:

• 49.

### General trees will always have fewer nodes than its binary tree representation

• A.

True

• B.

False

B. False
Explanation
more

Rate this question:

• 50.

### Which are Binary Trees?

• A.

A

• B.

B

• C.

C

• D.

D

• E.

E

A. A
B. B
C. C
D. D
E. E
Explanation
The given answer includes all the options A, B, C, D, and E. Therefore, all of these options are binary trees.

Rate this question:

Related Topics