CCP CCP Data Structures & Abstract Data Types 2 — Questions and Answers
Question 1: In a binary tree, a node with no children is called a:
- Root
- Parent
- Leaf (Correct answer)
- Branch
Correct answer: Leaf
A leaf node is a node in a binary tree that has no left or right child.
Question 2: A hash table resolves collisions using chaining by storing colliding elements in a:
- Stack at each bucket
- Linked list at each bucket (Correct answer)
- Sorted array at each bucket
- Binary tree at each bucket
Correct answer: Linked list at each bucket
Chaining stores all keys that hash to the same bucket in a linked list attached to that bucket.
Question 3: What is the average-case time complexity for searching in a balanced binary search tree (BST)?
- O(1)
- O(n)
- O(log n) (Correct answer)
- O(n log n)
Correct answer: O(log n)
A balanced BST halves the search space at each level, yielding O(log n) average-case search time.
Question 4: Which graph representation uses a 2D matrix to indicate edges between vertices?
- Adjacency list
- Adjacency matrix (Correct answer)
- Edge table
- Incidence matrix
Correct answer: Adjacency matrix
An adjacency matrix uses an n×n boolean (or weighted) matrix where entry [i][j] indicates an edge from vertex i to vertex j.
Question 5: A priority queue dequeues elements based on:
- Insertion order
- Alphabetical order
- Assigned priority value (Correct answer)
- Random selection
Correct answer: Assigned priority value
A priority queue always removes the element with the highest (or lowest) priority value, regardless of insertion order.
Question 6: Which property of a binary heap ensures the parent node's key is always greater than or equal to its children's keys?
- Min-heap property
- Max-heap property (Correct answer)
- BST property
- Balanced property
Correct answer: Max-heap property
The max-heap property states that every parent node has a key ≥ its children, placing the maximum at the root.
CCP CCP Data Structures & Abstract Data Types 2
In a binary tree, a node with no children is called a: