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
