CSCI 103L – Final Info

Sample Final (Gradescope) Solutions

Q1

1.1) before
1.2) False
1.3) has-a
1.4) shallow
1.5) fals3

Q2 - Runtime and Data Structures

2.1) pop_back on a vector: \(O(1)\)
2.2) push_front on a vector: \(O(n)\)
2.3) pop_back on a singly-linked list without a tail pointer: \(O(n)\)
2.4) pop_back on a doubly-linked list with a tail pointer: \(O(1)\)
2.5) Accessing the i-th element in an array: \(O(1)\)
2.6) If a list is sorted, we can search for an item in at most \(O(log n)\): True

Q3 - Streams and Parsing

Suppose you are given a data file, stream2.in:

 #
8 9 10 abc def 11 12 13
ab

cde fh hij;
42 28 14

Then the following program is run:

./streams2 stream2.in

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>

using namespace std;

int main(int argc, char* argv[]) {
    string s1, s2; char c; int x, cnt1 = 0, cnt2 = 0;
    ifstream ifile(argv[1]);
    ifile >> c;
    cout << c << endl;     // 1st output

    getline(ifile, s1);
    getline(ifile, s1);
    stringstream ssa(s1);
    while(ssa >> x)
      { cnt1++; }
    cout << cnt1 << endl;  // 2nd output

    getline(ifile, s1, ';');
    stringstream ssb(s1);
    while(ssb >> s2)
      { cnt2++; }
    cout << cnt2 << endl;  // 3nd output

    getline(ifile, s1);
    ifile >> s1;
    if(ifile.fail()) 
        { cout << "fail" << endl; } // 4a output
    else 
        { cout << s1 << endl; }     // 4b output

    c = ifile.get();
    c = ifile.get();
    cout << c << endl;          // 5th output
    ifile.close();
    return 0;
}

Show would will be printed on each of the 5 lines of output (Do not show the endl or \n explicitly in your answer). For example, if the program would print abc followed by a newline, then just type in abc to the blank.

Answers

3.1) #
3.2) 3
3.3) 4
3.4) 42
3.5) 2

Q4 - Inheritance and Polymorphism

Below is a program that involved several classes in an inheritance hierarchy with some virtual functions. Predict what will be output on the screen.

You may not use a compiler/editor

#include <string>
#include <iostream>
using namespace std;

class ClassA {
    public:
      ClassA(int value) : totalCounts(value) { }
      virtual ~ClassA() { cout << "~ClassA" << endl; }
      virtual void name() = 0;
      int increment() { return ++totalCounts; }

    protected:
      int totalCounts;

};

class ClassAB : public ClassA {
    public:
      ClassAB() : ClassA(10) { }
      ClassAB(int value) : ClassA(value) { }
      ~ClassAB() { cout << "~ClassAB" << endl;}
      void name() { cout << "ClassAB" << endl; }
      int increment() { return totalCounts + 3; }
      
};

class ClassAC : public ClassA {
    public:
      ClassAC() : ClassA(20) { }
      ClassAC(int value) : ClassA(value) { }
      ~ClassAC() { cout << "~ClassAC" << endl;}
      void name() { cout << "ClassAC" << endl; }
      int increment() { totalCounts += 5; return totalCounts; }
      
};

class ClassACD : public ClassAC {
    public:
      ClassACD() : ClassAC(35) { }
      ~ClassACD() { cout << "~ClassACD" << endl;}
      void name() { cout << "ClassACD" << endl; }
      int increment() { return totalCounts + 4; }
      
    private:
      int totalCounts;
};

int main()
{
    ClassA* arr1[3];
    arr1[0] = new ClassAB(2);
    arr1[1] = new ClassAC(4);
    for(int i = 0; i < 2; i++){
        arr1[i]->name();
        cout << arr1[i]->increment() << endl;
    }

    ClassAC* ptr = new ClassACD;
    ptr->name();
    cout << ptr->increment() << endl;
    cout << ptr->increment() << endl;

    delete ptr;
    return 0;

}

4.1) For the i=0 iteration of the for loop in main(), what will be printed by the call to arr[i]->name()?
- ClassAB
4.2) For the i=0 iteration of the for loop in main(), what will be printed by the cout << arr1[i]->increment() << endl; line?
- 3
4.3) For the i=1 iteration of the for loop in main(), what will be printed by the call to arr[i]->name()?
- ClassAC
4.4) For the i=1 iteration of the for loop in main(), what will be printed by the cout << arr1[i]->increment() << endl; line?
- 5
4.5) What will be printed by the line ptr->name();?
- ClassACD
4.6) What will be printed by the 1st cout << ptr->increment() << endl; line?
- 40
4.7) What will be printed by the 2nd cout << ptr->increment() << endl; line?
- 45
4.8) What else, if anything will be printed by the program?
- None of the above

Q5 - Recursion

Trace the execution of the following program by understanding the recursive functions. Show what it will printed to the screen.

(Do not show the endl or \n explicitly in your answer).

#include <iostream>
using namespace std;

int f1(int x){
    if(x >= 0) { return x; }
    else return f1(-x);
}

int f2(int k){
    if(k == 0){
        return 0;
    }
    else {
        return 1 + f2(k/2);
    }
}

int main()
{
    cout << f1(-3) << endl;
    cout << f2(8) << endl;
    cout << f2(100) << endl;
    return 0;
}

5.1) 1st line of output: 3
5.2) 2nd line of output: 4
5.3) 3rd line of output: 7