题型

选择题

判断连通分量的数量
In 2022, the Scheol of Sofware Engmneering las enrolled N fesmen. After a Icwmncnths, some are fiends and some are not Their tnendship is transitive.1f wknow tiat A is a flond of B and B is a fnend ot e then we can consider that A islso a triend of Csayig tha A B imd C form circle of friends. Plse use yourimowledge of dafa structure to compute the total nnmber of cireles of fends in1he fTesltnen
(a) What kind of datu structire will you design for the computation? Explainyour design.(7 puints)
(b) What algorithms will you design for solying Tom’s problem? Please givepsuudocode for e leoritlims.(10 points)
(c) Try to anulyze tho tiine complexity of your algorithm.. (3points )

bfs/dfs/并查集

识别图中是否有环
Professor Lee is responsible for reviewing the training programs(培养方案) of allmajors for his college. One of the audit contents is to check whether there arecircular dependencies among courses in each training program, that is, theprerequisites of a course is dependent on it. Please use your knowledge of datastructure to help Professor Lee finish his work as quick as possible.
(a) What kind of data structure will you design for Professor Lee? Explain yourdesign.(7 points)
(b) What algorithms will you design for arranging his work sequence? Pleasegive pseudocode(伪代码) of the algorithms.(10 points)
(c) Try to analyze the time complexity of your algorithm. (3points)

邻接表/邻接矩阵+拓扑排序

Given a set of points represented by their xy-coordinates, assign the points togroups. Any two points are defined to be in the same group if they are within aspecified distance d of each other. For the purpose of this problem, a group is anequivalence class set. In other words, points A, B, and C are defined to be in thesame group if the distance between A and B is less than d and the distancebetween A and C is also less than d, even if the distance between B and C isgreater than d Please use your knowledge of data structures to provide a solutionto solve the problem, and give your reason. (10 points)
At the end of the year, the Association(协会) will hold an annual meeting, inwhich outstanding members will be elected by the N members.In order to ensurethe fairness of the election, the election commission(选举委员会)declares that allvoters must vote on the spot(在现场) with their ID card (ID number ranges from0-N-1), and that each person can vote only one time. When voters vote, thesupervisor will check whether the voter has already voted, and only those whchave not voted can vote. Due to the large number of voters, manual checking willbe time-consuming,which seriously hampered(阻碍) the progress of the electionsPlease use your knowledge of data structures to provide a solution with timecomplexity of O(1) to solve the problem of checking inefficiencies in this electionand give your reason.(10 points)

重要知识点