Question

INSTRUCTIONS:
1. The Assignment contains 3 questions (20 MARKS Each) with a total of 60 MARKS
2. All questions must be answered electronically (No hand-written submissions)
3. Draw all the required diagrams using a drawing software application/tool e.g. Microsoft
Visio. (No snapshots/screengrabs will be accepted). You can use one of the CASE tools
you use in OOSAD if you wish.
4. Submit a Portable Document Format (PDF) as your final submission. No other file

QUESTION ONE
1. Briefly describe the 3 main operations that can be performed on a stack data structure.
[3 Marks]
2. Which container would best be used in each of the following situations? [4 Marks]
a. You have several phone messages coming in and want to handle them in the order
they were received.
b. You have a phone bill arriving each month and want to be able to look up any
month's bill.
c. You are planning a road trip and have listed several stops along the way but want
to be able to add a new one partway through.
d. You are having a conversation and keep going off on new topics. You want to
keep track of the conversation so that once you finish one topic, you can return to
the previous one—and then when that is done, the one before that, etc.
3. State three applications of the stack data structure [3 Marks]
4. Write a program that uses a queue or stack or both data structures to keep track of the
order of people who arrive to meet with you. You should repeatedly ask for a name, or, if
the user types next, you should print the name of the next person who should be met. An
example of a run of this might be as follows:
format will be accepted.
6. There will be no extension on the due date.
7. The assignment covers data structures and the C++ Standard Template Library (STL)
based on the recommended book (Malik, 2018)
8. This assignment will contribute 10 percent towards the final Continuous Assessment test

QUESTION TWO
1. Write a function called printVector that takes in a vector of integers called v, as a
parameter and then uses an iterator named iter, to print out each element, one per line.
[5 Marks]
2. Suppose you want to read in a bunch of peoples' names and salaries and then print a list
of the people from lowest to highest salary. To read in the information, imagine that you
just prompt users to enter their name and salary on the console repeatedly. Because
people won't have a negative salary, ask the user to indicate that he or she is done by
entering a sentinel value, such as a negative value for the salary.
Write a program that uses a vector from the Standard Template Library (STL) and
Templated sort function found in the Algorithm library to sort the data as pairs. Below is
the sample run of your program:

Enter a person's name and salary

(One name and then one salary per line. )

Enter a negative salary to stop.

Messi 500

Mane 200

Ronaldo 400

Neymar 300

Pogba 100

Mbesuma -2

100 pogba

200 Mane

300 Neymar

400 Ronaldo

500 Messi

QUESTION THREE
1. Suppose that stack is an object of type stackType<double>, the value of stack.top is 8,
and dec is a variable of type double. [4 Marks]
a. How many elements are in stack?
b. What is the index of the top element of stack?
c. Write the statement that assigns the top element of stack to dec.
d. Write the statement that removes the top element of stack.
2. What is a node in a binary tree that has no left and right children called? [1 Mark]

  

3. Use the binary tree shown below to answer the questions that follow: [5 Marks]
a. Find LA, the node in the left subtree of A.
b. Find LH, the node in the left subtree of H.
c. Find the height of the tree with root B.
d. List the nodes with exactly one child.
e. List the nodes of this binary tree in a preorder sequence.
4. The following lists the nodes in a binary tree in two different orders:
Preorder: A B C D E F G H I J K L M
Inorder: C E D F B A H J I K G M L
Draw the binary tree. [10 Marks]
References
Malik, D. S., 2018. C++ Programming: Program Design Including Data Structures. 8th ed. Boston:
Cengage Learning.

Answer 1

Question one:

1. i. PUSH--when we want to add an element in the stack we use the push operation to insert and element in the stack.

ii.POP - we want to delete the element that is on the top of the stack , than we use the POP function

iii.isEMPTY - we use this operation to see whether the stack is empty or not.

2.

a. You have several phone messages coming in and want to handle them in the order they were received.--we can use the queue data structure here as it stores the item based on their arrivale time and displays the item that was first arrived.

b. You have a phone bill arriving each month and want to be able to look up any month's bill.-- we can use the array here as we can easily see any item in the array using the index reference.

c. You are planning a road trip and have listed several stops along the way but want to be able to add a new one partway through.-- we can use array data structure because it allows the easy insertion and deletion of element at any index