AMCAT Computer Programming: Data Structures 2

Question 1

Which data structure is best suited for implementing a browser's back button (visit history)?

Accepted Answer

Stack

Answer

A stack (LIFO) is ideal for browser history: push each new page, pop to go back to the previous page.

Question 2

What is the time complexity of searching for an element in a balanced Binary Search Tree (BST)?

Accepted Answer

O(log n)

Answer

A balanced BST has height O(log n), so searching requires at most O(log n) comparisons.

Question 3

In a doubly linked list, each node contains:

Accepted Answer

Data and two pointers (prev, next)

Answer

A doubly linked list node has a data field and two pointers: prev and next.

Question 4

What is the output of an inorder traversal of a Binary Search Tree?

Accepted Answer

Sorted ascending order

Answer

Inorder traversal (Left-Root-Right) of a BST visits nodes in ascending sorted order due to the BST property.

Question 5

Which of the following operations is NOT O(1) for a hash table on average?

Accepted Answer

Sort all elements

Answer

Insert, delete, and search are O(1) average in a hash table. Sorting all elements requires O(n log n).

(AMCAT) Aspiring Minds Computer Adaptive Test Practice Test