GPL - Gate Question |

X Close

You need to enable javascript to view this page properly.

Branch

All

Loading

595.

Let G = (V,E) be a directed graph with n vertices. A path from v_i to v_j in G is a sequence of vertices (v_i, v_i+1, ... , v_j) such that (v_k, v_k+1) ∈ E for all k in i through j - 1. A simple path is a path in which no vertex appears more than once.
Let A be an n x n array initialized as follows.

Consider the following algorithm.
for i = 1 to n
for j = 1 to n
for k = 1 to n
A[j,k] = max(A[j,k], A[j,i] + A[i,k]);
Which of the following statements is necessarily true for all j and k after termination of the above algorithm? [2 marks]
(A) A[j,k] ≤ n
(B) If A[i,j] ≥ n - 1, then G has a Hamiltonian cycle
(C) If there exists a path from j to k, A[j,k] contains the longest path length from j to k
(D) If there exists a path from j to k, every simple path from j to k contains at most A[j,k} edges

asked in Computer Science And Engineering, 2003

View Comments [0 Reply]
596.

The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively in chronological order:
“a_s b_s c_s a_e d_s c_e e_s f_s b_e d_e g_s e_e f_e h_s g_e h_e”.
Here, x_s denotes the starting time and x_e denotes the ending time of activity X. We need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required? [2 marks]
(A) 3
(B) 4
(C) 5
(D) 6

asked in Computer Science And Engineering, 2003

View Comments [0 Reply]
597.

What is the weight of a minimum spanning tree of the following graph? [2 marks]

(A) 29
(B) 31
(C) 38
(D) 41

asked in Computer Science And Engineering, 2003

View Comments [0 Reply]
598.

Let G = (V,E) be an undirected graph with a subgraph G1 = (V₁, E₁). Weights are assigned to edges of G as follows.

A single-source shortest path algorithm is executed on the weighted graph (V,E,w) with an arbitrary vertex v₁ of V₁ as the source. Which of the following can always be inferred from the path costs computed? [2 marks]
(A) The number of edges in the shortest paths from v₁ to all vertices of G
(B) G₁ is connected
(C) V₁ forms a clique in G
(D) G₁ is a tree

asked in Computer Science And Engineering, 2003

View Comments [0 Reply]
599.

The cube root of a natural number n is defined as the largest natural number m such that m³≤n. The complexity of computing the cube root of n (n is represented in binary notation) is [2 marks]
(A) O(n) but not O(n^0.5)
(B) O(n^0.5) but not O((log n)k) for any constant k > 0
(C) O((log n)^k) for some constant k > 0, but not O((log log n)^m) for any constant m > 0
(D) O((log log n)^k) for some constant k > 0.5, but not O((log log n)^0.5)

asked in Computer Science And Engineering, 2003

View Comments [0 Reply]
600.

Consider the following 2-3-4 tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree.

What is the result of inserting G in the above tree? [2 marks]

(d) None of these

asked in Computer Science And Engineering, 2003

View Comments [0 Reply]

801 1 ...‹‹98 99100 101 102 ›› ... 134

High Frequency Word List with Mnemonics

GPL Dictionary is fast way to learn words with mnemonics.
It contains high frequency word list which are mostly asked in various examinations.
It is dedicated for student appearing for PSUs, GRE, UPSC or any other exams in which vocabulary test is taken.
User can save their own mnemonics (key and link).

Check Now