Are red-black trees asked in GATE CS Data Structure?

Yes, GATE has tested red-black tree properties, insertion rules, and comparison with AVL trees. Key properties include coloring rules, black-height, and rotation after insertion.

What is a disjoint set and how is it tested in GATE?

A disjoint set (union-find) data structure manages a collection of non-overlapping sets. GATE tests union by rank, path compression, and time complexity of find and union operations.

How is the Trie data structure relevant to GATE CS?

Tries are used for efficient string search and prefix matching. GATE tests number of nodes in a trie, search complexity, and space usage compared to hash tables for string keys.

CS/IT Gate Subject

Aptitude and Reasoning
Engineering Mathematics
C Programming
Data Structure
Design Algorithm Analysis
Operating System
Computer Network
Digital Logic Design
Compiler Design
Database Management System
Theory of Computation

Data Structure GATE previous year questions with answer

1 2 3 4 5 6

Ques 53 Gate 2016 Set-1

What will be the output of the following C program?

void count(int n)
{
static int d = 1;
printf("%d ", n);
printf("%d ", d);
d++;
if(n > 1) count(n-1);
printf("%d ", d);
}
int main()
{
count(3);
}

3 1 2 2 1 3 4 4 4

3 1 2 1 1 1 2 2 2

3 1 2 2 1 3 4

3 1 2 1 1 1 2

(C code) is the correct answer.

Ques 54 Gate 2016 Set-1

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change

P only

Q only

Both P and Q

Neither P nor Q

(Graph Theory) is the correct answer.

Ques 55 Gate 2016 Set-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)?

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 Ω(logn)

(Queue) is the correct answer.

Ques 56 Gate 2015 Set-3

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

(a) is the correct answer.

Ques 57 Gate 2015 Set-3

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

256

512

1024

2048

(a) is the correct answer.

Mergesort Time Complexity:
• The worst-case time complexity of Mergesort is Θ(n log n).
• This means that the running time T(n) can be expressed as T(n) = c · n log₂ n, where c is a constant and n is the input size.

Calculate the Constant 'c':
We are given that T(64) = 30 seconds.
• Substitute n = 64 into the formula:
    T(64) = c · 64 log₂ 64
• We know that log₂ 64 = 6 (since 2⁶ = 64).
    30 = c · 64 · 6
    30 = c · 384
• Solve for c:
    c = 30 / 384

Convert Target Time to Seconds:
The new time limit is 6 minutes.
• 6 minutes = 6 · 60 seconds = 360 seconds.

Set Up Equation for New Input Size:
Let n_new be the maximum input size we can solve in 360 seconds.
• T(n_new) = c · n_new log₂ n_new
• Substitute the values for T(n_new) and c:
    360 = (30 / 384) · n_new log₂ n_new

Solve for n_new log₂ n_new:
• Multiply both sides by 384/30:
    360 · (384 / 30) = n_new log₂ n_new
• Simplify the left side:
    (360 / 30) · 384 = n_new log₂ n_new
    12 · 384 = n_new log₂ n_new
    4608 = n_new log₂ n_new

Check the Given Options:
We need to find an n_new such that n_new log₂ n_new is approximately 4608.
• For n = 256:
    256 log₂ 256 = 256 · 8 = 2048
• For n = 512:
    512 log₂ 512 = 512 · 9 = 4608
• For n = 1024:
    1024 log₂ 1024 = 1024 · 10 = 10240
• For n = 2048:
    2048 log₂ 2048 = 2048 · 11 = 22528

Comparing the calculated values with 4608, n = 512 yields an exact match.
Therefore, the maximum input size that can be solved in 6 minutes is 512.

Ques 58 Gate 2015 Set-3

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

(Array) is the correct answer.

PROCESSED

Ques 59 Gate 2015 Set-3

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

(Binary Search Tree) is the correct answer.

PROCESSED

Ques 60 Gate 2015 Set-3

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

284

213

142

(Stack) is the correct answer.

PROCESSED

Ques 61 Gate 2015 Set-2

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

(a) is the correct answer.

Ques 62 Gate 2015 Set-2

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

Ω(logn)

Ω(n)

Ω(nlogn)

Ω(n²)

(Complexity) is the correct answer.

PROCESSED

1 2 3 4 5 6

Total Unique Visitors

Loading......

CS/IT Gate Subject

Data Structure GATE previous year questions with answer

Question Options

Sign in to ExamPrev