Arrays and Linked Lists Questions and Answers

Q: The following function computes the maximum value contained in an integer array p[] of size n (n \(\ge\) 1).int max(int *p, int n) { int a=0, b=n-1; while (__________) { if (p[a] \(\lt\)= p[b]) { a = a+1; } else { b = b-1; } } return p[a];}The missing loop condition is

The missing condition is b != a.The function keeps two candidate positions, a from the left and b from the right. At each step it discards the smaller of p[a] and p[b] by moving that index inward, since the smaller one cannot be the maximum. The maximum is always kept between a and b inclusive. The loop must stop when only one candidate remains, that is when a and b meet, and then p[a] is the maximum. So it should run while b != a.a != n would let a run past b and off the end of the array. b != 0 ignores a and can move b below a. b \(\gt\) (a + 1) stops with two candidates left and returns p[a] without comparing it with p[b], which fails when p[b] is larger, for example for the array {1, 2}.

Q: Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head.struct node{ int elt; struct node *next;};int getListSize (struct node *head){ if( E1 ) return 1; return E2;}Which one of the following options gives the correct replacements for the expressions E1 and E2?

The correct replacements are E1: head->next == NULL and E2: 1 + getListSize(head->next).The list is non-empty, so the base case is the last node: when head->next is NULL, the list from here has exactly 1 node. Otherwise the size is this node plus the size of the rest of the list, 1 + getListSize(head->next).Calling getListSize(head) again, as in two of the options, recurses on the same node forever. Testing head == NULL with head->next in the recursion reaches the NULL after the last node and returns 1 there, so it counts one node too many.

Q: \(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: \(\Theta(N)\) delete, \(O(\log N)\) insert, \(O(\log N)\) find, and \(\Theta(N)\) decrease-key. What is the time complexity of all these operations put together?

The total time is \(O(N^{2})\).Cost each batch on a sorted doubly linked list:\(\Theta(N)\) deletes: with a pointer to the node, each is \(O(1)\), so \(O(N)\) in all.\(O(\log N)\) inserts: finding the position in a sorted list takes \(O(N)\) each, so \(O(N\log N)\).\(O(\log N)\) finds: a linear search each, \(O(N\log N)\).\(\Theta(N)\) decrease-keys: the node is reached by pointer, but its new smaller key may belong much further forward, and moving it there takes \(O(N)\) each, so \(O(N^{2})\).The decrease-keys dominate, giving \(O(N^{2})\). \(O(N)\) ignores the cost of repositioning, \(O(\log^{2}N)\) assumes logarithmic operations a linked list cannot provide, and \(\Theta(N^{2}\log N)\) overstates the bound.

Q: 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?

SLLdel is \(O(n)\) and DLLdel is \(O(1)\).To unlink a node from a singly-linked list, the previous node's next pointer must be changed, and a singly-linked node has no pointer back to its predecessor. SLLdel must therefore walk from the head to find it, which takes up to n steps when the node is near the end. (Copying the next node's data into the node does not help in the worst case, because it fails for the last node.)In a doubly-linked list the node carries a prev pointer, so DLLdel can reset the predecessor's next pointer and the successor's prev pointer directly, a constant number of steps.So 'SLLdel O(1), DLLdel O(n)' is backwards, 'both O(1)' ignores the search, and no list operation here is logarithmic, which rules out \(O(\log(n))\).

A/An ______ is a rectangular array of numbers arranged in rows and columns enclosed by brackets.

A.matrix
B.record
C.object
D.field name

Exam Year(s)

DSSSB TGT - 2023,

Answer: A

A matrix is a rectangular array of numbers arranged in rows and columns and enclosed by brackets. A record is a collection of related fields, an object is an instance of a class, and a field name is a label of a column in a table, so none of them is such an array of numbers. A matrix with m rows and n columns is said to be of order m by n, and it is written inside brackets.

Discuss in Forum

The following function computes the maximum value contained in an integer array p[] of size n (n \(\ge\) 1).

int max(int *p, int n) {
    int a=0, b=n-1;

    while (__________) {
        if (p[a] \(\lt\)= p[b]) { a = a+1; }
        else { b = b-1; }
    }

    return p[a];
}

The missing loop condition is

A.a != n
B.b != 0
C.b \(\gt\) (a + 1)
D.b != a

Exam Year(s)

GATE CS - 2016,

Answer: D

The missing condition is b != a.

The function keeps two candidate positions, a from the left and b from the right. At each step it discards the smaller of p[a] and p[b] by moving that index inward, since the smaller one cannot be the maximum. The maximum is always kept between a and b inclusive. The loop must stop when only one candidate remains, that is when a and b meet, and then p[a] is the maximum. So it should run while b != a.

