4.2.4.1 Graphs: weighted, directed and adjacency representations Quiz: AQA Computer Science, Unit 2

The 20 questions

1. What is a graph in computing?

   • A type of loop with a counter, which repeats the statements a set number of times
   • A chart showing values as bars on a screen, with the height of each bar set by the data value
   • A structure of vertices joined by edges, used to represent relationships
   • A list of values in sorted order, where each value is placed in the position matching its rank

2. What is a vertex (or node) in a graph?

   • A weight attached to an edge
   • The number of edges in the graph
   • The line joining two items
   • An item in the graph that edges connect

3. What is an edge (or arc) in a graph?

   • A connection between two vertices
   • The total number of vertices
   • A vertex with no connections
   • A value stored in a vertex

4. What is a weighted graph?

   • A graph in which each edge has a numerical value
   • A graph stored in a binary file
   • A graph where every vertex has the same colour
   • A graph with no edges

5. What is the difference between a directed and an undirected graph?

   • Directed graphs have no vertices, so their connections are stored as a single list of edges
   • Undirected graphs have edges with weights, while directed graphs do not have any numerical values
   • There is no difference between them, since both use the same arrows to show every connection
   • Directed edges have a direction from one vertex to another, while undirected edges go both ways

6. 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

7. A one-way street system is best modelled as which kind of graph?

   • Directed
   • A hash table
   • A queue
   • Undirected

8. 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

9. In an adjacency matrix, what does a value of 1 in row i, column j mean?

   • There are no edges from i, so the cell records that the row vertex is unconnected to column j
   • Vertex i has a weight of 1, which is the cost of every edge that leaves the vertex in the graph
   • Vertex j is the root, which marks the column vertex as the starting point of the whole graph
   • There is an edge from vertex i to vertex j

10. 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

11. Which statement compares adjacency matrices and adjacency lists?

    • A matrix uses space proportional to the square of the vertex count, while a list is efficient for sparse graphs
    • A matrix cannot represent weighted graphs, because each cell can only hold the value 1 or 0 at a time
    • A list cannot represent directed graphs, so every edge in a list is taken to be two-way at all times
    • A list always uses more space than a matrix for every graph, because each edge is stored twice in lists

12. Why is an adjacency list often preferred for a sparse graph?

    • It always runs in constant time for every operation
    • It stores only the edges that exist, saving space
    • It cannot store the vertices
    • It stores every possible edge including those that do not exist

13. Which representation makes checking whether an edge exists between two given vertices quick?

    • Adjacency matrix
    • Stack
    • Queue
    • Adjacency list in every case

14. A graph models a social network where people are vertices and friendships are edges. Which kind of graph is it most likely?

    • A queue
    • Directed with weights only
    • Undirected
    • A tree with one root

15. A graph models a web site where pages link to other pages. Why is a directed graph suitable?

    • Links always go both ways, so a page that links to another page is always linked back to it
    • Web sites cannot be modelled as graphs, because graphs only describe physical networks of cables
    • Pages have no connections, so a directed graph is used only to show the layout of each page
    • A link from one page to another does not imply a link back

16. What is a typical use of a weighted graph?

    • Counting the lines in a file, with each edge weight representing the count of one line
    • Reversing a string, with each character weighted by its position in the original text
    • Finding the cheapest or shortest route between places
    • Storing a list of names in order, with the weight of each name giving its place in the list

17. A graph has 5 vertices and 6 directed edges. What does the adjacency matrix contain?

    • A 5 by 6 matrix with no entries, since the matrix size depends on the edges, not on the vertices
    • A 6 by 6 matrix with 5 entries set to 1, one entry for each vertex and each edge in the graph
    • A 5 by 5 matrix with 6 entries set to 1 (or the weights)
    • A matrix with 11 entries, one for each vertex and each edge, so that every item is stored once

18. Which term describes a path of edges that starts and ends at the same vertex?

    • Leaf
    • Weight
    • Root
    • Cycle

19. A directed graph has an edge from A to B but no edge from B to A. How is this shown in an adjacency matrix?

    • The matrix is replaced by a list, since a directed graph cannot be represented by any matrix at all
    • No cell is marked, because a one-way edge is recorded only in the list and never in the matrix
    • A is marked in the row for A and column for B, but the B row and A column are not marked
    • Both cells are marked for the pair, so the matrix shows that the connection runs in each direction

20. Why might a graph algorithm need the weights of edges?

    • To remove all cycles automatically, since the weights identify every loop in the graph
    • To sort the vertices alphabetically, so that the names appear in order in the final output
    • To find routes with the lowest total cost or distance
    • To count the number of vertices, so that the algorithm knows how many nodes must be visited

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