MCQs / Computer Science / NSCT: Data Structures & Algorithms

NSCT: Data Structures & Algorithms MCQs — Computer Science (page 6)

150 multiple-choice questions on NSCT: Data Structures & Algorithms from Computer Science, each with the correct answer and, where available, a teacher's explanation. Read through them to revise the chapter, then practise the same questions one by one to test yourself.

126. A node with no children is called a:

  1. Parent
  2. Leaf
  3. Sibling
  4. Root

Answer: B) Leaf

Explanation: Leaves are at the bottom of the tree. Lesson 3.3 · Data Structures & Algorithms

Discuss this question

127. Keys 8, 3, 10, 1, 6, 14 are inserted in this order into an empty binary search tree. What is the post-order traversal?

  1. 1, 3, 6, 8, 10, 14
  2. 14, 10, 8, 6, 3, 1
  3. 8, 3, 1, 6, 10, 14
  4. 1, 6, 3, 14, 10, 8

Answer: D) 1, 6, 3, 14, 10, 8

Explanation: Post-order visits left, right, then root – the first key inserted (root) comes last. Lesson 3.3 · Data Structures & Algorithms

Discuss this question

128. Keys 15, 10, 20, 8, 12, 25 are inserted in this order into an empty BST. What is the height of the tree (root at height 0)?

  1. 2
  2. 1
  3. 3
  4. 5

Answer: A) 2

Explanation: The longest root-to-leaf path has 2 edges. Lesson 3.3 · Data Structures & Algorithms

Discuss this question

129. Keys 50, 30, 70, 20, 40, 60, 80 are inserted in this order into an empty binary search tree. What is the pre-order traversal?

  1. 50, 30, 20, 40, 70, 60, 80
  2. 80, 60, 40, 20, 70, 30, 50
  3. 20, 30, 40, 50, 60, 70, 80
  4. 20, 40, 30, 60, 80, 70, 50

Answer: A) 50, 30, 20, 40, 70, 60, 80

Explanation: Pre-order visits root, then left subtree, then right subtree. Lesson 3.3 · Data Structures & Algorithms

Discuss this question

130. The values 20, 15, 30, 5, 25 are inserted one by one into an empty min-heap. Which value is at the root?

  1. 30
  2. 5
  3. 25
  4. 20

Answer: B) 5

Explanation: The root of a min-heap is always the smallest element. Lesson 3.3 · Data Structures & Algorithms

Discuss this question

131. Keys 8, 3, 10, 1, 6, 14 are inserted in this order into an empty BST. What is the height of the tree (root at height 0)?

  1. 5
  2. 2
  3. 3
  4. 1

Answer: B) 2

Explanation: The longest root-to-leaf path has 2 edges. Lesson 3.3 · Data Structures & Algorithms

Discuss this question

132. Using the hash function h(k) = k mod 13, what is the index of key 100?

  1. 7
  2. 4
  3. 10
  4. 9

Answer: D) 9

Explanation: 100 mod 13 = 9. Lesson 3.5 · Data Structures & Algorithms

Discuss this question

133. Evaluate the postfix expression: 7 2 2 + 3 -

  1. 8
  2. 16
  3. 10
  4. 7

Answer: A) 8

Explanation: Push operands; on an operator pop two values and push the result. Answer 8. Lesson 3.2 · Data Structures & Algorithms

Discuss this question

134. Using the hash function h(k) = k mod 10, what is the index of key 1234?

  1. 123
  2. 6
  3. 4
  4. 5

Answer: C) 4

Explanation: 1234 mod 10 = 4. Lesson 3.5 · Data Structures & Algorithms

Discuss this question

135. Space complexity measures:

  1. CPU speed
  2. Extra memory used as input grows
  3. Disk size of the program
  4. Number of lines of code

Answer: B) Extra memory used as input grows

Explanation: It counts additional memory, e.g. merge sort needs O(n). Lesson 3.1 · Data Structures & Algorithms

Discuss this question

136. Keys 40, 20, 60, 10, 30, 50 are inserted in this order into an empty BST. What is the height of the tree (root at height 0)?

  1. 2
  2. 1
  3. 5
  4. 3

Answer: A) 2

Explanation: The longest root-to-leaf path has 2 edges. Lesson 3.3 · Data Structures & Algorithms

Discuss this question

137. The worst-case search time in a hash table where all keys collide into one chain is:

  1. O(n)
  2. O(log n)
  3. O(1)
  4. O(n log n)

