摘要：为了提高系统级故障诊断中的诊断度，人们以牺牲很小一部分结点不能正确诊断为代价，提出了t／k-故障诊断策略，BC图是包括了超立方体和多种变形立方体的一类图．对于结点总数为N的BC图，本文提出了一个O（N log2N）的t／k-故障诊断算法．目前尚未有相关t／k-故障诊断算法的文章发表，但与著名的悲观一步t-故障诊断算法（t／k-故障诊断算法在k=1时的情况）的O（N^2.5）相比较，在时间复杂度上本文算法是高效的．

关键词：系统级故障诊断 诊断算法 bc图 宽度优先搜索 

单位：重庆大学计算机学院; 重庆400044