Examination II
Data Structures using C++, spring 2014
1. (4 pts)In C++, the arrow -> is called the member selection operator.
1). What is the other way to write the expression p->m?
2). In the expression p->m, p is (select the correct one)
a). a variable b). an object c). a pointer variable d). a member of an object
3). In the expression p->m, m is (select the correct one)
a). a variable b). an object c). a pointer variable d). a member of an object
4). In the expression p->m, what is the relationship between p and m?
2. (2 pts)What problem may dereferencing a null pointer cause?
3. (2 pts)What is the only RULE (not syntax) that a template function needs to follow?
4. (1 pt)What is the syntax for declaring your template prefix including type parameters when your template function or class has two or more template type parameters?
5. (2 pts)A regular class can only take fixed type of data while a class template depends on underlying data types. What extra work do you need to do when you implement the functions of a class template in a separate file (out of the definition file)?
6. (1 pt)What is the syntax for instantiating an object of a class template?
7. (2 pts)What is an iterator? What is the reason for having an iterator for each container class in the STL?
8. (2 pts)What are the four major parts that help us to use an iterator of the container classes in STL?
9. (2 pts)Each STL container class has a standard member function begin. What parameter(s) does this function take? What does this function return?
10. (2 pts)Each STL container class has a standard function end. What parameter(s) does this function need? What does this function return?
11. (4 pts)Write a section of code that accomplish the following tasks:
1). Instantiate an empty set object that may hold strings.
2). Insert each word of the following sentence into the object.
C++ is hard
3). Use an iterator to traverse the set and print out the words to the screen in the order given in 2).
12. (4 pts)The list class in STL uses a doubly linked list structure with bidirectional iterator (it has operators ++ and - - defined). Write a section of code to accomplish the following tasks:
1). declare a list type variable and use the default constructor to create a list object that may hold strings.
2). Use one of the list functions push_back(const item_T& item) or push_front(const T& item) to insert each word of the following sentence into the object from right to left such that the words in the list stay in the original order of the sentence.
C++ is hard
3). Use an iterator to traverse the list and print out the words to the screen in the original order
4). Use the same iterator used in 3) to traverse the list and print out the words in reversed order to the screen.
13. (3 pts)What is a linked list? What are the advantages and disadvantages of dynamic arrays and linked lists?
14. (3 pts)Inspect the following node class.
template<class T>
class node
{
public:
node(const T& init_data=T(), node* init_link=NULL)
{data=init_data; link=init_link;}
void set_data(const T& new_data){data=new_data;}
void set_link(node* new_link){link=new_link;}
T& get_data(){return data;}
const T& get_data() const{return data;}
node* get_link(){return link;}
const node* get_link() const{return link;}
private: T data; node* link;
}
Use this class to write a section of code that builds up the following linked list, use a loop to print this list out and then insert 6 between 5.5 and -2.5 in your list.
head
15.(20 pts)A queue is a container that follows the “first in first out” policy: data can only be pushed into a queue through one end called rear and popped out from another end called front. In this part, design and implement a template queue class by using the linked list technique (use the node class in problem #14, skip the comments).
Your queue class must have at least the following functions.
1). A size function that returns the number of elements in the queue
2). A front function that returns a reference to the front element of the queue
3). An empty function that returns true if the queue is empty and false otherwise
4). A push function that pushes a given element onto the rear of the queue
5). A pop function that removes the front element of the queue
6). A clear function that empties the queue
7). A destructor
8). Assignment operator =
9). constructor
16. (20 pts)A function for non-negative integers r and n is defined by
a. Write a recursive function that calculates the value of this function for any non-negative integers r and n.
b. Write a dynamic function that calculates the value of this function for any non-negative integers r and n.
