100+ Data Structures and Algorithms Questions

data structure and algorithms questions techhyme

A data structure is an arrangement of data in a computer’s memory (or sometimes on a disk). Data structures include
arrays, linked lists, stacks, binary trees, and hash tables, among others. Algorithms manipulate the data in these
structures in various ways, such as searching for a particular data item and sorting the data.

These questions are intended as a self-test for readers.

1. In many data structures you can ________ a single record, _________ it, and _______ it.

2. Rearranging the contents of a data structure into a certain order is called _________ .

3. In a database, a field is

a specific data item.
a specific object.
part of a record.
part of an algorithm.

4. The field used when searching for a particular record is the ______________ .

5. In object-oriented programming, an object

is a class.
may contain data and methods.
is a program.
may contain classes.

6. A class

is a blueprint for many objects.
represents a specific real-world object.
will hold specific values in its fields.
specifies the type of a method.

7. In Java, a class specification

creates objects.
requires the keyword new.
creates references.
none of the above.

8. When an object wants to do something, it uses a ________ .

9. In Java, accessing an object’s methods requires the _____ operator.

10. In Java, boolean and byte are _____________ .

11. Inserting an item into an unordered array

takes time proportional to the size of the array.
requires multiple comparisons.
requires shifting other items to make room.
takes the same time no matter how many items there are.

12. True or False: When you delete an item from an unordered array, in most cases you shift other items to fill in the gap.

13. In an unordered array, allowing duplicates

increases times for all operations.
increases search times in some situations.
always increases insertion times.
sometimes decreases insertion times.

14. True or False: In an unordered array, it’s generally faster to find out an item is not in the array than to find out it is.

15. Creating an array in Java requires using the keyword ________ .

16. If class A is going to use class B for something, then

class A’s methods should be easy to understand.
it’s preferable if class B communicates with the program’s user.
the more complex operations should be placed in class A.
the more work that class B can do, the better.

17. When class A is using class B for something, the methods and fields class A can access in class B are called class B’s __________.

18. Ordered arrays, compared with unordered arrays, are

much quicker at deletion.
quicker at insertion.
quicker to create.
quicker at searching.

19. A logarithm is the inverse of _____________ .

20. The base 10 logarithm of 1,000 is _____ .

21. The maximum number of elements that must be examined to complete a binary search in an array of 200 elements is

200.
8.
1.
13.

22. The base 2 logarithm of 64 is ______ .

23. True or False: The base 2 logarithm of 100 is 2.

24. Big O notation tells

how the speed of an algorithm relates to the number of items.
the running time of an algorithm for a given size data structure.
the running time of an algorithm for a given number of items.
how the size of a data structure relates to the number of items.

25. O(1) means a process operates in _________ time.

26. Either variables of primitive types or _________ can be placed in an array.

27. Computer sorting algorithms are more limited than humans in that

humans are better at inventing new algorithms.
computers can handle only a fixed amount of data.
humans know what to sort, whereas computers need to be told.
computers can compare only two things at a time.

28. The two basic operations in simple sorting are _________ items and _________ them (or sometimes _________ them).

29. True or False: The bubble sort always ends up comparing every item with every other item.

30. The bubble sort algorithm alternates between

comparing and swapping.
moving and copying.
moving and comparing.
copying and comparing.

31. True or False: If there are N items, the bubble sort makes exactly N*N comparisons.

32. In the selection sort,

the largest keys accumulate on the left (low indices).
a minimum key is repeatedly discovered.
a number of items must be shifted to insert each item in its correctly sorted position.
the sorted items accumulate on the right.

33. True or False: If, in a particular sorting situation, swaps take much longer than comparisons, the selection sort is about twice as fast as the bubble sort.

34. A copy is ________ times as fast as a swap.

35. What is the invariant in the selection sort?

36. In the insertion sort, the “marked player” described in the text corresponds to which variable in the insertSort.java program?

in
out
temp
a[out]

37. In the insertion sort, “partially sorted” means that

some items are already sorted, but they may need to be moved.
most items are in their final sorted positions, but a few still need to be sorted.
only some of the items are sorted.
group items are sorted among themselves, but items outside the group may need to be inserted in it.

38. Shifting a group of items left or right requires repeated __________.

39. In the insertion sort, after an item is inserted in the partially sorted group, it will

never be moved again.
never be shifted to the left.
often be moved out of this group.
find that its group is steadily shrinking.

