Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?(A) d(r, u) < d(r, v)(B) d(r,u) > d(r,v)(C) d(r,u) <= (r,v)(D) None of the above

Consider an undirected unweighted graph G. Let a breadth-first travers

1.	Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?(A) d(r, u) < d(r, v)(B) d(r,u) > d(r,v)(C) d(r,u) <= (r,v)(D) None of the above
Answer»

Discussion

No Comment Found

Related InterviewSolutions

The 2’s complement representation of (−539)10 in hexadecimal is(A) ABE(B) DBC(C) DE5(D) 9E7
Consider the following statements:S1: The sum of two singular n × n matrices may be non-singularS2: The sum of two n × n non-singular matrices may be singular. Which of the following statements is correct?(A) S1 and S2 are both true(B) S1 is true, S2 is false(C) S1 is false, S2 is true(D) S1 and S2 are both false
Which of the following requires a device driver?(A) Register(B) Cache(C) Main memory(D) Disk
Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will(A) always decrease the number of page faults(B) always increase the number of page faults(C) sometimes increase the number of page faults(D) never affect the number of page faults
Consider a relation geq which represents “greater than or equal to”, that is, (x,y) ∈ geq only if y >= x.create table geq( ib integer not null ub integer not null primary key 1b foreign key (ub) references geq on delete cascade )Which of the following is possible if a tuple (x,y) is deleted?(A) A tuple (z,w) with z > y is deleted(B) A tuple (z,w) with z > x is deleted(C) A tuple (z,w) with w < x is deleted(D) The deletion of (x,y) is prohibited
Which of the following does not interrupt a running process?(A) A device(B) Timer(C) Scheduler process(D) Power failure
Consider the following languagesWhich of the languages are regular?(A) Only L1 and L2(B) Only L2, L3 and L4(C) Only L3 and L4(D) Only L3
Consider a DFA over ∑ = {a, b} accepting all strings which have number of a’s divisible by 6 and number of b’s divisible by 8. What is the minimum number of states that the DFA will have?(A) 8(B) 14(C) 15(D) 48
Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i <= n), the index of the parent is(A) i – 1(B) floor(i/2)(C) ceiling(i/2)(D) (i+1)/2
Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?(A) O(n)(B) O(n Log n)(C) O(n2)(D) O(n!)

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment