1. What are the three cornerstones of object oriented programming? Explain each
ID: 3771027 • Letter: 1
Question
1. What are the three cornerstones of object oriented programming? Explain each of them.
2. Complete the codes, which are left as blanks in the following functions according to our discussions in the classes
(a) Recursive binary search
template
int binarySearch( const vector & v,
const T & x, int low, int high )
{
if( low > high )
return ________________________________;
int mid = ________________________________;
if( v[ mid ] < x )
return ________________________________;
else if( x < v[ mid ] )
return ________________________________;
else
return ________________________________;
}
(b) The following items are inserted into a binary search tree: 3, 9, 7, 2, 5, 11, 1, which node is the deepest? Show the BST you construct.
3. Complete the following table by giving the general average running times in big-O notations for the
indicated operations and data structure, where there are n data items for each. (Consider the operations on random data.)
// Your answers:
//print 1:
//print 2 :
//print 3:
//print 4:
Computing Times Insert (Add) Find (Search) Array Binary Search Tree Linked List StackExplanation / Answer
The "three pillars" of OOP are generally taken to be:
Encapsulation
Inheritance
Polymorphism
Encapsulation
In C++ the term encapsulation refers to the placing of both data and operations within a class definition to implement the conceptual notion of an abstract data type (ADT).
Closely related are the notions of abstraction and information hiding:
The term abstraction refers to the process of extracting the "essence" of a real world thing or concept and modeling it with the data (data abstraction) and operations (procedural abstraction) of the ADT. The data portion of this duo is generally placed in the "private" part of the class, while the operations form the public interface to the ADT and are therefore placed in the "public" part of the class definition.
The term information hiding refers to the fact that we prevent a client of the class from having access to the data in the class implementation. The client should not need any such information. We say that we are practicing information hiding by defining our classes in this way. We should be careful, however, not to confuse "inaccessibility" with "invisibility", since (at least in the case of C++) the private (data) part of a class is merely inaccessible, not invisible.
Inheritance
In C++ there are two forms of inheritance, which is also called derivation:
single inheritance, which is the mechanism by which one class (called the derived class) acquires the properties (data and operations) of another class (called the base class)
multiple inheritance, which is the mechanism by which one class acquires the properties of two or more base classes
a base class is one from which others are derived, while a derived class is one defined as an extension of another class.
Other terminology includes child class or subclass for a derived class, and parent class or superclass for the base class.
If there are one or more classes separating the two derivation-related classes in the class hierarchy, we say that the class at the higher level is an ancestor of the class at the lower level, which in turn is a descendant of the class at the higher level. We also say that the class at the lower level inherits indirectly from the one at the higher level. If there are no intermediate classes, the inheritance is direct.
A derived class often overrides one or more of the member functions in the base class, thereby changing the behavior (but not the interface) of that member function. A derived class will often also extend the base class by adding new member functions, with or without overriding base class functions.
Polymorphism
The term polymorphism (from the Greek for "many forms") refers to the ability to use the same name for what may be different actions on objects of different data types. Polymorphism may be achieved (or at least approximated) in several ways:
via function overloading and operator overloading
via function templates
via virtual functions with dynamic binding (i.e. run-time binding)
A member function "found" at run-time (i.e., bound to an object at run-time, or dynamically bound is called a virtual member function (or, more simply, a virtual function). To mark a member function for selection at run-time, its declaration in the header file must be preceded by the keyword virtual. Once a function has been declared virtual, it remains virtual in any and all derived classes, without repetition of the virtual keyword, though it is generally regarded as a best practice to repeat the keyword virtual in the derived classes, for readability.
Answer 2) a)
template
int binarySearch( const vector & v,
const T & x, int low, int high )
{
if( low > high )
return ______return -1__________________________;
int mid = _____(low+high)/2___________________________;
if( v[ mid ] < x )
return ___binarySearch(v,x,mid+1,high)________________________;
else if( x < v[ mid ] )
return binarySearch(v,x,low,mid-1)____________________;
else
return _____mid___________________________;
}
b)
3, 9, 7, 2, 5, 11, 1
3 Level 0
2 9 Level 1
1 7 11 Level 2
5 Level 3
Hence the deepest is 5
Answer 3
Computing Times Insert (Add) Find (Search)
Array O(n) O(n)
Binary Search Tree O(1) O(log(n))
Linked List O(1) O(n)
Stack O(n) O(n)
Answer 4
x1: 1
x2: 4
y1: 1
y2: 5
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.