Data Structures Previous Year Questions

Explanation

delete frees a single object, while delete[] frees an array of objects (and calls each destructor).

Explanation

Array indices start at 0, so the nth element is array[n-1].

Explanation

C++ arrays are classified as one-dimensional and multi-dimensional, i.e. two types, as the official key accepts.

Explanation

rank() reports the number of dimensions of an array type.

Explanation

is_array checks whether the given type or variable is an array.

Explanation

All three statements are true (new is an operator that calls constructors; malloc is a function returning void*), so more than one option, i.e. (D), is correct.

Explanation

Stacks are used for string reversal and backtracking; asynchronous data transfer is handled with queues (buffers), so it is not a stack application.

Explanation

The conversion holds operators on a stack while scanning the expression, so a stack is needed.

Explanation

Before dequeuing, one must check that the queue is not empty, i.e. underflow.

Explanation

Balancing of symbols (parentheses) is done with a stack, not a queue.

Explanation

Preorder, inorder and postorder are all binary-tree traversals, so none of A-C is the odd one out.

Explanation

An array is a container that stores elements of the same type.

Explanation

A circular queue is also called a ring buffer.

Explanation

A circular queue reuses the freed slots at the front, which avoids wasting memory.

Explanation

A binary heap gives O(log n) insertion and removal of the highest-priority item, better than a list or array.

Explanation

Recursive calls are kept in the call stack, so the stack is used.

Explanation

In a red-black tree the root is black and a newly inserted non-root node is coloured red, so both A and B hold (more than one).

Explanation

In a singly linked list the node before the tail must be found by traversing the whole list, so deleting from the rear takes O(N).

Explanation

Depending on whether rear points at the last used slot or one past it, both rear = MAX_SIZE-1 and rear = MAX_SIZE are accepted overflow conditions, so more than one is correct.

Explanation

Merge sort splits the list in halves, sorts them and merges, which is divide and conquer.

Explanation

PLA stands for Programmable Logic Array, a device with a programmable AND array followed by a programmable OR array.

Explanation

Stack, queue and array are all linear data structures. Trees and graphs are non-linear, and neither is listed.

Explanation

In a BST, keys smaller than a node go in its left subtree and larger keys in its right subtree.

Explanation

In a height-balanced (AVL) binary tree, the heights of the left and right subtrees of every node differ by at most 1.

Explanation

The front element d must stay in place. Delete a, b and c (3 deletions) and add them back as c, b, a (3 additions), giving d, c, b, a.

Explanation

Root 15. The left subtree from 10, 12, 11 is 10 with right child 12, whose left child is 11. The right subtree is 20 with left child 18, whose children are 16 and 19. Postorder: 11, 12, 10, 16, 19, 18, 20, 15.

Explanation

A spanning tree connects all N vertices with no cycle, so it has exactly N − 1 edges.

Explanation

Greedy, Divide and Conquer and Dynamic Programming are algorithm design paradigms, not graph traversal algorithms (BFS and DFS are), so more than one option is correct.

Explanation

A decision tree learns from labelled training data, so it is supervised learning. K-means is unsupervised, and reinforcement learning is a separate paradigm.

Explanation

int array[10]; declares an array of 10 integers by giving the type, the name and the size in square brackets.

Explanation

Recursion uses a stack. Each call pushes an activation record, and the record is popped when the call returns.

Explanation

Linear, circular and double-ended queues (deques) are all real types of queue, so none of the options is wrong.

Explanation

Before deleting, check for underflow (an empty queue). Overflow is checked before inserting.

Explanation

A deque (double-ended queue) allows insertion and deletion at both the front and the rear.

Explanation

Binary trees are traversed in preorder, inorder, postorder or level order. Randomized traversal is not a standard binary tree technique.

Explanation

A doubly linked list allows traversal in both directions but needs extra space for the previous pointer. It is harder to implement than a singly linked list, not easier.

Explanation

All three statements are true properties of a binary search tree, so none of them is false.

Explanation

The function takes a float* and a char** and returns an int**, so the correct declaration is int **fun(float *, char **).

Explanation

std::is_array<T> (in <type_traits>) checks whether a given type is an array type, returning true or false.

Explanation

Infix-to-postfix conversion pushes operators and parentheses onto a stack. It pops them according to precedence and associativity.

Explanation

A queue is FIFO (first in, first out). Elements are added at the rear and removed from the front.

Explanation

A queue works on FIFO (first in, first out), so the element inserted first is removed first.

Explanation

A stack works on LIFO (last in, first out). Push and pop both happen at the top.

Explanation

A C++ class bundles data members and member functions together into one unit, which is encapsulation.