Answer: A) O(n)

Explanation: The search degenerates into scanning a list. Lesson 3.5 · Data Structures & Algorithms

Discuss this question

138. Evaluate the postfix expression: 3 4 + 5 6 +

  1. 77
  2. 79
  3. 154
  4. 76

Answer: A) 77

Explanation: Push operands; on an operator pop two values and push the result. Answer 77. Lesson 3.2 · Data Structures & Algorithms

Discuss this question

139. Two loops of size n placed one after another (not nested) give:

  1. O(log n)
  2. O(2ⁿ)
  3. O(n)
  4. O(n²)

Answer: C) O(n)

Explanation: n + n = 2n = O(n). Lesson 3.1 · Data Structures & Algorithms

Discuss this question

140. After the FIRST pass of selection sort (ascending) on [9, 7, 5, 3, 1], the list is:

  1. [9, 7, 5, 3, 1]
  2. [1, 7, 5, 3, 9]
  3. [7, 5, 3, 1, 9]
  4. [1, 3, 5, 7, 9]

Answer: B) [1, 7, 5, 3, 9]

Explanation: Selection sort swaps the minimum into position 0. Lesson 3.6 · Data Structures & Algorithms

Discuss this question

141. Using the hash function h(k) = k mod 7, what is the index of key 58?

  1. 3
  2. 5
  3. 8
  4. 2

Answer: D) 2

Explanation: 58 mod 7 = 2. Lesson 3.5 · Data Structures & Algorithms

Discuss this question

142. A tree with 20 nodes has how many edges?

  1. 19
  2. 20
  3. 40
  4. 21

Answer: A) 19

Explanation: Every node except the root has exactly one incoming edge. Lesson 3.3 · Data Structures & Algorithms

Discuss this question

143. Linear search finds the target at the first position. This is its:

  1. Best case
  2. Amortised case
  3. Worst case
  4. Average case

Answer: A) Best case

Explanation: Best case is O(1). Lesson 3.1 · Data Structures & Algorithms

Discuss this question

144. Evaluate the postfix expression: 4 5 + 2

  1. 36
  2. 18
  3. 20
  4. 17

Answer: B) 18

Explanation: Push operands; on an operator pop two values and push the result. Answer 18. Lesson 3.2 · Data Structures & Algorithms

Discuss this question

145. GPS navigation apps find the fastest route mainly using variants of:

  1. Binary search
  2. Bubble sort
  3. Huffman coding
  4. Dijkstra's algorithm

Answer: D) Dijkstra's algorithm

Explanation: Roads are a weighted graph. Lesson 3.4 · Data Structures & Algorithms

Discuss this question

146. A minimum spanning tree of a connected graph with V vertices has:

  1. V − 1 edges
  2. 2V edges
  3. V edges
  4. V² edges

Answer: A) V − 1 edges

Explanation: A spanning tree connects all vertices without cycles. Lesson 3.4 · Data Structures & Algorithms

Discuss this question

147. What is the time complexity of this code fragment? c i = n; while (i 0) i = i / 3;

  1. O(n)
  2. O(n³)
  3. O(1)
  4. O(log n)

Answer: D) O(log n)

Explanation: Count how often the innermost statement runs as n grows: O(log n). Lesson 3.1 · Data Structures & Algorithms

Discuss this question

148. An algorithm takes 2 seconds for n = 1,000 and 8 seconds for n = 2,000. Its complexity is most likely:

  1. O(n²)
  2. O(log n)
  3. O(2ⁿ)
  4. O(n)

Answer: A) O(n²)

Explanation: Doubling n quadruples time, which is quadratic. Lesson 3.1 · Data Structures & Algorithms

Discuss this question

149. Which structure is used to check whether brackets in an expression are balanced?

  1. Stack
  2. Binary tree
  3. Hash table
  4. Queue

Answer: A) Stack

Explanation: Push opening brackets, pop on closing brackets. Lesson 3.2 · Data Structures & Algorithms

Discuss this question

150. A stack follows which principle?

  1. LIFO
  2. Random access
  3. FIFO
  4. Priority order

Answer: A) LIFO

Explanation: Last in, first out. Lesson 3.2 · Data Structures & Algorithms

Discuss this question

Previous Page 6 of 6

Practise NSCT: Data Structures & Algorithms MCQs

More Computer Science chapters