Based on Full-mode Linear Expansion Theory, the article puts forward two new algorithms which are called the full-mode algorithm and the high accuracy truncated modal algorithm for computing modal sensitivity of multiple-frequency damping structure. Firstly, through introducing the relaxation factors, the new full-mode algorithm proposed eliminates the influence of multiple frequency on modal sensitivity analysis. The article also theoretically analyzes the source of error and the controlling method of the full-mode algorithm. Secondly, the high accuracy truncated modal algorithm and its error analysis are proposed through analyzing the contributions of all modes, which are regarded as the truncation criterion, in the full-mode linear expansion subject to the sensitivity analysis of multiple-frequency mode. According to the high accuracy truncated modal algorithm, the fewer modes can obtain the certain information of multiple-frequency modal sensitivity in symmetrical or asymmetrical system, the facts show that not only the theoretical analysis but also numerical calculations indicate the correctness and efficiency of this algorithm.