课程名称︰资料结构与算法
课程性质︰资工系大一必修
课程教师︰张智星
开课学院：电机资讯学院
开课系所︰资工系
考试日期（年月日）︰2017/04/25
考试时限（分钟）：上机考 80 mins
试题 :
*本次考试有笔试与上机考两部分，此为上机考
For each of the following problems, the time limit is 1 second, and the memory
limit is 256MB.
1. (25 pts) Container identification:
Problem description:
Given an empty container, one can perform n operations, with each of them being
either "add" (put an integer xi into it) or "remove" (take an integer xi out of
it). Determine the type of the container based on the result of these n
operations.
Input format:
The first line is an integer indicating n, the number of operations.
Each of the following n lines contains two integers, ti and xi:
ti: 1 for "add", 2 for "remove"
xi: the integer for "add", or the integer returned from "remove".
Output format:
Please output one of the following answers:
both: The container is both a stack and a queue.
stack: The container is a stack, not a queue.
queue: The container is a queue, not a stack.
neither: The container is neither a stack nor a queue.
Ranges of variables:
1 <= xi,n <= 2*10^5
Test cases:
Input (p01_input01.txt):
4
1 10
2 10
1 20
2 20
Output (p01_output01.txt):
both
Input (p01_input02.txt):
4
1 10
1 20
2 20
2 10
Output (p01_output02.txt):
stack
Input (p01_input03.txt):
4
1 10
1 20
2 10
2 20
Output (p01_output03.txt):
queue
Input (p01_input04.txt):
4
1 10
1 20
2 30
2 40
Output (p01_output04.txt):
neither
2. (25 pts) Game of Ongress:
Problem description:
To play the game of Ongress, you need to walk along a street of nn blocks.
When you walk through block i, you earn pi points. You plan to play Ongress
m times. The jth time you play Ongress, you plan to walk from block uj to vj,
so you can collect points for each block you walk through, including block uj
and vj. Compute how many points you will earn each time you play Ongress.
Input format:
The first line contains two integers, n and m.
The second line contains n integers, p1,p2,…,pn
Each of the following mm lines contains two integers, uj and vj.
Output format:
On the jth line (j=1,2,…,m), print the amount of points you earn at the jth
time you play Ongress.
Ranges of variables:
1 <= n,m <= 2*10^5
1 <= pi <= 10^9
1 <= ui <= vi <= n
Test cases:
Input (p02_input01.txt):
5 3
10 30 50 20 40
1 5
1 2
4 4
Output (p02_output01.txt):
150
40
20
3. (25 pts) Story of Untied Airline:
Problem Description:
Untied Airline have n employees. The salary of the ith employee is wi per
month. On the first day of month j (j=1,2,…,m), one of two things could
happen:
If t_j=1, a new employee with salary v_j per month joined the airline.
If t_j=2, all employees with salary higher than v_j per month were laid
off.
Assuming all empolyees received their salary on the last day of the month,
compute the total amount the airline paid to its employees from month 1 to
month m.
Input format:
Line 1 contains two integers, nn and mm.
Line 2 contains nn integers, w1,w2,…,wn.
Each of the following m lines contains two integers, tj and vj.
Output format:
Print an integer, the total amount the airline paid.
Ranges of variables:
1 <= n,m,wi,ti <= 2*10^5
Test cases:
Input (p03_input01.txt):
4 2
30000 40000 50000 60000
1 22000
2 35000
Output (p03_output01.txt):
254000
4. (25 pts) A tree or not:
Problem Description:
In a country, there are n cities connected by m roads, where road j connects
city uj and vj. (Note that each pair of cities are connected by at most one
road, and no road connects a city to itself.) If any two given cities can be
connected by a unique path (consisting of one or several roads), then the
road system is a tree. Determine if the road system is a tree or not.
Input format:
Line 1 contains two integers, n and m.
Each of the following mm lines contains two integers, uj and vj,
indicating there is a road between cities uj and vj.
Output format:
Print yes if the road system is a tree. Print no otherwise.
Ranges of variables:
1 <= n,m <= 5*10^3
1 <= ui <= vi <= n
Test cases:
Input (p04_input01.txt):
3 2
1 3
2 3
Output (p04_output01.txt):
yes
Input (p04_input02.txt):
5 4
1 2
1 3
3 4
3 5
Output (p04_output02.txt):
yes
Input (p04_input03.txt):
6 6
1 2
1 3
2 4
3 4
4 5
5 6
Output (p04_output03.txt):
no
Input (p04_input04.txt):
6 4
1 2
2 3
4 5
5 6
Output (p04_output04.txt):
no
(Total score = 100)