40. The invariant in the insertion sort is that ________.

41. Stability might refer to

items with secondary keys being excluded from a sort.
keeping cities sorted by increasing population within each state, in a sort by state.
keeping the same first names matched with the same last names.
items keeping the same order of primary keys without regard to secondary keys.

42. Suppose you push 10, 20, 30, and 40 onto the stack. Then you pop three items. Which one is left on the stack?

43. Which of the following is true?

The pop operation on a stack is considerably simpler than the remove operation on a queue.
The contents of a queue can wrap around, while those of a stack cannot.
The top of a stack corresponds to the front of a queue.
In both the stack and the queue, items removed in sequence are taken from increasingly high index cells in the array.

44. What do LIFO and FIFO mean?

45. True or False: A stack or a queue often serves as the underlying mechanism on which an ADT array is based.

46. Assume an array is numbered with index 0 on the left. A queue representing a line of movie-goers, with the first to arrive numbered 1, has the ticket window on the right. Then

there is no numerical correspondence between the index numbers and the movie-goer numbers.
the array index numbers and the movie-goer numbers increase in opposite left-right directions.
the array index numbers correspond numerically to the locations in the line of movie-goers.
the movie-goers and the items in the array move in the same direction.

47. As other items are inserted and removed, does a particular item in a queue move along the array from lower to higher indices, or higher to lower?

48. Suppose you insert 15, 25, 35, and 45 into a queue. Then you remove three items. Which one is left?

49. True or False: Pushing and popping items on a stack and inserting and removing items in a queue all take O(N) time.

50. A queue might be used to hold

the items to be sorted in an insertion sort.
reports of a variety of imminent attacks on the star ship Enterprise.
keystrokes made by a computer user writing a letter.
symbols in an algebraic expression being evaluated.

51. Inserting an item into a typical priority queue takes what big O time?

52. The term priority in a priority queue means that

the highest priority items are inserted first.
the programmer must prioritize access to the underlying array.
the underlying array is sorted by the priority of the items.
the lowest priority items are deleted first.

53. One difference between a priority queue and an ordered array is that

the lowest-priority item cannot be extracted easily from the array as it can from the priority queue.
the array must be ordered while the priority queue need not be.
the highest priority item can be extracted easily from the priority queue but not from the array.
All of the above.

54. A priority queue might be used to hold

passengers to be picked up by a taxi from different parts of the city.
keystrokes made at a computer keyboard.
squares on a chessboard in a game program.
planets in a solar system simulation.

55. Which of the following is not true? A reference to a class object

can be used to access public methods in the object.
has a size dependant on its class.
has the data type of the class.
does not hold the object itself.

56. Access to the links in a linked list is usually through the _________ link.

57. When you create a reference to a link in a linked list, it

must refer to the first link.
must refer to the link pointed to by current.
must refer to the link pointed to by next.
can refer to any link you want.

58. How many references must you change to insert a link in the middle of a singly linked list?

59. How many references must you change to insert a link at the end of a singly linked list?

60. Assuming current points to the next-to-last link in a singly linked list, what statement will delete the last link from the list?

61. When all references to a link are changed to refer to something else, what happens to the link?

62. A double-ended list

can be accessed from either end.
is a different name for a doubly linked list.
has pointers running both forward and backward between links.
has its first link connected to its last link.

63. A special case often occurs for insertion and deletion routines when a list is ________.

64. Assuming a copy takes longer than a comparison, is it faster to delete an item with a certain key from a linked list or from an unsorted array?

65. How many times would you need to traverse a singly linked list to delete the item with the largest key?

66. Of the lists discussed in this chapter, which one would be best for implementing a queue?

67. Which of the following is not true? Iterators would be useful if you wanted to

do an insertion sort on a linked list.
insert a new link at the beginning of a list.
swap two links at arbitrary locations.
delete all links with a certain key value.

68. Which do you think would be a better choice to implement a stack: a singly linked list or an array?

69. Where are the copies of the argument, mentioned in question 1, stored?

in a variable in the triangle() method
in a field of the TriangleApp class
in a variable of the getString() method
on a stack

70. The disadvantage of mergesort is that

it is not recursive.
it uses more memory.
although faster than the insertion sort, it is much slower than quicksort.
it is complicated to implement.

71. Besides a loop, a ___________ can often be used instead of recursion.

72. The Shellsort works by

partitioning the array.
swapping adjacent elements.
dealing with widely separated elements.
starting with the normal insertion sort.

