Advanced Algorithm (Eldan) 1 (200)

Pregunta 1 de 200

1

What does the following function do for a given Linked List with first node as head?
void fun1(struct node* head)
{
if(head == NULL)
return;

fun1(head->next);
printf("%d ", head->data);
}

Selecciona una de las siguientes respuestas posibles:

Prints all nodes of linked lists
Prints all nodes of linked list in reverse order
Prints alternate nodes of Linked List
Prints alternate nodes in reverse order

Explicación

Pregunta 2 de 200

1

Which of the following points is/are true about Linked List data structure when it is compared with array

Selecciona una de las siguientes respuestas posibles:

Arrays have better cache locality that can make them better in terms of performance.
It is easy to insert and delete elements in Linked List
Random access is not allowed in a typical implementation of Linked Lists
The size of array has to be pre-decided, linked lists can change their size any time.
All of the above

Explicación

Pregunta 3 de 200

1

Consider the following function that takes reference to head of a Doubly Linked List as parameter. Assume that a node of doubly linked list has previous pointer as prev and next pointer as next.
void fun(struct node **head_ref)
{
struct node temp = NULL;
struct node current = head_ref;

while (current != NULL)
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}

if(temp != NULL )
head_ref = temp->prev;
}
Assume that reference of head of following doubly linked list is passed to above function 1 <--> 2 <--> 3 <--> 4 <--> 5 <-->6. What should be the modified linked list after the function call?

Selecciona una de las siguientes respuestas posibles:

2 <--> 1 <--> 4 <--> 3 <--> 6 <-->5
5 <--> 4 <--> 3 <--> 2 <--> 1 <-->6
6 <--> 5 <--> 4 <--> 3 <--> 2 <--> 1
6 <--> 5 <--> 4 <--> 3 <--> 1 <--> 2

Explicación

Pregunta 4 de 200

1

Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

Selecciona una de las siguientes respuestas posibles:

Insertion Sort
Quick Sort
Heap Sort
Merge Sort

Explicación

Pregunta 5 de 200

1

The following function reverse() is supposed to reverse a singly linked list. There is one line missing at the end of the function.
/* Link list node /
struct node
{
int data;
struct node next;
};
/* head_ref is a double pointer which points to head (or start) pointer
of linked list */
static void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = head_ref;
struct node next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
/ADD A STATEMENT HERE/
}
What should be added in place of "/ADD A STATEMENT HERE/", so that the function correctly reverses a linked list.

Selecciona una de las siguientes respuestas posibles:

*head_ref = prev;
*head_ref = current;
*head_ref = next;
*head_ref = NULL;

Explicación

Pregunta 6 de 200

1

What is the output of following function for start pointing to first node of following linked list? 1->2->3->4->5->6
void fun(struct node* start)
{
if(start == NULL)
return;
printf("%d ", start->data);

if(start->next != NULL )
fun(start->next->next);
printf("%d ", start->data);
}

Selecciona una de las siguientes respuestas posibles:

1 4 6 6 4 1
1 3 5 1 3 5
1 2 3 5
1 3 5 5 3 1

Explicación

Pregunta 7 de 200

1

The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank. Choose the correct alternative to replace the blank line.
typedef struct node
{
int value;
struct node next;
}Node;

Node move_to_front(Node head)
{
Node p, *q;
if ((head == NULL: || (head->next == NULL))
return head;
q = NULL; p = head;
while (p-> next !=NULL)
{
q = p;
p = p->next;
}
_______________________________
return head;
}

Selecciona una de las siguientes respuestas posibles:

q = NULL; p->next = head; head = p;
q->next = NULL; head = p; p->next = head;
head = p; p->next = q; q->next = NULL;
q->next = NULL; p->next = head; head = p;

Explicación

Pregunta 8 de 200

1

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;
}
}

Selecciona una de las siguientes respuestas posibles:

1,2,3,4,5,6,7
2,1,4,3,6,5,7
1,3,2,5,4,7,6
2,3,4,5,6,7,1

Explicación

Pregunta 9 de 200

1

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is (GATE CS 2002)

Selecciona una de las siguientes respuestas posibles:

log 2 n
n/2
log 2 n – 1
n

Explicación

Pregunta 10 de 200

1

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest? (GATE CS 2004)

Selecciona una de las siguientes respuestas posibles:

union only
intersection, membership
membership, cardinality
union, intersection

Explicación

Pregunta 11 de 200

1

Consider the function f defined below.
struct item
{
int data;
struct item * next;
};

int f(struct item *p)
{
return (
(p == NULL) ||
(p->next == NULL) ||
(( P->data <= p->next->data) && f(p->next))
);
}
For a given linked list p, the function f returns 1 if and only if (GATE CS 2003)

Selecciona una de las siguientes respuestas posibles:

the list is empty or has exactly one element
the elements in the list are sorted in non-decreasing order of data value
the elements in the list are sorted in non-increasing order of data value
not all elements in the list have the same data value

Explicación

Pregunta 12 de 200

1

A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time? (GATE 2004)

Selecciona una de las siguientes respuestas posibles:

rear node
front node
not possible with a single pointer
node next to front

Explicación

Pregunta 13 de 200

1

What are the time complexities of finding 8th element from beginning and 8th element from end in a singly linked list? Let n be the number of nodes in linked list, you may assume that n > 8.

Selecciona una de las siguientes respuestas posibles:

O(1) and O(n)
O(1) and O(1)
O(n) and O(1)
O(n) and O(n)

Explicación

Pregunta 14 de 200

1

Is it possible to create a doubly linked list using only one pointer with every node.

Selecciona una de las siguientes respuestas posibles:

Not Possible
Yes, possible by storing XOR of addresses of previous and next nodes.
Yes, possible by storing XOR of current node and next node
Yes, possible by storing XOR of current node and previous node

Explicación

Pregunta 15 de 200

1

Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?

Selecciona una de las siguientes respuestas posibles:

Possible if X is not last node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X.
Possible if size of linked list is even
Possible if size of linked list is odd
Possible if X is not first node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X.

Explicación

Pregunta 16 de 200

1

You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?

Selecciona una de las siguientes respuestas posibles:

Delete the first element
Insert a new element as a first element
Delete the last element of the list
Add a new element at the end of the list

Explicación

Pregunta 17 de 200

1

Consider the following function to traverse a linked list.
void traverse(struct Node *head)
{
while (head->next != NULL)
{
printf("%d ", head->data);
head = head->next;
}
}
Which of the following is FALSE about above function?

Selecciona una de las siguientes respuestas posibles:

The function may crash when the linked list is empty
The function doesn't print the last node when the linked list is not empty
The function is implemented incorrectly because it changes head

Explicación

Pregunta 18 de 200

1

Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?

Selecciona una de las siguientes respuestas posibles:

O(n)
O(log2 n)
O(logn)
O(1)

Explicación

Pregunta 19 de 200

1

N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key What is the time complexity of all these operations put together

Selecciona una de las siguientes respuestas posibles:

O(Log^2 N)
O(N)
O(N^2)
Θ(N^2 Log N)

Explicación

Pregunta 20 de 200

1

The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?

Selecciona una de las siguientes respuestas posibles:

singly linked list
doubly linked list
circular doubly linked list
array implementation of lists

Explicación

Pregunta 21 de 200

1

Consider the following statements:
i. First-in-first out types of computations are efficiently supported by STACKS.
ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on
an array for almost all the basic LIST operations.
iii. Implementing QUEUES on a circular array is more efficient than implementing QUEUES
on a linear array with two indices.
iv. Last-in-first-out type of computations are efficiently supported by QUEUES.

Selecciona una de las siguientes respuestas posibles:

(ii) and (iii) are true
(i) and (ii) are true
(iii) and (iv) are true
(ii) and (iv) are true

Explicación

Pregunta 22 de 200

1

Following is C like pseudo code of a function that takes a number as an argument, and uses a stack S to do processing.
void fun(int n)
{
Stack S; // Say it creates an empty stack S
while (n > 0)
{
// This line pushes the value of n%2 to stack S
push(&S, n%2);

n = n/2;
}

// Run while Stack S is not empty
while (!isEmpty(&S))
printf("%d ", pop(&S)); // pop an element from S and print it
}

