⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: 'Decompress current Excalidraw file'. For more info check in plugin settings under 'Saving'
Excalidraw Data¶
Text Elements¶
Questions and Mark Scheme
a) What is the difference between Min-Heap and Max-Heap
Answer:
Min-Heap the root node must be less than or equal to its children (1 Mark)
Whereas Max-Heap the root node must be greater than or equal to all of its children (1 Mark)
b) Explain what is meant by a binary tree
A binary tree is a data structure in which each node has at most two children, which are referred to as the left child, and right child.
c) Create an Adjacent Matrix for the following graph:
^zjRfMia9
For each correct row (1 marks) ^tyeBcTgo
01100 ^8TvOFO02
10011 ^eAOvY5fb
10010 ^VprleikN
01100 ^NsBT08uP
01000 ^wvmaaJqF
d) Using Breadth First Search (BFS), draw a tree that visualises travel from Stockholm to
London.
Use alphabetical order when drawing your tree structure and provide the final
DONE list. You do not need to provide the Frontier list. ^aZspaIGL
e) What is the purpose of sorting algorithms? Provide two examples of available sorting
algorithms?
The purpose of sorting algorithms is to arrange a collection of data or elements in a specific
order, typically in ascending or descending order, according to some criteria. (2 marks for
any sensible and correct answer)
Bubble Sort, Quick Sort (1 mark for any correct example)
^PSCJF4tz
Embedded Files¶
85f678cd35c80365ec0b3a8c69ef14acb44a9c05: Vertices and Edge Exam Question.png
a662fe55056d512e1a9aa6b0afeea69edc9da801: Binary Tree Exam Answer.png
%%
Drawing¶
N4KAkARALgngDgUwgLgAQQQDwMYEMA2AlgCYBOuA7hADTgQBuCpAzoQPYB2KqATLZMzYBXUtiRoIACyhQ4zZAHoFAc0JRJQgEYA6bGwC2CgF7N6hbEcK4OCtptbErHALRY8RMpWdx8Q1TdIEfARcZgRmBShcZQUebQBGAAYEmjoghH0EDihmbgBtcDBQMBKIEm4IIwArACUAMwBZKwBOVJLIWEQKqCwoNtLMbmcAZgBWeO0eAHYp0ameADZh+IAO
MeaAFn5SmCGNxNHtZubZg9Wp5pW17cgKEnVueOHE5u0Fi8SZ+I2VjeHZm5SBCEZTSbjPRKA6zKYLcSGFARQUhsADWCAAwmx8GxSBUAMTxBCEwn9SCaXDYFHKZFCDjETHY3ESJHWZhwXCBbKkiB1Qj4fAAZVgsIkgg83OYSNRCAA6vdJNw+AiIJLkWihTARegxeVATTQRxwrk0PFAWx2dg1LsTYl4e0INThHAAJLEY2oPIAXUBdXImVd3A4Qn5gMI
dKwFVwiW5NLphuY7qDIeVYQQxEeoxWlxWU32W2VjBY7C4aBW8VGgMLrE4ADlOGJHs8LuNvitQ8wACLpHrptB1AhhQGaYR0gCiwUy2UTwfwgKEcGIuB7j1zowWzQWCxWCw2PHz9qIHBRgZngOxlLT3H7+EHyp6mD6EgAikJwlBi8xUNZiKgGhyUagArYJIGQIAAOhwEG4AAlKgMqSEuqCEJ+6gIKgjh1HUTBZGIqCaAgUAUAgWS/mGzgABIhHAX50
r+uCYBRVEQQAghwzBEaQyAQU0LiUbg1GoagyJsFAqAcGwxBofoQiSnhaHBAmqDqNYqA4qgCAAI5CAQSlsEhOSoMBfJkCRAAU8R0aQKLQRB8HYaEdEMXxAkgUJbAiWJElSTJon4ag1IhD0pBKQhHCqcFmnafgulfvyql1Ppn5GfgJlheZlnWRBEGaLBo6YD4uBhqgFAIaJyGoJk1i+TAX54WGHI1UixEsXVHANUpgRoeVuDoUuPWqkI2BQCIXVhSV
5iSOpFKTeJkmoAhn6IfobCyYRenJal1DFZIE1foEQkIFhpCBD+UB6Q5gnBHUokbVt35CSC0iGTtKXaFlHDYLB6KBEuaEqcxxBVBSWSiX+SKEJgqB1GpgnQ/ybB3Bwyj+eQcCSFxXB6pQAAqvQVC+b4fjRP5/lZgHAaB70wXBpVIShrkYUdOFofhhHEWFPGMfxxOOVzcAsWxHEY5zzkhWhwmibN3myX5Cn0ypamRTpZ2Jc9xmcqg6Wk5lHB2T9n5/
k5VFi25HlSxVPlySjgVMCFCsRVpyvnXFbAJWoSUvalmsWdrNmQRwOWoHlBVFSViHlZV2R4TVPWaPVpCNZ1LVx21CcdcRdO1YuUSoANQ0jUhY07cBU0l+bC1fqJy2rRQ62e5yW3jSXHLi4dTAnTFF2uVdN2e3dtGkI9vfGW9/ufag302zRqAA0DYhR2Dg+Q9DwWw1i2KI8j1L8ejEHctD2QCoQRjiLwdqlAfUAAGK4PofLWqgFZ3r0zFEMoJboD33
KFu+7ivyCH9oDmm5HobIhVDSkADGgJMs5lQ4hBPVfAuMHz41fJKIm91tbkxApkKmsF4Lh3pmhRm2EPoswIkREiItjaYPonzAW7EmDCzIqLQSEtPJzWkjLeSRo7ZhUVo7aKKt3ZqxShrLW/4/Z6xCAbOhrDXLsPNlw3yaEAq/VXqFcK6lBGdxdm7AyG1xE+0ke9QOwd8DgO2oQiqIQo6aBjq1dqTVwIcGYo4tOzjM49Wzv1JEg1hr7VDsXSaIQy5e
Xmg5JaK1RJrVEZtbau0W4HSOh3FWXceHXTif3H8g9QTD1eu9cek9frT1nsDBeS4l5Qxhq5OGG8wxb1RrvTGypcBCDOjUcIx9T5+IQGeMMCBKJD0eJMUYhQAC+2xiilHKBIFY2N6AAHkr6LMSDwbknRT7QDxoCQYNoFjaFzDwUYPBnjblGBsXMpplQP2cPEVYRwZjjAWPEXMywdyAjuMQB4aA1xHHiMcFYPBmhJHLAsY5gIQLDLQBC1pSMtTn0RGq
DEWIcT4mJESJAQ4KRUljPSVFTJ0AsjYuyTkfQfR8kFMKLZOp0yAlVNKOU3yFQwvpVKdU1KKi0pjMIA0RpHhmgtFaR4tpASOnnK6d0XofR+gQFAsSp5lRhkkns9AuB4g8tpMQeM05kz2lTL2VA7xXk7m+IihgTBqwf3ueaqsxY6xkO4Jc9cJwLltiVZ2bsl4+wDj6cqYcWrxygSnCePVpR5zZ29agV5Gw1wbneO8UYzR+lHlDbAg8bALyGuvLee09
5HzoESDa6MWMKDIILRAItSQS3KkvkfE+ipzWXxvnffAD8n55pfm/QBX9KxMF/gQf+79ujAMBKAqIAzIGGpgWaXJiDy0VCrbabkbSOldIbWgXpKbBnAjySM45EyplKsNRgZiiz6AAE1Rh1E0Bs+AWz83clVUkV49zjnHLWMsYFGx9w7CGGsR5sx4gvLecB39tx5TcBOQkC4Jwrkup4ACyFu6wQwo7aUaECK2XIoZGiiQBJMUkmxZScVdJcOEugOQE
lLcuQUv5BqLUKosS6hTOy2UkHWWseRQxmlzG6XKn1JIHVAq4FCtgCK814qXRunyN6Wtsr5UzqVeGVVEBcDrL1CObV/LoGKv1cRQ15x4g8FtFMK4faiycEeEkCzVqHUNhtLMF5u4Tnti7MEZcPqbx+vtAGscE4Qa6vTeGhcv1DOrnXJuKYibk3KkPMeXTYbIDnjRNm31gJH0SGrfcmMOM8ZZdtDln0nAoD1tPiZ4r2QW33ygxlrtACKi9oLP28wg7
u0jrgCAkr4CmCKb06UeB/gCALoK1Wld7S2CdNYBujqr5t1DL3SaUZh7CjTMgLM9AAA1OApBgiEBRDWO9XRmQ7OVM+xIByjknLOQsC5VzAS3J+IB55Mb3n7AWJ8jjj8DkgsBcC0Fa5YX2ihYt3g6HICYdPuahlaJyPosI1i/1OLSP4sZN0KjbIaPktrZSnjXK+MSjY0yn5vBsPSjx6KAnmm/BCZ09GwVFJhU2kkzSaTUq5P2l9LfOV07+vrZU5GYY
mq4x06U/pqN5YpjVsWFuWzxZrO2stfa+sp8njrlGMMYYLylT2mQu5giUac0+dKH54gQbJw5DTXOULnno0RfjdF2YsWDxhgSwqpLEAUuG/S8/FBo2ki5bLfl9A2Wa2c5K2VxtlXr63xq78urD4h09sOtj+0P9Wv4CTx1rrYDJ19Y94N+dweICh/G2u6bPTSBzbiwMhbqHo3LZKJM1bx6Kg1mYAAIWxokFYQgAAKR2H2nftOdjY2ggV7guN8YzwwNg
goe0Mcs4+Thz+aD3n98xbsfeVF8knfzfuXH+0WwH4OgTQrB1CeFUOyew4JfDjF3JyQkbxXD5kGPSUg33rjzllPxQ3/Y8yoqP/hTtqFTgJryrTgmCJvaOaIzuJszmKqzpKrJjKtzvnsFvziqpGBsMLtplAYlhgSqAZo8M0NMCZlcK5s1pZtau8HLrWCrhJi8CsD3r8G5l6mlt5kOFpuboFlbsqBGmFiuLGpFluKsBsNci7qmgQWeJmqlleD7p2n7o
WsWoHiNsodWvvBHt0lHrWiVtVm2rVr7lAFnhIE1mni1n/O1syKOsqOOj1lOnwTAXOm1EgsXkumHhhhNlNtoZulXsbslrXihgWhMAek3kerriehQPQPoLgLgAAFIaRXyD7dDD4DAipj7/DvqJCa7HC3bDDur2gPyIbaBrJ7hrBAprhrBJrgYQC74spGoTC3aAq/DZHDAmbLDIbn5A4YZX5wj/6v7oAEYP7Ea4paYDGUasgf60Y470Y/6gF/5caMpf
Y66lAw4IAgFMYLH2iCbCYmgM6WjwHRqirKhSbIFoDSryZoG84e7KoRgSC4CjC4G7Hu6EEGqPCxp/CXKrCK7UEK50EcD2aq4XZbhTBtELDmp67sHyGcH+rcEBYhrSH8E24S725RYxYppu5i6lBe4cG5qlCZbKG2geGQDkBB5KGVrVrEk8haEzYVa6FVax4GHx5GEmGfwp7fwWFtYNbWGdZjrdZ57XGEGF4uFqEUlEll6TbrqV7V6SE7rn4hFjJhEt
4RHdAwAIAd7YDYzKBsDJEnYoK7IkErBHDZGJpS5r7DCH4L5oDOCZhvBmYa5mblhVHxqfaAFoAQhvAAqOlz7iHvadGg7dEQ69FoDQ5sbjFDGYqP7I4v535v6TFY5f6zGai8ZbGrFE7LHAFzGbEsbbEQHPESEDZiYPzVqIFOhnEegc4XwKaCmhgC73ELBPGi585EES6jAnJkGbg/FWrvE1F2r0GOomhApArzB5hsEebe4wm+ZwnBqW6In2gCG24xpx
oJqbDfAYmOHYmyETl4kdDF5XyKzTSGQ4iBBDRuQUDewVT/jMDQSqF7kHklx6DHQICnnIjnnpQxFWTXmaGHw+FnzR76HtoJ7GFWFsnXQcmkADqZ4gVAK8m2H8kQLoGzoIIil3kRSHmPknmiSvkXkfkohflQheFSncBbo16Gh17BGN5gDN4lBrZlAnoLDoibYwBdjEByjkQd4IAAAahAdy2AUw2A8QcRup6AhAMRygiOI+QwzwcQzBSamulyYwFyVp
qAdyxRSaQGxmIKow2RzupQdR4I7w2gWuvwSwVwfwJmKxkAIO9ewGUw2gJyhWzQGuxmp+kOfRixt+aOcZ1GZKUZz+YxsZRK7+CZdGVKyZ+OqZSKSxbppOHl6xWZ3K1OfK+B9OomcBxZxx9opxMm5xlZkAXO/oNZymWB9xUwjZKVWJAgxBpYLls+7y/xjY2+5h1BgJjVUuSwa4NRkJ45uJ/hEApuPBCJLx1uka4WwhG4UuM+BR2JruG5yWW5vVbKS4
MkFQiAdIDSiZPOFQKw167wKw2AxAYw2AzBWuowz5iQmgwwuA+164h03wFImgP6uAzQ2ABwEo7gp8BQ7QYABZJQ8QCIeVEA2AyInWBBK2NFreEgGkT4F6cRAA4iiEYAAPqSAABacNCwzgqN5EcRHeiy8QNQQuGW96FQol0QElaR1pxldpJmuRZYzwryylAKyQLBFpvw5Ye4G4ulEGMV4Kv1Z+oO8w/NblIZ/RgVExPln+IxKO4xxKmOvloVGxiVcV
xO9RllKobGStYBuZNO+Z+xTORxLOZZOVFZqBhVc1ZQdZaqrQ1OIuFVzZbxaAxwTwUunVDVaAc+/xrVJoYGwJs+0162nqPV0JO5/V05FuQWI1ghJoqJoJzQxl65c5m5WaIdfVkoy17oEAa1jgSMm18qamm4PAWEbZBwCwxA4wPARIz1sRCwmgiQuAWEIQt1xA2AzQi4zBGq9KH1+QCIP1NwP1ANY6INaa4NRQkNaqqNmOzocNAAMsJdsvqWdlJW2W
8HJcsD8MIYhsMMpdFpMMwWsJPtMGvuMK6STlmBMP8JsG2WuDuBdurdZcEZlT0TCNfnFeGRikRkjv5VqrLcFQrTMWFYxsrfqumTFerWsVrZFRADsXTvzbAQcRlUbRKibRcZztWRbbcaprgMxOVZHSmNVdGhaesEsE1aUH2R/JsOreQ97d9psJcjterd1QbotbCYGvCbOabUiaNUIcuR8DmOrfFhbTianUBRUMQLBAAKqsBIyoAd4/TMqoBXyEAsCi
QCghCiCTSmQd5XwCjQRbSeDnk9SeLKSiRmDMBRTIThAdS4CMDRS+gGCARnSUiSBYj6C6QQQz2cDECcDaCoAQRSN/T4Boy4CswZ7hSSTBQlQkQGMNKoAwDCCrydS5x+L5z7T3Q7ZsBmBzSwyIIQQdiLI1ijioBECSi+MXrCDoR6TiSSwGYxQZNZNoSCRXzIjZCEC2wlNQDaC3nkniOoBSOxNyMhAKNKMqOATqMlxaM6N6PoSkm1TGO0xmMWNhAoTk
C2NQzIhuNCiyEuP4BuNnQeNeM+N+McABOxTBOhPuDhO2xRNhQxMyPxMiDpxoR5wBJ/S0T1MkCNO1K5McD5OFPFPISdOoDlNCCVOeQ1Nph1PIgNMmzNMlZtPBQdNdPR6R4wpNp6GMmAUsnQVmFkOclQXclEo2H2h2ECkW3CnDbF69P9MyODO4DDPKOyRqMcgTPaO6P6OzNGNJMmOoCLMECWMrM2NBDrMONbPOOuPuMcCeN0hHP+NhBnMIQXM6Q4gR
PbTROkmxMPOJMZwvMFzpPQufMmy8guF5MFNFNIvAsVPePgtiS1MqwfPZOuRwutPtOAvIutKEUV7EV+HzZBH7qKlUXhEzInp94CjohxFXwbBQBGDz2PoGlU1Jrj5tFPBOXAYfrb03LcCbAHLiGZi/Aa497fDq36VO1PD2VEMJqzCOn31+tobmoi2oChk4bi0Rmf2+bRkBVeVBXxn/2c7f7hW/45lpnIqq1AFxWQNDskl5mwP62HElknFIEoOA0FVb
VJ2YF3Fqod64MW2O124go8Ds3Abu1HFrlUF2YMEmgXKAprKJBdVB3MMiOsP+Yzns5R2Ln25TBFobgbCkMBFSHDVxYLWPuKEVoID4K0zlSCRwAiBwArRoSuy5w4jvgyMEDamDzqD6DMAAD8qAfeBr2Ttc6kmAt8PgVjCHNjhUFimgwQiHEFDSUE+AaHagkgmHWH702Mrk0HpAsH8rCHggdHKHjH8CGHn4kH50x00If0R5/Iz574nA8UvUOcis7Don
YU/UiAlovI2AEEKrTAW0nQGebahcX4zA88OdyMakkkpnWQ5nVzpAd02Aj5tnKsggmQhk6HTAVgvjpkPAl5n51SpAUEHANUYQbEhA1HbzP4GFsnNEjCpAfsEEHeWgEXgESHW0L45gAEAoSHOF/4AXNENU0Xp5WAJHwQCXLS2xeW5JYHNM1iUHMHcHCn/HyHyMqHwnLH2HuH+HjThHJX+gpHn45H9AlHITNHzX9HLhTHInbH/sHHaEXHPH8HCU43gn
U3HXmcaSEnSMUnegMnQ0xYCnPiWi6QEdxn6nz5hAWnOnpAET+n8AhnNURUoQZnsTln4QL3Mjun9nX4jnKrsTLnBgaEwNagnnuA3nvnuFn4K8QXIXWQrAKX90RXokrIHE5XSXmgKX2XEF6XQgmXqXEFuXZMK8BXR5T5xXxH/XZX7035pWv5dJ4eDJraWLIHrJnu7JFmkFrPZ0sFJL8FvWRVThyFlL1X4HdXnHDXvHy3SHsTbX6HHXOHeHmThrsSfX
A3CnFHfIo3zz0vSMDHa3rH7H4v3HjXfHOvrXQncvmHG34nVG4ltUu3wQ+38nCHR3ynL7Z3ucGnl35g13t3Sk937gRnT31n61n3wUVnH3FnN3enP3Tn/3ekrnQPHng8YPmsEPV5AXMPuccP4XNHiPx5MXKPTAaPyXNHWPUAOPeP5fhPAExP1ghXBf5PpXYH1PBF5ev5JFsp5F/rEy4AHOamcAcAQov03A0y0AOCWyb8YI2wDAbTFAHeHbP9LbmEK/
dQ/QQNIgZKzoPQ+gQozbXbEArbFNG/T52Q2/GQC/39ZG4tctUxqekA2Am/IM5/+gSjSZQD2tD/T/Z/O/e/0VJOKxE/lv1/6a0Eqn/IAc/x341Bp2KVAshAJ/4ZBFkRZCTDP0f6n8oAL/fcozzjyPxUB3/DATvywG09aS58eAQQIyDlpWeuLMgS/2H4QVmIx0BGCBHpYbkaBO/UcHSAYGvlmBJ6DkK+XX5oDgBGQLgQjGxgk0JAeKdfqZ2RD8hOK4
IeOm8APbrgywmYXcKQV/Qqhga68C9EMFNQlEe88wUgjtVBJjAZ+RgdyPoFH4FgCAr4OEOPguSRZR6bAjINAK1TPFoGWmdftSBICos/yhQB0IPGIBCgEAoNXAf4O8HEAGgXkDgVrxYalAIhAxWih3ixAnpSAygckD50Zq8AshiGKYFtGSCjAbygITpMoGDAcgKgaQjIackhC8BngW0aofkPso3knBggkGH/zRBIC5ObEVgSu06ThhB4udNALRSyCx
DvWMpUoNgCIChDO+pQNqJkDGF9VhAUAQ8NKQQBOC7AVQWTswAFBtQ4AUQySDEIi5xCIc+3RgNjHcj4ArBeacQdqHSBO8KuEwnyAYDEHHYAOGaFOl5lDr2Nd+dwrocB2xKhBjCpwhAOcKxAj0m84AaijyD5DhBR+4yEAOMiAA
%%