Xem mẫu
Faculty of Computer Science and Engineering Department of Computer Science
Page 1/10
Faculty of Computer Science and Engineering Department of Computer Science
a. f – k b. f *k c. f\ 10 d. f\ x e. f* f2
Page 2/10
Faculty of Computer Science and Engineering Department of Computer Science
Part 2. Stack
Suppose that the following algorithms are implemented:
- PushStack (ref s , val n ):push the value nto the stack s
- PopStack(ref s , ref x ):remove the top element of the stack s and assign the data of that top element to x
- EmptyStack(val s ): check whether the stack s is empty
Required Questions Question 3.
Imagine we have two empty stacks of integers, s1and s2. Draw a picture of each stack after the following operations:
1: PushStack (s1, 1); 2: PushStack (s1, 9); 3: PushStack (s1, 4); 4: PushStack (s1, 2);
5: while (!EmptyStack (s1)) { 6: PopStack (s1, x);
7: PushStack (s2, x); 8: } //while
9: PushStack (s1, 10); 10: PushStack (s1, 7);
11: while (!EmptyStack (s2)) { 12: PopStack (s2, x);
13: PushStack (s1, x); 14: } //while
15: PopStack (s1, x); 16: PushStack (s2, x); 17: PopStack (s1, x); 18: PushStack (s2, x);
Question 4.
Write an algorithm for a function called RemoveSecondthat removes the second element of a stack. The order of other elements in the stack must be the same after the removal.
algorithm RemoveSecond (ref sourceStack)
This algorithm removes the second element in the sourceStack. The order of the remaing elements must be preserved after the removal.
Pre None
Post the sourceStack being removed its second element Return None
end RemoveSecond
Page 3/10
Faculty of Computer Science and Engineering Department of Computer Science
Part 3. Queue
Suppose that the following algorithms are implemented:
- EnQueue (ref q , val n ):push the value nto the queue queue - DeQueue(ref q , ref x ):remove the top element of the queue q
and assign the data of that top element to x
- EmptyQueue(val q ): check whether the queue q is empty - QueueRear()
- QueueFront()
Required Questions Question 5.
Imagine we have an empty stack of integers S, and two empty queues of integer Q1and Q2. What would be the value of queues Q1, Q2, and stack S, after the following segment?
1: Enqueue (Q1, 5) 2: Enqueue (Q1, 6) 3: Enqueue (Q1, 9) 4: Enqueue (Q1, 0) 5: Enqueue (Q1, 7) 6: Enqueue (Q1, 5) 7: Enqueue (Q1, 0) 8: Enqueue (Q1, 2) 9: Enqueue (Q1, 6)
10: while (! EmptyQueue (Q1)){ 11: DeQueue (Q1, x)
12: if (x == 0){ 13: z = 0
14: while (! EmptyStack (S)){ 15: PopStack(S, &y)
16: z = z + y 17: }
18: Enqueue (Q2, z) 19: }else{
20: PushStack (S, x) 21: }
22: }
Question 6.
What would be the contents of queue Q after the following code is executed and the following data are entered?
1: Q = createQueue
2: while (not end of file){ 3: read number
4: if (number != 0){
5: EnQueue (Q, number) 6: }else{
7: QueueRear (Q, x) 8: EnQueue (Q, x) 9: }
10: }
The data are: 5, 7, 12, 4, 0, 4, 6, 8, 67, 34, 23, 5, 0, 44, 33, 22, 6, 0.
Page 4/10
Faculty of Computer Science and Engineering Department of Computer Science
Question 7.
What would be the contents of queue Q1 after the following code is executed and the following data are entered?
11: Q1 = createQueue 12: S1 = createStack
13: while (not end of file){ 14: read number
15: if (number != 0){
16: PushStack (S1, number) 17: }else{
18: PopStack (S1, x) 19: PopStack (S1, x)
20: while (!EmptyStack(S1)){ 21: PopStack (S1, x) 22: EnQueue (Q1, x)
23: } 24: }
25: }
The data are: 5, 7, 12, 4, 0, 4, 6, 8, 67, 34, 23, 5, 0, 44, 33, 22, 6, 0
Question 8.
Imagine that the contents of queue Q1and queue Q2are as shown. What would be the contents of queues Q1, Q2 and Q3 after the following code is executed? The queue contents are shown front (left) to rear (right).
Q1: 42 30 41 31 19 20 25 14 10 11 12 15 Q2: 3 5 7 4 13
26: Q3 = CreateQueue 27: count = 0
28: while(!EmptyQueue(Q1)&&!EmptyQueue(Q2)){ 29: count = count + 1
30: DeQueue (Q1, x) 31: DeQueue (Q2, y) 32: if (y == count){
33: EnQueue (Q3, x) 34: }
35: }
Page 5/10
...
- tailieumienphi.vn
nguon tai.lieu . vn