ES242. Data Structures and Algorithms I. Quiz 02

ES242. Data Structures and Algorithms I.

Issued: 12 Jan, 2023

Problem 1. Doubly Linked Lists

If p is the address of a node in a doubly linked list L, then:

Note that:

Also, data(p), next(p) and prev(p) returns a sensible value only if p is not NULL, otherwise they are UNDEFINED.

If L is a linked list with five elements and p is the address of the third element, then what does next(prev(next(next(p)))) represent?

If L is a linked list with five elements and p is the address of the third element, then what does data(prev(prev(next(p)))) represent?

Problem 2. Adjacency Lists

Suppose A is the adjacency matrix of a simple undirected graph G = (V,E) with n vertices given by \{1,2,\ldots,n\}, that is,

A[i,j] = \begin{cases} 1 & \text{if } (i,j) \in E,\\ 0 & \text{if } (i,j) \notin E. \end{cases}

Note that A[i,i] = 0 for all i \in \{1,2,\ldots,n\} since G is simple.

Suppose (i,j) \in E for some i,j \in \{1,2,\ldots,n\}, i \neq j. Let k denote the number of vertices that are adjacent to both i and j.

What is the value of A^2[i,j]?

Suppose (i,j) \notin E for some i,j \in \{1,2,\ldots,n\}, i \neq j. Let k denote the number of vertices that are adjacent to both i and j.

What is the value of A^2[i,j]?

Problem 3. Edge List

Suppose every vertex of a graph G on n vertices has d neighbors.

What is the size of the edge list?

Is it possible that both d and n are odd?