DATA STRUCTURES AND ALGORITHMS IN
CPLUSPLUS FINAL PAPER TESTED
QUESTIONS WITH VERIFIED ANSWERS
COMPLETE STUDY SHEET
●● Tree
Answer: A nonlinear structure
●● Binary tree with ordering property
Answer: A binary tree with ordering property is called a binary search
tree. All keys in the left sub tree are less than the key in the root. All the
keys in the right sub tree are greater than the key in the root.
●● Tree traversal
Answer: Preorder Traversal, Inorder Traversal, and post order traversal.
●● Post Order traversal
Answer: Refers to the processing of the root being postponed until last
in a non-empty tree
In other words, the work at a node is performed after (post) it's children
Steps include 1. Process the nodes in the left sub tree with a recursive
call.
Step 2. Process the nodes in the right sub tree with a recursive call.
,Step 3. Process the root
●● Preorder traversal
Answer: Refers to when the root is processed; It is processed prior to its
two sub trees. In other words, a preorder traversal processes a node
before (pre) it's children. So a preorder traversal has the following steps
for a non-empty tree
Process the root
Process the nodes in the left sub tree with a recursive call.
Process the nodes in the right sub tree with a recursive call.
●● Inorder traversal
Answer: Process the nodes in the left sub tree with a recursive call
Process the root
Process the nodes in the right sub tree with a recursive call
●● Stacks
Answer: Sometimes known as last in first out LIFO.
●● Init
Answer: Creates two Node objects
One called head and the other tail.
, ●● The method size() available for different containers does the
following
Answer: It returns the number of elements stored in the present container
●● Which one of the following is true?
Answer: Using the "top" method for a stack class displays the last entry
added to the stack without removing it.
●● Given an expression like
(2 + 3) * (5 + 1) How does
The calculator program from our lecture notes operate
Answer: By encountering a right parenthesis , the entries on the numbers
stack are popped and combined using the operation on the stack
●● Which of the following is not a good application of the stack data
structure?
Answer: Handling documents to be printed
●● Which of the following is true regarding recursion
Answer: A serial search has O(N)Big-O
●● Which of the following is true of AVL trees
CPLUSPLUS FINAL PAPER TESTED
QUESTIONS WITH VERIFIED ANSWERS
COMPLETE STUDY SHEET
●● Tree
Answer: A nonlinear structure
●● Binary tree with ordering property
Answer: A binary tree with ordering property is called a binary search
tree. All keys in the left sub tree are less than the key in the root. All the
keys in the right sub tree are greater than the key in the root.
●● Tree traversal
Answer: Preorder Traversal, Inorder Traversal, and post order traversal.
●● Post Order traversal
Answer: Refers to the processing of the root being postponed until last
in a non-empty tree
In other words, the work at a node is performed after (post) it's children
Steps include 1. Process the nodes in the left sub tree with a recursive
call.
Step 2. Process the nodes in the right sub tree with a recursive call.
,Step 3. Process the root
●● Preorder traversal
Answer: Refers to when the root is processed; It is processed prior to its
two sub trees. In other words, a preorder traversal processes a node
before (pre) it's children. So a preorder traversal has the following steps
for a non-empty tree
Process the root
Process the nodes in the left sub tree with a recursive call.
Process the nodes in the right sub tree with a recursive call.
●● Inorder traversal
Answer: Process the nodes in the left sub tree with a recursive call
Process the root
Process the nodes in the right sub tree with a recursive call
●● Stacks
Answer: Sometimes known as last in first out LIFO.
●● Init
Answer: Creates two Node objects
One called head and the other tail.
, ●● The method size() available for different containers does the
following
Answer: It returns the number of elements stored in the present container
●● Which one of the following is true?
Answer: Using the "top" method for a stack class displays the last entry
added to the stack without removing it.
●● Given an expression like
(2 + 3) * (5 + 1) How does
The calculator program from our lecture notes operate
Answer: By encountering a right parenthesis , the entries on the numbers
stack are popped and combined using the operation on the stack
●● Which of the following is not a good application of the stack data
structure?
Answer: Handling documents to be printed
●● Which of the following is true regarding recursion
Answer: A serial search has O(N)Big-O
●● Which of the following is true of AVL trees
