Lesson 4.2.4.1
4.2.4.1 Graphs: weighted, directed and adjacency representations Quiz: AQA Computer Science, Unit 2
20 questions
In partnership with Revision Ninja
Lesson 4.2.4.1, Graphs: weighted, directed and adjacency representations: 20 multiple choice questions for the AQA Computer Science (7517), Unit 2: Fundamentals of data structures, written with Revision Ninja.
Host it live on the board and students join with a game code on their own devices, or revise alone with Free Play. The answers are revealed in the game.
The 20 questions
-
Which non-linear data structure consists of a set of nodes connected by edges?
- Stack
- Array
- Graph
- Queue
-
What is the term for a data point or entity in a graph?
- Weight
- Arc
- Edge
- Vertex
-
What term describes a connection linking two nodes in a graph?
- Edge
- Tree
- Root
- Vertex
-
What type of graph has a numerical value assigned to each of its edges?
- Weighted graph
- Directed graph
- Rooted tree
- Undirected graph
-
What type of graph contains edges that can only be traversed in one direction?
- Weighted graph
- Undirected graph
- Unweighted graph
- Directed graph
-
A road network where each road can be used in both directions is best modelled as which kind of graph?
- Undirected
- Directed
- A stack
- A tree with a root
-
A one-way street system is best modelled as which kind of graph?
- Directed
- A hash table
- A queue
- Undirected
-
In an adjacency matrix for a graph with 5 vertices, what size is the matrix?
- 5 by 5
- 5 by 4
- 10 by 10
- 1 by 5
-
In an unweighted adjacency matrix, what does an entry of 1 indicate?
- One vertex exists
- No edge exists
- A cycle exists
- An edge exists
-
A graph has 4 vertices and 3 undirected edges, stored in an adjacency list. How many list entries are stored in total for these edges?
- 3
- 12
- 6
- 4
-
What is the space complexity of an adjacency matrix for a graph with V vertices?
- O(V^2)
- O(V)
- O(V + E)
- O(E)
-
Which graph representation uses less memory for a graph with very few edges?
- Adjacency matrix
- Adjacency list
- 2D array
- Hash table
-
Which graph representation allows checking for a specific edge in O(1) constant time?
- Adjacency matrix
- Linked list
- Binary search tree
- Adjacency list
-
A graph models mutual Facebook friendships. Which type of graph is most appropriate?
- Binary tree
- Directed graph
- Undirected graph
- Weighted tree
-
A graph models web pages and hyperlinks between them. Which graph type is best?
- Weighted tree
- Binary search tree
- Undirected graph
- Directed graph
-
Which of these is a typical application of a weighted graph?
- Task priority queues
- Web page indexing
- GPS route planning
- Folder file systems
-
What are the dimensions of an adjacency matrix for a graph with 5 vertices?
- 6 by 6
- 5 by 6
- 5 by 5
- 25 by 1
-
Which term describes a path of edges that starts and ends at the same vertex?
- Leaf
- Weight
- Root
- Cycle
-
In a directed graph, an edge goes from vertex A to B. Where is the 1 placed?
- Row B, column B
- Row B, column A
- Row A, column B
- Row A, column A
-
What property of an edge does a weight represent in a graph?
- Node identifier
- Number of edges
- Distance or cost
- Direction of travel
Related quizzes
- Data structures and abstract data types Quiz · 4.2.1.1 · 20 questions
- Single- and multi-dimensional arrays Quiz · 4.2.1.2 · 20 questions
- Reading and writing text and binary files Quiz · 4.2.1.3 · 20 questions
- Linear, circular and priority queues Quiz · 4.2.2.1 · 20 questions
- Stack operations Quiz · 4.2.3.1 · 20 questions
- Trees and binary trees Quiz · 4.2.5.1 · 20 questions
- Hash tables, hashing and collisions Quiz · 4.2.6.1 · 20 questions
- Dictionaries and key-value pairs Quiz · 4.2.7.1 · 20 questions
- Vectors and vector operations Quiz · 4.2.8.1 · 20 questions
- Data types Quiz · 4.1.1.1 · 20 questions