电子科技大学软件测试笔试试题及答案

　一：编程题

　　现有一组共计N个固定的集合(N为万量级)，每个集合有个从0开始递增的集合ID，每个集

　　合包含1~M个TERM(M为0~100的量级)，希望设计一个程序能够持续对外服务，输入是一个

　　TERM数组，输出其中任意一个集合ID(如果该TERM数组包含该集合的所有TERM)，如果找

　　不到输出-1。要求：

　　1， 时间复杂度最优，能够在短时间内对大量输入逐个输出

　　2， 实现具体的代码(可以是伪代码)，其中常用的数据结构可以采用标准库。

　　3， 给出时间复杂度和空间复杂度。

　　TERM组合集合的文件格式举例：

　　TERM_1 空格 TERM_2

　　TERM_1 空格 TERM_3

　　TERM_1 空格 TERM_3 TERM_4

　　输入的为TERM数组(说明：TERM为一个词，可能是中文，固定字符串表示)

　　二：算法题

　　你现在有一个文件，文件中顺序存有N个记录，R1,R2,...,RN,这些记录不是有序的，但是

　　你知道一个整数M,这些记录满足R1

　　1,设计一个算法或编写一个程序，将文件中的记录排序为R1'取文件的次数为O(N),不限内存使用，

　　2,设计一个算法或编写一个程序，将文件中的记录排序为R1'写文件的次数为O(N)，空间复杂度为O(1)，(亦即，你使用的内存大小和M,N均无关。)