COMP2123A Programming Technologies and Tools
Quiz 2. Time: 100 minutes
• This quiz consists of 3 questions.
• Submit your work to Moodle VPL.
• Please put your student ID card in front of the computer.
Question 1: Friend suggestion
A social network system stores friendship information of members. The system supports 3 commands:
• FRIEND X Y – Specify X and Y are friends in the social network.
• KNOW X Y – Outputs “Yes” if X and Y are friend, outputs “No” otherwise.
• SUGGEST X Y – Outputs “Yes” if we suggest X and Y to become friend of each other, outputs
“No”otherwise. Inparticular,wewillsuggestXandYtobecomefriendif o X and Y are not friend, and
o There are at least one common friends among X and Y.
• You can assume the number of people <= 100. Sample case
Input
Output
FRIEND David Bob FRIEND Bob Alex FRIEND Alex Kitty FRIEND Daniel David FRIEND David Kit SUGGEST David Alex SUGGEST Bob Kitty SUGGEST David Kitty SUGGEST David Bob KNOW David Bob
Yes Yes No No Yes
Assessment
40%
Only FRIEND and KNOW command.
60%
All three kind of command.
All test cases
Test case
Input
Output
mark
1
FRIEND Tom Tim KNOW Tom Tim
Yes
5
2
FRIEND Tom Tim KNOW Tim Tom
Yes
5
3
KNOW Tim Tom
No
5
4
FRIEND Tom Tim KNOW Tim Kit
No
5
5
KNOW Tim Kit FRIEND Tim Tom KNOW Tim Kit FRIEND Kit Tom KNOW Tim Kit FRIEND Kit Tim KNOW Tim Kit
No No No Yes
5
6
FRIEND Tom Tim FRIEND Tim Kit KNOW Tom Kit
No
5
7
FRIEND Tom Kit FRIEND Tim Kit KNOW Tom Tim FRIEND Tim Tom KNOW Tom Tim
No Yes
10
8
SUGGEST David Kit
No
5
9
FRIEND David Kit SUGGEST David Kit
No
5
10
FRIEND David Kit FRIEND Kit Bob SUGGEST David Bob
Yes
5
11
FRIEND David Bob FRIEND Bob Alex FRIEND Alex Kitty FRIEND Daniel David FRIEND David Kit SUGGEST David Alex SUGGEST Bob Kitty SUGGEST David Kitty SUGGEST David Bob KNOW David Bob
Yes
Yes
No
No
Yes
5
12
FRIEND David Bob FRIEND Bob Alex FRIEND Alex Kitty FRIEND Daniel David FRIEND David Kit SUGGEST David Alex SUGGEST Bob Kitty SUGGEST David Kitty SUGGEST David Bob KNOW David Bob FRIEND Kit Kitty SUGGEST David Kitty
Yes
Yes
No
No
Yes
Yes
5
13
Random cases with many commands
15
14
Random cases with many commands (100 people).
20
Question 2: String Operation in C
Write a
• • •
•
Input
• •
C program that:
Reads a string s, you can assume that there is no space in s.
Reads a char c
Removes the first and last occurrence of c in s, and outputs the modified string.
o If there is only one occurrence of c in s, that one is regarded as both the first and last occurrence. (please refer to test case 3)
Output "wrong" if there no occurrences of c in s.
The first line is string s, you can assume the length of s does not exceed 100 characters. The second line is char c.
Output
The modified string, or “wrong” Sample Case
All test case
Input
Output
applepie p
apleie
iambob g
wrong
Test case
Input
Output
Mark
1
goodgame g
oodame
12.5
2
applepie p
apleie
12.5
3
colour u
color
12.5
4
dad d
a
12.5
5
xx x
12.5
6
x x
12.5
7
A case with s having 100 characters
12.5
8
iambob g
wrong
12.5
Question 3: Stack in C
A Stack is a Last-in First-out (LIFO) data structure. In a LIFO data structure, the last element added to the structure is the first one to be removed.
push x
pop
Write a C program to implement a stack S. There are two commands:
Implementation
• At most 60% mark will be given if you use fixed memory allocation to build the stack.
• At most 100% mark will be given if you use dynamic memory allocation to build the stack. There
should be no memory leak in both cases.
Input
Each line of the input contains a command.
Output
Print the result of each pop command. Sample case
Command
Task
push x
• Push x to stack S.
• You can assume x is an integer.
pop
• Print the top item in S.
• Removes the top item in S.
• If S is empty, output “empty stack”.
Input
Output
push 1
push 2
push 3
pop
push 4
pop
pop
pop
pop
pop
3
4
2
1
empty stack empty stack
Assessment
All test case
60%
the stack will hold no more than 100 items.
40%
the stack can hold arbitrary number of items. You cannot hardcode the number of slots in the stack to handle these test case.
Tips: Using Link list.
Test case
Input
Output
Mark
1
pop
empty stack
5
2
pop pop pop
empty stack empty stack empty stack
5
3
push 43 pop
43
5
4
push 1
push 2
pop
pop
2 1
5
5
push 1
push 1
push 1
push 1
pop
pop
pop
pop
1 1 1 1
5
6
push 1
pop (10 times) push 1
pop
1
empty stack (9 times)
1
5
7
push 1
push 2
push 3
pop
push 4
pop
pop
pop
pop
pop
3
4
2
1
empty stack empty stack
15
8
A case with 100 commands.
15
9,10(not provided in VPL)
We will use some techniques to test if you are using dynamic memory allocation to handle the stack.
40