MTH4300 Home
# MTH 4300: Final Practice 8

**Problem** 1.
**Problem** 2.
**Problem** 3. The nodes of the standard binary search tree (not balanced binary search tree) are declared in the following way:
**Problem** 4. The expansion of the number \(x\) in base
**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
**Problem** 7.

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";

**(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){ // ??? // }

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, 31What 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; }

`3`

is \(x=\overline{12010}_3\). What is the decimal representation of \(x\)?
`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; }

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