程序代写代做代考 data structure COMP2123A Programming Technologies and Tools

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