GATE CS Programming and Data Structures questions

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 $\text{enQueue}$ and $\text{deQueue}$ can be performed in constant time?

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

Consider the following C program segment: char p[20]; int i; char* s = "string"; int length = strlen(s); for(i = 0; i < length; i++) p[i] = s[length-i]; printf("%s", p); The output of the program is:

Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let $n = d_1\, d_2\, \ldots\, d_m$. int n, rev; rev = 0; while(n > 0) { rev = rev * 10 + n%10; n = n/10; } The loop invariant condition at the end of the $i^{th}$ iteration is:

Consider the following C function: int f(int n) { static int i = 1; if(n >= 5) return n; n = n+i; i++; return f(n); } The value returned by $f(1)$ is:

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? $9679, 1989, 4199$ hash to the same value $1471, 6171$ hash to the same value All elements hash to the same value Each element hashes to a different value

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

The best data structure to check whether an arithmetic expression has balanced parentheses is a

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)?

A single array $A[1 \ldots \text{MAXSIZE}]$ is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables $top1$ and $top2$ $(top1 < 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 $\text{“}\textsf{stack full}\text{”}$ is

The goal of structured programming is to:

In a min-heap with $n$ elements with the smallest element at the root, the $7^{th}$ smallest element can be found in time

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

Consider the C program shown below: #include<stdio.h> #define print(x) printf("%d", x) int x; void Q(int z) { z+=x; print(z); } void P(int *y) { int x = *y + 2; Q(x); *y = x - 1; print(x); } main(void) { x = 5; P(&x); print(x); } The output of this program is:

Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses dynamic binding. The language should not be assumed to be either Java or C++, though the syntax is similar. Class P { Class Q subclass of P { void f(int i) { void f(int i) { print(i); print(2*i); } } } } Now consider the following program …

The following program fragment is written in a programming language that allows global variables and does not allow nested declarations of functions. global int i=100, j=5; void P(x) { int i=10; print(x+10); i=200; j=20; print (x); } main() {P(i+j);} If the programming language uses static scoping and call by need parameter passing mechanism, the values …

Let S be a stack of size $n \geq1$. 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 operations 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 \geq1$, define the …

A data structure is required for storing a set of integers such that each of the following operations can be done in $O(\log n)$ time, where $n$ is the number of elements in the set. Deletion of the smallest element Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose?

Which of the following statements is FALSE?

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?