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)