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

Q: Which of the following concepts make extensive use of arrays ?

The concept given is spatial locality, the fourth option.An array is stored as one block of consecutive memory locations, and programs usually walk through it element by element. After one element is read, the neighbouring ones are very likely to be read next. This is spatial locality, and arrays are its standard example; it is why a cache loads a whole line of neighbouring words at once.Binary trees are normally built from nodes linked by pointers, although a complete tree can be stored in an array as a heap is. Scheduling of processes works with queues or lists of process records. Caching is a hardware or software technique that exploits locality and holds data in lines or entries, but it is the locality of array access that makes it pay.This is a loosely worded item, since a cache itself is built from arrays of lines and a tree can be stored in an array; the official key selects spatial locality as the concept most closely tied to arrays, and this explanation follows it.

Q: A doubly linked list is :

A doubly linked list is A linear data structure.Its elements are arranged in a single sequence: each node has one predecessor and one successor (except the ends). The extra backward pointer lets you traverse in both directions, but the order is still linear.Non-linear structures, such as trees and graphs, let a node connect to several others in a branching or network pattern.

Q: Which of these best describes an array ?

An array is best described as a container of objects of similar types.An array stores a fixed number of elements of the same type in consecutive memory locations, so any element can be reached directly by its index.A hierarchical structure is a tree, not an array. Containers of mixed or heterogeneous types are structures (records) or, in object-oriented languages, collections of base-class references, so those options describe something else.

Q: Which of the following application makes use of a circular linked list ?

A circular linked list is used in allocating CPU to resources (processes), as in round-robin scheduling.In round-robin scheduling the ready processes are kept in a circular list. The scheduler gives the CPU to one process for a time slice and then simply moves to the next node; after the last process it comes back to the first without any special case, which is exactly what a circular list provides.Undo operations, recursive function calls and expression evaluation are all classic uses of a stack, since each needs last-in, first-out order, not a circular list.

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

Which of the following concepts make extensive use of arrays ?

A.Binary trees
B.Scheduling of processes
C.Caching
D.Spatial locality

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: D

The concept given is spatial locality, the fourth option.

An array is stored as one block of consecutive memory locations, and programs usually walk through it element by element. After one element is read, the neighbouring ones are very likely to be read next. This is spatial locality, and arrays are its standard example; it is why a cache loads a whole line of neighbouring words at once.

Binary trees are normally built from nodes linked by pointers, although a complete tree can be stored in an array as a heap is. Scheduling of processes works with queues or lists of process records. Caching is a hardware or software technique that exploits locality and holds data in lines or entries, but it is the locality of array access that makes it pay.

This is a loosely worded item, since a cache itself is built from arrays of lines and a tree can be stored in an array; the official key selects spatial locality as the concept most closely tied to arrays, and this explanation follows it.

Discuss in Forum

A doubly linked list is :

A.A linear data structure
B.A non-linear data structure
C.Both linear and non-linear data structure
D.Neither linear nor non-linear data structure

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: A

A doubly linked list is A linear data structure.

Its elements are arranged in a single sequence: each node has one predecessor and one successor (except the ends). The extra backward pointer lets you traverse in both directions, but the order is still linear.

Non-linear structures, such as trees and graphs, let a node connect to several others in a branching or network pattern.

Discuss in Forum

Which of these best describes an array ?

A.A data structure that shows a hierarchical behaviour
B.Container of objects of similar types
C.Container of objects of mixed types
D.Heterogeneous data types

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: B

An array is best described as a container of objects of similar types.

An array stores a fixed number of elements of the same type in consecutive memory locations, so any element can be reached directly by its index.

A hierarchical structure is a tree, not an array. Containers of mixed or heterogeneous types are structures (records) or, in object-oriented languages, collections of base-class references, so those options describe something else.

Discuss in Forum

10.

Which of the following application makes use of a circular linked list ?

A.Undo operation in a text editor
B.Allocating CPU to resources
C.Recursive function calls
D.Expression evaluation

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: B

A circular linked list is used in allocating CPU to resources (processes), as in round-robin scheduling.

In round-robin scheduling the ready processes are kept in a circular list. The scheduler gives the CPU to one process for a time slice and then simply moves to the next node; after the last process it comes back to the first without any special case, which is exactly what a circular list provides.

Undo operations, recursive function calls and expression evaluation are all classic uses of a stack, since each needs last-in, first-out order, not a circular list.

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