Arrays and Linked Lists Questions and Answers

Answer: A

The odd one out is the array.

An array is a linear data structure: its elements lie in a single sequence and are accessed by index. A binary tree, a complete binary tree and a graph are all non-linear structures, in which an element may be connected to several others.

The two kinds of binary tree belong together, and a tree is a special case of a graph, so the array is the one that does not fit.

Answer: B

The false statement is that deleting the first element of a singly linked list requires O(n) operations.

Deleting the first node only needs the head pointer moved to the second node (head = head->next), which takes constant time, O(1), however long the list is.

The other statements are true. Searching a singly linked list may need every node to be checked, O(n). Finding the maximum in a circular list needs a full traversal, O(n). Deleting the middle node requires walking to it first, O(n).

Answer: B

A linked list is preferred when frequent insertion and deletion occur.

Inserting or deleting in a linked list only changes a few pointers, which takes constant time once the position is known; no other elements move. In an array, every element after the position must be shifted, which takes O(n) time. A linked list also grows and shrinks one node at a time, with no need to reserve space in advance.

Fast indexing favours arrays, which reach any element in O(1), while a list must be walked from the head. Static memory of a fixed size suits an array. Whether elements are uniform does not decide the choice.

Answer: D

The best way is an array of 50 numbers.

Only the frequencies of scores above 50 are printed, and the possible scores above 50 in the range [0, 100] are 51, 52, ..., 100: exactly 50 values. One counter for each, indexed by score minus 51, needs an array of 50 numbers.

An array of 100 numbers wastes space on scores that are never reported, an array of 500 confuses the number of students with the number of possible scores, and a dynamic array of 550 has no basis at all.

Answer: C

The key gives O(n) as the worst case for insertion in a singly linked list.

Inserting at the head takes constant time, but inserting at the end, or at a given position, needs a traversal from the head to find the node before it, up to n steps. With only a head pointer the worst case is therefore O(n).

O(1) is the best case (insertion at the head), O(log n) would need random access the list does not have, and \(O(n^2)\) is far too slow for a single insertion.

Answer: A

A doubly linked list uses more memory due to additional pointer.

Each node of a doubly linked list stores two pointers, to the next and previous nodes, while a singly linked list stores only one. The extra pointer costs memory in every node.

In return it allows traversal in both directions, so option C is wrong. Searching is still O(n) in both kinds of list, and it is not more efficient overall, only for operations such as deleting a given node.

Answer: B

The O(1) operation is deleting a node when a pointer to it is given.

Each node of a doubly linked list stores both its next and previous pointers. Given the node, you can set node.prev.next = node.next and node.next.prev = node.prev directly, with no traversal, so the work is constant.

Searching for an element and finding the middle both require walking the list, so they take O(n). Reversing the list must visit and swap the pointers of every node, which is also O(n).

Answer: B

The function prints all nodes of the linked list in reverse order.

It first calls itself on the next node and only prints the current node's data after that call returns. So the recursion runs down to the end of the list, and the printing happens as the calls return, from the last node back to the head.

Printing before the recursive call would give the normal order. Nothing skips nodes, so the 'alternate nodes' options are wrong.

Answer: C

The answer is 0.

The printed stem leaves out the thing it asks about (it reads 'what is the 'in an array''), but the options and the Commission's key show the intended question: in Java, and in most modern languages, the first element of an array is at index 0, so the starting index is 0.

An index of 1 is used by some older or specialised languages (Fortran and MATLAB count from 1). A negative index such as -1 is not a valid Java array index and throws an exception. 'Depends on language' is true of languages in general, but the question names Java and 'most modern' languages, and for these the answer is 0.

Answer: C

Each node of a linked list contains data and a pointer.

A linked list stores its elements in separate nodes scattered in memory. Each node holds the data item and a pointer (link) to the next node, and the last node's pointer is null. In a doubly linked list each node has a second pointer to the previous node.

Data alone would leave no way to find the next node, and a pointer alone would store nothing. Nodes are not reached by an index; that is how an array works.