Selecciona una de las siguientes respuestas posibles:

Prints binary representation of n in reverse order
Prints binary representation of n
Prints the value of Logn
Prints the value of Logn in reverse order

Explicación

Pregunta 23 de 200

1

Which one of the following is an application of Stack Data Structure?

Selecciona una de las siguientes respuestas posibles:

Managing function calls
The stock span problem
Arithmetic expression evaluation
All of the above

Explicación

Pregunta 24 de 200

1

Which of the following is true about linked list implementation of stack?

Selecciona una de las siguientes respuestas posibles:

In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.
In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.
Both of the above
None of the above

Explicación

Pregunta 25 de 200

1

Consider the following pseudocode that uses a stack
declare a stack of characters
while ( there are more characters in the word to read )
{
read a character
push the character on the stack
}
while ( the stack is not empty )
{
pop a character off the stack
write the character to the screen
}

Selecciona una de las siguientes respuestas posibles:

geeksquizgeeksquiz
ziuqskeeg
geeksquiz
ziuqskeegziuqskeeg

Explicación

Pregunta 26 de 200

1

Following is an incorrect pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced:
declare a character stack
while ( more input is available)
{
read a character
if ( the character is a '(' )
push it on the stack
else if ( the character is a ')' and the stack is not empty )
pop a character off the stack
else
print "unbalanced" and exit
}
print "balanced"
Which of these unbalanced sequences does the above code think is balanced?

Selecciona una de las siguientes respuestas posibles:

((())
())(()
(()()))
(()))()

Explicación

Pregunta 27 de 200

1

The following postfix expression with single digit operands is evaluated using a stack:
8 2 3 ^ / 2 3 * + 5 1 * -
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

Selecciona una de las siguientes respuestas posibles:

6, 1
5, 7
3, 2
1, 5

Explicación

Pregunta 28 de 200

1

Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

Selecciona una de las siguientes respuestas posibles:

n(X+ Y)
3Y + 2X
n(X + Y)-X
Y + 2X

Explicación

Pregunta 29 de 200

1

A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl< top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is (GATE CS 2004)

Selecciona una de las siguientes respuestas posibles:

