Exam 1 from 6:55pm to 8:45pm
CSCI-1200 Data Structures Test 1 — Practice Problems Note: This packet contains selected practice problems from Test 1 from three previous years. Your test will contain approximately one third to one half as many problems (totalling ∼100 pts). Problems may be extensions to specifc homework assignments used that year. 1 Image Doubler [ /15] Write a function named doubler that will double the dimensions (both width & height) of an ASCII art “image”. Your function should take 2 arguments, named input and output, which are STL vectors of STL strings. An example is shown on the right. .@...@. @#@.@#@ @##@##@ @#####@ .@###@. ..@#@.. ...@... → ..@@......@@.. ..@@......@@.. @@##@@..@@##@@ @@##@@..@@##@@ @@####@@####@@ @@####@@####@@ @@##########@@ @@##########@@ ..@@######@@.. ..@@######@@.. ....@@##@@.... ....@@##@@.... ......@@...... ......@@...... sample solution: 12 line(s) of code What assumptions did you make about the data in input? What error checking should be done with the input variable before calling your function? Write 1-2 well-written and concise sentences. 1 2 Image Rotator [ /20] Now let’s complete the fragment of code below to perform a 90◦ clockwise rotation of an ASCII art image. The input will again be an STL vector of STL strings. But this time, our output will be a two-dimensional dynamically allocated array, as shown in the diagram on the right. ABCD EFGH IJKL → p A B C D E F G H I J K L // NOTE: we can assume input has been initialized with an interesting image int rows = ; int cols = ; p; // dynamically allocate the structure and rotate the input sample solution: 7 line(s) of code // print the contents of p to the screen to help with debugging for (int i = 0; i < rows;="" i++)="" {="" for="" (int="" j="0;" j="">< cols;="" j++)="" {="" std::cout="">< ;="" }="" std::cout="">< std::endl;="" }="" what="" is="" an="" alternate,="" equivalent="" expression="" for="" the="" previous="" box?="" hint:="" use="" pointer="" arithmetic.="" 2="" 3="" searching="" for="" substrings="" [="" 27]="" let’s="" write="" a="" program="" to="" find="" all="" words="" containing="" a="" specific="" substring="" and="" print="" those="" words="" ordered="" by="" word="" length.="" words="" of="" the="" same="" length="" will="" be="" in="" reverse="" alphabetical="" order.="" on="" this="" page="" you’ll="" write="" two="" helper="" functions.="" read="" both="" pages="" of="" this="" problem="" before="" beginning="" your="" implementation.="" first,="" complete="" the="" definition="" of="" the="" contains="" helper="" function.="" please="" write="" this="" “from="" scratch”.="" even="" if="" you="" know="" how="" to="" use="" stl’s="" substr="" function="" or="" the="" c="" char*="" strstr="" function,="" don’t="" use="" them.="" bool="" contains(="" ,="" )="" {="" sample="" solution:="" 13="" line(s)="" of="" code="" next,="" write="" another="" helper="" function:="" sample="" solution:="" 4="" line(s)="" of="" code="" 3="" the="" program="" should="" expect="" 2="" command="" line="" arguments:="" the="" filename="" for="" a="" dictionary="" containing="" lots="" of="" words="" and="" the="" target="" substring.="" for="" example,="" we="" might="" call="" this="" program:="" ./search_for_substring.out="" dictionary.txt="" con="" resulting="" in="" the="" output="" shown="" on="" the="" right.="" note="" that="" for="" a="" full="" english="" dictionary="" there="" are="" over="" one="" thousand="" words="" containing="" the="" string="" “con”.="" complete="" the="" program="" below,="" using="" the="" helper="" functions="" you="" defined="" on="" the="" previous="" page.="" icon="" bacon="" second="" convoy="" convex="" economy="" coconut="" abscond="" uncontrolled="" inconsistent="" int="" main(int="" argc,="" char*="" argv[])="" {="" if="" (="" )="" {="" std::cerr="">< "wrong="" number="" of="" arguments"="">< std::endl;="" exit(1);="" }="" if="" (="" )="" {="" std::cerr="">< "cannot="" open="" file"="">< std::endl;="" exit(1);="" }="" sample="" solution:="" 9="" line(s)="" of="" code="" print="" the="" words="" for="" (int="" i="0;" i="">< matches.size();="" i++)="" {="" std::cout="">< matches[i]="">< std::endl;="" }="" }="" 4="" 4="" classy="" winners="" [="" 20]="" write="" the="" two="" header="" only="" classes="" (they="" don’t="" require="" a="" .cpp="" implementation="" file)="" used="" by="" the="" fragment="" of="" code="" on="" the="" right.="" you="" may="" omit="" #include="" and="" other="" pre-processor="" directives="" for="" your="" classes.="" this="" example="" code="" will="" print="" the="" following="" message="" to="" the="" screen:="" the="" high="" jump="" winner="" is="" mariya="" winner="" hj("high="" jump");="" hj.add(finisher("alessia",1.93));="" hj.add(finisher("mariya",2.01));="" hj.add(finisher("mirela",1.89));="" hj.add(finisher("morgan",1.93));="" hj.add(finisher("vashti",1.93));="" hj.add(finisher("yulia",1.89));="" hj.print();="" sample="" solution:="" 9="" line(s)="" of="" code="" sample="" solution:="" 9="" line(s)="" of="" code="" 5="" 5="" ben,="" clean="" up="" your="" mess!="" [="" 15]="" ben="" bitdiddle="" left="" some="" messy="" code="" behind="" at="" the="" end="" of="" his="" summer="" internship="" (he="" probably="" won’t="" be="" getting="" a="" return="" offer="" for="" next="" summer).="" the="" memory="" diagram="" for="" a="" key="" piece="" of="" the="" project="" (which="" is="" used="" many="" times,="" in="" many="" places)="" is="" shown="" on="" the="" right.="" first,="" figure="" out="" the="" types="" for="" each="" variable.="" complete="" this="" fragment="" of="" code="" to="" declare="" the="" 4="" variables:="" heap="" d="" c="" b="" a="" 42="" stack="" a;="" b;="" c;="" d;="" we="" skip="" the="" code="" where="" ben="" dynamically-allocates="" and="" initializes="" the="" memory="" to="" make="" the="" picture="" above.="" finally,="" write="" a="" fragment="" of="" code="" to="" clean="" up="" the="" dynamically-allocated="" memory="" to="" ensure="" we="" don’t="" have="" any="" memory="" leaks.="" use="" at="" least="" 3="" different="" variables.="" sample="" solution:="" line(s)="" of="" code="" what="" might="" happen="" to="" clients="" if="" they="" use="" this="" software="" without="" the="" cleanup="" code="" above?="" write="" 1-2="" well-="" written="" and="" concise="" sentences.="" 6="" 6="" my="" dog="" ate="" my="" budget="" [="" 42]="" alyssa="" p.="" hacker="" is="" helping="" her="" friend="" ben="" bitdiddle="" manage="" expenses="" so="" he="" can="" survive="" on="" a="" meager="" graduate="" ta="" stipend.="" important:="" read="" through="" all="" 4="" pages="" of="" this="" problem="" before="" beginning="" your="" implementation.="" here’s="" an="" example="" main.cpp="" showing="" how="" ben="" will="" record="" and="" manage="" his="" expenses:="" #include="" "budget.h"="" int="" main()="" {="" budget="" my_budget;="" my_budget.addexpense("home",expense("water",20));="" my_budget.addexpense("food",expense("groceries",100));="" my_budget.addexpense("home",expense("rent",900));="" my_budget.addexpense("other",expense("movie="" tickets",14));="" my_budget.addexpense("home",expense("electricity",93));="" my_budget.addexpense("food",expense("pizza",7));="" my_budget.print();="" }="" and="" here’s="" the="" nicely="" formatted="" output="" that="" will="" be="" printed="" when="" the="" program="" is="" run:="" note="" how="" the="" categories="" are="" alphabetized="" and="" the="" costs="" are="" sorted.="" category:="" food="" $="" 107="" groceries="" $="" 100="" pizza="" $="" 7="" category:="" home="" $="" 1013="" rent="" $="" 900="" electricity="" $="" 93="" water="" $="" 20="" category:="" other="" $="" 14="" movie="" tickets="" $="" 14="" total="" $="" 1134="" before="" she="" had="" to="" leave,="" alyssa="" wrote="" out="" the="" whole="" program="" on="" the="" whiteboard.="" after="" she="" left,="" ben’s="" overly="" friendly="" (and="" very="" fluffy)="" dog,="" muffit,="" erased="" a="" bunch="" of="" the="" code.="" help="" ben="" by="" filling="" in="" the="" blanks.="" 6.1="" expense="" class="" declaration="" (expense.h)="" [="" 8]="" sample="" solution:="" 11="" line(s)="" of="" code="" 7="" 6.2="" expense="" class="" implementation="" (expense.cpp)="" [="" 2]="" #include="" "expense.h"="" void="" expense::print()="" const="" {="" std::cout="">< "="" "="">< std::left="">< std::setw(18)="">< name="">< "$"="">< std::right="">< std::setw(5)="">< cost="">< std::endl;="" }="" bycost(="" )="" {="" return="" (a.getcost()="">b.getCost()) || (a.getCost()==b.getCost() && a.getName()Fred: 'I just ate lunch with @Fred at Bella's and it was delicious.' Fred->Sally: 'Mmmm... food... good! @Sally @Joe' Fred->Joe: 'Mmmm... food... good! @Sally @Joe' Joe->Fred: 'Hey @Fred why didn't you invite me?' Fred->Sally: '@Sally next time let's call Joe!' void notify(const std::string &sender, const std::string& receiver, const std::string &message) { // we use substr to remove the '@' symbol from the receiver's name string std::cout < std::right="">< std::setw(6)="">< sender="">< "-="">" < std::left="">< std::setw(8)="">< receiver.substr(1,receiver.size()-1)+":"="">< "'"="">< message="">< "'"="">< std::endl; } int main() { std::ifstream istr("tworder_input.txt"); // note: skip error checking for this problem sample solution: 17 line(s) of code } 13 10 searching for symbols in ascii art [ / 21 ] in this problem we will search a large ascii art canvas for matches std::endl;="" }="" int="" main()="" {="" std::ifstream="" istr("tworder_input.txt");="" note:="" skip="" error="" checking="" for="" this="" problem="" sample="" solution:="" 17="" line(s)="" of="" code="" }="" 13="" 10="" searching="" for="" symbols="" in="" ascii="" art="" [="" 21="" ]="" in="" this="" problem="" we="" will="" search="" a="" large="" ascii="" art="" canvas="" for="">