**1. Which graph traversal algorithm uses a queue to keep track of the vertices which need to be processed?**

**Answers:**

- Breadth-first search
- Depth-first search

**2. A simple graph with n vertices and k components can have at the most _______.**

**Answers:**

- n edges
- n-k edges
- (n-k)(n-k-1)/2 edges
- (n-k)(n-k+1)/2 edges

**3. What is the minimum number of edges which must be removed from a complete bipartite graph of six nodes K(6) so that the remaining graph is a planar?**

**Answers:**

- 2
- 3
- 4
- 6

**4. Which feature of heaps allows them to be efficiently implemented using a partially filled array?**

**Answers:**

- Heaps are binary search trees
- Heaps are complete binary trees
- Heaps are full binary trees
- Heaps contain only integer data

**5. What happens if you make a recursive call without making the problem smaller?**

**Answers:**

- The operating system detects the infinite recursion because of the “repeated state”
- The program keeps running until you press Ctrl-C
- The results are non-deterministic
- The run-time stack overflows, halting the program

**6. Tree algorithms typically run in time O(d) . What is d?**

**Answers:**

- The depth of the tree
- The number of divisions at each level
- The number of nodes in the tree
- The total number of entries in all the nodes of the tree

**7. Here is a code for an integer variable n**

**while (n > 0)**

** {**

** n = n/10; // Use integer division**

** }**

** What is the worst case scenario analysis for the above loop?**

**Answers:**

- O(1)
- O(log n)
- O(n)
- O(n2)

**8. Suppose we have a circular array implementation of a queue, with ten items in the queue stored at data[2] through data[11]. The CAPACITY is 42. Where does the push member function place the new entry in the array?**

**Answers:**

- data[1]
- data[2]
- data[11]
- data[12]

**9. Which of the following sorting algorithms yield approximately the same worst-case and average-case running time behavior in O(n*log(n))?**

**Answers:**

- Bubble sort and selection sort
- Heap sort and merge sort
- Quick sort and radix sort
- Tree sort and Median-of-3 quicksort

**10. The operation for adding an entry to a stack is traditionally called ________.**

**Answers:**

- add
- append
- insert
- push

**11. For a complete binary tree with depth d, the total number of nodes is:**

**Answers:**

- 2d+1
- 2d
- 2d-1
- 2d2

**12. Which of the following is false?**

**Answers:**

- A binary search begins with the middle element in the array
- A binary search continues halving the array either until a match is found or until there are no more elements to search
- If the search argument is greater than the value located in the middle of the binary, the binary search continues in the lower half of the array

**13. Which of the following applications may use a stack?**

**Answers:**

- A parentheses balancing program
- Keeping track of local variables at run time
- Syntax analyzer for a compiler
- All of the above

**14. What is the value of the post-fix expression 6 3 2 4 + – *?**

**Answers:**

- Something between -15 and -100
- Something between -5 and -15
- Something between 5 and 15
- Something between 15 and 100

**15. The minimum number of interchanges needed to convert the array 89,19,14,40,17,12,10,2,5,7,11,6,9,70 into a heap with the maximum element at the root is:**

**Answers:**

- 0
- 1
- 2
- 3

**16. Suppose T is a complete binary tree with 14 nodes. What would be the minimum possible depth of T?**

**Answers:**

- 0
- 3
- 4
- 5

**17. In which data structure do the insertion and deletion take place at the same end?**

**Answers:**

- Linked list
- Tree
- Stack
- Linked list of stack

**18. What is the formulae to find maximum number of nodes n in a perfect binary tree?**

**Answers:**

- 2h + 1 – 1
- 2h + 1
- 2h
- 2h + 1 + 1

**19. A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?**

**Answers:**

- 511
- 512
- 1024
- There is no maximum limit

**20. In which dynamically created linked list can the first node be recovered after moving to the second node?**

**Answers:**

- Simple linked list
- Circular linked list
- Doubly linked list
- Both b and c

**21. What is the best definition of a collision in a hash table?**

**Answers:**

