Linear Data Structures - Programming and Data Structures - Computer Science & Information Technology Previous Year Questions

1

2007 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2007

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

6, 1

B

5, 7

C

3, 2

D

1, 5

Open complete paper

2

2007 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2007

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.

A

8, –, –, –, –, –, 10

B

1, 8, 10, –, –, –, 3

C

1, –, –, –, –, –, 3

D

1, 10, 8, –, –, –, 3

Open complete paper

3

2009 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2009

Consider the HTML table definition given below :
<table border=1> <tr> <td rowspan=2> ab </td> <td colspan=2> cd </td> </tr> <tr> <td> ef </td> <td rowspan=2> gh </td> </tr> <tr> <td colspan=2> ik </td> </tr> </table>The number of rows in each column and the number of columns in each row are :

A

(2,2,3) and (2,3,2)

B

(2,2,3) and (2,2,3)

C

(3,2,2) and (2,3,2)

D

(3,2,2) and (2,2,3)

Open complete paper

4

2009 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2009

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 ?

(A)	(B)	(C)	(D)
0 1 2 2 3 23 4 5 15 6 7 8 18 9	0 1 2 12 3 13 4 5 5 6 7 8 18 9	0 1 2 12 3 13 4 2 5 3 6 23 7 5 8 18 9 15	0 1 2 12, 2 3 13, 3, 23 4 5 5, 15 6 7 8 18 9

A

Table (A)

B

Table (B)

C

Table (C)

D

Table (D)

Open complete paper

5

2009 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2009

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

A

{ 14, 13, 12, 10, 8 }

B

{ 14, 12, 13, 8, 10 }

C

{ 14, 13, 8, 12, 10 }

D

{ 14, 13, 12, 8, 10 }

Open complete paper

6

2010 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2010

The following C function takes a singly-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.
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;
}

Choose the correct alternative to replace the blank line.

A

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

B

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

C

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

D

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

Open complete paper

7

2010 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2010

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

A

46, 42, 34, 52, 23, 33

B

34, 42, 23, 52, 33, 46

C

46, 34, 42, 23, 52, 33

D

42, 46, 33, 23, 34, 52

Open complete paper

8

2010 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2010

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?

A

10

B

20

C

30

D

40

Open complete paper

9

2013 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2013 [Session 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 queue operations on an initially empty queue?

A

Θ(n)

B

Θ(n + k)

C

Θ(nk)

D

Θ(n²)

Open complete paper

10

2013 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2013 [Session 3]

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?

A

Θ(n)

B

Θ(n + k)

C

Θ(nk)

D

Θ(n²)

Open complete paper

11

2014 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2014 [Session 1]

Consider a hash table with 9 slots. The hash function is \(h(k) = k \bmod 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

A

3, 0, and 1

B

3, 3, and 3

C

4, 0, and 1

D

3, 0, and 2

Open complete paper

12

2014 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2014 [Session 2]

Suppose a stack 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?

A

A queue cannot be implemented using this stack.

B

A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.

C

A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.

D

A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

Open complete paper

13

2016 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2016 [Session 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)?

Check answer

Open complete paper

14

2017 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2017 [Session 2]

A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time?
I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.

A

I only

B

II only

C

Both I and II

D

Neither I nor II

Open complete paper

15

2018 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2018 [Session 2]

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let \(n\) denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail.
Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?

A

\(\Theta(1), \Theta(1)\)

B

\(\Theta(1), \Theta(n)\)

C

\(\Theta(n), \Theta(1)\)

D

\(\Theta(n), \Theta(n)\)

Open complete paper

16

2020 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2020 [Session 2]

What is the worst case time complexity of inserting \(n\) elements into an empty linked list, if the linked list needs to be maintained in sorted order?

A

\(\Theta(n)\)

B

\(\Theta(n \log n)\)

C

\(\Theta(n^2)\)

D

\(\Theta(1)\)

Open complete paper

17

2022 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2022 [Session 2]

Consider the problem of reversing a singly linked list. To take an example, given the linked list below,
[Image: linked list a->b->c->d->e]
the reversed linked list should look like
[Image: linked list e->d->c->b->a]
Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

A

The best algorithm for the problem takes θ(n) time in the worst case.

B

The best algorithm for the problem takes θ(n log n) time in the worst case.

C

The best algorithm for the problem takes θ(n²) time in the worst case.

D

It is not possible to reverse a singly linked list in O(1) space.

Open complete paper

18

2022 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2022 [Session 2]

Consider the queues Q1 containing four elements and Q2 containing none (shown as the Initial State in the figure). The only operations allowed on these two queues are Enqueue (Q, element) and Dequeue (Q). The minimum number of Enqueue operations on Q1 required to place the elements of Q1 in Q2 in reverse order (shown as the Final State in the figure) without using any additional storage is __________.

[Diagram: Initial State: Q1: Head -> 1 | 2 | 3 | 4, Q2: Head -> empty. Final State: Q1: Head -> empty, Q2: Head -> 4 | 3 | 2 | 1]

Check answer

Open complete paper

19

2023 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2023 [Session 2]

Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list.
Let \(n\) denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?

A

SLLdel is \(O(1)\) and DLLdel is \(O(n)\)

B

Both SLLdel and DLLdel are \(O(\log(n))\)

C

Both SLLdel and DLLdel are \(O(1)\)

D

SLLdel is \(O(n)\) and DLLdel is \(O(1)\)

Open complete paper

20

2023 · Computer Science & Information Technology · Programming and Data Structures · Linear Data Structures

Computer Science & Information Technology (CS) 2023 [Session 2]

Consider a sequence \(a\) of elements \(a_0 = 1, a_1 = 5, a_2 = 7, a_3 = 8, a_4 = 9,\) and \(a_5 = 2\). The following operations are performed on a stack \(S\) and a queue \(Q\), both of which are initially empty.
I: push the elements of \(a\) from \(a_0\) to \(a_5\) in that order into \(S\).
II: enqueue the elements of \(a\) from \(a_0\) to \(a_5\) in that order into \(Q\).
III: pop an element from \(S\).
IV: dequeue an element from \(Q\).
V: pop an element from \(S\).
VI: dequeue an element from \(Q\).
VII: dequeue an element from \(Q\) and push the same element into \(S\).
VIII: Repeat operation VII three times.
IX: pop an element from \(S\).
X: pop an element from \(S\).
The top element of \(S\) after executing the above operations is ______

Check answer

Open complete paper