联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> Java编程Java编程

日期:2021-03-11 11:12

CSCI-1200 Data Structures

Test 2 — Practice Problems

Note: This packet contains selected practice problems from Test 2 from three previous years.

Your test will contain approximately one third to one half as many problems (totalling ~100 pts).

1 Linked Tube Repair [ / 33 ]

Alyssa P. Hacker is working on a modified linked list that is both twodimensional

and circular. A small sample with height=3 and circumference=4

is shown below. Each templated Node has pointers to its 4 neighbors. The

top and bottom edges of the tube structure have NULL pointers. But the left

and right edges wrap around, like a circularly linked list. This cylindrical tube

structure may have any number of nodes for its height and its circumference.

template <class T>

class Node {

public:

// REPRESENTATION

T value;

Node<T> *up;

Node<T> *down;

Node<T> *left;

Node<T> *right;

}; 1.1 Tube repair Diagram [ / 4 ]

First Alyssa wants to tackle the challenge of repairing a hole in the structure. Assume a single Node is

missing from the structure, and we have a pointer n to the Node immediately to the left of the hole. Modify

the diagram below to show all of the necessary edits for a call to repair(n,7);

n

up:

1.2 Thinking about Tube repair Complexity [ / 3 ]

The repair function should have constant running time in most cases. Describe an example structure with

a single missing Node that can be repaired, but not in constant time. Write 2-3 concise and well-written

sentences. You may want to complete the implementation on the next page before answering.

1

1.3 Tube repair Implementation [ / 13 ]

Now, implement repair, which takes 2 arguments: a pointer to the Node immediately to the left of the

hole and the value to be stored in the hole. You may assume a single Node is missing from the structure.

sample solution: 26 line(s) of code

2

1.4 Non-Iterative destroy tube Implementation [ / 13 ]

Now write destroy_tube (and any necessary helper functions) to clean up the heap memory associated

with this structure. The function should take a single argument, a pointer to any Node in the structure.

You may assume the structure has no holes or other errors. You cannot use a for or while loop.

sample solution: 17 line(s) of code

3

2 Rehashing the Vec Assignment Operator [ / 15 ]

Complete the Vec assignment operator implementation below, while minimizing wasted heap memory.

Assume the allocator is most efficient when all heap allocations are powers of two (1, 2, 4, 8, 16, etc.)

1 template <class T>

2 Vec<T>& Vec<T>::operator=(const Vec<T>& v) {

3 if (this != &v) {

4 delete ;

5 m_size = ;

6 m_alloc = ;

7 m_data = ;

8 for (int i = 0; i < ; ++i) {

9 m_data[i] = ;

10 }

11 }

12 return *this;

13 }

Add code below to perform a simple test of the assignment operator:

Vec<double> v; v.push_back(3.14159); v.push_back(6.02); v.push_back(2.71828);

Is line 12 necessary? Continue your testing code above with a test that would break if line 12 was omitted.

What is the purpose of line 3? Write code for a test that would break if lines 3 and 10 were omitted.

4

3 Essay Revision: Embellishment [ / 14 ]

Write a function embellish that modifies its single argument, sentence (an STL list of STL strings),

adding the word “very” in front of “pretty” and adding “with a wet nose” after “grey puppy”. For

example:

the pretty kitty sat next to a grey puppy in a pretty garden

Should become:

the very pretty kitty sat next to a grey puppy with a wet nose in a very pretty garden

sample solution: 20 line(s) of code

If there are w words in the input sentence, what is the worst case Big O Notation for this function? If we

switched each STL list to STL vector in the above function, what is the Big O Notation?

STL list: STL vector:

5

4 Essay Revision: Redundant Phrases [ / 15 ]

Complete redundant, which takes a sentence and 2 phrases and replaces all occurrences of the first phrase

with the second, shorter phrase. For example “pouring down rain” is replaced with “pouring rain”:

it is pouring down rain so take an umbrella → it is pouring rain so take an umbrella

Or we can just eliminate the word “that” (the replacement phrase is empty):

I knew that there would be late nights when I decided that CS was the career for me

→ I knew there would be late nights when I decided CS was the career for me

typedef std::list<std::string> words;

void redundant( sentence, phrase, replace) {

sample solution: 19 line(s) of code

}

6

5 Don’t Ignore Compilation Warnings! [ / 15 ]

Write a useful but buggy segment of code (or function) that will compile with no errors but will produce

the indicated compilation warning. Put a star next to the line of code that will trigger the warning.

Write a concise and well-written sentence describing the intended vs. actual (buggy) behavior of the code.

warning: comparison of integers of different signs: 'int' and 'unsigned int'

warning: control reaches / may reach end of non-void function

warning: variable is uninitialized when used here / in this function

warning: returning reference to local temporary object / reference to stack memory

associated with a local variable returned

7

warning: expression result unused / expression has no effect

warning: unused variable / unused parameter

6 Cyber Insecurity [ / 5 ]

Ben Bitdiddle wrote the following code fragment to manage his personal information.

1 std::ifstream istr("my_information.txt");

2 std::string s;

3 std::vector<std::string> data;

4 while (istr >> s) { data.push_back(s); }

5 std::vector<std::string>::iterator password = data.begin()+4;

6 data.push_back("credit_card:");

7 data.push_back("1234-5678-8765-4321");

8 data[4] = "qwerty";

9 std::cout << "my password is: " << *password << std::endl;

my information.txt

name: Ben Bitdiddle

password: pa$$word

SSN: 123-45-6789

Write “True” in the box next to each true statement. Leave the boxes next to the false statements empty.

Lines 2 & 3 will produce an “uninitialized read” error when run under gdb or lldb.

Line 5 is not a valid way to initialize an iterator.

Ben’s credit card information is not saved back to the file.

This program might behave differently if re-run on this computer or another computer.

A memory debugger might detect an “unaddressable access of freed memory” error on Line 9.

If we move lines 6 & 7 after line 9, this code fragment will run without memory errors.

This code contains memory leaks that can be detected by Dr. Memory or Valgrind.

These password choices disqualify Ben from any job in computer security.

8

7 Boxy Storage Solutions [ / 25 ]

Eva Lu Ator is working on her capstone project to manage physical storage facilities. She’s mapped out

the overall design and started implementation of the two classes.

class Box {

public:

Box(int w, int d, int h) :

width(w), depth(d), height(h) {}

int width;

int depth;

int height;

};

B

width

depth

height

A

C

Storage storage(4,3,2);

assert (storage.available_space() == 24);

Box *a = new Box(2,2,2);

assert (storage.add(a,0,0,0));

Box *b = new Box(3,2,1);

assert (!storage.add(b,2,0,0));

delete b;

Box *b_rotated = new Box(2,3,1);

assert (storage.add(b_rotated,2,0,0));

Box *c = new Box(1,1,1);

assert (storage.add(c,2,0,1));

assert (storage.available_space() == 9);

class Storage {

public:

Storage(int w, int d, int h);

// FILL IN FOR PART 1

bool add(Box *b, int w, int d, int h);

int available_space();

private:

void remove(Box *b, int w, int d, int h);

Box ****data;

int width;

int depth;

int height;

};

bool Storage::add (Box *b, int w, int d, int h) {

for (int i = w; i < w+b->width; i++) {

if (i >= width) return false;

for (int j = d; j < d+b->depth; j++) {

if (j >= depth) return false;

for (int k = h; k < h+b->height; k++) {

if (k >= height) return false;

if (data[i][j][k] != NULL) return false;

}

}

}

for (int i = w; i < w+b->width; i++) {

for (int j = d; j < d+b->depth; j++) {

for (int k = h; k < h+b->height; k++) {

data[i][j][k] = b;

}

}

}

return true;

}

9

7.1 Missing functions from Storage Class Declaration [ / 5 ]

Her friend Ben Bitdiddle doesn’t remember much from Data Structures, but he reminds her that classes

with dynamically-allocated memory need a few key functions. Fill in the missing prototypes for PART 1.

7.2 Storage Destructor [ / 20 ]

Eva explains to Ben that the private remove member function will be useful in implementing the destructor.

