DSA Finals Flashcards by LUIS KEINE CERTEZA

What is a tree data structure defined as?
a) A linear data structure with nodes connected sequentially.
b) A recursive data structure with one root node and remaining nodes as children.
c) A data structure where every node can have multiple parents.
d) A collection of disconnected nodes.

A recursive data structure with one root node and remaining nodes as children.

How well did you know this?

Not at all

Perfectly

In a tree, what are the nodes other than the root node partitioned into?
a) Parent nodes
b) Sibling sets
c) Non-empty sets, each called a sub-tree.
d) Leaf nodes only.

Non-empty sets, each called a sub-tree.

How well did you know this?

Not at all

Perfectly

What relationship can nodes in a tree maintain?
a) Only parent-child relationships.
b) Only sister node relationships.
c) Parent-child relationships or sister node relationships.
d) Grandparent-grandchild relationships exclusively.

Parent-child relationships or sister node relationships.

How well did you know this?

Not at all

Perfectly

Parent-child relationships or sister node relationships.

How well did you know this?

Not at all

Perfectly

In a general tree, how many parents can a node have?
a) Any number of parents.
b) Only a single parent.
c) At most two parents.
d) Zero parents if it’s not a root node.

Only a single parent.

How well did you know this?

Not at all

Perfectly

Which node is designated as the topmost node in the tree hierarchy?
a) Leaf Node
b) Parent Node
c) Root Node
d) Sibling Node

Root Node

How well did you know this?

Not at all

Perfectly

A node that doesn’t have any parent is called the:
a) Child Node
b) Leaf Node
c) Root Node
d) Internal Node

Root Node

How well did you know this?

Not at all

Perfectly

If the root node is not null, T1, T2, and T3 connected to the root are called:
a) Parent nodes
b) Sub-trees
c) Sibling nodes
d) Forests

Sub-trees

How well did you know this?

Not at all

Perfectly

What is a leaf node?
a) A node with only one child.
b) A node that doesn’t have any child node.
c) The root node of a sub-tree.
d) Any node that is not the root.

A node that doesn’t have any child node.

How well did you know this?

Not at all

Perfectly

Leaf nodes can also be called:
a) Internal nodes
b) Parent nodes
c) External nodes
d) Root nodes

External nodes

How well did you know this?

Not at all

Perfectly

What is a path in a tree?
a) Any collection of nodes.
b) A single edge connecting two nodes.
c) The sequence of consecutive edges.
d) All nodes at the same level.

The sequence of consecutive edges.

How well did you know this?

Not at all

Perfectly

An ancestor of a node is:
a) Any child node of that node.
b) Any sibling node of that node.
c) Any predecessor node on a path from the root to that node.
d) Only the immediate parent of that node.

Any predecessor node on a path from the root to that node.

How well did you know this?

Not at all

Perfectly

Which node in a tree doesn’t have any ancestors?
a) Leaf node
b) Root node
c) Any internal node
d) A node with the highest degree

Root node

How well did you know this?

Not at all

Perfectly

The degree of a node is equal to:
a) The number of parents it has.
b) The number of children it has.
c) The number of siblings it has.
d) Its level number.

The number of children it has.

How well did you know this?

Not at all

Perfectly

What is the degree of a leaf node?
a) 0
b) 1
c) 2
d) Depends on the tree type.

How well did you know this?

Not at all

Perfectly

The root node of a tree is always present at which level?
a) Level 1
b) Level -1
c) Level 0
d) The maximum level of the tree.

Level 0

How well did you know this?

Not at all

Perfectly

In a general tree, nodes present on the same level are called:
a) Ancestors
b) Descendants
c) Siblings
d) Sub-trees

Siblings

How well did you know this?

Not at all

Perfectly

A tree in which each node contains 3 sub-trees is called a:
a) Binary tree
b) General tree
c) Ternary tree
d) Complete tree

Ternary tree

How well did you know this?

Not at all

Perfectly

How is a forest defined?
a) A single tree with many branches.
b) A tree where every node is a leaf node.
c) The set of disjoint trees obtained by deleting the root node and its connecting edges.
d) A collection of nodes without any edges.

The set of disjoint trees obtained by deleting the root node and its connecting edges.

How well did you know this?

Not at all

Perfectly

A binary tree is a data structure in which each node can have at most how many children?
a) 1
b) 2
c) 3
d) Any number

How well did you know this?

Not at all

Perfectly

Which of the following is NOT a disjoint subset a binary tree is generally partitioned into?
a) The root of the node.
b) Left sub-tree.
c) Right sub-tree.
d) Parent sub-tree.

Parent sub-tree.

How well did you know this?

Not at all

Perfectly

In a Strictly Binary Tree, what is true about every non-leaf node?
a) It contains at least one child.
b) It contains non-empty left and right sub-trees.
c) It has a degree of 0.
d) It must be at level 0.

It contains non-empty left and right sub-trees.

How well did you know this?

Not at all

Perfectly

What is the degree of every non-leaf node in a Strictly Binary Tree?
a) 0
b) 1
c) 2
d) It varies.

How well did you know this?

Not at all

Perfectly

A strictly binary tree with ‘n’ leaves will have how many nodes?
a) n
b) 2n
c) 2n - 1
d) n - 1

2n - 1

How well did you know this?

Not at all

Perfectly

A Binary Tree is said to be a complete binary tree if: a) Every node has exactly two children. b) All of the leaves are located at the same level d. c) It has at least one leaf node. d) The root node has two children.

All of the leaves are located at the same level d.

In a complete binary tree, how many nodes are at each level 'l' between level 0 and d (depth)? a) l b) 2l c) 2^l d) l+1

2^l

What is the total number of nodes in a complete binary tree with depth 'd'? a) 2^d b) 2^d - 1 c) 2^(d+1) - 1 d) 2d + 1

2^(d+1) - 1

In a complete binary tree with depth 'd', how many leaf nodes are there? a) 2^d - 1 b) 2^(d+1) c) 2^d d) d

2^d

In a complete binary tree with depth 'd', how many non-leaf nodes are there? a) 2^d - 1 b) 2^d c) 2^(d+1) - 1 d) d - 1

2^d - 1

What is traversal in the context of data structures? a) Deleting all elements from the structure. b) Adding new elements to the structure. c) The process in which each element is "visited" at least once. d) Sorting the elements in the structure.

The process in which each element is "visited" at least once.

Which of the following is NOT listed as a binary tree traversal method in the text? a) Preorder b) Inorder c) Postorder d) Reverseorder

Reverseorder

What is the correct order of operations for In-order Traversal? a) Visit Root, Traverse Left, Traverse Right b) Traverse Left, Visit Root, Traverse Right c) Traverse Left, Traverse Right, Visit Root d) Visit Root, Traverse Right, Traverse Left

Traverse Left, Visit Root, Traverse Right

Given a tree with root '1', left child '2' (with children '4' left, '5' right), and right child '3', what is the In-order traversal? a) 1 2 4 5 3 b) 4 2 5 1 3 c) 4 5 2 3 1 d) 1 2 3 4 5

4 2 5 1 3

What is the correct order of operations for Pre-order Traversal? a) Visit Root, Traverse Left, Traverse Right b) Traverse Left, Visit Root, Traverse Right c) Traverse Left, Traverse Right, Visit Root d) Traverse Right, Traverse Left, Visit Root

Visit Root, Traverse Left, Traverse Right

Given a tree with root '1', left child '2' (with children '4' left, '5' right), and right child '3', what is the Pre-order traversal? a) 1 2 4 5 3 b) 4 2 5 1 3 c) 4 5 2 3 1 d) 2 4 5 3 1

1 2 4 5 3

In the pre-order traversal example (18, 211, 90, 20, 190), which element is visited first? a) 211 b) 18 c) 90 d) 190

What is the correct order of operations for Post-order Traversal? a) Visit Root, Traverse Left, Traverse Right b) Traverse Left, Visit Root, Traverse Right c) Traverse Left, Traverse Right, Visit Root d) Visit Root, Traverse Right, Traverse Left

Traverse Left, Traverse Right, Visit Root d) Visit Root, Traverse Right, Traverse Left

Given a tree with root '1', left child '2' (with children '4' left, '5' right), and right child '3', what is the Post-order traversal? a) 1 2 4 5 3 b) 4 2 5 1 3 c) 4 5 2 3 1 d) 3 5 4 2 1

4 5 2 3 1

How can individual elements be accessed from an array? a) Using the -> notation. b) Using the . notation. c) Using the [] notation. d) Using a getNode() function.

Using the [] notation.

What programming construct is typically used for iterating over an array? a) Switch statement b) If-else statement c) For or while loop d) Recursive function call

For or while loop

How is traversing through a linked list typically initiated? a) By starting from the last node. b) By creating a temp node pointing to the head of the list. c) By randomly selecting a node. d) By accessing an index like in an array.

By creating a temp node pointing to the head of the list.

In linked list traversal, when does the process stop? a) When the temp node's data matches a specific value. b) After a fixed number of iterations. c) When the temp node becomes null. d) When the temp node points back to the head.

When the temp node becomes null.

If a temp node used for linked list traversal is empty (null) at the start, what does it imply? a) The list has only one element. b) The list is circular. c) The list contains no items. d) The traversal algorithm is incorrect.

The list contains no items.

A graph is a non-linear data structure consisting of: a) Only nodes. b) Only edges. c) Nodes and edges. d) Levels and branches.

Nodes and edges.

n a graph, nodes are sometimes also referred to as: a) Arcs b) Vertices c) Links d) Paths

Vertices

What do edges in a graph represent? a) The data stored in the nodes. b) Lines or arcs that connect any two nodes. c) The order of nodes. d) The capacity of the graph.

Lines or arcs that connect any two nodes.

Which of these is mentioned as an application of graphs? a) Storing hierarchical employee data in a company. b) Expression evaluation. c) Representing social networks like Facebook. d) Implementing a spell checker.

Representing social networks like Facebook.