(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
top1 + top2 = MAXSIZE
(top1= MAXSIZE/2) or (top2 = MAXSIZE)
top1= top2 -1

Explicación

Pregunta 30 de 200

1

Assume that the operators +, -, × are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, x , +, -. The postfix expression corresponding to the infix expression a + b × c - d ^ e ^ f is

Selecciona una de las siguientes respuestas posibles:

abc × + def ^ ^ -
abc × + de ^ f ^ -
ab + c × d - e ^ f ^
- + a × bc ^ ^ def

Explicación

Pregunta 31 de 200

1

To evaluate an expression without any embedded function calls:

Selecciona una de las siguientes respuestas posibles:

One stack is enough
Two stacks are needed
As many stacks as the height of the expression tree are needed
A Turing machine is needed in the general case

Explicación

Pregunta 32 de 200

1

The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is

Selecciona una de las siguientes respuestas posibles:

284
213
142
71

Explicación

Pregunta 33 de 200

1

A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i.
If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?

Selecciona una de las siguientes respuestas posibles:

6
4
3
2

Explicación

Pregunta 34 de 200

1

Consider the following C program:
#include
#define EOF -1
void push (int); /* push the argument on the stack /
int pop (void); / pop the top of the stack /
void flagError ();
int main ()
{ int c, m, n, r;
while ((c = getchar ()) != EOF)
{ if (isdigit (c) )
push (c);
else if ((c == '+') || (c == ''))
{ m = pop ();
n = pop ();
r = (c == '+') ? n + m : nm;
push (r);
}
else if (c != ' ')
flagError ();
}
printf("% c", pop ());
}
What is the output of the program for the following input ? 5 2 3 3 2 + * +

Selecciona una de las siguientes respuestas posibles:

15
25
30
150

Explicación

Pregunta 35 de 200

1

Suppose a stack is to be implemented with a linked list instead of an array. What would be the effect on the time complexity of the push and pop operations of the stack implemented using linked list (Assuming stack is implemented efficiently)?

Selecciona una de las siguientes respuestas posibles:

O(1) for insertion and O(n) for deletion
O(1) for insertion and O(1) for deletion
O(n) for insertion and O(1) for deletion
O(n) for insertion and O(n) for deletion

Explicación

Pregunta 36 de 200

1

Consider n elements that are equally distributed in k stacks. In each stack, elements of it are arranged in ascending order (min is at the top in each of the stack and then increasing downwards). Given a queue of size n in which we have to put all n elements in increasing order. What will be the time complexity of the best known algorithm?

Selecciona una de las siguientes respuestas posibles:

O(n logk)
O(nk)
O(n^2)
O(k^2)

Explicación

Pregunta 37 de 200

1

A priority queue Q is used to implement a stack S that stores characters. PUSH(C) is implemented as INSERT(Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in

Selecciona una de las siguientes respuestas posibles:

Non-increasing order
Non-decreasing order
strictly increasing order
strictly decreasing order

Explicación

Pregunta 38 de 200

1

Consider the following statements:
i. First-in-first out types of computations are efficiently supported by STACKS.
ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on
an array for almost all the basic LIST operations.
iii. Implementing QUEUES on a circular array is more efficient than implementing QUEUES
on a linear array with two indices.
iv. Last-in-first-out type of computations are efficiently supported by QUEUES.

Selecciona una de las siguientes respuestas posibles:

(ii) and (iii) are true
(i) and (ii) are true
(iii) and (iv) are true
(ii) and (iv) are true

Explicación

Pregunta 39 de 200

1

Following is C like pseudo code of a function that takes a Queue as an argument, and uses a stack S to do processing.
void fun(Queue *Q)
{
Stack S; // Say it creates an empty stack S

// Run while Q is not empty
while (!isEmpty(Q))
{
// deQueue an item from Q and push the dequeued item to S
push(&S, deQueue(Q));
}

// Run while Stack S is not empty
while (!isEmpty(&S))
{
// Pop an item from S and enqueue the poppped item to Q
enQueue(Q, pop(&S));
}
}
What does the above function do in general?

Selecciona una de las siguientes respuestas posibles:

Removes the last from Q
Keeps the Q same as it was before the call
Makes Q empty
Reverses the Q

Explicación

Pregunta 40 de 200

1

Which one of the following is an application of Queue Data Structure

Selecciona una de las siguientes respuestas posibles:

When a resource is shared among multiple consumers
When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes
Load Balancing
All of the above

Explicación

Pregunta 41 de 200

1

How many stacks are needed to implement a queue. Consider the situation where no other data structure like arrays, linked list is available to you.

Selecciona una de las siguientes respuestas posibles:

1
2
3
4

Explicación

Pregunta 42 de 200

1

How many queues are needed to implement a stack. Consider the situation where no other data structure like arrays, linked list is available to you.

Selecciona una de las siguientes respuestas posibles:

1
2
3
4

Explicación

Pregunta 43 de 200

1

A priority queue can efficiently implemented using which of the following data structures? Assume that the number of insert and peek (operation to see the current highest priority item) and extraction (remove the highest priority item) operations are almost same.

Selecciona una de las siguientes respuestas posibles:

Array
Linked List
Heap Data Structures like Binary Heap, Fibonacci Heap
None of the above

Explicación

Pregunta 44 de 200

1

Which of the following is true about linked list implementation of queue?

Selecciona una de las siguientes respuestas posibles:

In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.
In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.
Both of the above
None of the above

Explicación

Pregunta 45 de 200

1

Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are

Selecciona una de las siguientes respuestas posibles:

Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT
Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR
Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT
Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT

Explicación

Pregunta 46 de 200

1

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

Selecciona una de las siguientes respuestas posibles:

10, 8, 7, 5, 3, 2, 1
10, 8, 7, 2, 3, 1, 5
10, 8, 7, 1, 2, 3, 5
10, 8, 7, 3, 2, 1, 5

Explicación

Pregunta 47 de 200

1

An implementation of a queue Q, using two stacks S1 and S2, is given below:
void insert(Q, x) {
push (S1, x);
}

void delete(Q){
if(stack-empty(S2)) then
if(stack-empty(S1)) then {
print(“Q is empty”);
return;
}
else while (!(stack-empty(S1))){
x=pop(S1);
push(S2,x);
}
x=pop(S2);
}
Let n insert and m (<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?

Selecciona una de las siguientes respuestas posibles:

n+m <= x < 2n and 2m <= y <= n+m
n+m <= x < 2n and 2m<= y <= 2n
2m <= x < 2n and 2m <= y <= n+m
2m <= x <2n and 2m <= y <= 2n

Explicación

Pregunta 48 de 200

1

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.
MultiDequeue(Q){
m = k
while (Q is not empty and m > 0) {
Dequeue(Q)
m = m - 1
}
}
What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue? (GATE CS 2013)

Selecciona una de las siguientes respuestas posibles:

O(n)
O(n +k)
O(nk)
O(n^2)

Explicación

Pregunta 49 de 200

1

Consider the following pseudo code. Assume that IntQueue is an integer queue. What does the function fun do?
void fun(int n)
{
IntQueue q = new IntQueue();
q.enqueue(0);
q.enqueue(1);
for (int i = 0; i < n; i++)
{
int a = q.dequeue();
int b = q.dequeue();
q.enqueue(b);
q.enqueue(a + b);
ptint(a);
}
}

Selecciona una de las siguientes respuestas posibles:

Prints numbers from 0 to n-1
Prints numbers from n-1 to 0
Prints first n Fibonacci numbers
Prints first n Fibonacci numbers in reverse order

Explicación

Pregunta 50 de 200

1

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.
MultiDequeue(Q){
m = k
while (Q is not empty and m > 0) {
Dequeue(Q)
m = m - 1
}
}
What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue? (GATE CS 2013)

Selecciona una de las siguientes respuestas posibles:

O(n)
O(n+k)
O(n^2)
O(nk)

Explicación

Pregunta 51 de 200

1

Suppose implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?

Selecciona una de las siguientes respuestas posibles:

A queue cannot be implemented using this stack
A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.
A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.
A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

Explicación

Pregunta 52 de 200

1

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

Selecciona una de las siguientes respuestas posibles:

Both operations can be performed in O(1) time
At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
The worst case time complexity for both operations will be Ω(n)
Worst case time complexity for both operations will be Ω(log n)

Explicación

Pregunta 53 de 200

1

Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below.

The maximum possible number of iterations of the while loop in the algorithm is______

Selecciona una de las siguientes respuestas posibles:

16
32
256
64

Explicación

Pregunta 54 de 200

1

Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:
i. isEmpty (Q) — returns true if the queue is empty, false otherwise.
ii. delete (Q) — deletes the element at the front of the queue and returns its value.
iii. insert (Q, i) — inserts the integer i at the rear of the queue.
Consider the following function:
void f (queue Q) {
int i ;
if (!isEmpty(Q)) {
i = delete(Q);
f(Q);
insert(Q, i);
}
}
What operation is performed by the above function f ?

Selecciona una de las siguientes respuestas posibles:

Leaves the queue Q unchanged
Reverses the order of the elements in the queue Q
Deletes the element at the front of the queue Q and inserts it at the rear keeping the other elements in the same order
Empties the queue Q

Explicación

Pregunta 55 de 200

1

Consider the following statements:
i. First-in-first out types of computations are efficiently supported by STACKS.
ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on
an array for almost all the basic LIST operations.
iii. Implementing QUEUES on a circular array is more efficient than implementing QUEUES
on a linear array with two indices.
iv. Last-in-first-out type of computations are efficiently supported by QUEUES.

Selecciona una de las siguientes respuestas posibles:

(ii) and (iii) are true
(i) and (ii) are true
(iii) and (iv) are true
(ii) and (iv) are true

Explicación

Pregunta 56 de 200

1

Which of the following is a true about Binary Trees

Selecciona una de las siguientes respuestas posibles:

Every binary tree is either complete or full
Every complete binary tree is also a full binary tree
Every full binary tree is also a complete binary tree.
No binary tree is both complete and full.
None of the above

Explicación

Pregunta 57 de 200

1

If arity of operators is fixed, then which of the following notations can be used to parse expressions without parentheses?
a) Infix Notation (Inorder traversal of a expression tree)
b) Postfix Notation (Postorder traversal of a expression tree)
c) Prefix Notation (Preorder traversal of a expression tree)

Selecciona una de las siguientes respuestas posibles:

b and c
Only b
a, b and c
None of them

Explicación

Pregunta 58 de 200

1

What are the main applications of tree data structure? 1) Manipulate hierarchical data 2) Make information easy to search (see tree traversal). 3) Manipulate sorted lists of data 4) Router algorithms 5) Form of a multi-stage decision-making, like Chess Game. 6) As a workflow for compositing digital images for visual effects

Selecciona una de las siguientes respuestas posibles:

1, 2, 3, 4 and 6
1, 2, 3, 4 and 5
1, 3, 4, 5 and 6
1, 2, 3, 4, 5 and 6

Explicación

Pregunta 59 de 200

1

Level of a node is distance from root to that node. For example, level of root is 1 and levels of left and right children of root is 2. The maximum number of nodes on level i of a binary tree is

Selecciona una de las siguientes respuestas posibles:

2^(i)-1
2^
2^(i+1)
2^[(i+1)/2]

Explicación

Pregunta 60 de 200

1

In a complete k-ary tree, every internal node has exactly k children or no child. The number of leaves in such a tree with n internal nodes is:

Selecciona una de las siguientes respuestas posibles:

nk
(n – 1) k+ 1
n( k – 1) + 1
n(k – 1)

Explicación

Pregunta 61 de 200

1

The maximum number of binary trees that can be formed with three unlabeled nodes is

Selecciona una de las siguientes respuestas posibles:

1
5
4
3

Explicación

Pregunta 62 de 200

1

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

Selecciona una de las siguientes respuestas posibles:

n/2
(n-1)/3
(n-1)/2
(2n+1)/3

Explicación

Pregunta 63 de 200

1

A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?

Selecciona una de las siguientes respuestas posibles:

log_2 n
log_{4/3} n
log_3 n
log_{3/2} n

Explicación

Pregunta 64 de 200

1

A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?

Selecciona una de las siguientes respuestas posibles:

6
3
4
5

Explicación

Pregunta 65 de 200

1

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

Selecciona una de las siguientes respuestas posibles:

2^h -1
2^(h-1) – 1
2^(h+1) -1
2*(h+1)

Explicación

Pregunta 66 de 200

1

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be. (GATE CS 2006)

Selecciona una de las siguientes respuestas posibles:

log2n
b
2n + 1
2^n — 1

Explicación

Pregunta 67 de 200

1

Postorder traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an in-order traversal of the tree T? (GATE CS 2005)

Selecciona una de las siguientes respuestas posibles:

9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

Explicación

Pregunta 68 de 200

1

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

Selecciona una de las siguientes respuestas posibles:

(1 2 (4 5 6 7))
(1 (2 3 4) 5 6) 7)
(1 (2 3 4)(5 6 7))
(1 (2 3 NULL) (4 5))

Explicación

Pregunta 69 de 200

1

Consider a node X in a Binary Tree. Given that X has two children, let Y be Inorder successor of X. Which of the following is true about Y?

Selecciona una de las siguientes respuestas posibles:

Y has no right child
Y has no left child
Y has both children
None of the above

Explicación

Pregunta 70 de 200

1

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

Selecciona una de las siguientes respuestas posibles:

0
1
(n-1)/2
n-1

Explicación

Pregunta 71 de 200

1

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

Selecciona una de las siguientes respuestas posibles:

2^h −1
2^(h−1) -1
2^(h+1) -1
2^(h+1)

Explicación

Pregunta 72 de 200

1

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

Selecciona una de las siguientes respuestas posibles:

63 and 6, respectively
64 and 5, respectively
32 and 6, respectively
31 and 5, respectively

Explicación

Pregunta 73 de 200

1

A binary tree T has 20 leaves. The number of nodes in T having two children is

Selecciona una de las siguientes respuestas posibles:

18
19
17
Any number between 10 and 20

Explicación

Pregunta 74 de 200

1

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

Selecciona una de las siguientes respuestas posibles:

Ω(logn)
Ω(n)
Ω(nlogn)
Ω(n2)

Explicación

Pregunta 75 de 200

1

An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n - 1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n - 1)/2⌋, ⌊(n - 3)/ 2⌋, ....., 0. The time required to construct a heap in this manner is

Selecciona una de las siguientes respuestas posibles:

O(log n)
O(n)
O (n log log n)
O(n log n)

Explicación

Pregunta 76 de 200

1

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is:

Selecciona una de las siguientes respuestas posibles:

2^(h - 1)
2^(h - 1) + 1
2^h - 1
2^h

Explicación

Pregunta 77 de 200

1

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is ________

Selecciona una de las siguientes respuestas posibles:

15
16
31
32

Explicación

Pregunta 78 de 200

1

In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is

Selecciona una de las siguientes respuestas posibles:

10
11
12
15

Explicación

Pregunta 79 de 200

1

The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which.
MBCAFHPYK
KAMCBYPFH
MABCKYFPH
Pick the true statement from the following.

Selecciona una de las siguientes respuestas posibles:

I and II are preorder and inorder sequences, respectively
I and III are preorder and postorder sequences, respectively
II is the inorder sequence, but nothing more can be said about the other two sequences
II and III are the preorder and inorder sequences, respectively

Explicación

Pregunta 80 de 200

1

A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors.
n3 can be expressed as

Selecciona una de las siguientes respuestas posibles:

n1 + n2 - 1
n1 - 2
[((n1 + n2)/2)]
n2 - 1

Explicación

Pregunta 81 de 200

1

A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors.
Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?

Selecciona una de las siguientes respuestas posibles:

2 * n1 - 3
n2 + 2 * n1 - 2
n3 - n2
n2 + n1 - 2

Explicación

Pregunta 82 de 200

1

A binary search tree contains the values 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?

Selecciona una de las siguientes respuestas posibles:

53124786
53126487
53241678
53124768

Explicación

Pregunta 83 de 200

1

In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?
a
/ \
b e
/ \ /
c d f
/
g

Selecciona una de las siguientes respuestas posibles:

1
3
7
8

Explicación

Pregunta 84 de 200

1

Which of the following sequences denotes the post order traversal sequence of the given tree?
a
/ \
b e
/ \ /
c d f
/
g

Selecciona una de las siguientes respuestas posibles:

f e g c d b a
g c b d a f e
g c d b f e a
f e d g c b a

Explicación

Pregunta 85 de 200

1

What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree?

Selecciona una de las siguientes respuestas posibles:

O(n) for all
O(Logn) for all
O(Logn) for search and insert, and O(n) for delete
O(Logn) for search, and O(n) for insert and delete

Explicación

Pregunta 86 de 200

1

In delete operation of BST, we need inorder successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. Which of the following is true about inorder successor needed in delete operation?

Selecciona una de las siguientes respuestas posibles:

Inorder Successor is always a leaf node
Inorder successor is always either a leaf node or a node with empty left child
Inorder successor may be an ancestor of the node
Inorder successor is always either a leaf node or a node with empty right child

Explicación

Pregunta 87 de 200

1

We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree? (GATE CS 2011)

Selecciona una de las siguientes respuestas posibles:

n!
(1/(n+1)).2nCn
0
1

Explicación

Pregunta 88 de 200

1

How many distinct binary search trees can be created out of 4 distinct keys?

Selecciona una de las siguientes respuestas posibles:

4
14
24
42

Explicación

Pregunta 89 de 200

1

Which of the following traversal outputs the data in sorted order in a BST?

Selecciona una de las siguientes respuestas posibles:

Preorder
Inorder
Postorder
Level order

Explicación

Pregunta 90 de 200

1

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

Selecciona una de las siguientes respuestas posibles:

7 5 1 0 3 2 4 6 8 9
0 2 4 3 1 6 5 9 8 7
0 1 2 3 4 5 6 7 8 9
9 8 6 4 2 3 0 1 5 7

Explicación

Pregunta 91 de 200

1

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)? (GATE CS 2004)

Selecciona una de las siguientes respuestas posibles:

2
3
4
6

Explicación

Pregunta 92 de 200

1

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

Selecciona una de las siguientes respuestas posibles:

10, 20, 15, 23, 25, 35, 42, 39, 30
15, 10, 25, 23, 20, 42, 35, 39, 30
15, 20, 10, 23, 25, 42, 35, 39, 30
15, 10, 23, 25, 20, 35, 42, 39, 30

Explicación

Pregunta 93 de 200

1

Consider the following Binary Search Tree

10
/ \
5 20
/ / \
4 15 30
/
11
If we randomly search one of the keys present in above BST, what would be the expected number of comparisons?

Selecciona una de las siguientes respuestas posibles:

2.75
2.25
2.57
3.25

Explicación

Pregunta 94 de 200

1

Which of the following traversals is sufficient to construct BST from given traversals
1) Inorder
2) Preorder
3) Postorder

Selecciona una de las siguientes respuestas posibles:

Any one of the given three traversals is sufficient
Either 2 or 3 is sufficient
2 and 3
1 and 3

Explicación

Pregunta 95 de 200

1

Consider the following code snippet in C. The function print() receives root of a Binary Search Tree (BST) and a positive integer k as arguments.
// A BST node
struct node {
int data;
struct node left, right;
};

int count = 0;

void print(struct node *root, int k)
{
if (root != NULL && count <= k)
{
print(root->right, k);
count++;
if (count == k)
printf("%d ", root->data);
print(root->left, k);
}
}
What is the output of print(root, 3) where root represent root of the following BST.
15
/ \
10 20
/ \ / \
8 12 16 25

Selecciona una de las siguientes respuestas posibles:

10
16
20
10 20

Explicación

Pregunta 96 de 200

1

Consider the same code as given in above question. What does the function print() do in general? The function print() receives root of a Binary Search Tree (BST) and a positive integer k as arguments.
// A BST node
struct node {
int data;
struct node left, right;
};

int count = 0;

void print(struct node *root, int k)
{
if (root != NULL && count <= k)
{
print(root->right, k);
count++;
if (count == k)
printf("%d ", root->data);
print(root->left, k);
}
}

Selecciona una de las siguientes respuestas posibles:

Prints the kth smallest element in BST
Prints the kth largest element in BST
Prints the leftmost node at level k from root
Prints the rightmost node at level k from root

Explicación

Pregunta 97 de 200

1

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

Selecciona una de las siguientes respuestas posibles:

O(Logn)
O(n)
O(nLogn)
none of the above, as the tree cannot be uniquely determined

Explicación

Pregunta 98 de 200

1

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(nalogb n + mc logd n), the value of a + 10b + 100c + 1000d is ____.

Selecciona una de las siguientes respuestas posibles:

60
110
210
50

Explicación

Pregunta 99 de 200

1

Let T(n) be the number of different binary search trees on n distinct elements. Where x is

Selecciona una de las siguientes respuestas posibles:

n-k+1
n-k
n-k-1
n-k-2

Explicación

Pregunta 100 de 200

1

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

Selecciona una de las siguientes respuestas posibles:

Θ(logn) for both insertion and deletion
Θ(n) for both insertion and deletion
Θ(n) for insertion and Θ(logn) for deletion
Θ(logn) for insertion and Θ(n) for deletion

Explicación

Pregunta 101 de 200

1

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

Selecciona una de las siguientes respuestas posibles:

65
67
69
83

Explicación

Pregunta 102 de 200

1

The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _____________ Note: The height of a tree with a single node is 0.

Selecciona una de las siguientes respuestas posibles:

2
4
64
32

Explicación

Pregunta 103 de 200

1

Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined?

Selecciona una de las siguientes respuestas posibles:

{10, 75, 64, 43, 60, 57, 55}
{90, 12, 68, 34, 62, 45, 55}
{9, 85, 47, 68, 43, 57, 55}
{79, 14, 72, 56, 16, 53, 55}

Explicación

Pregunta 104 de 200

1

When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?

Selecciona una de las siguientes respuestas posibles:

35
64
128
5040

Explicación

Pregunta 105 de 200

1

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

I. 81, 537, 102, 439, 285, 376, 305

II. 52, 97, 121, 195, 242, 381, 472

III. 142, 248, 520, 386, 345, 270, 307

IV. 550, 149, 507, 395, 463, 402, 270

Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

Selecciona una de las siguientes respuestas posibles:

II and III only
I and III only
III and IV only
III only

Explicación

Pregunta 106 de 200

1

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270
Which of the following statements is TRUE?

Selecciona una de las siguientes respuestas posibles:

I, II and IV are inorder sequences of three different BSTs
I is a preorder sequence of some BST with 439 as the root
II is an inorder sequence of some BST where 121 is the root and 52 is a leaf
IV is a postorder sequence of some BST with 149 as the root

Explicación

Pregunta 107 de 200

1

How many distinct BSTs can be constructed with 3 distinct keys?

Selecciona una de las siguientes respuestas posibles:

4
5
9
6

Explicación

Pregunta 108 de 200

1

A binary search tree is generated by inserting in order the following integers:
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
The number of nodes in the left subtree and right subtree of the root respectively is

Selecciona una de las siguientes respuestas posibles:

(4, 7)
(7, 4)
(8, 3)
(3, 8)

Explicación

Pregunta 109 de 200

1

The worst case running time to search for an element in a balanced in a binary search tree with n2^n elements is

Selecciona una de las siguientes respuestas posibles:

O(n log n)
O (n2^n)
O (n)
O(log n)

Explicación

Pregunta 110 de 200

1

What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

Selecciona una de las siguientes respuestas posibles:

2
3
4
5

Explicación

Pregunta 111 de 200

1

What is the worst case possible height of AVL tree?

Selecciona una de las siguientes respuestas posibles:

2Logn
Assume base of log is 2
1.44log n
Assume base of log is 2
Depends upon implementation
Theta(n)

Explicación

Pregunta 112 de 200

1

Which of the following is AVL Tree?
A
100
/ \
50 200
/ \
10 300

B
100
/ \
50 200
/ / \
10 150 300
/
5

C
100
/ \
50 200
/ \ / \
10 60 150 300
/ \ \
5 180 400

Selecciona una de las siguientes respuestas posibles:

Only A
A and C
A, B and C
Only B

Explicación

Pregunta 113 de 200

1

Consider the following AVL tree.
60
/ \
20 100
/ \
80 120
Which of the following is updated AVL tree after insertion of 70
A
70
/ \
60 100
/ / \
20 80 120

B
100
/ \
60 120
/ \ /
20 70 80

C
80
/ \
60 100
/ \ \
20 70 120

D
80
/ \
60 100
/ / \
20 70 120

Selecciona una de las siguientes respuestas posibles:

A
B
C
D

Explicación

Pregunta 114 de 200

1

Consider the following left-rotate and right-rotate functions commonly used in self-adjusting BSTs
T1, T2 and T3 are subtrees of the tree rooted with y (on left side)
or x (on right side)
y x
/ \ Right Rotation / \
x T3 – - – - – - – > T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
Which of the following is tightest upper bound for left-rotate and right-rotate operations.

Selecciona una de las siguientes respuestas posibles:

O(1)
O(Logn)
O(LogLogn)
O(n)

Explicación

Pregunta 115 de 200

1

Which of the following is true

Selecciona una de las siguientes respuestas posibles:

The AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion.
Heights of AVL and Red-Black trees are generally same, but AVL Trees may cause more rotations during insertion and deletion.
Red Black trees are more balanced compared to AVL Trees, but may cause more rotations during insertion and deletion.
Heights of AVL and Red-Black trees are generally same, but Red Black rees may cause more rotations during insertion and deletion.

Explicación

Pregunta 116 de 200

1

Which of the following is true about Red Black Trees?

Selecciona una de las siguientes respuestas posibles:

The path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf
At least one children of every black node is red
Root may be red
A leaf node may be red

Explicación

Pregunta 117 de 200

1

Which of the following is true about AVL and Red Black Trees?

Selecciona una de las siguientes respuestas posibles:

In AVL tree insert() operation, we first traverse from root to newly inserted node and then from newly inserted node to root. While in Red Black tree insert(), we only traverse once from root to newly inserted node.
In both AVL and Red Black insert operations, we traverse only once from root to newly inserted node,
In both AVL and Red Black insert operations, we traverse twiceL first traverse root to newly inserted node and then from newly inserted node to root.
None of the above

Explicación

Pregunta 118 de 200

1

What is the worst case possible height of Red-Black tree? Assume base of Log as 2 in all options

Selecciona una de las siguientes respuestas posibles:

2Log(n+1)
1.44 Logn
4Logn
None of the above

Explicación

Pregunta 119 de 200

1

Which of the following is a self-adjusting or self-balancing Binary Search Tree

Selecciona una de las siguientes respuestas posibles:

Splay Tree
AVL Tree
Red Black Tree
All of the above

Explicación

Pregunta 120 de 200

1

Is the following statement valid? A Red-Black Tree which is also a perfect Binary Tree can have all black nodes

Selecciona una de las siguientes respuestas posibles:

Yes
No

Explicación

Pregunta 121 de 200

1

Which of the following operations are used by Red-Black trees to maintain balance during insertion/deletion?

a) Recoloring of nodes
b) Rotation (Left and Right)

Selecciona una de las siguientes respuestas posibles:

Only a
Only b
Both a and b
Neither a nor b

Explicación

Pregunta 122 de 200

1

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then the worst-case time complexity of the program is

Selecciona una de las siguientes respuestas posibles:

Θ(n)
Θ(nLogn)
Θ(n^2)
Θ(n^2 log n)

Explicación

Pregunta 123 de 200

1

Which of the following is TRUE?

Selecciona una de las siguientes respuestas posibles:

The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n)
The cost of searching an AVL tree is θ (log n) but that of a complete binary tree is θ (n log n)
The cost of searching a binary search tree is O (log n ) but that of an AVL tree is θ(n)
The cost of searching an AVL tree is θ (n log n) but that of a binary search tree is O(n)

Explicación

Pregunta 124 de 200

1

Given two Balanced binary search trees, B1 having n elements and B2 having m elements, what is the time complexity of the best known algorithm to merge these trees to form another balanced binary tree containing m+n elements ?

Selecciona una de las siguientes respuestas posibles:

O(m+n)
O(mlogn)
O(nlogm)
O(m^2 + n^2)

Explicación

Pregunta 125 de 200

1

Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?

Selecciona una de las siguientes respuestas posibles:

Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?
DFS and BSF can be done in O(V + E) time for adjacency list representation. These operations take O(V^2) time in adjacency matrix representation. Here is V and E are number of vertices and edges respectively.
Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
All of the above

Explicación

Pregunta 126 de 200

1

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
I. 7, 6, 5, 4, 4, 3, 2, 1
II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2
IV. 8, 7, 7, 6, 4, 2, 1, 1

Selecciona una de las siguientes respuestas posibles:

I and II
III and IV
IV only
II and IV

Explicación

Pregunta 127 de 200

1

The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be:

Selecciona una de las siguientes respuestas posibles:

O(n)
O(nLogn)
O(n ^ (3/2))
O(n^3)

Explicación

Pregunta 128 de 200

1

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity.

Selecciona una de las siguientes respuestas posibles:

O(n)
O(m)
O(m+n)
O(mn)

Explicación

Pregunta 129 de 200

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. lf u is visited before v during the breadth-first traversal, which of the following statements is correct? (GATE CS 2001)

Selecciona una de las siguientes respuestas posibles:

d(r, u) < d (r, v)
d(r, u) > d(r, v)
d(r, u) <= d (r, v)
None of the above

Explicación

Pregunta 130 de 200

1

How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2,…V n} of n vertices ?

Selecciona una de las siguientes respuestas posibles:

n(n-l)/2
2^n
n!
2^(n(n-1)/2)

Explicación

Pregunta 131 de 200

1

Which of the following statements is/are TRUE for an undirected graph?
P: Number of odd degree vertices is even
Q: Sum of degrees of all vertices is even

Selecciona una de las siguientes respuestas posibles:

P Only
Q Only
Both P and Q
Neither P nor Q

Explicación

Pregunta 132 de 200

1

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?

Selecciona una de las siguientes respuestas posibles:

1/8
1
8
7

Explicación

Pregunta 133 de 200

1

Given an undirected graph G with V vertices and E edges, the sum of the degrees of all vertices is

Selecciona una de las siguientes respuestas posibles:

E
2E
V
2V

Explicación

Pregunta 134 de 200

1

How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v1, v2, ... vn} of n vertices?

Selecciona una de las siguientes respuestas posibles:

n(n-1)/2
2^n
n!
2^(n(n-1)/2)

Explicación

Pregunta 135 de 200

1

What is the maximum number of edges in an acyclic undirected graph with n vertices?

Selecciona una de las siguientes respuestas posibles:

n-i
n
n + 1
2n-1

Explicación

Pregunta 136 de 200

1

Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?

Selecciona una de las siguientes respuestas posibles:

There exists a cutset in G having all edges of maximum weight
There exists a cycle in G having all edges of maximum weight
Edge e cannot be contained in a cycle
All edges in G have the same weight

Explicación

Pregunta 137 de 200

1

A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.
i = 0
do {
j = i + 1;
while ((j < n) && E1) j++;
if (j < n) E2;
} while (j < n);

flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3)
flag = 0;

if (flag)
printf("Sink exists");
else
printf("Sink does not exist");
Choose the correct expressions for E3

Selecciona una de las siguientes respuestas posibles:

(A[i][j] && !A[j][i])
(!A[i][j] && A[j][i])
(!A[i][j] | | A[j][i])
(A[i][j] | | !A[j][i])

Explicación

Pregunta 138 de 200

1

Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updation interval, three tasks are performed.
1)A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as 1. Otherwise, the cost is set to ∞.
2)From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
3)Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.
For the graph given above, possible routing tables for various nodes after they have stabilized, are shown in the following options. Identify the correct table.

Selecciona una de las siguientes respuestas posibles:

A - -
B B 1
C C 1
D B 3
E C 3
F C 4
A A 1
B B 1
C - -
D D 1
E E 1
F E 3
A A 1
B - -
C C 1
D D 1
E C 2
F D 2
A B 3
B B 1
C C 1
D - -
E E 1
F F 1

Explicación

Pregunta 139 de 200

1

Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updation interval, three tasks are performed.
1)A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as 1. Otherwise, the cost is set to ∞.
2)From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
3)Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.
For the graph given above, possible routing tables for various nodes after they have stabilized, are shown in the following options. Identify the correct table.
Table for node A
A - -
B B 1
C C 1
D B 3
E C 3
F C 4
2) Table for node C
A A 1
B B 1
C - -
D D 1
E E 1
F E 3
3)
Table for node B
A A 1
B - -
C C 1
D D 1
E C 2
F D 2
4) Table for node D
A B 3
B B 1
C C 1
D - -
E E 1
F F 1
Continuing from the earlier problem, suppose at some time t, when the costs have stabilized, node A goes down. The cost from node F to node A at time (t + 100) is

Selecciona una de las siguientes respuestas posibles:

>100 but finite
∞
3
>3 and ≤100

Explicación

Pregunta 140 de 200

1

The cyclomatic complexity of the flow graph of a program provides

Selecciona una de las siguientes respuestas posibles:

an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at most once
a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at most once
an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once
a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at least once

Explicación

Pregunta 141 de 200

1

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?

Selecciona una de las siguientes respuestas posibles:

1
2
3
n

Explicación

Pregunta 142 de 200

1

For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree?

Selecciona una de las siguientes respuestas posibles:

(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)
(c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)
(d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)
(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)

Explicación

Pregunta 143 de 200

1

Consider a directed graph with n vertices and m edges such that all edges have same edge weights. Find the complexity of the best known algorithm to compute the minimum spanning tree of the graph?

Selecciona una de las siguientes respuestas posibles:

O(m+n)
O(m logn)
O(mn)
O(n logm)

Explicación

Pregunta 144 de 200

1

You are given a graph containing n vertices and m edges and given that the graph doesn’t contain cycle of odd length. Time Complexity of the best known algorithm to find out whether the graph is bipartite or not is ?

Selecciona una de las siguientes respuestas posibles:

O(m+n)
O(1)
O(mn)
O(n2)

Explicación

Pregunta 145 de 200

1

Let G be a simple graph with 20 vertices and 8 components. If we delete a vertex in G, then number of components in G should lie between ____.

Selecciona una de las siguientes respuestas posibles:

8 and 20
8 and 19
7 and 19
7 and 20

Explicación

Pregunta 146 de 200

1

Let G be the graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent iff |i−j|=8 or |i−j|=12. The number of connected components in G is

Selecciona una de las siguientes respuestas posibles:

8
4
12
25

Explicación

Pregunta 147 de 200

1

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.
Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

Selecciona una de las siguientes respuestas posibles:

46, 42, 34, 52, 23, 33
34, 42, 23, 52, 33, 46
46, 34, 42, 23, 52, 33
42, 46, 33, 23, 34, 52

Explicación

Pregunta 148 de 200

1

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

Selecciona una de las siguientes respuestas posibles:

10
20
30
40

Explicación

Pregunta 149 de 200

1

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?

Selecciona una de las siguientes respuestas posibles:

A
B
C
D

Explicación

Pregunta 150 de 200

1

Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.

Selecciona una de las siguientes respuestas posibles:

8, _, _, _, _, _, 10
1, 8, 10, _, _, _, 3
1, _, _, _, _, _,3
1, 10, 8, _, _, _, 3

Explicación

Pregunta 151 de 200

1

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?
i. 9679, 1989, 4199 hash to the same value
ii. 1471, 6171 has to the same value
iii. All elements hash to the same value
iv. Each element hashes to a different value (GATE CS 2004)

Selecciona una de las siguientes respuestas posibles:

i only
ii only
i and ii only
iii or iv

Explicación

Pregunta 152 de 200

1

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

Selecciona una de las siguientes respuestas posibles:

(97 × 97 × 97)/100^3
(99 × 98 × 97)/100^3
(97 × 96 × 95)/100^3
(97 × 96 × 95)/(3! × 100^3)

Explicación

Pregunta 153 de 200

1

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

Selecciona una de las siguientes respuestas posibles:

h(i) =i^2 mod 10
h(i) =i^3 mod 10
h(i) = (11 ∗ i^2) mod 10
h(i) = (12 ∗ i) mod 10

Explicación

Pregunta 154 de 200

1

Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is __________

Selecciona una de las siguientes respuestas posibles:

80
0.0125
8000
1.25

Explicación

Pregunta 155 de 200

1

Which of the following statement(s) is TRUE?
1) A hash function takes a message of arbitrary length and generates a fixed length code.
2) A hash function takes a message of fixed length and generates a code of variable length.
3) A hash function may give the same hash value for distinct messages.

Selecciona una de las siguientes respuestas posibles:

I only
II and III only
I and III only
II only

Explicación

Pregunta 156 de 200

1

Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5.

Selecciona una de las siguientes respuestas posibles:

5
6
7
10

Explicación

Pregunta 157 de 200

1

An advantage of chained hash table (external hashing) over the open addressing scheme is

Selecciona una de las siguientes respuestas posibles:

Worst case complexity of search operations is less
Space used is less
Deletion is easier
None of the above

Explicación

Pregunta 158 de 200

1

A program P reads in 500 integers in the range [0..100] exepresenting the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

Selecciona una de las siguientes respuestas posibles:

An array of 50 number
An array of 100 numbers
An array of 500 numbers
A dynamically allocated array of 550 numbers

Explicación

Pregunta 159 de 200

1

Which of the following operations is not O(1) for an array of sorted data. You may assume that array elements are distinct.

Selecciona una de las siguientes respuestas posibles:

Find the ith largest element
Delete an element
Find the ith smallest element
All of the above

Explicación

Pregunta 160 de 200

1

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

Selecciona una de las siguientes respuestas posibles:

O(n)
O(logn)
O(log*n)
O(1)

Explicación

Pregunta 161 de 200

1

Let A be a square matrix of size n x n. Consider the following program. What is the expected output?
C = 100
for i = 1 to n do
for j = 1 to n do
{
Temp = A[i][j] + C
A[i][j] = A[j][i]
A[j][i] = Temp - C
}
for i = 1 to n do
for j = 1 to n do
Output(A[i][j]);

Selecciona una de las siguientes respuestas posibles:

The matrix A itself
Transpose of matrix A
Adding 100 to the upper diagonal elements and subtracting 100 from diagonal elements of A
None of the above

Explicación

Pregunta 162 de 200

1

An algorithm performs (logN)^1/2 find operations, N insert operations, (logN)^1/2 operations, and (logN)^1/2 decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

Selecciona una de las siguientes respuestas posibles:

Unsorted array
Min-heap
Sorted array
Sorted doubly linked list

Explicación

Pregunta 163 de 200

1

Consider an array consisting of –ve and +ve numbers. What would be the worst time comparisons an algorithm can take in order to segregate the numbers having same sign altogether i.e all +ve on one side and then all -ve on the other ?

Selecciona una de las siguientes respuestas posibles:

N-1
N
N+1
(N*(N-1))/2

Explicación

Pregunta 164 de 200

1

What is the time complexity of Build Heap operation. Build Heap is used to build a max(or min) binary heap from a given array. Build Heap is used in Heap Sort as a first step for sorting.

Selecciona una de las siguientes respuestas posibles:

O(nLogn)
O(n^2)
O(Logn)
O(n)

Explicación

Pregunta 165 de 200

1

Suppose we are sorting an array of eight integers using heapsort, and we have just finished some heapify (either maxheapify or minheapify) operations. The array now looks like this: 16 14 15 10 12 27 28 How many heapify operations have been performed on root of heap?

Selecciona una de las siguientes respuestas posibles:

1
2
3 or 4
5 or 6

Explicación

Pregunta 166 de 200

1

A max-heap is a heap where the value of each parent is greater than or equal to the values of its children. Which of the following is a max-heap?

Selecciona una de las siguientes respuestas posibles:

A
B
C
D

Explicación

Pregunta 167 de 200

1

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?

Selecciona una de las siguientes respuestas posibles:

1, 3, 5, 6, 8, 9
9, 6, 3, 1, 8, 5
9, 3, 6, 8, 5, 1
9, 5, 6, 8, 3, 1

Explicación

Pregunta 168 de 200

1

Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question, Which one of the following is the sequence of items in the array representing the resultant heap?

Selecciona una de las siguientes respuestas posibles:

10, 7, 9, 8, 3, 1, 5, 2, 6, 4
10, 9, 8, 7, 6, 5, 4, 3, 2, 1
10, 9, 4, 5, 7, 6, 8, 2, 1, 3
10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Explicación

Pregunta 169 de 200

1

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

Selecciona una de las siguientes respuestas posibles:

25,12,16,13,10,8,14.
25,12,16,13,10,8,14
25,14,16,13,10,8,12
25,14,12,13,10,8,16

Explicación

Pregunta 170 de 200

1

What is the content of the array after two delete operations on the correct answer to the previous question?

Selecciona una de las siguientes respuestas posibles:

14,13,12,10,8
14,12,13,8,10
14,13,8,12,10
14,13,12,8,10

Explicación

Pregunta 171 de 200

1

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 is

Selecciona una de las siguientes respuestas posibles:

O(logn)
O(n)
O(nlogn)
O(n^2)

Explicación

Pregunta 172 de 200

1

In a min-heap with n elements with the smallest element at the root, the 7th smallest element can be found in time a) \theta(n log n) b) \theta(n) c) \theta(log n) d) \theta(1) The question was not clear in original GATE exam. For clarity, assume that there are no duplicates in Min-Heap and accessing heap elements below root is allowed.

Selecciona una de las siguientes respuestas posibles:

O(nlogn)
O(n)
O(logn)
O(1)

Explicación

Pregunta 173 de 200

1

In a binary max heap containing n numbers, the smallest element can be found in time

Selecciona una de las siguientes respuestas posibles:

0(n)
O(logn)
0(loglogn)
0(1)

Explicación

Pregunta 174 de 200

1

The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is.

Selecciona una de las siguientes respuestas posibles:

A
B
C
D

Explicación

Pregunta 175 de 200

1

Given two max heaps of size n each, what is the minimum possible time complexity to make a one max-heap of size from elements of two max heaps?

Selecciona una de las siguientes respuestas posibles:

O(nLogn).
O(nLogLogn)
O(n)
O(nLogn)

Explicación

Pregunta 176 de 200

1

A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

Selecciona una de las siguientes respuestas posibles:

10, 8, 7, 3, 2, 1, 5
10, 8, 7, 2, 3, 1, 5
10, 8, 7, 1, 2, 3, 5
10, 8, 7, 5, 3, 2, 1

Explicación

Pregunta 177 de 200

1

Which of the following Binary Min Heap operation has the highest time complexity?

Selecciona una de las siguientes respuestas posibles:

Inserting an item under the assumption that the heap has capacity to accommodate one more item
Merging with another heap under the assumption that the heap has capacity to accommodate items of other heap
Deleting an item from heap
Decreasing value of a key

Explicación

Pregunta 178 de 200

1

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

Selecciona una de las siguientes respuestas posibles:

i - 1
floor(i/2)
ceiling(i/2)
(i+1)/2

Explicación

Pregunta 179 de 200

1

Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

Selecciona una de las siguientes respuestas posibles:

40, 30, 20, 10, 15, 16, 17, 8, 4, 35
40, 35, 20, 10, 30, 16, 17, 8, 4, 15
40, 30, 20, 10, 35, 16, 17, 8, 4, 15
40, 35, 20, 10, 15, 16, 17, 8, 4, 30

Explicación

Pregunta 180 de 200

1

Consider the following array of elements. 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉. The minimum number of interchanges needed to convert it into a max-heap is

Selecciona una de las siguientes respuestas posibles:

4
5
2
3

Explicación

Pregunta 181 de 200

1

An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?

Selecciona una de las siguientes respuestas posibles:

O(1)
O(d) but not O(1)
O(2^d) but not O(d)
O(d2^d) but not O(2^d)

Explicación

Pregunta 182 de 200

1

A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _____________

Selecciona una de las siguientes respuestas posibles:

6
7
8
9

Explicación

Pregunta 183 de 200

1

Which of the following sequences of array elements forms a heap?

Selecciona una de las siguientes respuestas posibles:

{23, 17, 14, 6, 13, 10, 1, 12, 7, 5}
{23, 17, 14, 6, 13, 10, 1, 5, 7, 12}
{23, 17, 14, 7, 13, 10, 1, 5, 6, 12}
{23, 17, 14, 7, 13, 10, 1, 12, 5, 7}

Explicación

Pregunta 184 de 200

1

The minimum number of interchanges needed to convert the array 89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70 into a heap with the maximum element at the root is

Selecciona una de las siguientes respuestas posibles:

0
1
2
3

Explicación

Pregunta 185 de 200

1

Following function is supposed to calculate the maximum depth or height of a Binary tree -- the number of nodes along the longest path from the root node down to the farthest leaf node.
int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree /
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);

/ use the larger one */
if (lDepth > rDepth)
return X;
else return Y;
}
}
What should be the values of X and Y so that the function works correctly?