First write the remove member function:

sample solution: 10 line(s) of code

Now write the Storage class destructor:

sample solution: 14 line(s) of code

10

8 Transpose Linked Grid [ / 27 ]

Louis B. Reasoner is working on a new member function for our Homework 5 Linked Grid named transpose.

This function should mirror or flip the elements along the diagonal. Here’s a sample grid with integer data

and how it prints before and after a call to transpose:

grid.print();

std::cout << std::endl;

grid.transpose();

grid.print();

1 2 3 4

8 7 6 5

9 10 11 12

1 8 9

2 7 10

3 6 11

4 5 12

template <class T>

class Node {

public:

// REPRESENTATION

T value;

Node<T> *up;

Node<T> *down;

Node<T> *left;

Node<T> *right;

}; 8.1 Diagram [ / 7 ]

First neatly modify the diagram of this smaller grid below to show all of the necessary edits that must be

performed by a call to transpose().

:upper_left

up:

down:

right:

value:

:left

up:

down:

right:

value:

:left

up:

down:

right:

value:

:left

up:

down:

right:

value:

:left

up:

down:

right:

value:

:left

up:

down:

right:

value:

:left

height:

upper_right:

width:

:lower_left lower_left:

Grid<int>

NULL

NULL NULL NULL

NULL

NULL

NULL NULL NULL

NULL

4 5 6

1 2 3

3 2

8.2 Complexity Analysis [ / 5 ]

What is the Big ’O’ Notation for the running time of the transpose() member function? Assume the grid

width is w and the height is h. Write 1-2 concise and well-written sentences justifying your answer. You

probably want to complete the implementation on the next page before answering.

11

8.3 Implementation [ / 15 ]

Louis has suggested that we first implement a helper non-member function named swap, which will make

the implementation of transpose more concise.

sample solution: 5 line(s) of code

Now implement transpose, as it would appear outside of the Grid class declaration.

sample solution: 16 line(s) of code

12

9 Organizing Words [ / 30 ]

Alyssa P. Hacker is working on a program to clean up a dataset of words. The task is to write a function

named organize_words that takes in an STL vector of STL lists of words (STL strings). The function

should organize the words into groups by word length, and ensure that the words are sorted within each

group. Many or most of the words will already be in the right place. That is, they will already be in the

slot of the vector that matches the length of the word. And the neighboring words in each slot/list will

already be mostly alphabetized.

For example, given the data shown on the left, your implementation should move the four misplaced words

to produce the data shown on the right.

0

1 diamond

2

3 gem malachite

4 jade opal rock ruby

5 geode pearl talc stone topaz

6 garnet quartz gypsum

7 amethyst azurite emerald

8 fluorite sapphire

9

0

1

2

3 gem

4 jade opal rock ruby talc

5 geode pearl stone topaz

6 garnet gypsum quartz

7 azurite diamond emerald

8 amethyst fluorite sapphire

9 malachite

To make the problem a little more “fun”, you are NOT ALLOWED to use:

? the STL vector subscript/indexing operator, [ ], or .at(),

? the STL sort function, or

? any of the push or pop functions on vector or list.

You may assume that the initial vector has at least as many slots as the longest word in the structure.

9.1 Complexity Analysis - Big ’O’ Notation [ / 6 ]

Once you’ve finished your implementation on the next pages, analyze the running time of your solution.

Assume there are w total words in the whole structure, v slots in the vector, a maximum of m words

per list, and x words are misplaced and need to be moved. Write 2-3 concise and well-written sentences

justifying your answer.

13

9.2 Helper Function Implementation [ / 12 ]

Alyssa suggests writing a helper function named place that will place a word in the correct location in the

structure. Work within the provided framework below. Do not add any additional for or while loops.

void place( ) {

sample solution: 2 line(s) of code

while ( ) {

sample solution: 3 line(s) of code

while ( ) {

sample solution: 5 line(s) of code

}

sample solution: 5 line(s) of code

}

}

14

9.3 Organize Implementation [ / 12 ]

And now write the organize function, which calls the place function. Again, work within the provided

