Which of the following scenarios cannot be properly modeled by a tree structure?
Think about whether each node can have multiple parents or cycles.
Trees have a strict hierarchy with no cycles and each child has exactly one parent. Social networks allow multiple connections and cycles, so they cannot be modeled as trees.
What is the printed adjacency list after adding edges in this Rust code?
use std::collections::HashMap;
fn main() {
let mut graph: HashMap<&str, Vec<&str>> = HashMap::new();
graph.entry("A").or_default().push("B");
graph.entry("B").or_default().push("C");
graph.entry("C").or_default().push("A");
for (node, edges) in &graph {
println!("{} -> {:?}", node, edges);
}
}Check which edges are added for each node.
The code adds edges A->B, B->C, and C->A, creating a cycle. Each node's adjacency list shows its direct neighbors.
Given this Rust code for a tree node, why can't it represent a graph where a node has multiple parents?
struct TreeNode {
value: i32,
children: Vec<TreeNode>,
}
fn main() {
let child = TreeNode { value: 2, children: vec![] };
let parent1 = TreeNode { value: 1, children: vec![child] };
let parent2 = TreeNode { value: 3, children: vec![child] };
}Think about ownership and how Rust handles data in vectors.
In Rust, the child node is moved into the first parent's children vector. Trying to move it again into the second parent's children vector is not allowed because it violates ownership rules. This prevents multiple parents for the same child, unlike graphs.
You want to model a city's road network where intersections connect multiple roads and some roads loop back. Which data structure fits best?
Consider if the structure allows cycles and multiple connections per node.
City road networks have intersections connected by multiple roads and loops (cycles). Graphs can model these many-to-many relationships and cycles, unlike trees or lists.
What is the output of this Rust code that tries to detect a cycle in a directed graph?
use std::collections::{HashMap, HashSet};
fn has_cycle(node: &str, graph: &HashMap<&str, Vec<&str>>, visited: &mut HashSet<&str>, stack: &mut HashSet<&str>) -> bool {
if stack.contains(node) {
return true;
}
if visited.contains(node) {
return false;
}
visited.insert(node);
stack.insert(node);
if let Some(neighbors) = graph.get(node) {
for &neighbor in neighbors {
if has_cycle(neighbor, graph, visited, stack) {
return true;
}
}
}
stack.remove(node);
false
}
fn main() {
let mut graph: HashMap<&str, Vec<&str>> = HashMap::new();
graph.insert("A", vec!["B"]);
graph.insert("B", vec!["C"]);
graph.insert("C", vec!["D"]);
graph.insert("D", vec!["B"]);
let mut visited = HashSet::new();
let mut stack = HashSet::new();
let result = has_cycle("A", &graph, &mut visited, &mut stack);
println!("Cycle detected: {}", result);
}Trace the recursion and check if the cycle B->C->D->B is detected.
The code uses depth-first search with a recursion stack to detect cycles. The cycle B->C->D->B exists, so the function returns true.