Selecciona una de las siguientes respuestas posibles:

X = lDepth, Y = rDepth
X = lDepth + 1, Y = rDepth + 1
X = lDepth - 1, Y = rDepth -1
None of the above

Explicación

Pregunta 186 de 200

1

What is common in three different types of traversals (Inorder, Preorder and Postorder)?

Selecciona una de las siguientes respuestas posibles:

Root is visited before right subtree
Left subtree is always visited before right subtree
Root is visited after left subtree
All of the above
None of the above

Explicación

Pregunta 187 de 200

1

The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:

Selecciona una de las siguientes respuestas posibles:

d e b f g c a
e d b g f c a
e d b f g c a
d e f g b c a

Explicación

Pregunta 188 de 200

1

What does the following function do for a given binary tree?
int fun(struct node *root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 0;
return 1 + fun(root->left) + fun(root->right);
}

Selecciona una de las siguientes respuestas posibles:

Counts leaf nodes
Counts internal nodes
Returns height where height is defined as number of edges on the path from root to deepest node
Return diameter where diameter is number of edges on the longest path between any two nodes.

Explicación

Pregunta 189 de 200

1

Which of the following pairs of traversals is not sufficient to build a binary tree from the given traversals?

Selecciona una de las siguientes respuestas posibles:

Preorder and Inorder
Preorder and Postorder
Inorder and Postorder
None of the Above