framework below and do not add any additional for or while loops.

void organize_words( ) {

sample solution: 2 line(s) of code

while ( ) {

sample solution: 2 line(s) of code

while ( ) {

sample solution: 8 line(s) of code

}

sample solution: 2 line(s) of code

}

}

15

10 Merge-Spiration: Recursive Interval Computation [ / 15 ]

Ben Bitdiddle was inspired by the recursive merge sort example

from Data Structures lecture and proposes it as a guide to compute

the smallest interval that contains a collection of floating point

numbers (e.g., the minimum and maximum). Implement Ben’s idea,

a recursive function named compute interval that takes in an STL

vector of floats and returns an Interval object.

For example: 6.2 4.3 10.4 2.5 8.4 1.5 3.7 → [1.5, 10.4]

class Interval {

public:

Interval(float i, float j)

: min(i), max(j) {}

float min;

float max;

};

sample solution: 12 line(s) of code

Without resorting to personal insults, explain in two or three concise and well-written sentences why Ben’s

idea isn’t going to result in significant performance improvements. Be technical.

16

11 How many DS students to change a lightbulb? [ / 38 ]

In this problem you will complete the implementation of two new classes named Bulb and Lamp. We begin

with an example of how these classes are used.

First, we create a new lamp that will hold 3 bulbs and make a note of the manufacturer’s recommended

bulb: a 60 watt bulb with an estimated lifetime of 300 hours from Phillips. Note that initially this lamp

has no bulbs installed. We install one of manufacturer’s recommended bulbs and use the lamp (turn it

“on”) for a total of 50 hours.

Lamp floorlamp(Bulb(60,300,"Phillips"),3);

bool success;

success = floorlamp.install(); assert(success);

floorlamp.On(50);

assert (floorlamp.getTotalWattage() == 60);

Next, we attempt to install 3 bulbs, another of the manufacturer’s recommended bulbs, and then two other

brands of bulbs. The installation of the 3rd bulb made by Sylvania fails because there are no available

sockets slots in the lamp and no bulbs are burnt out and need replacement.

success = floorlamp.install(); assert(success);

success = floorlamp.install(Bulb(40,120,"GE")); assert(success);

success = floorlamp.install(Bulb(120,500,"Sylvania")); assert(!success);

We then use the lamp for another 100 hours. Once the wattage drops (due to a burnt out bulb), we again

try to install the Sylvania bulb and it is successful.

floorlamp.On(100);

assert (floorlamp.getTotalWattage() == 160);

floorlamp.On(50);

assert (floorlamp.getTotalWattage() == 120);

success = floorlamp.install(Bulb(120,500,"Sylvania")); assert(success);

assert (floorlamp.getTotalWattage() == 240);

Finally, we create a duplicate lamp. Note that when we do this, we match the bulbs currently installed in

the original lamp, but the bulbs installed in the new lamp are brand new (and unused).

Lamp another(floorlamp);

assert (floorlamp.getTotalWattage() == another.getTotalWattage());

for (int i = 0; i < 10; i++) {

floorlamp.On(50);

another.On(50);

std::cout << "compare " << floorlamp.getTotalWattage() << " "

<< another.getTotalWattage() << std::endl;

}

Which results in this output:

compare 240 240

compare 240 240

compare 180 240

compare 120 240

compare 120 240

compare 120 240

compare 120 120

compare 120 120

compare 120 120

compare 120 120

11.1 Bulb Class Declaration [ / 14 ]

The Bulb class is missing only one function. You will need to read the rest of the problem to determine what’s

missing. Fill in the missing function – implement the function right here, within the class declaration.

17

class Bulb {

public:

// constructors

Bulb(int w, int l, const std::string &b) :

wattage(w),lifetime(l),hours_used(0),brand(b) {}

sample solution: 2 line(s) of code

// accessors

int getWattage() const { return wattage; }

bool burntOut() const { return hours_used > lifetime; }

const std::string& getBrand() const { return brand; }

// modifier

void On(int h) { hours_used += h; }

private:

// representation

int wattage;

int lifetime;

int hours_used;

std::string brand;

};

