Lab_6_worksheet

docx

School

Langara College *

*We aren’t endorsed by this school

Course

1050

Subject

Computer Science

Date

Feb 20, 2024

Type

docx

Pages

Uploaded by GrandGuineaPig4093

Lab 6: Chapter 8, Abstract Data Types. Lab9_Manual.pdf, Abstract Data Types. [60 marks] In all of the problems, you must show your work to qualify for the mark. Type your answer in this worksheet after each question. Submit the PDF version of completed worksheet with D2L. Learning Objectives At the end of this lab, you should be able to gain a deeper understanding for stacks, queues, and trees. Lab Readings 1. Chapter 8 – Abstract Data Types 2. Lab 9 Abstract Data Types (Lab9_Manual.pdf) Lab Questions 1. Lab 9 Abstract Data Type (Lab9_Manual.pdf) a. [3] Exercise 1 Carl, Bob, Alice WHILE(more data) Read value Push(myStack, value) WHILE(NOT IsEmpty(myStack)) Pop(myStack, value) Write value WHILE(more data) Read value Push(myStack, value) WHILE(NOT IsEmpty(myStack)) Pop(myStack, output) Write output IF initial value== output Print “yes it ia a palindrome” ELSE Print “Not a palindrome ” 1

b. [3] Exercise 2 The Value that appears is different from the one added which means that the mystery object is a queue as it is following the FIFO(First In, First Out) concept. c. [3] Exercise 3 Attach as a Right child Poppy to Petunia d. [6] Exercise 4 The tree looks very unsymmetrical. Inserting elements from a sorted list into a tree will result in an unsymmetrical tree. This list can be considered as a special kind of tree (a unsymmetrical one.) 2

ORDER: M,G,T,F,H,S,U. Yes, there are multiple different orders in which a balanced tree can be made as it is determined by the order of how we add the alphabets and also on their alphabetical order. e. [3] Exercise 5 So, when we add a name which is already in the tree, the app add the name to the left of the name which is already present there. The other two methods which the app could have used are: It could add the name as the right child to the same name It could also just add the second same name to the parent node only and represent it as Mark(2) which shows that we have two entries as Mark. Yes, Find still works but it only finds the Mark which appears first in the search. 2. [5] What is the output of the following stack algorithm? Push(myStack, 'Jack') Push(myStack, 'Jose') Push(myStack, 'Ali') Push(myStack, 'Mike') Pop(myStack, name) Write name + ", " Pop(myStack, name) Push(myStack, name) 3

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Push(myStack, name) Push(myStack, 'Harman') WHILE(NOT IsEmtpy(myStack)) Pop(myStack, name) Write name + ", " Mike, Harman, Ali, Ali, Jose, Jack. 3. [5] What is the output of the following stack algorithm? Push(myStack, 2) Push(myStack, 7) Push(myStack, 8) Push(myStack, 5) Push(myStack, 9) Push(myStack, 1) Pop(myStack, item) Write item + ", " Pop(myStack, item) Pop(myStack, item) Write item + ", " Push(myStack, item) Push(myStack, item) WHILE(NOT IsEmtpy(myStack)) Pop(myStack, item) Write item + ", " 1,5,5,5,8,7,2, 4. [4 marks]. A letter means push and an asterisk means pop in the following sequence. Give the sequence of values returned by the pop operations when this sequence of operations is performed on an initially empty LIFO stack. E A S * Y * Q U E * * * S T * * * I O * N * * * SYEUQTSAONIE 4

5. [6 marks, 2 marks each part]. Consider the pseudocode where FlipCoin() returns either “head” or “tail”. set count = 0 while (count < 5) count = count + 1 if (“head” = FlipCoin()) print count + " " else push(myStack, count) while (not IsEmpty(myStack)) pop(myStack, number) Write number + " " Which one of the outputs is possible? Justify your answer a. 5 4 3 2 1 b. 1 3 5 4 2 c. 1 3 5 2 4 6. [5] What is the output of the following queue algorithm? Enque(myQueue, 'Mary') Enque(myQueue, 'Susan') Deque(myQueue, name) Write name + ", " Enque(myQueue, 'Sara') Enque(myQueue, 'Tom') Deque(myQueue, name) 5

Write name + ", " Deque(myQueue, name) Enque(myQueue, 'Chang') Enque(myQueue, name) Enque(myQueue, name) WHILE(NOT IsEmtpy(myQueue)) Deque(myQueue, name) Write name + ", " 7. [5] What is the output of the following queue algorithm? Enque(myQueue, 2) Enque(myQueue, 7) Enque(myQueue, 8) Enque(myQueue, 5) Enque(myQueue, 9) Enque(myQueue, 1) Deque(myQueue, item) Write item + " " Deque(myQueue, item) Deque(myQueue, item) Write item + " " Enque(myQueue, item) WHILE(NOT IsEmtpy(myQueue)) Deque(myQueue, item) Write item + " " 8. Given the following set of names: George Michael Jack Elvis Tara Chris Debra Ann David Sara a. [5] Draw the Binary Search Tree that results from inserting the names in the given order. 6

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

b. [1] How many comparisons are required to search for Debra in this tree? 4 9. Given the following set of numbers: 88 93 24 18 24 99 9 66 27 18 35 85 a. [5] Draw the Binary Search Tree that results from inserting the numbers in the given order. NOT CORECT. b. [1] How many comparisons are required to search for the value 27 in this tree? 4 7

Submit the PDF version of the completed worksheet with D2L 8

Related Documents

4.2.1 Lecture - Start.sql

3.2.1 Lecture SQL - Start.sql

CYB 210 Network Configuration Scavenger Hunt Template.docx

lab_2_worksheet.docx

lab_2_worksheet.doc

lab_13_worksheet.docx

Lab_11_worksheet.docx

INST201 Flashcard Assignment - Week 12.docx

Smahir Abdalgalil-Module 03 - Data Representation.docx

Smahir Abdalgalil-Module 02-Demonstrating Knowledge - Systems Architecture (1).docx

Qualitative Research Review Paper.docx

02-01 Introduction to SAP - SCC V3.0 1909 - Student Web GUI (1).docx

Recommended textbooks for you

Systems Architecture

Computer Science

ISBN:9781305080195

Author:Stephen D. Burd

Publisher:Cengage Learning

C++ for Engineers and Scientists

Computer Science

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Course Technology Ptr

Oracle 12c: SQL

Computer Science

ISBN:9781305251038

Author:Joan Casteel

Publisher:Cengage Learning

Np Ms Office 365/Excel 2016 I Ntermed

Computer Science

ISBN:9781337508841

Author:Carey

Publisher:Cengage

New Perspectives on HTML5, CSS3, and JavaScript

Computer Science

ISBN:9781305503922

Author:Patrick M. Carey

Publisher:Cengage Learning

MIS

Computer Science

ISBN:9781337681919

Author:BIDGOLI

Publisher:Cengage

SEE MORE TEXTBOOKS

Recommended textbooks for you

Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Oracle 12c: SQL
Computer Science
ISBN:9781305251038
Author:Joan Casteel
Publisher:Cengage Learning
Np Ms Office 365/Excel 2016 I Ntermed
Computer Science
ISBN:9781337508841
Author:Carey
Publisher:Cengage
New Perspectives on HTML5, CSS3, and JavaScript
Computer Science
ISBN:9781305503922
Author:Patrick M. Carey
Publisher:Cengage Learning
MIS
Computer Science
ISBN:9781337681919
Author:BIDGOLI
Publisher:Cengage