四川大学数据结构复习.docx

Review of Data Structures and AlgorithmsChapter 1 Data structures and algorithmsConceptType: A type is a collection of values.Simple type: Its values contain no subparts.Composite type/Aggregate type: Its values contain subparts called data item or member.Data type: A data type is a type together with a collection of operations to manipulate the type.ADT: An abstract data type (ADT) is the realization of a data type as a software component. The interface of the ADT is defined in terms of a type and a set of operations on that type. The behavior of each operation is determined by its inputs and outputs.Data structure: A data structure is the physical implementation for an ADT.Problems: A problem is a task to be performed.Function: A function is a matching between inputs (the domain) and outputs (the range).Algorithm: An algorithm is a recipe for solving a problem whose steps are concrete and unambiguous. Algorithms must be correct, of finite length, and must terminate for all inputs.Programs: A program is an instantiation of an algorithm in a programming language.Chapter 2 Mathematical preliminariesConceptSet: A set is a collection of distinguishable members or elements.Recursion: An algorithm is recursive if it calls itself to do part of its work.Chapter 3 Algorithm AnalysisConceptAsymptotic algorithm analysis(对资源消耗进行评估，对同一程序算法进行分析): Asymptotic analysis attempts to estimate the resource consumption of an algorithm. It allows us to compare the relative costs of two or more algorithms for solving the same problem. Asymptotic analysis also gives algorithm designers a tool for estimating whether a proposed solution is likely to meet the resource constraints for a problem before they implement an actual program.Growth rate（算法随着输入增长导致整体花费增长的比重）: the rate at which the cost of the algorithm grows as the size of its input grows.Best/worst/average case: They express what the resource usage is at least, at most and on average, respectively.Upper/Lower bound: It indicates the u