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

Queue

Answer

Linked List

Answer

Binary Tree

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

O(1)

Answer

O(n)

Answer

O(n squared)

Question 3

In a doubly linked list, each node contains:

Accepted Answer

Data and two pointers (prev, next)

Answer

Data and one pointer

Answer

Only pointers

Answer

Data, prev, next, and parent pointers

Question 4

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

Accepted Answer

Sorted ascending order

Answer

Random order

Answer

Reverse sorted order

Answer

Level-by-level order

Question 5

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

Accepted Answer

Sort all elements

Answer

Insert

Answer

Delete

Answer

Search

Question 6

What is the maximum number of nodes in a binary tree of height h (root at height 0)?

Accepted Answer

2^(h+1) minus 1

Answer

2h

Answer

2^h minus 1

Answer

h squared