11.2 Lamp Class Declaration [ / 14 ]

The Lamp class has a few more missing pieces. Read through the rest of the problem before attempting to fill

this in. Write the prototypes (not the implementation!) for the four missing functions. You will implement

some of these missing functions later. Also, fill in the member variables for the Lamp representation.

Important: You may not use STL vector on this problem.

class Lamp {

public:

// constructors, assignment operator, destructor

sample solution: 4 line(s) of code

18

// accessor

int getTotalWattage() const;

// modifiers

bool install(const Bulb &b = Bulb(0,0,""));

void On(int h);

private:

// representation

sample solution: 3 line(s) of code

};

Lamp Class Implementation

Here’s the implementation of one of the key member functions of the Lamp class.

bool Lamp::install(const Bulb &b) {

// first, let's figure out where to install the bulb

int which = -1;

for (int i = 0; i < max_bulbs; i++) {

// check for an empty socket

if (installed[i] == NULL) {

which = i;

break;

}

// or a socket that contains a burnt out bulb

if (installed[i]->burntOut()) {

which = i;

delete installed[i];

break;

}

}

// return false if we cannot install this bulb

if (which == -1) return false;

if (b.getWattage() == 0) {

// install the manufacturer's recommended bulb type

installed[which] = new Bulb(recommended);

} else {

// install the specified bulb

installed[which] = new Bulb(b);

}

return true;

}

On the last two pages of this problem you will implement three important functions for the Lamp class, as

they would appear outside of the class declaration (in the lamp.cpp file) because their implementations

are > 1 line of code.

19

11.3 Lamp Constructor [ / 9 ]

sample solution: 7 line(s) of code

11.4 Lamp Destructor [ / 5 ]

sample solution: 8 line(s) of code

20

11.5 Lamp Assignment Operator [ / 9 ]

sample solution: 10 line(s) of code

21

12 Singly Linked List Subsequence Sum [ / 18 ]

Write a recursive function named FindSumStart that takes the head Node of a

singly-linked list storing positive numbers. The function should return a pointer

to the Node that begins a subsequence of numbers that ends in the sum of that

subsequence. For example, given this sequence: 5 1 4 2 3 9 6 7 the function

should return a pointer to the Node storing 4, because 4 + 2 + 3 = 9.

template <class T>

class Node {

public:

Node(const T& v)

: value(v),

next(NULL) {}

T value;

Node* next;

};

sample solution: 15 line(s) of code

Assuming the sequence has n numbers, what is the order notation for the running time of your function?

22

13 Reverse Splice [ / 20 ]

Write a function named reverse_splice that takes in 3 arguments: an STL list named data and two

iterators i and j. The function should reverse the order of the data between those iterators. For example,

if data initially stores this sequence: 1 2 3 4 5 6 7 8 9 and i refers to 3 and j refers to 7, then after

the call reverse_splice(data,i,j), data will contain: 1 2 7 6 5 4 3 8 9 , i will refer to element 7,

and j will refer to element 3. Your function should return true if the operation was successful, and false if

the request is invalid. Note: Your function may only use a constant amount of additional memory.

sample solution: 21 line(s) of code

23

14 Doubly Linked Factorization [ / 17 ]

class Node {

public:

Node(int v) :

value(v),

next(NULL),

prev(NULL) {}

int value;

Node* next;

Node* prev;

};

Write a recursive function named Factor that takes in two arguments, pointers to the head and tail Nodes

of a doubly linked list. This function should look for a non-prime number in the linked list structure, break

the Node into two Nodes storing two of its factors, and then return true. If all elements are prime the

function returns false. For example, if we start with a 3 element list containing 35 30 28 and repeatedly

call Factor:

PrintNodes(head);

while (Factor(head,tail)) { PrintNodes(head); }

This is the output:

35 30 28

5 7 30 28

5 7 2 15 28

5 7 2 3 5 28

5 7 2 3 5 2 14

5 7 2 3 5 2 2 7

5 7 2 3 5 2 2 7

You may write a helper function. You do not need to write the PrintNodes function.

24

sample solution: 21 line(s) of code

25


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp