GATE CS Arrays, Stacks and Queues questions

Consider a hash table with $9$ slots. The hash function is $h(k)= k \mod 9$. The collisions are resolved by chaining. The following $9$ keys are inserted in the order: $5, 28, 19, 15, 20, 33, 12, 17, 10$. The maximum, minimum, and average chain lengths in the hash table, respectively, are

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

Consider the C function given below. Assume that the array $listA$ contains $n (>0)$ elements, sorted in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n-1; do { k = (i+j)/2; if (x <= listA[k]) j = k-1; if (listA[k] <= x) i = k+1; } while (i <= j); if (listA[k] == x) return(k); else return -1; } Which …

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?

The procedure given below is required to find and replace certain characters inside an input character string supplied in array $A$. The characters to be replaced are supplied in array $oldc$, while their respective replacement characters are supplied in array $newc$. Array $A$ has a fixed length of five characters, while arrays $oldc$ and $newc$ …

The procedure given below is required to find and replace certain characters inside an input character string supplied in array $A$. The characters to be replaced are supplied in array $oldc$, while their respective replacement characters are supplied in array $newc$. Array $A$ has a fixed length of five characters, while arrays $oldc$ and $newc$ …

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$ queue operations on an initially empty queue?

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

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 shown as below …

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 shown as below …

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?

Consider a hash table of size seven, with starting index zero, and a hash function $(3x + 4)\mod 7$. 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.

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(\leq n)$ delete operations be …

A program $P$ reads in $500$ integers in the range $[0, 100]$ representing 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?

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

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

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

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 …

What is the minimum number of stacks of size $n$ required to implement a queue of size $n$?

An $n \times n$ array $v$ is defined as follows: $v\left[i,j\right] = i - j$ for all $i, j, i \leq n, 1 \leq j \leq n$ The sum of the elements of the array $v$ is