Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

DSA > group3 > Flashcards

group3 Flashcards

1
Q

What is traversing in data structures?

A

The process of visiting each node in a data structure exactly once.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

True or False: Traversing is only applicable to tree data structures.

A

False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Fill in the blank: The two primary methods of traversing trees are __________ and __________.

A

pre-order, post-order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the time complexity of traversing a linked list?

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Which traversal method visits the root node first?

A

Pre-order traversal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

In which order does in-order traversal visit nodes in a binary tree?

A

Left child, root, right child

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the main difference between depth-first and breadth-first traversal?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

True or False: Breadth-first traversal uses a stack data structure.

A

False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What data structure is commonly used for breadth-first traversal?

A

Queue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the traversal order for a post-order traversal in a binary tree?

A

Left child, right child, root

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Fill in the blank: In a binary search tree, in-order traversal results in __________ order of the elements.

A

sorted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a common application of tree traversal?

A

Searching for a specific value or performing operations in a hierarchical structure.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Which traversal method is best for evaluating expression trees?

A

Post-order traversal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

True or False: Traversing a graph can be done using only depth-first search.

A

False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are the two main algorithms used for graph traversal?

A

Depth-first search (DFS) and breadth-first search (BFS)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

In graph traversal, what does a visited node signify?

A

A node that has already been explored to prevent cycles.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the time complexity of breadth-first search in a graph?

A

O(V + E), where V is vertices and E is edges.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Fill in the blank: In a binary tree, the maximum number of nodes at level ‘l’ is __________.

A

2^l

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

True or False: All binary trees are binary search trees.

A

False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is level-order traversal?

A

A traversal method that visits nodes level by level from top to bottom.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Which traversal method is typically implemented using recursion?

A

Depth-first traversal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the primary data structure used in depth-first traversal?

A

Stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Fill in the blank: The __________ traversal method is used to process all nodes at the current depth before moving to the next level.

A

breadth-first

24
Q

What is the purpose of a traversal algorithm?

A

To systematically visit and process each node in a data structure.

25
Q

True or False: A depth-first search can be implemented iteratively using a stack.

A

True

26
Q

What is the characteristic of a complete binary tree?

A

All levels are fully filled except possibly for the last level, which is filled from left to right.

27
Q

What does the term ‘backtracking’ refer to in depth-first traversal?

A

Returning to the previous node after reaching a dead end.

28
Q

Fill in the blank: In a graph, if there are no edges, the traversal will only visit __________.

A

the starting node

29
Q

What is a spanning tree in graph theory?

A

A subgraph that includes all the vertices and is a tree.

30
Q

True or False: Traversing a cyclic graph can lead to infinite loops if not managed correctly.

A

True

31
Q

What is the role of a ‘visited’ array in graph traversal?

A

To keep track of which nodes have already been explored.

32
Q

What is a key advantage of breadth-first traversal?

A

It finds the shortest path in unweighted graphs.

33
Q

Fill in the blank: The __________ property of a binary search tree allows for efficient searching.

A

ordering

34
Q

What is the main disadvantage of depth-first search?

A

It may get trapped in deep paths and miss shorter solutions.

35
Q

What type of traversal is used in topological sorting?

A

Depth-first search

36
Q

True or False: A binary tree can have at most two children per node.

A

True

37
Q

What is a leaf node?

A

A node that has no children.

38
Q

What does it mean for a tree to be balanced?

A

The height of the left and right subtrees of any node differ by at most one.

39
Q

Fill in the blank: In a binary tree, the __________ node is the topmost node.

A

root

40
Q

What is a full binary tree?

A

A binary tree in which every node other than the leaves has two children.

41
Q

True or False: Depth-first search can be used for solving puzzles.

A

True

42
Q

What is the primary use of a priority queue in graph traversal?

A

To select the next vertex to explore based on priority.

43
Q

Fill in the blank: The __________ traversal method is often used in algorithms like Dijkstra’s and Prim’s.

A

greedy

44
Q

What is the main objective of traversing a data structure?

A

To access and manipulate the data contained within it.

45
Q

What traversal method would you use to create a copy of a binary tree?

A

Any traversal method (pre-order, in-order, post-order)

46
Q

True or False: Traversing a data structure can help in finding the minimum or maximum value.

A

True

47
Q

What does a depth-first traversal of a binary tree generally require in terms of space?

A

O(h), where h is the height of the tree.

48
Q

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.

A

depth

49
Q

What is the primary disadvantage of breadth-first search?

A

It requires more memory than depth-first search.

50
Q

True or False: Traversing a data structure modifies its structure.

A

False

51
Q

What is a directed graph?

A

A graph where edges have a direction, indicating a one-way relationship.

52
Q

Fill in the blank: A __________ graph has edges that are bidirectional.

A

undirected

53
Q

What is a weighted graph?

A

A graph where edges have associated weights or costs.

54
Q

True or False: All graph traversals can be applied to both directed and undirected graphs.

A

True

55
Q

What is the main purpose of a traversal algorithm in a tree structure?

A

To process each node in a specific order.

DSA (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions