### Elance Data Structures and Algorithms Test Answers 2015

·

**External sorting is a way of**

sorting data outside a specific performance bound

sorting data without the usage of a recursive
implementation

sorting data that is too large to fit into RAM

**Which data structure provides the fastest lookup time**

Sorted list

Doubly-linked list

HashMap

Fibonacci heap

B-tree

**Which is an ordered collection of elements in which insertions are restricted to the rear end and deletions are restricted to the front end?**

Array

Binary tree

Stack

Queue

**Which represents data as a chain of nodes and provides dynamic growth of data?**

Sequence

Stack

Array

Linked List

**Minimum number of queues needed to implement the priority queue?**

One.

Four.

Three.

Two. One queue is used for actual storing of data
and another for storing priorities.

**What is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself?**

Induction

Looping

Sequencing

Recursion

**The smalled element of an array's index is called its:**

Midpoint

Lower bound

Upper bound

Range

**What is the most suitable data structure for a situation where tasks must be scheduled for execution on a computer and the tasks include system tasks?**

Linked List

Tree

Array

Priority Queue

**Which is the most suitable data structure for hierarchical data models?**

Array

Linked List

Priority Queue

Tree

**The most common solution to the Towers of Hanoi involves the use of which datastructure**

Set

Stack

Hashtable

Queue

**What is a precondition for a binary search?**

Sequential Search

Unsorted Array

Hashing algorithm has been performed

Sorted Array

**A(n) ______ is the data structure used more than any other data structure.**

Binary Tree

Array

Linked List

B-tree

**Which steps through an array sequentially until a match is found?**

Hashing

Binary Search

Fibonacci Search

Sequential Search

**Can a binary tree be implemented using an array?**

No

Yes

**What is the difference between the stack and queue data structures?**

Stack uses selection sort; Queue uses bubble sort.

Stack is LIFO; Queue is FIFO.

Stack is FIFO; Queue is LIFO.

Stack requires recursive search technique; Queue
does not.

**Which of the following data structures is efficient in tree construction?**

Array

Queue

Stack

Linked List

**Which starts with an empty list and adds elements one-by-one to create a sorted list?**

Selection sort

Bubble sort

Quicksort

Insertion sort

**All binary trees are balanced**

True

False

**Which is an access mechanism that transforms the search key into a storage address, thereby providing very fast access to stored data?**

Hashing

Pointers

Binary Search

Recursion

**BFS and DFS are two types of**

Searching algorithms

Sorting algorithms

computational complexity measurements

**What is the running time of finding Nth element in array using quick sort? (For example: Find the 4th smallest element in an unsorted array.)**

2 ^ n

n ^ 2

n!

n ^ 3

n * log(n)

**A stack must always be implemented using an array**

False

True

**What is the data structure used to perform recursion?**

Stack

B-tree

Array

Binary Tree

**In which of the following areas is data structures NOT applied extensively?**

Compiler design

Website design

Graphics

Simulation

**Which of the following is NOT a basic function of a linked list?**

Insertion of a node

Deletion of a node

Deletion of a leaf

Creation of a list

**A perfect hash function is**

maps each hash value to a different valid input

maps each valid input to a different hash value

not possible

**Which is a collection of distinct unordered elements with a common type and no duplicates?**

Set

Structure

Sequence

Stack

**Collision resolution is not required if a hash function is perfect**

True

False

**What is the time complexity to compute the average of a N×M matrix?**

O(N^2)

O(N+M)

O(N*M)

It depends on how both N and M vary.

**What is the data structures used to perform recursion?**

Queue

Heap

Linked List

Stack

**Which of the following problems has the fastest algorithms?**

Find the median value in an array

Find the 2nd largest value in an array

Find the 2nd smallest value in an array

Find the maximum value in an array.

**What compares adjacent elements and exchanges them to put an array in order?**

Insertion sort

Selection sort

Bubble sort

Quicksort

**Bubble sort's worst case performance is**

O(1)

O(n)

O(n^2)

O(log n)

O(n^3)

**A balanced binary search tree search average output is**

O(n^2)

O(n * log n)

O(n)

O(1)

O(log n)

**What is the minimum number of queues needed to implement a priority queue?**

Once

Three

Two

Ten

**What is the time complexity to insert an item into a B-Tree?**

O(N^2)

O(log N)

O(N)

O(N * log N)

O(1)

**What is the correct order for a in-order binary tree traversal?**

Left Child - Parent - Right Child

Right Child - Parent - Left Child

Parent - Left Child - Right Child

Left Child - Right Child - Parent

**Worst case insert for a dynamic array is**

O(1)

O(n)

O(n^2)

O(log n)

**The path length from root to farthest leaf node is the ______ of the tree.**

Depth

Height

Size

Set

**Heapsort's worst case performance is**

O(n^2)

O(n)

O(n^2 * log n)

O(n * log n)

O(1)

**Merge sorts' worst case performance is**

O(n log n)

O(n^2)

O(1)

O(n)

O(logn)

**Which is a sequence of statements that form a logical argument?**

Proof

Theory

Recursion

Set

**A hash table typically has worst case behaviour of**

O(1)

O(log n)

O(n^2)

O(N)

O(n*log n)

**What is the worst case time complexity to insert a value into a hash table?**

O(N * log N)

O(N^2)

O(log N)

O(1)

O(N)

**What is a disadvantage of a linked list?**

A linked list will use more storage space than an
array to store the same number of elements.

A linked list wastes memory space.

Insertions and deletions in the list are
inefficient.

Linked lists cannot grow and shrink in size.

**What kind of problem does Prim's algorithm solves?**

Minimum Spanning Tree

Maximum Flow

Shortest Path One-to-One

Shortest Path One-to-Many

Flood Fill

**A ________ is a group of elements in a specified order that may contain duplicates.**

Set

Sequence

Array

Structure

**Hashtables are typically used for iterating through values stored in the hashtable**

False

True

**How is a sequence different from a set?**

A sequence allows duplicates but is not ordered.

A sequence allows duplicates and is ordered.

A set allows duplicates and a sequence is ordered.

A set allows duplicates and is ordered.

**What is a partition-exchange sorting algorithm?**

Quicksort

Insertion sort

Shell sort

Selection sort

**The postfix form of A*B+C/D is:**

A*BC+/D

*AB/CD+

AB*CD/+

ABCD*+/

**Quicksort worst case is**

O(n^2)

O(n)

O(1)

O(n log n)

O(n^3)

**One can convert a binary tree into its mirror image by traversing it in:**

Preorder

Inorder

Postorder

Hashing order

**What is the correct order for a pre-order binary tree traversal?**

Left Child - Right Child - Parent

Parent - Left Child - Right Child

Left Child - Parent -Right Child

Right Child - Parent - Left Child

**What is the simplest file structure?**

Binary

Sequential

Indexed

Random

**Selection sort's average case performance is**

O(n * log n)

O(n)

O(log n)

O(n^2)

O(1)

**What is the amortized insertion time into a red and black tree?**

O(2)

log(N)

constant

N * log(N)

N^2

**Which finds the minimum of the array and exchanges it with the first element of the array?**

Selection sort

Bubble sort

Shell sort

Quicksort

**What is the correct order for a post-order binary tree traversal?**

Right Child - Parent - Left Child

Left Child - Right Child - Parent

Parent - Left Child - Right Child

Left Child - Parent - Right Child

**Which data structure is used in performing non-recursive depth-first search in graphs?**

Priority Queue

Hash Tables

Queue

Stack

**What is the time complexity of a breadth-first-search in an undirected graph G with vertex set V and edge set E? G = (V,E).**

O(|V||E|^2)

O(|E|)

O(|V||E|)

O(|V|)

O(|V| + |E|)

**What is the time complexity to find unique integers in an unsorted indexed array?**

O(1)

O(N)

O(N^2)

O(N*log N)

O(log N)

**What is the best-case for comparison based sorting?**

O(n^2)

O(n lg n)

O(lg n)

Not known yet.

O(n)

**Which of the following is NOT a metric of algorithm analysis?**

Correctness

Coverage

Simplicity

Space Usage

**What is the complexity to radix sort a list of integers in a known range?**

O(1)

O(n)

O(2^n)

O(n log n)

O(n^2)

**A stable sorting algorithm maintains**

the absolute order of records with equal keys

the relative order of records with equal keys

the same big-O performance in worst and average
cases

the relative order of records with different keys

**BFS Algorithm use which data structure ?**

Array

Queue

Stack

Priority Queue

Linked List

**What algorithm uses polynomial time to find the largest common subsequence of two sequences?**

Creating a trie and searching both sequences.

Divide and conquer.

Greedily search for the optimal subsequence
starting from the beginning of each sequence.

Brute force search.

Dynamic programming with memoization.

**Which is a way of organizing data that considers not only the items stored, but also their relationship to each other?**

Algorithm

Data Structure

Database

Database table

**What is the time complexity of the recursive fibonacci sequence without memoization?**

O(1)

O(n)

O(n log n)

O(2^n)

O(n^2)

**A technique for direct search is _______.**

Binary search

Linear search

Tree search

Hashing

**Which sort will you use if you want to optimize sorting time?**

Quick sort

Merge sort

Insertion sort

Bubble sort

**Can Dijkstra's be used to find the longest-path in a graph?**

Yes, by multiplying each edge in the graph by -1,
and finding the shortest-path.

No, they can't

Yes, with a slight modification to the algorithm.

**Which of the following is NOT a property of a B-Tree?**

Root is leaf, or has between 2 & M children.

Data is stored only on the branches.

All leaf nodes are at the same level.

Data stored only on the leaves.

**Worst case for a binary search tree is**

O(log n)

O(n)

O(2n)

O(n^2)

O(n * log n)

**The path length from a node to the deepest leaf under it is the _________.**

Depth

Set

Size

Height

**If a node having two children is deleted from a binary tree, it is replaced by its:**

Inorder predecessor

Inorder successor

Preorder predecessor

Suborder successor

**What is the worst-case time complexity of finding a maximum cardinality matching in a bipartite graph G = (V,E)?**

O(|E|^2|V|^2)

O(|V|)

O(|E||V|)

O(|E| + |V|)

O(|E|*sqrt(|V|))

**What is the worst-case time complexity of the simple Ford-Fulkerson algorithm for finding the maximum flow in a graph given a source and a sink, and all integer capacities on edges? Assume the graph G = (V,E) has a finite, integer maximum flow value of f.**

O(|E|)

O(|E||V|)

O(|V|)

O(|E|f)

O(|E|^2|V|)

**You have a file with 4 billion 32-bit integers. The distribution of the integers is random but uniform. You are supposed to find a number NOT in the file. If you created a bit array and used the index to that array to determine if a number existed in the file approximately how much memory would you need?**

128 Gigabytes

16 Gigabytes

2 Gigabytes

512 Megabytes

1024 Megabytes

**A full binary tree with 2n+1 nodes contains:**

n-1 non-leaf nodes

n non-leaf nodes

n leaf nodes

n-1 leaf nodes

Subscribe to:
Posts (Atom)