### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Midterm 2 Study Guide CSCI-2270

CU

GPA 3.0

### View Full Document

## 153

## 1

1 review

## Popular in Data Structures

## Popular in ComputerScienence

This 9 page Study Guide was uploaded by Elliott Saslow on Monday August 31, 2015. The Study Guide belongs to CSCI-2270 at University of Colorado taught by in Fall 2014. Since its upload, it has received 153 views. For similar materials see Data Structures in ComputerScienence at University of Colorado.

## Reviews for Midterm 2 Study Guide

I love that I can count on (Elliott for top notch notes! Especially around test time...

-*Alisha Koelpin*

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 08/31/15

Midterm 2 review CSCI 2270 1 How does a binary search tree s shape depend on the order of the numbers inserted into it If you have a root with descendants of smaller numbers than the root number the tree shape will be lopsided A A binary search tree s shape is entirely dependant on the order of insertions If you insert into a binary tree in monotonical increasing or decreasing order you will just get a worse linked list think about it see fig 1 2 What parts are similar in the two processes of searching a binary tree and searching a sorted array by binary search What parts are different What depends onluck The time it takes to search in both processes is Ologn time Binary search trees have a hierarchy If it is a lopsided tree it could take longer to search The array is linear so it does not depend on a hierarchy and only has one way to go in searching The order of the numbers depends on luck A Binary search of a sorted array is similar to searching a binary tree in that for a balanced binary search tree the problem size is shrinking by a factor of two at every step Note that this is the best case for a binary search tree as it is possible for the tree to be wildly out of balance In the worst case you end up with a linked list which just gives linear search time If the tree is being populated with random data it is largely luck dependant how well balanced the tree is See figure 1 for an example 3 Given an arbitrary binary tree print it out in preorder inorder and postorder Algorithm 2 Shuf e tzurlr if 1 simple in nitan lfiillmry tm printer rm hide insts erim Timid printin rdarfhmarygsmarchtmn dm nude std tream 13111 E 5111 input litmus printgj i i il nudes left out out fit Meuh ata 2 5111quot andl printgmurwdelr unusa right out I 39ixl l hl l p preorderprint const binarytreenode bintree if bintree is not empty print out data at root preorderprintleft subtree of bintree s root preorderprintright subtree of bintree s root Alignriithm 1 553111111 tznrlrt If 11 simple prmrtlrttr bimer printer i Lucile nstre am I Tmid printpr9nrdarh g saarchgtmgn da Imdn aidquot natreanamp out a std mut iftmdn nut U unda hdata it 5111 iandl lprintgpra rdarr nudaw iil it out printgpra rdarr undaw right out J Egal lhh lfli inorderprint const binarytreenode bintree if bintree is not empty inorderprintleft subtree of bintree s root print out data at root inorderprintright subtree of bintree s root Alguriithm 3 111111 indE If 1 silnplr pm39tm tzr biliary tl p utm atrte Ernie iasm enm 1 1 Timid parintparn rdarhmarg saarchbtmydni m n 5mquot manualk 9111 E std mut a iftmdn 5 printprenrd rinndew l it out I Vprintgpre rdarinode right out um Ct nudn hdata nili 5111 mull it 1quot J postorderprint const binarytreenode bintree if bintree is not empty postorderprintleft subtree of bintree s root postorderprintright subtree of bintree s root print out data at root 4 Given a bunch of numbers in some order insert them into a binary search tree A The rule is simple if whatever number we are going to insert is less than the number of the node we are at go left and repeat Otherwise go right and repeat Stop when you find an empty nodebecause that is where your data should be inserted 5a Given the binary search code and a particular array of sorted numbers tell me the first array slot the search code will check to find 3 in the array 1 3 5 6 8 9 11 14 What s the last array slot a search for the 3 will check THEEweEHTLriiz FNN It will check 6 firstindex 3 H 0 First it will count the numbers of elements in the MEN 2M array then divide by two We will go to that index and if compare it It will find 3 astindex 1 if altey matey Jrirsle else xszg t 243 HFZHmg 5b Repeat the question but look for a number Ir that s not in the array like 10 What will be the 1ng f fwa may last slot checked eleeif ignite 1e ri e 1r 11mg 3 1 1 will be the last number checked look at picture Jr to better understand why gt else mm 3 6 To get the 6 bignumber comparison functions lt gt lt and gt how many must you write and why and what can you do for the other ones instead of writing them all from scratch equivalence less than greater you can create everything else from stemming from these functions eeid htreeiheertliht hey he e leaf iflheye leaf hhe ealue iflleef hleftleh h iheeetlhey leef hleft else leaf hlefthew hede leaf hleft hhegealueke leaf hleft hleftMULL ff ete the left ehild ef the ehild he e te hull leaf left hightNULL ff ete the Eight ehild ef the ehild te hull l l elee iflheyhleef heyeeluel iffleef hright1MULL iheertihey leaf hright else leaf hrighthew he e lehf hright hhegehluehey leef hright hleftNULL ff ete the left ehili f the chili heee te hull leef hright hrighte l ff ete the right ehili ef the ehild hede te hull l l l Insert function for a binary tree 7 What time penalty comes from using the addnode function when copying a list walk through the length of the list every single time that add a node and that on time A It moves the operation from On to On2 The add node function only has access to the head ptr node and so it is forced to wal to the end of the list again and again as we repeatedly call add node In contrast an implementation written specifically for the purpose of copying a list or even stdcopy provided you are smart enough to write your own iterator would be much faster See algorithm 4 for a simple pseudocode example Allguriithm t1 Ef cisut llLiist Mpg l prucs urs LIE39l xtit iPYhesdptr 3 if hesiptr mullptr th return nullptr ll sursur as hssdptr 5 target is usu uuds usulist target i39 wh ls cursur 3E uul1ptr u 3 target is new nude ti tsr gnstErdats as sursurhhdsts 1f cursqu if cur surzrnsxt 11 target 7 tsr gstzrnsxt 13 returns usulist 8 When is a binary search tree most efficient Least efficient Why A binary search tree is most efficient when it is perfectly balanced It is least efficient when its depth is equal to the number of nodes it contains ie it has degenerated into a linked list The point of a binary search tree is to provide for fast lookup and insert It does this by putting its data in a sorted order This order is such that at every step of the insert and search algorithms the problem size is cut in half providing Olog n execution time This is best case for a binary search tree In the worst case the tree has degenerated into a line linked list and you get linear On execution time Advantages Binary Search Tree is fast in insertion and deletion etc when balanced Very efficient and its code is easier than other data structures Stores keys in the nodes in a way that searching insertion and deletion can be done efficiently Implementation is very simple in Binary Search Trees Nodes in tree are dynamic in nature Disadvantages The shape of the binary search tree totally depends on the order of insertions and it can be degenerated When inserting or searching for an element in binary search tree the key of each visited node has to be compared with the key of the element to be inserted or found ie it takes a long time to search an element in a binary search tree The keys in the binary search tree may be long and the run time may increase Alguriithm 5 CH filIHIZtiD which nnil tipiiw nnrlt Henna1th 1211 given mink a giwn factnr WM11 drifmilts in T cunst int DEEIULTFAETUHIE T void binarytreemn1tiply hinarytr gnndn ma a int factor a nernu13rncrnn iftmda nndndata m factor binarygtrngnnltiply nude l it factor binarygtrnmgnnltiplynnda right factor E l hih l ld After a long intermixed sequence of random insertion and deletion the expected height of the tree approaches square root of the number of keys which grows much faster than 39widl lth reenneamp pa rent E h39iFHIHH l 9 Given the code in bintreecpp can you make a function that multiplies every number if pa rent Eta in a binary tree by 7 Emmata m 7I lt Recurswe mult by 7 funct if parent bright nullptr I I I I Go to the print function and where It prints out FEE rent1eft the data the data II if parent2161 nullptr lith reejfa rent bright 10 Given the code in bintreecpp can you make a function that reverses mirror images a binary search tree Go to the print function and replace right with left and left with right Algaliith Binary ScarI311 Mirmr fl pr ul l tutti11111131quotlt39l39lrtLE EuErltmotilej vd tjDde E if arc ude ail L nnl lptr th 3 if dst ude nullptr than 4 datjude at new nude 5 d tJlDdEL d ta at srcmudebdata v Hlnnnninenfnrcinadeeleftjdsmnude right Hlnanninenfnrcinaneerigntj st4node left Algurithm If Hal implnmnntniti n If Binary TM Mirntlr vnid mirrnrtreebinary5archttrn nndn arc hinarytramnndah st ifisrc nest list a 11m binarytmnuda d thdata a arc1dala mirrantrm i rcJlaft gt right i mirrantrmaiarchright det l iti 11 If you had a mirror imaged binary search tree what would you need to do when inserting data into it The smallest item is on the right this time so when the entry is less than the node it puts it to the right and when it is greater it goes to the left A Follow the opposite rules as normal If the default rule is to go left when lt and right otherwise then you need to go left when not lt ie when gt and right otherwise See algorithm 8 12 Why is selfassignment a problem for operator the self operater will clear the big number when assign and so if you self assign it will clear the number before it sets it 13 Why is selfassignment not a problem for the copy constructor passed in by const reference clear the copy then reset it but it cant change it because its passed in by const reference charm left 3H1 14 What is the difference between an charm right EHEmgthil assignment operator and a copy from 5 leftmigfft 39 leftks Pight conStrUCtor ll 39 one is passed by const refere i 319131 Weft Fight Eright C 15 Use poInter arithmetic to write a function to reverse an array Go to the first location in the array and switch with the very last one 0 Temp datai o Datai datacount i o DataCount i temp 16 Why can t we do binary search on a linked list you can only go through the list one by one and you cannot go backward Only points fonNard so you cant start at the end and move backward to the 14 point BUT you can walk to the 14 point from the front in fact because of this you theoretically could do binary search a singly linked list I have attached an explanation It39s aluieiy nnssihte tn malte this wnrft In ten there39s pretty much nnly nne ehange ynu heed tn matte tn the den hty lfinlted list algnnthm tn malte it went The issue with the singly linked list ease is that if ynu have a nninter tn the middle nf the list ynu nan t gn has Itwards tn get hanlt tn the first quarter nf39 the list Heweyer if yen thinit ahnut it yen dnn t need tn start frnm the middle tn tin this Instead ynn can start at the eet nf the list and wallt 2 the first quarter This iessentially the same amnunt nf hefnre rather than gning hanltwarnl n I 4 steps ynu nan start at the frnnt and gn fnrwards n f d steps Hnw sn npnse ynui39ye dnne the rst step and are at gnsitinn h t 4 nr an t 4 In this case ynui39re gning tn hate the same nrnhlemi hefnre ifynn need tn hath up tn pnsitinn n i nr pnsitinn an i h In the that yen need tn get tn nnsitinn n I ynn can start at the frnnt nf the list again and wall fnrward n i steps ahnnt the Eh I ease Here39s the theft if yen still have nninr tn the n I 2 nnint then ynn can start there and wallt fnrwards n i sps whieh will talte yen tn life right sent hfnre generality ins vd nf39 stnring a gninter tn the middIe at the list sre pointers intn tre list nre at the frnnt nf the range where the trainer might he and nne in the middle at the range where the yalne miiht he If ynu need tn adyanee fnrward in the list update tre nninter tn the start nf the range tn he the nninter tn the middle nf the range tl39ten wallit the pninter tn the middle nf the range fnrward hallfway 2 the end at tre rane If ynn heed tn advance hanltwardl in the list Linda the painter tn the middle nf the range tn he the pninter tn the frnnt nf the range tl39ten wallit haifway Ctyerall this has the exact same time an mnlesiiy as the dnnhty l finlted ease we talte n i 2 stage than n f d steps then it t s stens etn which sums up tn Cam tntall steps We aisn nnly malte ilni n tal enmparhnns quotIl39he nniy differente is the extra pninter we need tn tract nt Hnne this hellnst lt FOI39Q16 17 Why is contains for a Iinked istbinary search tree faster than On Can binary tree contains be this fast Binary search tree is sorted so it does not have to check every single item it just has to compare and go left or right depend on the output of the compare function The binary tree is unsorted so you need to check every item I think that a doubly linked list will always be On because you don t have to check every node whereas a binary tree can be this fast if the data was put in fairly randomly BUT if it was entered in like figure1 then you will pretty much have to check every node which is no On 18 Suppose I am adding 2 bignumbers as followsbignumber alice98 bignumber bobo87 alicebobo In the code for operator bignumberamp bignumberoperator const bignumberamp b which number alice or bobo corresponds to b Which number corresponds to this b Bobo emswee nee rePairtcher epeningjeher lesingj if epening 3939VEamp Eleeing 39339 return true else ifEepening 3939 fee eeing 3939 return true me how a else ifEep ening 3939 ee 1105ng 39J39 return true StaCK can be return take5 used to tell if a 139 program has heel reParantheeeeEeleneeeetrlng exp t balanced eteckienarn 5 ferint i Egitenp1engthilgi iftenmi quotIi39 EHpEi 39t39 H ex i 3939 61hr 119 EWEMEEMH If stack 5 empty else iFtEHnti 39Zi39 exnii 393 Jenni 39139 at the end and ifi5emptyl II iArePeir5tep expil never underflowed return felee your are balanced emee inept return 5empty truefelee5 20 Trace out the treecopy function for a particular binary tree Which node is copied first Last ld eeid EST TeepfiTreeHe eeT rent ltlg l if treat HULL 151 13 152 ineertireet element 153 eepytreet bleft 15d eepyireet bright 1555 I 1155 I 155 The Ier mn rueter lime HEB I44 a hinmjr tree engaging the term an en i i rmg tree This is nine Mimi inner ng the em en ieiirmg tree te the new using eiszllmur uletiee lietea tn l 5mm 3 139 ESTeTEETtESTeT etree ld ldl rent HULL 1a EiEE H 143 eepyitreereet if aeeeeeiueu eeew eedee e iiie ieee lad I ldli The very left item is copied first Then the right side The root is copied last 21 Trace out the treecear function for a particular binary tree Which node is cleared first Last treenddeE Clear left clear right clear root if thi5 leftj delete thi5 lett if thie height delete thi5 right if thie ekey delete tmi5 key 22 Be nauseatingly familiar with the copy command binarytreenode treecopyconst binarytreenode rootptr binarytreenode ptr binarytreenode rptr if rootptr nullptr return nullptr else ptr treecopy rootptrgtleft rptr treecopy rootptrgtright binarytreenode newtree new binarytreenode newtreegtdata rootptrgtdata newtreegtleft ptr newtreegtright r ptr return newtree 23 Where is the smallest number in a binary search tree How would you find it The very left branch item If entry is not equal to node check to see if entry is less than the node If it is keep going left If it is not go to the right 24 When I compare 2 bignumbers which digits should I compare first and why start with largest base in the number because that will the easiest way to test inequality

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.