73. If an array has 100 elements, then Knuth’s algorithm would start with an interval of ________.

74. To transform the insertion sort into the Shellsort, which of the following do you not do?

Substitute h for 1.
Insert an algorithm for creating gaps of decreasing width.
Enclose the normal insertion sort in a loop.
Change the direction of the indices in the inner loop.

75. True or false: A good interval sequence for the Shellsort is created by repeatedly dividing the array size in half.

76. Fill in the big O values: The speed of the Shellsort is more than _______ but less than ________.

77. Partitioning is

putting all elements larger than a certain value on one end of the array.
dividing an array in half.
partially sorting parts of an array.
sorting each half of an array separately.

78. When partitioning, each array element is compared to the _______.

79. True or false: In quicksort, the pivot can be an arbitrary element of the array.

80. Assuming larger keys on the right, the partition is

the element between the left and right subarrays.
the key value of the element between the left and right subarrays.
the left element in the right subarray.
the key value of the left element in the right subarray.

81. Quicksort involves partitioning the original array and then _________.

82. After a partition in a simple version of quicksort, the pivot may be

used to find the median of the array.
exchanged with an element of the right subarray.
used as the starting point of the next partition.
discarded.

83. Median-of-three partitioning is a way of choosing the _______ .

84. In quicksort, for an array of N elements, the partitionIt() method will examine each element approximately ______ times.

85. True or false: You can speed up quicksort if you stop partitioning when the partition size is 5 and finish by using a different sort.

86. Insertion and deletion in a tree require what big O time?

87. A binary tree is a search tree if

every non-leaf node has children whose key values are less than (or equal to) the parent.
every left child has a key less than the parent and every right child has a key greater than (or equal to) the parent.
in the path from the root to every leaf node, the key of each node is greater than (or equal to) the key of its parent.
a node can have a maximum of two children.

88. True or False: Not all trees are binary trees.

89. In a complete binary tree with 20 nodes, and the root considered to be at level 0, how many nodes are there at level 4?

90. A subtree of a binary tree always has

a root that is a child of the main tree’s root.
a root unconnected to the main tree’s root.
fewer nodes than the main tree.
a sibling with the same number of nodes.

91. In the Java code for a tree, the ______ and the _______ are generally separate classes.

92. Finding a node in a binary search tree involves going from node to node, asking

how big the node’s key is in relation to the search key.
how big the node’s key is compared to its right or left children.
what leaf node we want to reach.
what level we are on.

93. An unbalanced tree is one

in which most of the keys have values greater than the average.
whose behavior is unpredictable.
in which the root or some other node has many more left children than right children, or vice versa.
that is shaped like an umbrella.

94. Inserting a node starts with the same steps as _______ a node.

95. Suppose a node A has a successor node S. Then S must have a key that is larger than _____ but smaller than or equal to _______.

96. In a binary tree used to represent a mathematical expression, which of the following is not true?

Both children of an operator node must be operands.
Following a postorder traversal, no parentheses need to be added.
Following an inorder traversal, parentheses must be added.
In pre-order traversal a node is visited before either of its children.

97. If a tree is represented by an array, the right child of a node at index n has an index of _______ .

98. True or False: Deleting a node with one child from a binary search tree involves finding that node’s successor.

99. A Huffman tree is typically used to _______ text.

100. Which of the following is not true about a Huffman tree?

The most frequently used characters always appear near the top of the tree.
Normally, decoding a message involves repeatedly following a path from the root to a leaf.
In coding a character you typically start at a leaf and work upward.
The tree can be generated by removal and insertion operations on a priority queue.

101. A balanced binary search tree is desirable because it avoids slow performance when data is inserted ________.

102. In a balanced tree,

the tree may need to be restructured during searches.
the paths from the root to all the leaf nodes are about the same length.
all left subtrees are the same height as all right subtrees.
the height of all subtrees is closely controlled.

103. True or False: The red-black rules rearrange the nodes in a tree to balance it.

104. A null child is

a child that doesn’t exist but will be created next.
a child with no children of its own.
one of the two potential children of a leaf node where an insertion will be made.
a non-existent left child of a node with a right child (or vice versa).

105. Which of the following is not a red-black rule?

Every path from a root to a leaf, or to a null child, must contain the same number of black nodes.
If a node is black, its children must be red.
The root is always black.
All three are valid rules.

106. The two possible actions used to balance a tree are _______ and _______ .

107. Newly inserted nodes are always colored _______ .

108. Which of the following is not involved in a rotation?

rearranging nodes to restore the characteristics of a binary search tree
changing the color of nodes
ensuring the red-black rules are followed
attempting to balance the tree

109. A “crossover” node or subtree starts as a ________ and becomes a _______ , or vice versa.

110. Which of the following is not true? Rotations may need to be made

before a node is inserted.
after a node is inserted.
during a search for the insertion point.
when searching for a node with a given key.

111. A color flip involves changing the color of ______ and ______ .

112. An outside grandchild is

on the opposite side of its parent that its parent is of its sibling.
on the same side of its parent that its parent is of its parent.
one which is the left descendant of a right descendant (or vice versa).
on the opposite side of its parent that its sibling is of their grandparents.

113. True or False: When one rotation immediately follows another, they are in opposite directions.

114. Two rotations are necessary when

the node is an inside grandchild and the parent is red.
the node is an inside grandchild and the parent is black.
the node is an outside grandchild and the parent is red.
the node is an outside grandchild and the parent is black.

115. True or False: Deletion in a red-black tree may require some readjustment of the tree’s structure.

116. A 2-3-4 tree is so named because a node can have

three children and four data items.
two, three, or four children.
two parents, three children, and four items.
two parents, three items, and four children.

117. A 2-3-4 tree is superior to a binary search tree in that it is ________ .

118. Imagine a parent node with data items 25, 50, and 75. If one of its child nodes had items with values 60 and 70, it would be the child numbered __________ .

119. True or False: Data items are located exclusively in leaf nodes.

120. Which of the following is not true each time a node is split?

Exactly one new node is created.
Exactly one new data item is added to the tree.
One data item moves from the split node to its parent.
One data item moves from the split node to its new sibling.

121. A 2-3-4 tree increases its number of levels when ________.

122. Searching a 2-3-4 tree does not involve

splitting nodes on the way down if necessary.
picking the appropriate child to go to, based on data items in a node.
ending up at a leaf node if the search key is not found.
examining at least one data item in any node visited.

123. After a non-root node of a 2-3-4 tree is split, does its new right child contain the item previously numbered 0, 1, or 2?

124. A 4-node split in a 2-3-4 tree is equivalent to a _______ in a red-black tree.

125. Which of the following statements about a node-splitting operation in a 2-3 tree (not a 2-3-4 tree) is not true?

The parent of a split node must also be split if it is full.
The smallest item in the node being split always stays in that node.
When the parent is split, child 2 must always be disconnected from its old parent and connected to the new parent.
The splitting process starts at a leaf and works upward.

126. What is the big O efficiency of a 2-3 tree?

127. In accessing data on a disk drive,

inserting data is slow but finding the place to write data is fast.

moving data to make room for more data is fast because so many items can be accessed at once.
deleting data is unusually fast.
finding the place to write data is comparatively slow but a lot of data can be written quickly.

128. In a B-tree each node contains _______ data items.

129. True or False: Node splits in a B-tree have similarities to node splits in a 2-3 tree.

130. In external storage, indexing means keeping a file of

keys and their corresponding blocks.
records and their corresponding blocks.
keys and their corresponding records.
last names and their corresponding keys.

131. Using big O notation, say how long it takes (ideally) to find an item in a hash table.

132. A __________ transforms a range of key values into a range of index values.

133. Open addressing refers to

keeping many of the cells in the array unoccupied.
keeping an open mind about which address to use.
probing at cell x+1, x+2, and so on until an empty cell is found.
looking for another location in the array when the one you want is occupied.

134. Using the next available position after an unsuccessful probe is called _____________.

135. What are the first five step sizes in quadratic probing?

136. Secondary clustering occurs because

many keys hash to the same location.
the sequence of step lengths is always the same.
too many items with the same key are inserted.
the hash function is not perfect.

137. Separate chaining involves the use of a _____________ at each location.

138. A reasonable load factor in separate chaining is ________.

139. True or False: A possible hash function for strings involves multiplying each character by an ever-increasing power.

140. The best technique when the amount of data is not well known is

linear probing.
quadratic probing.
double hashing.
separate chaining.

141. If digit folding is used in a hash function, the number of digits in each group should reflect _____________.

142. True or False: In linear probing an unsuccessful search takes longer than a successful search.

143. In separate chaining the time to insert a new item

