Data Structures and Algorithms 2015

1. External sorting is a way of

Answers:

• sorting data that is too large to fit into RAM

• sorting data without the usage of a recursive implementation

• sorting data outside a specific performance bound

2. Collision resolution is not required if a hash function is perfect

Answers:

• False

• True

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

Answers:

• Set

• Size

• Height

• Depth

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

Answers:

• Three

• Ten

• Two

• Once

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

Answers:

• Stack

• Sequence

• Set

• Structure

6. What is the data structure used to perform recursion?

Answers:

• Binary Tree

• Array

• Stack

• B-tree

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

Answers:

• Array

• Stack

• Linked List

• Queue

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

Answers:

• Queue

• Array

• Binary tree

• Stack

9. What is the difference between the stack and queue data structures?

Answers:

• Stack is LIFO; Queue is FIFO.

• Stack is FIFO; Queue is LIFO.

• Stack requires recursive search technique; Queue does not.

• Stack uses selection sort; Queue uses bubble sort.

10. What is a precondition for a binary search?

Answers:

• Sequential Search

• Unsorted Array

• Hashing algorithm has been performed

• Sorted Array

11. Which is the most suitable data structure for hierarchical data models?

Answers:

• Tree

• Priority Queue

• Linked List

• Array

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

Answers:

• Array

• Linked List

• Sequence

• Stack

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

Answers:

• Looping

• Induction

• Sequencing

• Recursion

14. Minimum number of queues needed to implement the priority queue?

Answers:

• One.

• Three.

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

• Four.

15. 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?

Answers:

• Priority Queue

• Array

• Linked List

• Tree

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

Answers:

• Upper bound

• Midpoint

• Lower bound

• Range

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

Answers:

• Sequential Search

• Fibonacci Search

• Binary Search

• Hashing

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

Answers:

• B-tree

• Array

• Linked List

• Binary Tree

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

Answers:

• Stack

• Set

• Queue

• Hashtable

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

Answers:

• Quicksort

• Insertion sort

• Selection sort

• Bubble sort

21. All binary trees are balanced

Answers:

• False

• True

22. BFS and DFS are two types of

Answers:

• Sorting algorithms

• computational complexity measurements

• Searching algorithms

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

Answers:

• Binary Search

• Hashing

• Recursion

• Pointers

24. Can a binary tree be implemented using an array?

Answers:

• Yes

• No

25. 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.)

Answers:

• n ^ 3

• n!

• n ^ 2

• n * log(n)

• 2 ^ n

26. A perfect hash function is

Answers:

• not possible

• maps each valid input to a different hash value

• maps each hash value to a different valid input

27. A stack must always be implemented using an array

Answers:

• True

• False

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

Answers:

• Deletion of a leaf

• Deletion of a node

• Creation of a list

• Insertion of a node

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

Answers:

• O(N*M)

• O(N+M)

• It depends on how both N and M vary.

• O(N^2)

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

Answers:

• Bubble sort

• Quicksort

• Selection sort

• Insertion sort

31. What is the data structures used to perform recursion?

Answers:

• Queue

• Stack

• Linked List

• Heap

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

Answers:

• Graphics

• Simulation

• Website design

• Compiler design

33. A balanced binary search tree search average output is

Answers:

• O(log n)

• O(n^2)

• O(n * log n)

• O(1)

• O(n)

34. Which of the following problems has the fastest algorithms?

Answers:

• Find the maximum value in an array.

• Find the median value in an array

• Find the 2nd largest value in an array

• Find the 2nd smallest value in an array

35. Bubble sort's worst case performance is

Answers:

• O(log n)

• O(1)

• O(n^2)

• O(n)

• O(n^3)

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

Answers:

• O(N^2)

• O(N)

• O(N * log N)

• O(log N)

• O(1)

37. Which data structure provides the fastest lookup time

Answers:

• Fibonacci heap

• B-tree

• HashMap

• Doubly-linked list

• Sorted list

38. Worst case insert for a dynamic array is

Answers:

• O(1)

• O(n^2)

• O(n)

• O(log n)

39. A hash table typically has worst case behaviour of

Answers:

• O(n*log n)

• O(log n)

• O(1)

• O(n^2)

• O(N)

40. What is a disadvantage of a linked list?

Answers:

• Insertions and deletions in the list are inefficient.

• Linked lists cannot grow and shrink in size.

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

• A linked list wastes memory space.

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

Answers:

• O(N)

• O(N^2)

• O(1)

• O(N * log N)

• O(log N)

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

Answers:

• Right Child - Parent - Left Child

• Parent - Left Child - Right Child

• Left Child - Parent - Right Child

• Left Child - Right Child - Parent

43. Heapsort's worst case performance is

Answers:

