group3 Flashcards
What is traversing in data structures?
The process of visiting each node in a data structure exactly once.
True or False: Traversing is only applicable to tree data structures.
False
Fill in the blank: The two primary methods of traversing trees are __________ and __________.
pre-order, post-order
What is the time complexity of traversing a linked list?
O(n)
Which traversal method visits the root node first?
Pre-order traversal
In which order does in-order traversal visit nodes in a binary tree?
Left child, root, right child
What is the main difference between depth-first and breadth-first traversal?
Depth-first explores as far down a branch as possible before backtracking, while breadth-first explores all neighbors at the present depth prior to moving on to nodes at the next depth level.
True or False: Breadth-first traversal uses a stack data structure.
False
What data structure is commonly used for breadth-first traversal?
Queue
What is the traversal order for a post-order traversal in a binary tree?
Left child, right child, root
Fill in the blank: In a binary search tree, in-order traversal results in __________ order of the elements.
sorted
What is a common application of tree traversal?
Searching for a specific value or performing operations in a hierarchical structure.
Which traversal method is best for evaluating expression trees?
Post-order traversal
True or False: Traversing a graph can be done using only depth-first search.
False
What are the two main algorithms used for graph traversal?
Depth-first search (DFS) and breadth-first search (BFS)
In graph traversal, what does a visited node signify?
A node that has already been explored to prevent cycles.
What is the time complexity of breadth-first search in a graph?
O(V + E), where V is vertices and E is edges.
Fill in the blank: In a binary tree, the maximum number of nodes at level ‘l’ is __________.
2^l
True or False: All binary trees are binary search trees.
False
What is level-order traversal?
A traversal method that visits nodes level by level from top to bottom.
Which traversal method is typically implemented using recursion?
Depth-first traversal
What is the primary data structure used in depth-first traversal?
Stack
Fill in the blank: The __________ traversal method is used to process all nodes at the current depth before moving to the next level.
breadth-first
What is the purpose of a traversal algorithm?
To systematically visit and process each node in a data structure.
True or False: A depth-first search can be implemented iteratively using a stack.
True
What is the characteristic of a complete binary tree?
All levels are fully filled except possibly for the last level, which is filled from left to right.
What does the term ‘backtracking’ refer to in depth-first traversal?
Returning to the previous node after reaching a dead end.
Fill in the blank: In a graph, if there are no edges, the traversal will only visit __________.
the starting node
What is a spanning tree in graph theory?
A subgraph that includes all the vertices and is a tree.
True or False: Traversing a cyclic graph can lead to infinite loops if not managed correctly.
True
What is the role of a ‘visited’ array in graph traversal?
To keep track of which nodes have already been explored.
What is a key advantage of breadth-first traversal?
It finds the shortest path in unweighted graphs.
Fill in the blank: The __________ property of a binary search tree allows for efficient searching.
ordering
What is the main disadvantage of depth-first search?
It may get trapped in deep paths and miss shorter solutions.
What type of traversal is used in topological sorting?
Depth-first search
True or False: A binary tree can have at most two children per node.
True
What is a leaf node?
A node that has no children.
What does it mean for a tree to be balanced?
The height of the left and right subtrees of any node differ by at most one.
Fill in the blank: In a binary tree, the __________ node is the topmost node.
root
What is a full binary tree?
A binary tree in which every node other than the leaves has two children.
True or False: Depth-first search can be used for solving puzzles.
True
What is the primary use of a priority queue in graph traversal?
To select the next vertex to explore based on priority.
Fill in the blank: The __________ traversal method is often used in algorithms like Dijkstra’s and Prim’s.
greedy
What is the main objective of traversing a data structure?
To access and manipulate the data contained within it.
What traversal method would you use to create a copy of a binary tree?
Any traversal method (pre-order, in-order, post-order)
True or False: Traversing a data structure can help in finding the minimum or maximum value.
True
What does a depth-first traversal of a binary tree generally require in terms of space?
O(h), where h is the height of the tree.
Fill in the blank: In a binary tree, the __________ of a node refers to the number of edges from the node to the tree’s root.
depth
What is the primary disadvantage of breadth-first search?
It requires more memory than depth-first search.
True or False: Traversing a data structure modifies its structure.
False
What is a directed graph?
A graph where edges have a direction, indicating a one-way relationship.
Fill in the blank: A __________ graph has edges that are bidirectional.
undirected
What is a weighted graph?
A graph where edges have associated weights or costs.
True or False: All graph traversals can be applied to both directed and undirected graphs.
True
What is the main purpose of a traversal algorithm in a tree structure?
To process each node in a specific order.