increases linearly with the load factor.
is proportional to the number of items in the table.
is proportional to the number of lists.
is proportional to the percentage of full cells in the array.

144. True or False: In external hashing, it’s important that the records don’t become full.

145. In external hashing, all records with keys that hash to the same value are located in ___________.

146. What does the term complete mean when applied to binary trees?

All the necessary data has been inserted.
All the rows are filled with nodes, except possibly the bottom one.
All existing nodes contain data.
The node arrangement satisfies the heap condition.

147. What does the term weakly ordered mean when applied to heaps?

148. A node is always removed from the __________.

149. To “trickle up” a node in a descending heap means

to repeatedly exchange it with its parent until it’s larger than its parent.
to repeatedly exchange it with its child until it’s larger than its child.
to repeatedly exchange it with its child until it’s smaller than its child.
to repeatedly exchange it with its parent until it’s smaller than its parent.

150. A heap can be represented by an array because a heap

is complete.
is weakly ordered.
is a binary tree.
satisfies the heap condition.

151. The last node in a heap is

always a left child.
always a right child.
always on the bottom row.
never less than its sibling.

152. A heap is to a priority queue as a(n) _______ is to a stack.

153. Insertion into a descending heap involves trickle _____.

154. Heapsort involves

removing data from a heap and then inserting it again.
inserting data into a heap and then removing it.
copying data from one heap to another.
copying data from the array representing a heap to the heap.

155. How many arrays, each big enough to hold all the data, does it take to sort a heap?

156. In a graph, an _______ connects two _________ .

157. How do you tell, by looking at its adjacency matrix, how many edges there are in an undirected graph?

158. In a game simulation, what graph entity corresponds to a choice about what move to make?

159. A directed graph is one in which

you must follow the minimum spanning tree.
you must go from vertex A to vertex B to vertex C and so on.
you can go in only one direction from one given vertex to another.
you can go in only one direction on any given path.

160. If an adjacency matrix has rows {0,1,0,0}, {1,0,1,1}, {0,1,0,0}, and {0,1,0,0}, what is the corresponding adjacency list?

161. A minimum spanning tree is a graph in which

the number of edges connecting all the vertices is as small as possible.
the number of edges is equal to the number of vertices.
all unnecessary vertices have been removed.
every combination of two vertices is connected by the minimum number of edges.

162. How many different minimum spanning trees are there in an undirected graph of three vertices and three edges?

163. An undirected graph must have a cycle if

any vertex can be reached from some other vertex.
the number of paths is greater than the number of vertices.
the number of edges is equal to the number of vertices.
the number of paths is less than the number of edges.

164. A ______ is a graph with no cycles.

165. Can a minimum spanning tree for an undirected graph have cycles?

166. True or False: There may be many correct topological sorts for a given graph.

167. Topological sorting results in

vertices arranged so the directed edges all go in the same direction.
vertices listed in order of increasing number of edges from the beginning vertex.
vertices arranged so A precedes B, which precedes C, and so on.
vertices listed so the ones later in the list are downstream from the ones earlier.

168. What’s a DAG?

169. Can a tree have cycles?

170. What evidence does the topo.java program (Listing 13.4) use to deduce that a graph has a cycle?

171. The weight in a weighted graph is a property of the graph’s _______.

172. In a weighted graph, the minimum spanning tree (MST) tries to minimize

the number of edges from the starting vertex to a specified vertex.
the number of edges connecting all the vertices.
the total weight of the edges from the starting vertex to a specified vertex.
the total weight of edges connecting all the vertices.

173. True or False: The weight of the MST depends on the starting vertex.

174. In the MST algorithm, what is removed from the priority queue?

175. In the cable TV example, each edge added to the MST connects

the starting vertex to an adjacent vertex.
an already-connected city to an unconnected city.
the current vertex to an adjacent vertex.
two cities with offices.

176. The MST algorithm “prunes” an edge from the list when the edge leads to a vertex that _________ .

177. True or False: The shortest-path problem (SPP) must be carried out on a directed graph.

178. Dijkstra’s algorithm finds the shortest path

from one specified vertex to all other vertices.
from one specified vertex to another specified vertex.
from all vertices to all other vertices that can be reached along one edge.
from all vertices to all other vertices that can be reached along multiple edges.

179. True or False: The rule in Dijkstra’s algorithm is to always put in the tree the vertex that is closest to the starting vertex.

180. In the railroad fares example, a fringe town is one