复习重点

约 138 个字

知识

• hashing
• sort
• network flow
• graph
• tree

代码

• sort
• BFS,DFS
• heap
• BST
• dijkstra
• disjoint
• insertion sort

历年卷中的知识点

15-16 Autumn-Winter

• merge run?
• is a sorting algorithm stable?
• do one BFS visit all vertices?
• the time complexity to compute Fibonacci
• \(10^6\) 1-digit number?
• LSD radix sort?
• in hashing, what key, hash value and collision is. Collision is Two elements with different keys share the same hash value.
• how to check cycle in a graph.
• the methods to sovle collision?
• The DFS of adjacency lists has order by the links.

16-17 Autumn-Winter

• which sort need extra space? how much?
• the best sort based on comparison is?
• when can quadratic probing be successful?
• negative-cost edge won't cause infinity loop in dijkstra.
• when to use heap in dijkstra?