ES242. Data Structures and Algorithms I. Quiz 02
ES242. Data Structures and Algorithms I.
Quiz 02
Issued: 12 Jan, 2023
If p
is the address of a node in a doubly linked list L
, then:
next(p)
is the address of the next node in the linked listprev(p)
is the address of the previous node in the linked listdata(p)
is the information contained in the the node at addressp
Note that:
- if
p
is the address of the first node inL
thenprev(p)
isNULL
. - if
p
is the address of the last node inL
thennext(p)
isNULL
.
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?
- Address of the 1st element
- Address of the 2nd element
- Address of the 3rd element
- Address of the 4th element
- Address of the 5th element
UNDEFINED
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?
- Data of the 1st element
- Data of the 2nd element
- Data of the 3rd element
- Data of the 4th element
- Data of the 5th element
UNDEFINED
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]\)?
- \(0\)
- \(1\)
- \(k\)
- \(k+1\)
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]\)?
- \(0\)
- \(1\)
- \(k\)
- \(k+1\)
Suppose every vertex of a graph \(G\) on \(n\) vertices has \(d\) neighbors.
What is the size of the edge list?
- \(d \cdot n\)
- \(d \cdot n/2\)
- \(2d \cdot n\)
- \((d + n)\)
Is it possible that both \(d\) and \(n\) are odd?
- Yes
- No