a != n would let a run past b and off the end of the array. b != 0 ignores a and can move b below a. b \(\gt\) (a + 1) stops with two candidates left and returns p[a] without comparing it with p[b], which fails when p[b] is larger, for example for the array {1, 2}.

Discuss in Forum

Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head.

struct node{
int elt;
struct node *next;
};
int getListSize (struct node *head)
{
if( E1 ) return 1;
return E2;
}

Which one of the following options gives the correct replacements for the expressions E1 and E2?

A.E1: head == NULL / E2: 1 + getListSize(head)
B.E1: head-\(\gt\)next == NULL / E2: 1 + getListSize(head-\(\gt\)next)
C.E1: head == NULL / E2: 1 + getListSize(head-\(\gt\)next)
D.E1: head-\(\gt\)next == NULL / E2: 1 + getListSize(head)

Exam Year(s)

GATE CS - 2026,

Answer: B

The correct replacements are E1: head->next == NULL and E2: 1 + getListSize(head->next).

The list is non-empty, so the base case is the last node: when head->next is NULL, the list from here has exactly 1 node. Otherwise the size is this node plus the size of the rest of the list, 1 + getListSize(head->next).

Calling getListSize(head) again, as in two of the options, recurses on the same node forever. Testing head == NULL with head->next in the recursion reaches the NULL after the last node and returns 1 there, so it counts one node too many.

Discuss in Forum

\(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: \(\Theta(N)\) delete, \(O(\log N)\) insert, \(O(\log N)\) find, and \(\Theta(N)\) decrease-key. What is the time complexity of all these operations put together?

A.\(O(\log^{2}N)\)
B.\(O(N)\)
C.\(O(N^{2})\)
D.\(\Theta(N^{2}\log N)\)

Exam Year(s)

GATE CS - 2016,

Answer: C

The total time is \(O(N^{2})\).

Cost each batch on a sorted doubly linked list:

\(\Theta(N)\) deletes: with a pointer to the node, each is \(O(1)\), so \(O(N)\) in all.
\(O(\log N)\) inserts: finding the position in a sorted list takes \(O(N)\) each, so \(O(N\log N)\).
\(O(\log N)\) finds: a linear search each, \(O(N\log N)\).
\(\Theta(N)\) decrease-keys: the node is reached by pointer, but its new smaller key may belong much further forward, and moving it there takes \(O(N)\) each, so \(O(N^{2})\).

The decrease-keys dominate, giving \(O(N^{2})\). \(O(N)\) ignores the cost of repositioning, \(O(\log^{2}N)\) assumes logarithmic operations a linked list cannot provide, and \(\Theta(N^{2}\log N)\) overstates the bound.

Discuss in Forum

Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

head → a → b → c → d → e → (null)

the reversed linked list should look like

head → e → d → c → b → a → (null)

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 \(\theta(n)\) time in the worst case.
B.The best algorithm for the problem takes \(\theta(n \log n)\) time in the worst case.
C.The best algorithm for the problem takes \(\theta(n^{2})\) time in the worst case.
D.It is not possible to reverse a singly linked list in \(O(1)\) space.

Exam Year(s)

GATE CS - 2022,

Answer: A

The best algorithm takes \(\theta(n)\) time in the worst case.

The standard in-place reversal walks the list once with three pointers (previous, current, next), turning each node's next pointer around as it passes. It uses a constant number of extra pointers, so \(O(1)\) space, and does constant work per node, so \(O(n)\) time.

No algorithm can do better, because every one of the \(n\) next pointers must change, which already needs \(\Omega(n)\) steps. So \(\theta(n\log n)\) and \(\theta(n^{2})\) overstate the cost of the best algorithm, and the claim that reversal is impossible in \(O(1)\) space is refuted by the three-pointer method.

Discuss in Forum

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

Exam Year(s)

GATE CS - 2023,

Answer: D

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

To unlink a node from a singly-linked list, the previous node's next pointer must be changed, and a singly-linked node has no pointer back to its predecessor. SLLdel must therefore walk from the head to find it, which takes up to n steps when the node is near the end. (Copying the next node's data into the node does not help in the worst case, because it fails for the last node.)

In a doubly-linked list the node carries a prev pointer, so DLLdel can reset the predecessor's next pointer and the successor's prev pointer directly, a constant number of steps.

So 'SLLdel O(1), DLLdel O(n)' is backwards, 'both O(1)' ignores the search, and no list operation here is logarithmic, which rules out \(O(\log(n))\).

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Arrays and Linked Lists Questions and Answers || Arrays and Linked Lists MCQ Questions and Answers || Arrays and Linked Lists GK Questions and Answers || Arrays and Linked Lists GK MCQ Questions || Arrays and Linked Lists Multiple Choice Questions and Answers || Arrays and Linked Lists GK || GK on Arrays and Linked Lists || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Arrays and Linked Lists Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications