Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Bridge to Computer Science Program — Spring Extended 2020

Third Midterm Exam

1.   (3 pts) If we’re storing a queue of integers using a vector (not a list) you may store items in such a way that the front of the queue is not necessarily at the zero position.  If using  this technique, what would be the Big-Theta runtime of the clear function?

a.    Theta(1)

b.   Theta(N)

c.    Theta(N* log(N) )

d.   Theta(N^2)

2.   (4 pts) What datatype (not value) will be printed when the following code runs (or error if you feel there is an error):

class Thing {

public:

Thing(int newval=42) : {x = newval; }

int x;

};

int main() {

Thing* one;

cout << *(one.x) << endl;

}

3.   (4 pts) Given the following definition of a tree node (Parent-Child-Sibling form):

class TreeNode {

public:

int data;

TreeNode* child;

TreeNode* sibling;

};

 

Provide the code (just a single line) to print (cout) the value in the node labelled 6 above given a pointer (called root) which points to the node labelled 1 above.

4. (5 pts) When overloading the input operator, we take a parameter of istream by reference, but can pass a variable of type ifstream by reference.  What does this tell you about the    istream and ifstream classes?

5.   (6 pts) Given the tree listed below.  Print the post-order traversal.

 

6.   (3 pts) Given that an ifstream object has been used to read the entire file and is pointing to, but has not yet read, the EOF marker.  What will be the result of calling .eof() on this object?

a.   true

b.   false

c.   undefined

d.   it depends on the compiler

.

7.   (5 pts) When trying to sort a data set, which of the following data structures might be useful?

a.   A double ended queue

b.   A Singularly linked list

c.   A Stack

d.   A Binary SearchTree

8.   (25 pts) In cryptography, a substitution cypher is a simple way to obfuscate a message. However, most substitution cyphers can be broken by counting the number of               occurrences of all letters and realizing that “A” and “E” are the most common letters in the English language.

Write a program to ask the user for an input filename and output (cout) the frequency of  the letters in the file.  You should not be concerned with non-alphabetic letters (such as   numbers, whitespace or punctuation).  Only letters A-Z should be considered and, for our purposes, an uppercase and lowercase letter should be counted the same (i.e. “aaaAAA” is a count of 6 a’s).  You do not need to worry about sorting or formatting the output.

9.   (10 pts) Given a series of integers stored inside of a queue (you do not have access to the private section of the queue), describe, in English, how you would determine the             minimum (not front) integer in the queue.  In your answer, list the big-theta runtime of   your algorithm.

10. ( 10 pts) Assuming a Binary Search Tree node as described below, write a recursive          function (not a member of the class) which, given the root node of the tree, will return the number of null child pointers (left or right) in the entire tree.

class BSTNode {

public:

int data;

BST* left;

BST* right;

BST* parent;

//MORE CODE HERE (not provided)

};

11. (25 pts) We will be designing a system to keep track of gifts and their value.  To do this, we will need you to design a few classes.

First, we will need a class called “Gift.”  The Gift class will store a string describing the  gift (i.e. “Car,” “Book” or “Computer”) and a double which is the value of the gift stored in the private section.  The class should provide a constructor which requires the string to be set, and allows, but does not require, the double to be set (default of zero).  It should   also have accessor functions and a mutator for the double (the string cannot be changed).

Design an output operator for the Gift class which will print “Gift: “followed by the string followed by “: $” and the double.  (I.e. “Gift: Car: $23000”)

Next, we will need two classes, one will be RealGift which derives from the Gift class  and has a break” function.  If a gift is broken, its value is, obviously, decreased in half (its the thought that counts).  Please implement the break function which should take no parameters and return void.

The third class will be a MoneyGift class which derives from Gift and has a constructor for the value of the MoneyGift.  The string for a MoneyGift object will always be         “Money,” the value MUST be provided to the constructor.