noc创新思维编程初赛试题

1. 请写出2个常见的数据结构，并简要介绍它们的特点。 答案：常见的数据结构包括数组和链表。数组是一种线性数据结构，它可以存储相同类型的元素，这些元素在内存中是连续的。数组具有O(1)的访问时间复杂度，但插入和删除的时间复杂度为O(n)。链表也是一种线性数据结构，不同于数组的是它的元素在内存中不是连续的，而是通过指针链接起来的。链表具有O(1)的插入和删除时间复杂度，但访问元素的时间复杂度为O(n)。

2. 给定一个长度为n的数组arr，请编写代码实现查找数组中第k大的元素。

答案：有不同的方法可以解决这个问题，以下是其中一种利用快速排序思想的方法： ```

#include using namespace std;

int partition(vector& nums, int low, int high){ int pivot = nums[high]; int i = low - 1;

for(int j = low; j < high; j++){ if(nums[j] > pivot){ i++;

swap(nums[i], nums[j]); } }

swap(nums[i+1], nums[high]);

return i+1; }

int findKthLargest(vector& nums, int k) { int n = nums.size();

int low = 0, high = n - 1; while(1){

int pivotIndex = partition(nums, low, high); if(pivotIndex == k-1) return nums[pivotIndex]; else if(pivotIndex > k-1) high = pivotIndex-1; else low = pivotIndex+1; } }

int main(){ int n,k;

cin >> n >> k; vector arr(n);

for(int i = 0; i < n; i++){ cin >> arr[i]; }

int kthLargest = findKthLargest(arr, k); cout << kthLargest; return 0; } ```

3. 给定一个字符串，编写一个函数判断它是否是回文字符串。 答案：回文字符串是指正向和反向读取都相同的字符串，可以通过比较正向和反向的字符串是否相等来判断一个字符串是否

是回文字符串。以下是普通的方法和利用栈的方法实现： ```

// 普通方法

bool isPalindrome(string s) { int n = s.length();

for(int i = 0; i < n/2; i++){

if(s[i] != s[n-i-1]) return false; }

return true; }

// 利用栈

bool isPalindrome(string s) { stack st; for(char c : s){

if(isalnum(c)) st.push(tolower(c)); }

for(int i = 0; i < s.length(); i++){ if(!isalnum(s[i])) continue;

char c = tolower(st.top()); st.pop(); if(c != tolower(s[i])) return false; }

return true; } ```

4. 给定两个整数m和n，编写一个函数计算它们的最大公约数。 答案：最大公约数可以用辗转相除法来计算，即先求出m除以n的余数r，然后用n去除r，将最后一个除数n作为结果

即可。这个过程可以用递归来实现，如下： ```

int (int m, int n){ if(n == 0) return m; return (n, m % n); } ```

5. 给定一个由整数组成的非空数组，编写一个函数计算它的平均数。

答案：平均数就是将数组中所有元素相加然后除以数组长度，可以用以下代码实现： ```

double getAverage(vector& nums){ int n = nums.size(); int sum = 0;

for(int num : nums){ sum += num; }

return sum / (double)n; } ```