在当今信息化不断发展的时代,计算机软件作为信息化的关键组成部分,已经广泛参与和应用于人类信息产业和日常生活的各个方面。因此,软件的质量问题备受人们关注。软件测试在软件开发阶段为保障软件质量起到了重要作用。测试用例生成作为其中关键一环,如何生成较高揭错率的测试用例,一直是软件测试领域的热点话题。基于此,自适应随机测试（Adaptive Random Testing,ART）被提出,其保证测试用例尽可能在输入域中均匀分布,进而提升错误检测能力。FSCS-ART（Fixed-size-Candidate-set ART）作为众多ART算法中的经典算法,由于其较好的揭错能力,被研究人员深入研究以及广泛应用。然而,由于其生成测试用例时需要进行大量的测试用例相似性计算,不断膨胀的测试用例数量将引发严重的计算时间开销问题。此外,维度的升高导致其有效性明显降低。上述两类问题限制其实际应用。本文重点分析了FSCS-ART算法的整个过程,首先从提升效率的角度,将一种空间划分模式应用其中实现了测试用例快速生成。随后从改善有效性的角度,提出了两种改进策略来获得更均匀的测试用例分布。并通过一系列实验分析所提算法的效率和有效性情况。最后,通过一个原型系统对所提算法进行验证。本文主要完成了如下工作:1、针对传统的ART算法高昂的时间开销问题,提出了基于改进内存度量树的FSCS-ART算法（FSCS-ART based on the modified Metric-Memory tree,MMFCART）。该算法利用内存度量树（MM树）的划分模式将输入域划分成不同的子区域,空间相似性高的测试用例被划分到同一个或相邻子区域中。通过搜索半径将最近邻搜索限制在某一个或几个子区域中,大幅降低全输入域搜索带来的高昂时间开销。同时为了匹配ART算法的动态过程,提出了一种改进的MM树结构,将子区域与树的节点相对应来存储测试用例。通过与多种ART算法进行实验对比,表明了MMFC-ART算法不仅大幅减少了时间开销,同时一定程度上提高了高维有效性。2、针对MMFC-ART算法低维有效性稍差以及在高维仍然存在较严重的边界效应问题,提出了基于森林策略和信息熵策略的改进MMFC-ART算法,即（ForestStrategy MMFC-ART,FS-MMFC）和（Information-Entropy Strategy MMFC-ART,IES-MMFC）。森林策略引入多棵改进的MM树对输入域进行划分,将每一个测试用例分别存储到多棵树中。在进行最近邻搜索时,分别在多棵树中进行搜索获得多个最近邻,保留距离值最小的作为最终最近邻。信息熵策略通过加入信息熵指标,和原有的距离指标综合度量测试用例相似性来选择测试用例（即距离-信息熵选择策略）,以此实现测试用例在高维更为均匀的分布,提升算法高维有效性。同样通过实验验证了两种改进算法仍远比FSCS-ART算法检测异常所需时间短,并且进一步提升了MMFC-ART算法的有效性,其中IES-MMFC算法在高维的有效性大幅提升。3、设计并实现了一个原型系统。该系统由测试模式预处理模块、测试算法执行模块、测试结果统计分析模块和测试结果存取模块构成。系统以自动化的形式完成每个算法的测试工作,并验证了本文所提算法的表现。