GATE CSE 2008
Q21.
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexityQ22.
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this isQ24.
Which of the following statements about synchronous and asynchronous I/O is NOT true?Q25.
The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution? struct node { int value; struct node *next; }; Void rearrange(struct node *list) { struct node *p, * q; int temp; if(!list|| !list-> next) return; p=list; q=list->next; while(q) { temp = p->value; p->value = q->value; q->value = temp; p = q->next; q = p?p->next:0; } }Q26.
G is a graph on n vertices and 2n-2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?Q27.
Match the following NFAs with the regular expressions they correspond to 1. \epsilon + 0(01*1 + 00) * 01* 2. \epsilon + 0(10 *1 + 00) * 0 3. \epsilon + 0(10 *1 + 10) *1 4. \epsilon + 0(10 *1 + 10) *10 *Q28.
Given below are two finite state automata (\rightarrow indicates the start state and F indicates a final state) Which of the following represents the product automaton ZxY?Q30.
Consider the following relational schemes for a library database: Book (Title, Author, Catalog_ no, Publisher, Year, Price) Collection (Title,Author, Catalog_ no) with in the following functional dependencies: I. Title Author \rightarrow Catalog_no II. Catalog_no \rightarrow Title Author Publisher Year III. Publisher Title Year \rightarrow Price Assume {Author, Title} is the key for both schemes. Which of the following statements is true?