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 EarlProtonWombat32

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  Alice  1. Create an empty stack. 2. FOR each element in the original list: - Push the element onto the stack. 3. Create a new empty list. 4. WHILE the stack is not empty: - Pop an element from the stack and append it to the new list. //The new list now contains the elements of the original list in reverse order.  1. Create an empty stack. 2. FOR each letter in the sequence: - Push the letter onto the stack. 3. Create a new empty list. 4. WHILE the stack is not empty: 1

- Pop a letter from the stack and append it to the new list. 5. IF the new list is equal to the original sequence: - The sequence is a palindrome. 6. ELSE: - The sequence is not a palindrome. b. [3] Exercise 2   It appeared the same value, since the added value is going to the top, therefore is a stack. c. [3] Exercise 3   Attach as right child Poppy to Petunia 2 a. ✓ b. ✓ c. ✓

d. [6] Exercise 4   The tree looks like the English alphabet.  When inserting elements from a sorted list into a tree, the resulting tree will be a balanced binary tree, as long as the sorted list is inserted in a way that preserves the order and ensures that tree remains balanced.  A list can be considered a special kind of tree where each node has only one child (except for the last node, which has no child), and the traversal is unidirectional (from the first node to the last node).  The order that I used was: 1. D as the root 2. B as left child to D 3. A as left child to B 4. C as right child to B 5. F as right child to D 6. E as left child to B 7. G as right child to B 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

 Yes, there can be multiple valid ways to insert elements into a binary tree to achieve a balanced tree, and the specific order of insertion can vary based on the chosen algorithm or approach. e. [3] Exercise 5    It inserts the name at the left child of the original name.  Merge both names into a single node.  Display an error message informing the user that the name is already in the tree and suggesting a different action.  It finds the first node (descending order) containing the duplicate name. 4

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) Push(myStack, name) Push(myStack, 'Harman') WHILE(NOT IsEmtpy(myStack)) Pop(myStack, name) Write name + ", "  Output: 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 + ", "  Output: 1, 5, 5, 5, 8, 7, 2, 5

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 * * *  S,Y,E,U,Q,T,S,A,O,N,I,E 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  This output is possible since the numbers are written in descending order and the numbers from the stack are ordered in ascending order. b. 1 3 5 4 2 c. 1 3 5 2 4 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

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) 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: 7

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. b. [1] How many comparisons are required to search for Debra in this tree? 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. b. [1] How many comparisons are required to search for the value 27 in this tree? Submit the PDF version of the completed worksheet with D2L 8

Related Documents

ECE9065-2023-lab2.pdf

ELEMENTS OF DIFFERENTIATED INSTRUCTION.docx

HW1 - SQL.pdf

Assignment 4 Math.docx

Midterm Programming Languages.docx

ML_A1_Tanmay-merged.pdf

CYB 230 Module Two Lab Worksheet.docx

LDRCB535 Competency 3.pptx

Assignment 03.docx

SCS 100 Module Five Activity.docx

SCS 100 Module Three Activity.docx

SCS 100 Module Four Activity.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