Explicación

Pregunta 190 de 200

1

Consider two binary operators '\uparrow ' and '\downarrow' with the precedence of operator \downarrow being lower than that of the \uparrow operator. Operator \uparrow is right associative while operator \downarrow is left associative. Which one of the following represents the parse tree for expression (7 \downarrow 3 \uparrow 4 \uparrow 3 \downarrow 2)?

Selecciona una de las siguientes respuestas posibles:

A
B
C
D

Explicación

Pregunta 191 de 200

1

Which traversal of tree resembles the breadth first search of the graph?

Selecciona una de las siguientes respuestas posibles:

Preorder
Inorder
Postorder
Level order

Explicación

Pregunta 192 de 200

1

Which of the following tree traversal uses a queue data structure?

Selecciona una de las siguientes respuestas posibles:

Preorder
Inorder
Postorder
Level order

Explicación

Pregunta 193 de 200

1

Which of the following cannot generate the full binary tree?

Selecciona una de las siguientes respuestas posibles:

Inorder and Preorder
Inorder and Postorder
Preorder and Postorder
None of the above

Explicación

Pregunta 194 de 200

1

Consider the following C program segment
struct CellNode
{
struct CelINode leftchild;
int element;
struct CelINode rightChild;
}

int Dosomething(struct CelINode *ptr)
{
int value = 0;
if (ptr != NULL)
{
if (ptr->leftChild != NULL)
value = 1 + DoSomething(ptr->leftChild);
if (ptr->rightChild != NULL)
value = max(value, 1 + DoSomething(ptr->rightChild));
}
return (value);
}
The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is

