DATA STRUCTURES PRACTICE EXAM
QUESTIONS AND ANSWERS
A C++ class can have more than one constructor - Correct Answers -true
In a preorder traversal of a binary tree, for each node, first the node is visited, then the
left tree subtree is visited, then the right subtree is visited - Correct Answers -true
The general case in a recursive function is the case for which the solution is obtained
directly - Correct Answers -false
The elements at the top of the stack have been in the stack the longest - Correct
Answers -false
A linked list in which the last node points to the first node is called a circular linked list -
Correct Answers -true
Every call to a recursive function requires the system to allocate memory for the local
variables and formal parameters - Correct Answers -true
A doubly linked list is a linked list in which every node has a next pointer and a previous
pointer - Correct Answers –true
A depth first search is similar to traversing a binary tree level by level - Correct Answers
-false
The height of a heap is log(n^2) - Correct Answers -false
In an array, item insertion (especially if the array is sorted) and item deletion can be
very time consuming, especially if the list size is very large - Correct Answers -true
The worst case behavior of quicksort is __________ - Correct Answers -O(n^2)
In the analysis of algorithms, the key comparisons refer to comparing the key of the
search item with the position of an item in the list - Correct Answers -false
You have analyzed a function and determined its runtime is characterized by E^n,
subscript i=1, i
what is the Big Oh for the analyzed code? - Correct Answers -O(n^2)
, What is the Big Oh best associated with the following code?
void donald(int n, int x, int y)
{
for (int i = 0; i < n; ++i)
{
if (x < y)
{
for (int j = 0; j < n + n; ++j)
cout << "j= " << j << endl;
} else
cout << "i= " << i << endl;
}
} - Correct Answers -O(n^2)
A data structure in which the elements are added and removed from one end only is
known as a__________ - Correct Answers -stack
The sequential search is also called a _______________ search - Correct Answers -
linear
Sequential and binary search algorithms are called _________ search algorithms -
Correct Answers -comparison-based
A hash table has which two major components? - Correct Answers -"bucket" array and
hash function
In quicksort, all the sorting work is done in _____________ the list - Correct Answers -
partitioning
In heapsort, after we convert the array into a heap, the ______________ phase begins -
Correct Answers -sorting
Problem: Inheritance
Given there exists a C++ class named Person (ie class Person {...}; is declared in file:
Person.h) Write the code to declare a class named Student that is derived from class
Person. Include the appropriate header file. Use the public specifier. You do NOT need
to have a "using namespace" line. - Correct Answers -#include "Person.h"
class Student: public Person
{
}
Problem: Templates
QUESTIONS AND ANSWERS
A C++ class can have more than one constructor - Correct Answers -true
In a preorder traversal of a binary tree, for each node, first the node is visited, then the
left tree subtree is visited, then the right subtree is visited - Correct Answers -true
The general case in a recursive function is the case for which the solution is obtained
directly - Correct Answers -false
The elements at the top of the stack have been in the stack the longest - Correct
Answers -false
A linked list in which the last node points to the first node is called a circular linked list -
Correct Answers -true
Every call to a recursive function requires the system to allocate memory for the local
variables and formal parameters - Correct Answers -true
A doubly linked list is a linked list in which every node has a next pointer and a previous
pointer - Correct Answers –true
A depth first search is similar to traversing a binary tree level by level - Correct Answers
-false
The height of a heap is log(n^2) - Correct Answers -false
In an array, item insertion (especially if the array is sorted) and item deletion can be
very time consuming, especially if the list size is very large - Correct Answers -true
The worst case behavior of quicksort is __________ - Correct Answers -O(n^2)
In the analysis of algorithms, the key comparisons refer to comparing the key of the
search item with the position of an item in the list - Correct Answers -false
You have analyzed a function and determined its runtime is characterized by E^n,
subscript i=1, i
what is the Big Oh for the analyzed code? - Correct Answers -O(n^2)
, What is the Big Oh best associated with the following code?
void donald(int n, int x, int y)
{
for (int i = 0; i < n; ++i)
{
if (x < y)
{
for (int j = 0; j < n + n; ++j)
cout << "j= " << j << endl;
} else
cout << "i= " << i << endl;
}
} - Correct Answers -O(n^2)
A data structure in which the elements are added and removed from one end only is
known as a__________ - Correct Answers -stack
The sequential search is also called a _______________ search - Correct Answers -
linear
Sequential and binary search algorithms are called _________ search algorithms -
Correct Answers -comparison-based
A hash table has which two major components? - Correct Answers -"bucket" array and
hash function
In quicksort, all the sorting work is done in _____________ the list - Correct Answers -
partitioning
In heapsort, after we convert the array into a heap, the ______________ phase begins -
Correct Answers -sorting
Problem: Inheritance
Given there exists a C++ class named Person (ie class Person {...}; is declared in file:
Person.h) Write the code to declare a class named Student that is derived from class
Person. Include the appropriate header file. Use the public specifier. You do NOT need
to have a "using namespace" line. - Correct Answers -#include "Person.h"
class Student: public Person
{
}
Problem: Templates
