Question Bank

In how many ways can we color the following graph G with three colors?

Which of the following graphs are eulerian graphs and which ones are not?

In the Internet, which is made up of interconnected physical networks of computers, each network connection of a computer is assigned an Internet address. In IPv4 Internet protocol, every Internet address is a 32-bit string, made of a network number (netid) followed by a host number (hostid). There are 3 types of Internet addresses:
(a) Class A: these are of the form: $0\,\underbrace{b_1b_2b_3b_4\ldots b_7b_8}_{\text{netid}}\underbrace{b_9\ldots b_{30}b_{31}}_{\text{hostid}}$
(b) Class B: these are of the form: $10\,\underbrace{b_2b_3b_4\ldots b_{15}b_{16}}_{\text{netid}}\underbrace{b_{17}\ldots b_{30}b_{31}}_{\text{hostid}}$
(c) Class C: these are of the form: $110\,\underbrace{b_3b_4b_5\ldots b_{23}b_{24}}_{\text{netid}}\underbrace{b_{25}\ldots b_{30}b_{31}}_{\text{hostid}}$
How many different IPv4 addresses are available for the internet network connections?

Consider the following weighted graph

What is the total weight of a minimum spanning tree of this graph?

Let $G$ be a simple undirected graph with $n$ nodes numbered from $1$ to $n$, and $A_G ∈ M_n$ be its adjacency matrix. What is the number of simple undirected graphs with $n$ nodes labeled from $1$
to $n$.

Let $M_n$ be the set of matrices of dimension $n×n$ whose elements are 0 or 1.
For every two matrices $A,B ∈ M_n$ and $1 ≤ k ≤ n$ we define the operations $A⊕B$ and $A⊙_kB$ as follows:
$A⊕B = C ∈ M_n$ if $C[i][j] = max(A[i][j],B[i][j])$ and
$A⊙_kB = D ∈ M_n$ if $D[i][j] = A[i][k]·B[k][j]$ for all $1 ≤ i, j ≤ n$.
Let $G$ be a simple undirected graph with $n$ nodes numbered from $1$ to $n$, and $A_G ∈ M_n$ be its adjacency matrix.

What is the number of simple undirected graphs with n nodes labeled from $1$ to $n$ ?

Let $M_n$ be the set of matrices of dimension $n×n$ whose elements are 0 or 1.
For every two matrices $A,B ∈ M_n$ and $1 ≤ k ≤ n$ we define the operations $A⊕B$ and $A⊙_kB$ as follows:
$A⊕B = C ∈ M_n$ if $C[i][j] = max(A[i][j],B[i][j])$ and
$A⊙_kB = D ∈ M_n$ if $D[i][j] = A[i][k]·B[k][j]$ for all $1 ≤ i, j ≤ n$.
Let $G$ be a simple undirected graph with $n$ nodes numbered from $1$ to $n$, and $A_G ∈ M_n$ be its adjacency matrix.
Let $I_n$ be the identity matrix of dimension $n × n$, and $1 ≤ p ≤ n$.
Consider the following algorithm to compute the matrix
$B ∈ Mn: B = AG ⊕ In;$
for $k := 1$ to $p$ do $C = B ⊕ (B ⊙_k B); B = C;$

What is the runtime complexity of this algorithm?

Let $M_n$ be the set of matrices of dimension $n×n$ whose elements are 0 or 1.
For every two matrices $A,B ∈ M_n$ and $1 ≤ k ≤ n$ we define the operations $A⊕B$ and $A⊙_kB$ as follows:
$A⊕B = C ∈ M_n$ if $C[i][j] = max(A[i][j],B[i][j])$ and
$A⊙_kB = D ∈ M_n$ if $D[i][j] = A[i][k]·B[k][j]$ for all $1 ≤ i, j ≤ n$.
Let $G$ be a simple undirected graph with $n$ nodes numbered from $1$ to $n$, and $A_G ∈ M_n$ be its adjacency matrix.
Let $I_n$ be the identity matrix of dimension $n × n$, and $1 ≤ p ≤ n$.

Consider the following algorithm to compute the matrix $B ∈ M_n: B = A_G ⊕ I_n$; for $k := 1$ to $p$ do $C = B ⊕ (B ⊙_k B); B = C;$
Which of the following assertions holds when $B[i][j] = 1$?

What’s wrong with the sequence:

int t[N], *low=t, *mid, *high=&t[N-1]; 
mid = (low+high) / 2;

Knowing that the . and the -> operators have equal precedence, higher than the precedence of the * operator and assuming the following declarations, which of the expressions bellow are correct?

struct point { 
    int x, y; 
}; 
struct rectangle{ 
    struct point p1, p2; 
}*r[N];

What would the value of q-p be if:

int t[20], *p=t, *q=&t[19];

What will be the value of variable a (before return) by running the following C code:

int main(){ 
    char a, a1=200, a2=110; 
    a = a1 + a2; 
    return 0; 
}

What will be the value of variable “b” after execution of the following code:

unsigned char a; 
int b=0; for (a=0; a<256; a++) { 
   b++;
}

Select the correct statement(s) regarding the following lines:

const int a = 12; 
#define b 12

What will be the output after running the following code :

int compute(int x){ 
     static int b=20; 
    b--; 
    return b+x; 
} 
int main (void){ 
    int i; 
    for (i=3;i>=0;i--) 
    printf("%d ",compute(i)); 
    return 0; 
}