- Two entries are identical except for their keys
- Two entries with different data have exactly the same key
- Two entries with different keys have exactly the same hash value
- Two entries with exactly the same key have different hash values

**22. What is the pre-order traversal equivalent of the following algebraic expression?**

**[a+(b-c)]*[(d-e)/(f+g-h)]**

**Answers:**

- abc-+de-fg+h-/*
- *+a-bc/-de-+fgh
- a+*b-/c-d-e+fgh
- *+a-bc-/d+e-fgh

**23. A sparse matrix can be a lower-triangular matrix when____.**

**Answers:**

- all the non-zero elements lie only on the leading diagonal
- all the non-zero elements lie above the leading diagonal
- all the non-zero elements lie below the leading diagonal
- None of the above

**24. A graph in which all nodes are of an equal degree is known as:**

**Answers:**

- Multigraph
- Non – regular graph
- Regular graph
- Complete graph

**25. What is the maximum number of statements that may be recursive calls in a single function declaration?**

**Answers:**

- 1
- 2
- n (n is the argument)
- There is no fixed maximum

**26. Which additional requirement is placed on an array so that binary search may be used to locate an entry?**

**Answers:**

- The array elements must form a heap
- The array must have at least 2 entries
- The array must be sorted
- The array’s size must be a power of two

**27. What is the worst-case scenario for heapsort to sort an array of n elements?**

**Answers:**

- O(log n)
- O(n)
- O(n log n)
- O(n2)

**28. The recurrence relation T(n)=mT(n/2)+an2 is satisfied by___**

**Answers:**

- T(n)=O(nm)
- T(n)=O(m*log(m))
- T(n)=O(n*log(m))
- T(n)=O(m*log(n))

**29. If ‘data’ is a circular array of CAPACITY elements and ‘last’ is an index in that array, what is the formula for the index after ‘last’?**

**Answers:**

- (last % 1) + CAPACITY
- last % (1 + CAPACITY)
- (last + 1) % CAPACITY
- last + (1 % CAPACITY)

**30. Consider the node of a complete binary tree whose value is stored in data[i] for an array implementation. If this node has a right child, where will the right child’s value be stored (the array’s first index is 0)?**

**Answers:**

- data[i+1]
- data[i+2]
- data[2*i + 1]
- data[2*i + 2]

**31. In a complete binary tree, the parent of any node k can be determined by ________.**

**Answers:**

- 2k
- 2k+1
- K/2
- 2K-1

**32. Consider a linked list of n elements which is pointed by an external pointer. What is the time taken to delete the element which is a successor of the pointed element by a given pointer?**

**Answers:**

- O(1)
- O(log2n)
- O(n)
- O(n*log2n)

**33. Suppose X is a B-tree leaf containing 41 entries and has at least one sibling. Which of the statements would be true in this case?**

**Answers:**

- Any sibling of X is also a leaf
- Any sibling of X contains at least 41 entries
- The parent of X has exactly 42 entries
- X has at least 41 siblings

**34. In a complete binary tree of n nodes, how far are the most distant two nodes? Assume each in the path counts 1. Assume log(n) is log base 2.**

**Answers:**

- about log(n)
- about 2*log(n)
- about 3*log(n)
- about 4*log(n)

**35. In a graph G, F is a spanning forest of G if**

** (i)F is a subgraph of G containing all the nodes of G**

** (ii)F is an order forest containing trees T1,T2,…Tn**

** (iii)Ti contains all the nodes that are reachable in G from the root Ti and are contained in Tj for some j<i..**

**Which of the above conditions is/are true?**

**Answers:**

- (i),(ii)
- (ii),(iii)
- (i),(iii)
- (i),(ii) and (iii)

**36. Which information is not saved in the activation record when a function call is executed?**

**Answers:**

- Current depth of recursion
- Formal parameters
- Location where the function should return when done
- Local variables

**37. The linked list implementation of sparse matrices is superior to the generalized dope vector method because it is __________.**

**Answers:**

- conceptually easier and completely dynamic
- efficient if the sparse matrix is a band matrix
- efficient in accessing an entry
- all of these

**38. Which situation occurs frequently if the selected hash function is poor?**

**Answers:**

- Overflow
- Underflow
- Collision
- None of the above

**39. The post-order traversal of a binary tree starts with:**

**Answers:**

- Post-order traversal of the left sub tree
- Post-order traversal of the right sub tree
- Post-order traversal of the root
- Post-order traversal of the lowest node

**40. One difference between a queue and a stack is:**

**Answers:**

- Queues require dynamic memory but stacks do not
- Stacks require dynamic memory but queues do not
- Queues use two ends of the structure but stacks use only one
- Stacks use two ends of the structure but queues use only one

**41. What is the minimum number of nodes in a full binary tree with depth 3?**

**Answers:**

- 4
- 8
- 11
- 15

**42. Using which traversal in a sorted binary insertion tree can a sorted array of numbers be obtained?**

**Answers:**

- Pre-order traversal
- Post-order traversal
- In order traversal
- Top-down traversal

**43. Where does the push member function place the new entry on the linked list in the linked list implementation of a queue?**

**Answers:**

- At the head
- At the tail
- After all other entries that are greater than the new entry
- After all other entries that are smaller than the new entry

**44. Which term is used to describe an O(n) algorithm?**

**Answers:**

- Constant
- Linear
- Logarithmic
- Quadratic

**45. What is the minimum number of nodes in a complete binary tree with depth 3?**

**Answers:**

- 4
- 8
- 11
- 15

**46. What is true of the complete bipartite graphs K(3,3) and K(2,4)?**

**Answers:**

- Both are planar
- Neither is a planar
- Both are isomorphic
- None of these

**47. If X is the adjacency matrix of a graph G with no self loops, the entries along the principle diagonal of X are ______.**

**Answers:**

- all zeros
- all ones
- both zeros and ones
- different

**48. Consider a linked list implementation of a queue with two pointers: front and rear. The time needed to insert element in a queue of length n is:**

**Answers:**

- O(1)
- O(log2n)
- O(n)
- O(n*log2n)

**49. What is the worst-case scenario for mergesort to sort an array of n elements?**

**Answers:**

- O(log n)
- O(n)
- O(n log n)
- O(n2)

**50. Consider a hashing function that resolves collision by quadratic probing. Assume that the address space is indexed from 1 to 8. If a collision occurs at position 4, the location which will never be probed is:**

**Answers:**

- 4
- 5
- 8
- 2

**51. In which data structure is the concept of rotation used?**

**Answers:**

- Binary search tree
- Circular queue
- AVL tree
- Circular linked list

**52. You have implemented a queue with a circular array keeping track of the first, the last, and the count (the number of items in the array). Suppose the first is zero, and the last is CAPACITY-1, what can you say about the count?**

**Answers:**

- The count must be zero
- The count must be CAPACITY
- The count can be zero or CAPACITY, but no other value can occur
- None of the above

**53. A procedure that calls itself in a program is called _______.**

**Answers:**

- Repeat
- Loop
- Recursion
- Tree

**54. State whether True or False.**

**For all possible inputs, a linear algorithm to solve a problem must perform faster than a quadratic algorithm to solve the same problem.**

**Answers:**

- True
- False

**55. If a max heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), where is the entry with the greatest value?**

**Answers:**

- data[0]
- data[n-1]
- data[n]
- data[2*n + 1]

**56. What is the worst-case scenario for quicksort to sort an array of n elements?**

**Answers:**

- O(log n)
- O(n)
- O(n log n)
- O(n2)

**57. Which of the following lines of the code will delete two successive nodes of a single linked linear list(with more than two nodes)? Here ‘LINK[X]’ denotes the address field of node X.**

**Answers:**

- LINK[X]:=LINK[LINK[X]]
- X:=LINK[LINK[X]]
- LINK[LINK[X]]:=X
- LINK[X]:=LINK[LINK[LINK[X]]]

**58. A non- planar graph with the minimum number of vertices has:**

**Answers:**

- 10 edges, 5 vertices
- 9 edges, 6 vertices
- 6 edges, 4 vertices
- 9 edges, 5 vertices

**59. A circuit which is a connected graph and which includes every vertex of the graph is known as_____.**

**Answers:**

- Euler
- Unicursal
- Hamiltonian
- Clique

**60. A one dimensional array A has indices 1…75. Each element is a string and takes up three memory words. The array is stored starting at location 1120 decimal. The starting address of A[49] is:**

**Answers:**

- 1267
- 1164
- 1264
- 1169

**61. A simple graph in which there exists an edge between every pair of vertices is called a/an _________.**

**Answers:**

- incomplete graph
- complete graph
- Euler graph
- planner graph

**62. Let A be a sorted array of n=10 elements. Assume that only one comparison is required to determine whether the target is equal to, less than, or greater than A[i]. Which of the following denotes the average successful time of finding an arbitrary element x in A using the binary search?**

**Answers:**

- 1.6
- 2.9
- 4.2
- 5.5

**63. Which operations require linear time for their worst-case behavior in the linked-list version of a queue?**

**Answers:**

- front
- push
- empty
- None of these operations require linear time

**64. Which of the following statements about binary trees is false?**

**Answers:**

- Every Node must have at least two children
- Every non-empty tree has exactly one root node
- Every node has at the most two children
- None of the above

**65. How many real links are required for a sparse matrix having 10 rows, 10 columns and 15 non-zero elements? (Pick the nearest answer)**

**Answers:**

- 15
- 20
- 50
- 100

**66. In a graph G having the cut set matrix C(G) and an incidence matrix A(G), the rank of C(G) would be____**

**Answers:**

- The same as that of A(G)
- More than that of A(G)
- Less than that of A(G)
- Independent of the rank of A(G)

**67. Which of the operations is simpler in the doubly linked list than it is in the simple linked list?**

**Answers:**

- Insertion
- Deletion
- Both a and b
- None of the above

**68. Which of the following formulae in big-Oh notation best represents the expression n2+35n+6?**

**Answers:**

- O(n3)
- O(n2)
- O(n)
- O(42)

**69. The operation for removing an entry from a stack is traditionally called _______.**

**Answers:**

- delete
- peek
- pop
- remove

**70. Which queue allows insertion and deletion at both ends?**

**Answers:**

- Simple queue
- Circular queue
- Dequeue
- Special queue

**71. What kind of initialization needs to be done for a chained hash table?**

**Answers:**

- None
- The key at each array location must be initialized
- The head pointer of each chain must be set to NULL
- Both B and C must be carried out

**72. The number of nodes in the largest maximal independent set of the complete bipartite graph K(4,2) is_____ .**

**Answers:**

- 2
- 3
- 4
- 6

**73. Which of the following techniques is used to resolve collision in hashing?**

**Answers:**

- Separate chaining
- Open addressing
- Linear probing
- All of the above

**74. You have implemented a queue with a linked list keeping track of a front pointer and a rear pointer. Which of these pointers will you change during an insertion into a NONEMPTY queue?**

**Answers:**

- Neither of them changes
- Only front_ptr changes
- Only rear_ptr changes
- Both change

**75. Which of the following operations is performed more efficiently by the doubly linked list than by the linear linked list?**

**Answers:**

- Deleting a node the location of which is given
- Searching an unsorted list for a given item
- Inserting a node after the node with a given location
- Traversing the list to process each node

**76. Four characters are placed in a queue in the following order: D, C, B, and A. If they are removed one at a time, what will be the order of their removal?**

**Answers:**

- ABCD
- ABDC
- DCAB
- DCBA

**77. What is the meaning of the statement: “Entries in a stack are ‘ordered'”?**

**Answers:**

- A collection of stacks can be sorted
- Stack entries may be compared with the ‘<‘ operation
- The entries must be stored in a linked list
- There is a first entry, a second entry, and so on

**78. A given connected graph G is a Euler graph if and only if all vertices of G are of ______.**

**Answers:**

- the same degree
- even degrees
- odd degrees
- different degrees

**79. Which of the following data structures has a balanced condition?**

**Answers:**

- AVL Tree
- Doubly Linked List
- Double Ended Queue
- Stack

**80. A matrix is called sparse when______**

**Answers:**

- most of its elements are non-zero
- most of its elements are zero
- all of its elements are non-zero
- None of the above

**81. Which of the following operations in the simple linked list will modify the beginning of the linked list?**

**Answers:**

- Deletion of the first node
- Insertion after the last node
- Insertion after the first node
- None of the above

**82. You have implemented a queue with a circular array keeping track of the first item, the last item, and the count (the number of items in the array). Suppose the address of the first is zero, and that of the last is CAPACITY-1, what can you say about the count?**

**Answers:**

- The count must be zero
- The count must be CAPACITY
- The count can be zero or CAPACITY, but no other value can occur
- None of the above

**83. What is the worst-case scenario for the binary search for finding a single item in an array?**

**Answers:**

- Constant time
- Logarithmic time
- Linear time
- Quadratic time

**84. A binary tree, all the levels of which except possibly the last have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is known as:**

**Answers:**

- Full binary tree
- 2-Tree
- Threaded tree
- Complete binary tree

**85. What is the pre-order traversal equivalent of the following algebraic expression?**

**[a+(b-c)]*[(d-e)/(f+(g-h))]**

**Answers:**

- abc-+de-fg+h-/*
- *+a-bc/-de+f-gh
- a+*b-/c-d-e+fgh
- *+a-bc-/d+e-fgh

**86. In the linked representation of a sparse matrix, the head node for a column list stores_____**

**Answers:**

- a pointer to the next column head node
- a pointer to the first node in the column list
- column number
- All of the above

**87. The hashing function which dynamically adapts to changes in the table being accessed is called ________.**

**Answers:**

- Real
- Linear
- Partial
- Virtual

**88. What will happen if in data structure a pop operation on the stack causes the stack pointer to move past the origin of the stack?**

**Answers:**

- Overflow
- Underflow
- Null
- Garbage collection

**89. If h is the depth of the tree, which formula will be used to find the maximum number of nodes n in a perfect binary tree?**

**Answers:**

- 2h + 1 – 1
- 2h + 1
- 2h
- 2h + 1 + 1

**90. What is the minimum number of edges and vertices possible in a non- planar graph?**

**Answers:**

- 10 edges, 5 vertices
- 9 edges, 6 vertices
- 6 edges, 4 vertices
- 9 edges, 5 vertices

**91. Which of the following is the worst-case scenario for operations on heaps?**

**Answers:**

- Neither insertion nor removal is better than linear
- Insertion is better than linear, but removal is not
- Removal is better than linear, but insertion is not
- Both insertion and removal are better than linear

**92. Which of these are standard operations of Stack Data Structure?**

**Answers:**

- Push, delete
- Insert, pop
- Put, extract
- Push, pop

**93. Suppose we have a circular array implementation of a queue, with ten items in the queue stored at data[2] through data[11]. The CAPACITY is 42. Where does the enqueue member function place the new entry in the array?**

**Answers:**

- data[1]
- data[2]
- data[11]
- data[12]

**94. A binary search tree is generated by inserting the following integers in the order: 50,15,62,5,20,58,91,3,8,37,60,24. How many nodes are in the left and right subtrees, respectively?**

**Answers:**

- (4,7)
- (7,4)
- (8,3)
- (3,8)

**95. What is the worst-case scenario for the binary search for finding a single item in an sorted array?**

**Answers:**

- Constant time
- Logarithmic time
- Linear time
- Quadratic time

**96. What is the maximum depth of recursive calls a function may make?**

**Answers:**

- 1
- 2
- n (where n is the argument)
- There is no fixed maximum

**97. Consider this binary search tree.**

**Which will be the new root if you remove the root and replace it with something from the left subtree?**

**Answers:**

- 1
- 2
- 4
- 5

**98. The number of distinct simple graphs with up to three nodes is _______.**

**Answers:**

- 15
- 10
- 7
- 9

**99. In a selection sort algorithm, the number of passes required to perform the sort are ______.**

**Answers:**

- N
- N-1
- N-2
- N^2

3,866 total views, 9 views today

## Latest Comments