Selecciona una de las siguientes respuestas posibles:

The number of leaf nodes in the tree
The number of nodes in the tree
The number of internal nodes in the tree
The height of the tree

Explicación

Pregunta 195 de 200

1

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true?

Selecciona una de las siguientes respuestas posibles:

LASTIN = LASTPOST
LASTIN = LASTPRE
LASTPRE = LASTPOST
None of the above

Explicación

Pregunta 196 de 200

1

The array representation of a complete binary tree contains the data in sorted order. Which traversal of the tree will produce the data in sorted form?

Selecciona una de las siguientes respuestas posibles:

Preorder
Inorder
Postorder
Level order

Explicación

Pregunta 197 de 200

1

Consider the following rooted tree with the vertex P labeled as root
The order in which the nodes are visited during in-order traversal is

Selecciona una de las siguientes respuestas posibles:

SQPTRWUV
SQPTURWV
SQPTWUVR
SQPTRUWV

Explicación

Pregunta 198 de 200

1

Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.
typedef struct treeNode* treeptr;
struct treeNode
{
treeptr leftMostChild, rightSibling;
};
int DoSomething (treeptr tree)
{
int value=0;
if (tree != NULL)
{
if (tree->leftMostChild == NULL)
value = 1;
else
value = DoSomething(tree->leftMostChild);
value = value + DoSomething(tree->rightSibling);
}
return(value);
}

