Tài liệu Feaculty of Computer Science and Engineering Department of Computer Scienc Tutorial 3

Faculty of Computer Science and Engineering

Department of Computer Science

1/4

DATA STRUCTURES & ALGORITHMS

Tutorial 3 Questions

Recursion and Binary Tree

Part 1. Recursion

Required Questions

Question 1.

What would be the contents of queue Q1 after the following code is executed and the

following data are entered?

1 Q1 = createQueue

2 S1 = createStack

3 loop (not end of file)

1 read number

2 if (number not 0)

1 pushStack (S1, number)

3 else

1 popStack (S1, x)

2 popStack (S1, x)

3 loop (not empty S1)

1 popStack (S1, x)

2 enqueue (Q1, x)

4 end loop

4 end if

4 end loop

The data are: 9, 5, 10, 4, 0, 5, 4, 6, 8, 67, 32, 25, 51, 0, 54, 23, 20, 6, 10

Question 2.

The following algorithm is to reverse a queue

Algorithm reverse (val q <Queue>)

Pre true

Return a reversed queue of q

1 S = createStack

2 Q = createQueue

3 while (not empty(q))

1 dequeue(q,temp)

2 pushStack(S,temp)

4 while (not empty(S))

1 popStack(S,temp)

2 enqueu (Q,temp)

4 return Q

End reverse

Develop a similar algorithm to append a stack to a queue

Algorithm append (val q <Queue>, val s <Stack>)

Pre true