1.7 习题

（1）什么是算法的时间复杂度和空间复杂度？

（2）什么是数据结构？

（3）数据结构在火车票管理系统中起到什么作用？

（4）算法的优劣可以用哪几个指标衡量？

（5）在递归实现分治法时，为什么要定义包裹函数？

（6）设计一个函数，计算 S =1−2+3−4+5−6+…+(−1) ^{n − 1} × n 的值，要求时间复杂度为 O (1)。

（7）给出下列代码时间复杂度的大O表示。

sum = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < i; j++)
        sum++;　

（8）在面向对象的数据结构中，用类来封装一种数据结构有什么好处？

（9）请设计一个算法，判断整数 N 是否是素数，并分析其时间复杂度的大O表示。

（10）试说明下列数据集合中数据元素的逻辑关系。

1）列车站点中排队等候上车的乘客。

2）公园里的游客。

3）某人通讯录中的人员。

（11）下列与计算机相关的技术中，数据元素的逻辑结构分别是什么？

1）面向对象程序设计中，通过单继承形成的所有类。

2）面向对象程序设计中，通过多继承形成的所有类。

3）计算机中的文件和文件夹。 p6AyPTkxOkF9g/HuvuDU53A6eZ6QURtXLqcymQpoGncQS5AoyFzrGXSvzTthzCRi