CS311 Midterm Paper

CS 311 Data Structures and Algorithms, Fall 2020

Midterm Exam

Due 2 pm Friday, October 9, 2020

Name:

The exam is worth 120 points. 7 pages (including this cover page), 8 problems.

Instructions

Answer all of the problems on the following pages.

This exam is to be done individually. You may reference an class materials, books, your own notes, or anything on the web, but not other people.

Turn in a PDF on UAF Blackboard, under “Midterm Exam” for this class. The PDF should have your name on the first page. It should be turned in by 2 pm Friday, October 9, 2020.

1. [15 pts total] Order of Useful Operations. In each part, indicate the order of the given operation, first using Θ, and then, based on this, in words (e.g., “exponential time”). Assume that a good algorithm is used—within the constraints given. Use n to denote the number of items in the list that the algorithm is given as input. The model of computation is our usual one. 1a. [3 pts] Printing the last item in an array whose size is known.

Θ:

In Words:

1b. [3 pts] Printing the last item in a Linked List whose size is known.

Θ:

In Words:

1c. [3 pts] Finding an item with a given value in a sorted array.

Θ:

In Words:

1d. [3 pts] Sorting a Linked List.

Θ:

In Words:

1e. [3 pts] Sorting an array with Insertion Sort.

Θ:

In Words:

2. [5 pts] Iterators & Ranges. Vector src has size 8. It contains, in order, the values 0, 10, 20, 30, 40, 50, 60, 70. The following function call copies certain items in src to vector dest. List the values of the items of src that are copied.

std::copy(begin(src)+2, begin(src)+5, begin(dest));

3. [12 pts total] Overloaded Operators. For each of the following operators, indicate whether we should declare it as a member or a global function and how each of the parameter(s) should be passed (by value, etc.). If you wish, you may answer each part by giving a prototype. 3a. [4 pts] operator+=

3b. [4 pts] Binary operator+

3c. [4 pts] operator<< (stream output)

4. [8 pts total] Ownership & Releasing. Give 2 examples of resources that can be owned, along with what it means to release each one. An example is given.

Example resource: An open file What it means to release the example resource: Close the file

Resource #1: · What it means to release resource #1: · Resource #2: · What it means to release resource #2: