1.
Stack is an Abstract Class
Correct Answer
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.
2.
Stack is an Abstract Data Type
Correct Answer
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.
3.
Pez Dispenser Anaolgy
Correct Answer
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.
4.
LIFO structire stands for...
Correct Answer
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.
5.
A queue is and ADT in which elemets are added and removed from one end only; first-in-first-out (FIFO) structure.
Correct Answer
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.
6.
The running time of RETREIVE call on a linked list is O(1) = constant
Correct Answer
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.
7.
Insert, Append, Delete, and Next are all valid list operations.
Correct Answer
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.
8.
An enque is the opposite of a deque
Correct Answer
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.
9.
A node at level X is also said to be a depth of X
Correct Answer
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.
10.
Postfix notation may not contain negative numbers
Correct Answer
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.
11.
An ordered tree in which each vertex has 0, 1, or 2 children
Correct Answer
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.
12.
The name of the second child of a vertex on a binary tree
Correct Answer
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.
13.
A node connected via edges to a higher node
Correct Answer
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.
14.
The unique vertex in a rooted tree
Correct Answer
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.
15.
A node connected via edges to a lower node
Correct Answer
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.
16.
If "X" is a descendent of "Y", then "Y" is a __________ of "X".
Correct Answer
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.
17.
A child (grandchild, great-grand-child, etc...) of a specific vertext.
Correct Answer
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.
18.
The length of the path from the root to the vertext of interst
Correct Answer
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.
19.
Any non-leaf vertext
Correct Answer
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".
20.
All the descendents of a vertex
Correct Answer
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.
21.
Correct Answer
B. B
22.
The length of the longest path from a vertex to a leaf that is a descendent of the vertex
Correct Answer
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.
23.
All parents have the same depth, but not necessarily the same height
Correct Answer
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.
24.
Property of all trees
Correct Answer
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.
25.
An ordered tree in which each vertex has either no children, one child, or two children
Correct Answer
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.
26.
Every vertex has two children or is a leaf
Correct Answer
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.
27.
A Full Binary Tree in which all leaves have the same depth
Correct Answer
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.
28.
What is the In Order Traversal:
Correct Answer
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.
29.
Prior to inserting intoa B.S.T., you must sort the tree
Correct Answer
B. False
Explanation
^search not sort
30.
The "best case" search time for a B.S.T. is O(n). (where n = the number of nodes in the tree)
Correct Answer
B. False
Explanation
^worst case
31.
A Red-Black tree is an BST tree
Correct Answer
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.
32.
A BST tree is always balanced
Correct Answer
B. False
Explanation
AVL
33.
All AVL trees are BST
Correct Answer
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.
34.
For a normal (double-linked) binary tree, 8 pointers are assigned to each node.
Correct Answer
B. False
Explanation
4
35.
Inserting a node in an AVL tree will sometimes change the height of the tree
Correct Answer
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.
36.
A splay tree is also an AVL
Correct Answer
B. False
Explanation
B.S.T.
37.
A red-black tree is also a B.S.T.
Correct Answer
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.
38.
Red-Black trees are tree that have been restrctured with a heuristic similar to a self-organizing list
Correct Answer
B. False
Explanation
Splay trees
39.
A hash table tends to perform better overall (bot time and space) than an array, linked list, or balanced B.S.T.
Correct Answer
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.
40.
Linear probing is not a good solution for clustering
Correct Answer
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.
41.
Double hashing requires more "computational overhead" than linear probing.
Correct Answer
B. False
Explanation
Rehashing
42.
Rehashing guarentees a reduction in clustering
Correct Answer
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.
43.
Linear probing uses the numer of times the rehash function has been applied as a value in the hash formula
Correct Answer
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.
44.
What is a disadvantage of using buckets for collision resolution? Choose all that apply
Correct Answer(s)
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.
45.
Choose two ways to resolve problems following a deletion in a list using linear probing. Choose all that apply
Correct Answer(s)
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.
46.
All ordered trees are binary trees
Correct Answer
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.
47.
Reading a book (cover to cover) is an example of Pre Order Traversal
Correct Answer
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".
48.
A post oder traversal may be used to evaluate an arithmetic expression
Correct Answer
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.
49.
General trees will always have fewer nodes than its binary tree representation
Correct Answer
B. False
Explanation
more
50.
Which are Binary Trees?
Correct Answer(s)
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.