When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the

Selecciona una de las siguientes respuestas posibles:

number of internal nodes in the tree.
height of the tree
number of nodes without a right sibling in the tree
number of leaf nodes in the tree

Explicación

Pregunta 199 de 200

1

Level order traversal of a rooted tree can be done by starting from the root and performing

Selecciona una de las siguientes respuestas posibles:

preorder traversal
inorder traversal
depth first search
breadth first searc

Explicación

Pregunta 200 de 200

1

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely ?
(i) preorder and postorder
(ii) inorder and postorder
(iii) preorder and inorder
(iv) level order and postorder

Selecciona una de las siguientes respuestas posibles:

(i) only
(ii), (iii)
(iii) only
(iv) only

	Creado por Alex Q hace casi 9 años

Test sobre Advanced Algorithm (Eldan) 1 (200), creado por Alex Q el 23/12/2017.

Advanced Algorithm (Eldan) 1 (200)

Advanced Algorithm (Eldan) 1 (200)

Pregunta 1 de 200

What does the following function do for a given Linked List with first node as head? void fun1(struct node* head) { if(head == NULL) return; fun1(head->next); printf("%d ", head->data); }

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 2 de 200

Which of the following points is/are true about Linked List data structure when it is compared with array

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 3 de 200

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 4 de 200

Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 5 de 200

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 6 de 200

