考研真题数据结构

【2018年山西大学真题】试编写一个算法，使之能在数组L【1～n】中找到最小元素。

（1）给出算法的基本思想。

（2）根据设计思想，给出描述算法。

（3）分析所给算法的时间复杂度。

（1）算法基本思想：
1.?假设数组中的第一个元素为当前的最小元素，将其保存在一个变量?`min_element`?中。
2.?从数组的第二个元素开始遍历，比较遍历到的元素和?`min_element`?的大小。
3.?如果遍历到的元素小于?`min_element`，则更新?`min_element`?的值为遍历到的元素的值。
4.?继续遍历数组，重复步骤?2?~?3?直到遍历完整个数组。
5.?返回?`min_element`?即为数组中的最小元素。

（2）根据上述设计思想，可以用?C?语言编写以下算法：

```c
#include?<stdio.h>

int?findMinElement(int*?arr,?int?n)?{
????if?(arr?==?NULL?||?n?<=?0)?{
????????return?-1;??//?错误的输入
????}

????int?min_element?=?arr[0];???//?假设数组的第一个元素为最小元素

????for?(int?i?=?1;?i?<?n;?i++)?{
????????if?(arr[i]?<?min_element)?{
????????????min_element?=?arr[i];???//?更新最小元素
????????}
????}

????return?min_element;???//?返回最小元素
}

int?main()?{
????int?arr[]?=?{9,?5,?2,?7,?6,?1,?4,?3};
????int?n?=?sizeof(arr)?/?sizeof(arr[0]);

????int?min_element?=?findMinElement(arr,?n);

????printf("数组的最小元素为：%d\n",?min_element);

????return?0;
}
```

在上述代码中，定义了?`findMinElement`?函数，根据设计思想实现了寻找数组中最小元素的算法。在?`main`?函数中，通过调用?`findMinElement`?函数，找到数组中的最小元素，并打印出来。输出结果为：

```
数组的最小元素为：1
```

（3）分析时间复杂度：
在算法中，需要遍历整个数组一次，所以时间复杂度为?O(n)，其中?n?是数组的长度。