MTH4300 Home

MTH 4300: Final Practice 8

Problem 1.

Assume that x is of type long, that the content of x is 3, and that p is a pointer whose content is the address of x. What does the following code print?

long y=x;
long& z=y;
long* r=&y;
long* q=p;
*q=2;
z=y+7;
*r=y+z;
std::cout<<x+y+z<<"\n";

Problem 2.
  • (a) What is stack? Provide the declaration of the stack node whose elements are of type long. The name of the structure for the node should be SN, the name of the attribute that keeps the content of the node should be cont, and the name of the pointer to the next node should be aNext. Create an implementation of the function pop.
  • (b) The class Sequence is declared in the following way:
    class Sequence{
    public:
       long* a;
       long n;
    };
    The objects of the class are sequences. The attribute n should contain the length of the sequence, and the attribute a should contain the pointer to the beginning of the block of consecutive memory locations of size n. Create an implementation for the function fromStackToSequence that identifies all the elements of the stack that belong to the interval \([50,500]\) and creates a sequence that contains these elements. The function should not delete nor modify any of the elements from the stack. The ordering of the elements in the sequence can be either the same as it was in the stack or the opposite from the ordering in the stack (you can choose whichever is more convenient for you). Your code should replace the text // ??? // below.
    Sequence fromStackToSequence(SN* aTop){
       // ??? //
    }

Problem 3. The nodes of the standard binary search tree (not balanced binary search tree) are declared in the following way:
struct TN{
public:
  long cont;
  TN* aL;
  TN* aR;
};
Assume that aRoot contains the address of the root of the tree which has \(15\) elements inserted in this order:
17, 9, 25, 5, 13, 21, 29, 3, 7, 11, 15, 19, 23, 27, 31
What is the result of the evaluation recursion(aRoot)? (The function recursion is implemented below.)
long recursion(TN* a){
  if(a==nullptr){return 0;}
  long sum=0;
  if(a->cont!=9){sum+=recursion(a->aL);}
  sum+=recursion(a->aR);
  sum+=a->cont;
  return sum;
}

Problem 4. The expansion of the number \(x\) in base 3 is \(x=\overline{12010}_3\). What is the decimal representation of \(x\)?

Problem 5. Assume that storage for real numbers consists of a total of \(12\) bits. One bit is for sign, \(5\) bits are for exponent, and \(6\) bits are for the mantissa. Determine the decimal representation of the number that corresponds to \(110011101101\).

Problem 6. How many times is the letter e printed when the function print_e() is executed? Assume that the program is compiled with the flag -fno-elide-constructors.
 
#include<iostream>
class Tiger{
public:
     Tiger();
     Tiger(const Tiger&);
     Tiger(Tiger&&);
     void operator=(const Tiger&);
     void operator=(Tiger&&);
     ~Tiger();
};
Tiger::Tiger(){
     std::cout<<"ee";
}
Tiger::Tiger(const Tiger& x){
     std::cout<<"eeeee";
}
Tiger::Tiger(Tiger&& x){
     std::cout<<"ee";
}
void Tiger::operator=(const Tiger& x){
     std::cout<<"eee";
}
void Tiger::operator=(Tiger&& x){
    std::cout<<"e";
}
Tiger::~Tiger(){
     std::cout<<"ee";
}
Tiger swim(Tiger & x){
     Tiger y=x;
     y=x;
     return y;
}
int print_e(){
     Tiger x,z; 
     for(int i=0;i<10;++i){
          z=swim(x);
     }
     return 0;
}

Problem 7.

The user input consists of two positive integers \(n\) and \(M\) and two sequences \(x[0]\), \(x[1]\), \(\dots\), \(x[n-1]\) and \(w[0]\), \(w[1]\), \(\dots\), \(w[n-1]\) of positive integers. The numbers \(w[0]\), \(w[1]\), \(\dots\), \(w[n-1]\) are the weights of the items \(0\), \(1\), \(\dots\), \(n-1\). The numbers \(x[0]\), \(x[1]\), \(\dots\), \(x[n-1]\) are the values of the items. The number \(M\) is the maximal weight that can fit in a backpack. However, the backpack must not contain the items whose indices are adjacent integers. In other words, if the item \(i\) is in the backpack, then the items \(i-1\) and \(i+1\) must not be in the backpack. Create the program that calculates the largest value that can fit in the backpack and prints a list of items that need to be selected to achieve this largest value. Your program should have polynomial complexity in \(M\cdot n\) (If your solution involves a recursion, then you should use data structures based on balanced search trees to make the recursion more efficient.)

Example:

Input:
7 12
20 30 30 10 40 50 55 
 1 10  1  1  7  1 11
Output:
Best value that backpack can hold is: 100
Items to take: 5 2 0