笔试题（正整数序列）

1.9 现有如下任务需要安排在若干机器上并行完成，每个任务都有开始时间和结束时间（开始和结束时间都包括在任务执行时间内）的要求

任务名称 开始时间 结束时间

a 1 7

b 8 9

c 2 5

d 7 11

e 3 6

f 7 9

g 10 13

则最少需要使用的机器数目为

A1B2C3D4

1.10 在设计一个操作系统时，哪项不是必须考虑的

A 设备管理模块B文件系统模块C用户管理模块D进程管理模块

2.1正整数序列Q中的每个元素都至少能被正整数a和b中的一个整除，现给定a和b，需要计算出Q中的前几项，例如，当a=3，b=5，N=6时，序列为3，5，6，9，10，12

（1）设计一个函数void generate（int a,int b,int N ,int * Q）计算Q的前几项

（2）设计测试数据来验证函数程序在各种输入下的正确性

2.2 有一个由大小写组成的字符串，现在需要对他进行修改，将其中的所有小写字母排在答谢字母的前面（大写或小写字母之间不要求保持原来次序），如有可能尽量选择时间和空间效率高的算法 c语言函数原型void proc（char *str） 也可以采用你自己熟悉的语言

2.3 已知一颗无向无环连通图T的所有顶点和边的信息，现需要将其转换为一棵树，要求树的深度最小，请设计一个算法找到所有满足要求的树的根结点，并分析时空复杂度（描述算法即可，无需代码）