What is the output of following function for start pointing to first node of following linked list? 1->2->3->4->5->6 void fun(struct node* start) { if(start == NULL) return; printf("%d ", start->data); if(start->next != NULL ) fun(start->next->next); printf("%d ", start->data); }

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 7 de 200

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 8 de 200

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 9 de 200

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is (GATE CS 2002)

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 10 de 200

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest? (GATE CS 2004)

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 11 de 200

Consider the function f defined below. struct item { int data; struct item * next; }; int f(struct item *p) { return ( (p == NULL) || (p->next == NULL) || (( P->data <= p->next->data) && f(p->next)) ); } For a given linked list p, the function f returns 1 if and only if (GATE CS 2003)

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 12 de 200

A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time? (GATE 2004)

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 13 de 200

What are the time complexities of finding 8th element from beginning and 8th element from end in a singly linked list? Let n be the number of nodes in linked list, you may assume that n > 8.

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 14 de 200

Is it possible to create a doubly linked list using only one pointer with every node.

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 15 de 200

Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 16 de 200

You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 17 de 200

Consider the following function to traverse a linked list. void traverse(struct Node *head) { while (head->next != NULL) { printf("%d ", head->data); head = head->next; } } Which of the following is FALSE about above function?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 18 de 200

Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 19 de 200

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 20 de 200

The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 21 de 200

Selecciona una de las siguientes respuestas posibles:

What does the following function do for a given Linked List with first node as head?
void fun1(struct node* head)
{
if(head == NULL)
return;

fun1(head->next);
printf("%d ", head->data);
}

What is the output of following function for start pointing to first node of following linked list? 1->2->3->4->5->6
void fun(struct node* start)
{
if(start == NULL)
return;
printf("%d ", start->data);

if(start->next != NULL )
fun(start->next->next);
printf("%d ", start->data);
}

Consider the function f defined below.
struct item
{
int data;
struct item * next;
};

int f(struct item *p)
{
return (
(p == NULL) ||
(p->next == NULL) ||
(( P->data <= p->next->data) && f(p->next))
);
}
For a given linked list p, the function f returns 1 if and only if (GATE CS 2003)

Consider the following function to traverse a linked list.
void traverse(struct Node *head)
{
while (head->next != NULL)
{
printf("%d ", head->data);
head = head->next;
}
}
Which of the following is FALSE about above function?

Consider the following pseudocode that uses a stack
declare a stack of characters
while ( there are more characters in the word to read )
{
read a character
push the character on the stack
}
while ( the stack is not empty )
{
pop a character off the stack
write the character to the screen
}

The following postfix expression with single digit operands is evaluated using a stack:
8 2 3 ^ / 2 3 * + 5 1 * -
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i.
If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?