In the context of a directed graph (digraph), the pair (u, v) for an edge indicates: a) An edge between u and v, direction doesn't matter. b) There is an edge from vertex u to vertex v. c) The edge has a weight of 'uv'. d) u and v are adjacent but not connected.

There is an edge from vertex u to vertex v

Which term describes two nodes or vertices if they are connected to each other through an edge? a) Path b) Degree c) Adjacency d) Level

Adjacency

What does a "Path" in a graph represent? a) A single vertex. b) A single edge. c) A sequence of edges between two vertices. d) All vertices connected to a specific vertex.

A sequence of edges between two vertices.

Which of the following is NOT listed as a basic graph operation? a) Add Vertex b) Add Edge c) Display Vertex d) Sort Vertices

Sort Vertices

Adjacency Matrix is a 2D array of size V x V where V is: a) The number of edges. b) The number of vertices. c) The maximum weight of an edge. d) The number of paths.

The number of vertices.

In an adjacency matrix adj[][] for an unweighted graph, what does adj[i][j] = 1 indicate? a) There is no edge between vertex i and vertex j. b) There is an edge from vertex i to vertex j. c) Vertex i and vertex j have a weight of 1. d) The distance between vertex i and j is 1.

There is an edge from vertex i to vertex j.

The adjacency matrix for an undirected graph is always: a) Asymmetric b) Symmetric c) Diagonal d) Empty

Symmetric

What is a "Pro" of using an Adjacency Matrix? a) Consumes less space for sparse graphs. b) Adding a vertex is O(1) time. c) Queries like whether there is an edge from vertex ‘u’ to vertex ‘v’ are efficient O(1). d) It's complex to implement.

Queries like whether there is an edge from vertex ‘u’ to vertex ‘v’ are efficient O(1).

What is a "Con" of using an Adjacency Matrix? a) Removing an edge takes O(V) time. b) Representation is difficult to follow. c) Consumes more space O(V^2), even for sparse graphs. d) Edge queries are O(V) time.

Consumes more space O(V^2), even for sparse graphs.

Adding a vertex to a graph represented by an Adjacency Matrix takes how much time? a) O(1) b) O(V) c) O(V^2) d) O(E) (where E is number of edges)

O(V^2)

In an Adjacency List representation, what does an entry array[i] represent? a) The weight of vertex i. b) A boolean indicating if vertex i is visited. c) The list of vertices adjacent to the i-th vertex. d) The i-th edge in the graph.

The list of vertices adjacent to the i-th vertex.

Which graph representation is generally more space-efficient for sparse graphs? a) Adjacency Matrix b) Adjacency List c) Incidence Matrix d) Edge List

Adjacency List

Why is a boolean visited array used in graph traversals like BFS and DFS? a) To count the number of nodes. b) To store the weights of edges. c) To avoid processing a node more than once due to cycles. d) To prioritize nodes with higher degrees.

To avoid processing a node more than once due to cycles.

Breadth-First Search (BFS) for a graph is similar to BFS of a: a) Linked List b) Array c) Tree d) Stack

Tree

What data structure does BFS primarily use to remember the next vertex to visit? a) Stack b) Queue c) Priority Queue d) Array

Queue

According to the BFS rules provided, what is Rule 1? a) If no adjacent vertex is found, remove the first vertex from the queue. b) Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue. c) Repeat Rule 1 and Rule 2 until the queue is empty. d) Push the current vertex onto a stack.

Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.

In the BFS example (A to B to E to F first then to C and G lastly to D), which node is processed immediately after F? a) B b) C c) D d) G

When does the BFS algorithm typically terminate? a) When all nodes have been pushed to the stack. b) When the queue gets emptied. c) After visiting a predefined number of nodes. d) When a specific target node is found.

When the queue gets emptied.

Depth-First Search (DFS) for a graph is similar to DFS of a: a) Queue b) Hash Table c) Tree d) Heap

Tree

What data structure does DFS primarily use to remember the next vertex to visit when a dead end occurs? a) Queue b) Array c) Stack d) Linked List

Stack

According to the DFS rules provided, what happens if no adjacent unvisited vertex is found for the current vertex? a) The algorithm terminates. b) The current vertex is added to a queue. c) A vertex is popped up from the stack. d) The algorithm backtracks using a visited array.

A vertex is popped up from the stack.

In the DFS example (S to A to D to G to E to B first, then to F and lastly to C), which node is processed immediately after G? a) A b) D c) E d) B

When does the DFS algorithm typically terminate? a) When the queue is empty. b) When the stack is empty. c) When all nodes are marked as partially visited. d) When the first cycle is detected

When the stack is empty.

Which traversal algorithm explores as far as possible along each branch before backtracking? a) Breadth-First Search (BFS) b) Depth-First Search (DFS) c) Level-Order Traversal d) In-Order Traversal

Depth-First Search (DFS)

Which traversal algorithm explores neighbor nodes first before moving to the next level neighbors? a) Breadth-First Search (BFS) b) Depth-First Search (DFS) c) Pre-Order Traversal d) Post-Order Traversal

Breadth-First Search (BFS)

DSA Finals Flashcards

(72 cards)