• O(1)

• O(n^2 * log n)

• O(n * log n)

• O(n)

• O(n^2)

44. What is a partition-exchange sorting algorithm?

Answers:

• Shell sort

• Selection sort

• Insertion sort

• Quicksort

45. Which is a sequence of statements that form a logical argument?

Answers:

• Theory

• Proof

• Set

• Recursion

46. Merge sorts' worst case performance is

Answers:

• O(n log n)

• O(n^2)

• O(1)

• O(n)

• O(logn)

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

Answers:

• AB*CD/+

• A*BC+/D

• *AB/CD+

• ABCD*+/

48. How is a sequence different from a set?

Answers:

• A sequence allows duplicates but is not ordered.

• A sequence allows duplicates and is ordered.

• A set allows duplicates and is ordered.

• A set allows duplicates and a sequence is ordered.

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

Answers:

• Sequence

• Structure

• Set

• Array

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

Answers:

• True

• False

51. What kind of problem does Prim's algorithm solves?

Answers:

• Maximum Flow

• Flood Fill

• Minimum Spanning Tree

• Shortest Path One-to-One

• Shortest Path One-to-Many

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

Answers:

• Inorder

• Hashing order

• Postorder

• Preorder

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

Answers:

• Parent - Left Child - Right Child

• Left Child - Right Child - Parent

• Right Child - Parent - Left Child

• Left Child - Parent -Right Child

54. What is the simplest file structure?

Answers:

• Binary

• Random

• Indexed

• Sequential

55. Quicksort worst case is

Answers:

• O(1)

• O(n log n)

• O(n^3)

• O(n^2)

• O(n)

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

Answers:

• N^2

• constant

• log(N)

• N * log(N)

• O(2)

57. 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).

Answers:

• O(|V| + |E|)

• O(|V|)

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

• O(|E|)

• O(|V||E|)

58. Selection sort's average case performance is

Answers:

• O(n * log n)

• O(1)

• O(n^2)

• O(n)

• O(log n)

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

Answers:

• Selection sort

• Bubble sort

• Shell sort

• Quicksort

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

Answers:

• Priority Queue

• Queue

• Stack

• Hash Tables

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

Answers:

• O(N)

• O(1)

• O(N*log N)

• O(log N)

• O(N^2)

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

Answers:

• Left Child - Parent - Right Child

• Left Child - Right Child - Parent

• Parent - Left Child - Right Child

• Right Child - Parent - Left Child

63. A stable sorting algorithm maintains

Answers:

• the absolute order of records with equal keys

• the relative order of records with different keys

• the relative order of records with equal keys

• the same big-O performance in worst and average cases

64. What is the best-case for comparison based sorting?

Answers:

• O(n lg n)

• O(lg n)

• O(n)

• Not known yet.

• O(n^2)

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

Answers:

• O(2^n)

• O(n log n)

• O(n^2)

• O(n)

• O(1)

66. Which of the following is NOT a metric of algorithm analysis?

Answers:

• Correctness

• Space Usage

• Simplicity

• Coverage

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

Answers:

• Database table

• Database

• Data Structure

• Algorithm

68. A technique for direct search is _______.

Answers:

• Hashing

• Tree search

• Linear search

• Binary search

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

Answers:

• No, they can't

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

• Yes, with a slight modification to the algorithm.

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

Answers:

• Insertion sort

• Bubble sort

• Merge sort

• Quick sort

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

Answers:

• Divide and conquer.

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

• Creating a trie and searching both sequences.

• Brute force search.

• Dynamic programming with memoization.

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

Answers:

• O(n log n)

• O(n)

• O(n^2)

• O(2^n)

• O(1)

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

Answers:

• All leaf nodes are at the same level.

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

• Data stored only on the leaves.

• Data is stored only on the branches.

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

Answers:

• O(|E| + |V|)

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

• O(|V|)

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

• O(|E||V|)

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

Answers:

• Height

• Set

• Size

• Depth

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

Answers:

• Inorder predecessor

• Inorder successor

• Preorder predecessor

• Suborder successor

77. Worst case for a binary search tree is

Answers:

• O(2n)

• O(n)

• O(n^2)

• O(log n)

• O(n * log n)

78. 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.

Answers:

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

• O(|E|f)

• O(|V|)

• O(|E|)

• O(|E||V|)

79. 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?

Answers:

• 2 Gigabytes

• 1024 Megabytes

• 16 Gigabytes

• 512 Megabytes

• 128 Gigabytes

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

Answers:

• n leaf nodes

• n-1 leaf nodes

• n non-leaf nodes

• n-1 non-leaf nodes

81. BFS Algorithm use which data structure ?

Answers:

• Priority Queue

• Stack

• Queue

• Linked List

• Array