企业网站的缺点学做网站论坛vip账户

当前位置： 首页 > news >正文

企业网站的缺点,学做网站论坛vip账户,网站开发用什么框架好,济南学生网站建设求职文章目录 考点数据结构基础线性结构非线性结构 常见算法排序算法查找算法递归算法分治算法动态规划贪心算法 复杂度分析 考点 在软考中#xff0c;数据结构与算法的考点主要集中在以下方面#xff1a; 基本概念#xff1a;掌握各类数据结构的定义、特点和应用场景。常用算… 文章目录 考点数据结构基础线性结构非线性结构 常见算法排序算法查找算法递归算法分治算法动态规划贪心算法 复杂度分析 考点 在软考中数据结构与算法的考点主要集中在以下方面 基本概念掌握各类数据结构的定义、特点和应用场景。常用算法的理解与应用尤其是排序算法和查找算法的实现及复杂度分析。递归与分治思想通过实际案例理解递归和分治的原理和用法。算法效率分析理解时间复杂度和空间复杂度能够分析给定算法的效率。 数据结构基础 数据结构是指一组数据的存储和组织方式决定了数据的操作效率。主要包括线性结构和非线性结构具体如下 线性结构 线性结构的数据按顺序排列典型的数据结构包括数组、链表、栈和队列。 数组一种定长数据结构优点是可以通过索引快速访问元素但删除和插入操作的效率较低。链表由节点构成的链式存储结构适合动态数据管理。链表分为单链表、双链表和循环链表操作灵活但需要额外的存储空间存放指针。 反转链表 #include iostream using namespace std;struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {} };ListNode* reverseList(ListNode* head) {ListNode* prev nullptr;ListNode* curr head;while (curr ! nullptr) {ListNode* nextTemp curr-next;curr-next prev;prev curr;curr nextTemp;}return prev; }int main() {ListNode* head new ListNode(1);head-next new ListNode(2);head-next-next new ListNode(3);head-next-next-next new ListNode(4);head-next-next-next-next new ListNode(5);ListNode* reversed reverseList(head);while (reversed) {cout reversed-val ;reversed reversed-next;}return 0; } // 输出: 5 4 3 2 1 栈一种“后进先出”LIFO, Last In First Out的数据结构适用于递归和逆序操作。队列一种“先进先出”FIFO, First In First Out的数据结构适合需要按顺序处理的场景。队列有普通队列、双端队列和循环队列等变种。 非线性结构 非线性结构的数据排列方式更为复杂主要包括树、图等。 树一种层次结构每个节点有一个父节点和多个子节点。常见的树包括二叉树、平衡树、B树和红黑树等。树结构用于表达层级关系适合快速查找和动态排序。 使用递归计算二叉树的深度 /* 输入1/ \2 3/
4 5 / #include iostream using namespace std;struct TreeNode {int val;TreeNode left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };int maxDepth(TreeNode* root) {if (!root) return 0;int leftDepth maxDepth(root-left);int rightDepth maxDepth(root-right);return max(leftDepth, rightDepth) 1; }int main() {TreeNode* root new TreeNode(1);root-left new TreeNode(2);root-right new TreeNode(3);root-left-left new TreeNode(4);root-left-right new TreeNode(5);cout 最大深度: maxDepth(root);return 0; } // 输出: 最大深度: 3 图一种更加复杂的非线性结构由顶点和边构成可以表示节点间的多对多关系。图分为无向图和有向图广泛应用于网络连接、地图导航等场景。 常见算法 算法是解决特定问题的步骤集合软考中级软件设计师考试常考的算法包括排序、查找、递归、分治和贪心算法等。 排序算法 排序算法是将数据按照一定顺序排列的过程。常见的排序算法包括 冒泡排序每次相邻比较交换复杂度为 O ( n 2 ) O(n^2) O(n2) 适用于小规模数据。是一种稳定的排序算法。 #include iostream #include vector using namespace std;void bubbleSort(vectorint arr) {int n arr.size();for (int i 0; i n - 1; i) {for (int j 0; j n - i - 1; j) {if (arr[j] arr[j 1]) {swap(arr[j], arr[j 1]);}}} }int main() {vectorint arr {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);for (int i : arr) cout i ;return 0; } // 输出: 11 12 22 25 34 64 90 选择排序每次选择最小或最大元素放到正确位置复杂度为 O ( n 2 ) O(n^2) O(n2) 。是一种不稳定的排序算法。 #include iostream #include vector using namespace std;void selectionSort(vectorint arr) {int n arr.size();for (int i 0; i n - 1; i) {int min_index i;for (int j i 1; j n; j) {if (arr[j] arr[min_index]) {min_index j;}}swap(arr[i], arr[min_index]);} }int main() {vectorint arr {64, 25, 12, 22, 11};selectionSort(arr);for (int i : arr) cout i ;return 0; } // 输出: 11 12 22 25 64 插入排序每次将一个元素插入已排序的部分复杂度为 O ( n 2 ) O(n^2) O(n2) 对少量元素时高效。是一种稳定的排序算法。 #include iostream #include vector using namespace std;void insertionSort(vectorint arr) {int n arr.size();for (int i 1; i n; i) {int key arr[i];int j i - 1;while (j 0 arr[j] key) {arr[j 1] arr[j];j j - 1;}arr[j 1] key;} }int main() {vectorint arr {12, 11, 13, 5, 6};insertionSort(arr);for (int i : arr) cout i ;return 0; } // 输出: 5 6 11 12 13 快速排序分治算法的典型应用通过选择“基准”将数据分割成两部分复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。是一种不稳定的排序算法最坏的情况是数据基本有序的时候时间复杂度为 O ( n 2 ) O(n^2) O(n2)。 #include iostream #include vector using namespace std;int partition(vectorint arr, int low, int high) {int pivot arr[high];int i (low - 1);for (int j low; j high; j) {if (arr[j] pivot) {i;swap(arr[i], arr[j]);}}swap(arr[i 1], arr[high]);return i 1; }void quickSort(vectorint arr, int low, int high) {if (low high) {int pi partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);} }int main() {vectorint arr {3, 6, 8, 10, 1, 2, 1};quickSort(arr, 0, arr.size() - 1);for (int i : arr) cout i ;return 0; } // 输出: 1 1 2 3 6 8 10 归并排序也是分治算法通过递归将数据不断分割、排序后合并复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。是一种稳定的排序算法。 #include iostream #include vector using namespace std;void merge(vectorint arr, int left, int mid, int right) {int n1 mid - left 1;int n2 right - mid;vectorint L(n1), R(n2);for (int i 0; i n1; i) L[i] arr[left i];for (int j 0; j n2; j) R[j] arr[mid 1 j];int i 0, j 0, k left;while (i n1 j n2) {if (L[i] R[j]) {arr[k] L[i];i;} else {arr[k] R[j];j;}k;}while (i n1) arr[k] L[i];while (j n2) arr[k] R[j]; }void mergeSort(vectorint arr, int left, int right) {if (left right) return;int mid left (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid 1, right);merge(arr, left, mid, right); }int main() {vectorint arr {12, 11, 13, 5, 6, 7};mergeSort(arr, 0, arr.size() - 1);for (int i : arr) cout i ;return 0; } // 输出: 5 6 7 11 12 13 堆排序基于堆这种特殊的树结构进行排序复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。是一种不稳定的排序算法。 #include iostream #include vector using namespace std;// 调整堆使得以i为根节点的子树满足最大堆性质 void heapify(vectorint arr, int n, int i) {int largest i; // 初始化 largest 为根节点int left 2 * i 1; // 左子节点int right 2 * i 2; // 右子节点// 如果左子节点存在且大于根节点if (left n arr[left] arr[largest]) {largest left;}// 如果右子节点存在且大于当前最大节点if (right n arr[right] arr[largest]) {largest right;}// 如果最大值不是根节点则交换并继续堆化if (largest ! i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);} }// 主函数使用堆排序对数组进行排序 void heapSort(vectorint arr) {int n arr.size();// 构建最大堆for (int i n / 2 - 1; i 0; i–) {heapify(arr, n, i);}// 一个个取出元素进行排序for (int i n - 1; i 0; i–) {// 将当前堆顶最大值移到数组末尾swap(arr[0], arr[i]);// 调整剩余堆heapify(arr, i, 0);} }int main() {vectorint arr {12, 11, 13, 5, 6, 7};heapSort(arr);cout 排序后的数组: ;for (int i : arr) cout i ;return 0; } // 输出: 5 6 7 11 12 13 查找算法 查找算法用于在数据集合中寻找特定元素常见的查找算法有 顺序查找逐个检查每个元素复杂度为 O(n)适用于无序数据。 #include iostream #include vector using namespace std;int linearSearch(const vectorint arr, int target) {for (int i 0; i arr.size(); i) {if (arr[i] target) {return i; // 找到目标元素返回其索引}}return -1; // 未找到返回 -1 }int main() {vectorint arr {10, 20, 30, 40, 50};int target 30;int index linearSearch(arr, target);if (index ! -1)cout 元素 target 在索引 index 处;elsecout 元素未找到;return 0; } // 输出: 元素 30 在索引 2 处 二分查找要求数据有序通过不断将搜索范围缩小一半复杂度为 O(logn)。 #include iostream #include vector using namespace std;int binarySearch(const vectorint arr, int target) {int left 0, right arr.size() - 1;while (left right) {int mid left (right - left) / 2;if (arr[mid] target) {return mid; // 找到目标值返回索引}if (arr[mid] target) {left mid 1; // 目标值在右半部分} else {right mid - 1; // 目标值在左半部分}}return -1; // 未找到返回 -1 }int main() {vectorint arr {10, 20, 30, 40, 50};int target 40;int index binarySearch(arr, target);if (index ! -1)cout 元素 target 在索引 index 处;elsecout 元素未找到;return 0; } // 输出: 元素 40 在索引 3 处 哈希查找通过散列函数将键值直接映射到位置查找效率高但需要合理的哈希函数和冲突处理策略。 #include iostream #include unordered_map using namespace std;int hashSearch(const unordered_mapint, int hashTable, int target) {if (hashTable.find(target) ! hashTable.end()) {return hashTable.at(target); // 找到目标值返回索引}return -1; // 未找到返回 -1 }int main() {vectorint arr {10, 20, 30, 40, 50};unordered_mapint, int hashTable;// 将数组元素存入哈希表中键为元素值值为索引for (int i 0; i arr.size(); i) {hashTable[arr[i]] i;}int target 30;int index hashSearch(hashTable, target);if (index ! -1)cout 元素 target 在索引 index 处;elsecout 元素未找到;return 0; } // 输出: 元素 30 在索引 2 处 递归算法 递归是指一个函数调用自身的方式适合解决结构相似的问题。常见的递归算法包括斐波那契数列、阶乘计算、全排列等。 递归的基本思想是将问题分解成更小的子问题。实现递归算法时必须定义好递归出口以避免无限递归。 分治算法 分治法将大问题分解成多个小问题分别求解再将小问题的解合并得到原问题的解。快速排序和归并排序就是典型的分治法应用。 分治算法的一般步骤为 将大问题划分为若干子问题递归解决每个子问题合并子问题的结果。 动态规划 动态规划是一种将复杂问题分解为多个子问题通过保存子问题的解避免重复计算的策略适合有重叠子问题和最优子结构的情况。 常见动态规划问题有背包问题、最长公共子序列、矩阵链乘法等。 贪心算法 贪心算法是一种每一步选择当前最优解的策略适合求解一些局部最优即全局最优的问题。例如活动选择问题、最小生成树Prim算法和Kruskal算法等。 复杂度分析 算法复杂度分为时间复杂度和空间复杂度。 时间复杂度衡量算法执行时间随输入规模增长的变化。常见的时间复杂度有常数阶 O ( 1 ) O(1) O(1)、对数阶 O ( l o g n ) O(logn) O(logn)、线性阶 O ( n ) O(n) O(n)、平方阶 O ( n 2 ) O(n^2) O(n2) 等。空间复杂度衡量算法运行时所需的额外空间。需要在设计算法时平衡时间和空间的效率。