GESP-C++五级 题库
插入排序的时间复杂度总是比快速排序低。
插入排序的时间复杂度为O(n2),快速排序的均摊时间复杂度为O(nlogn),但是快速排序的最坏情况下,时间复杂度也是O(n2)
引入分治策略往往可以提升算法效率。一方面,分治策略减少了操作数量;另一方面,分治后有利于系统的并行优化。
分治算法的思想就是把问题划分成子问题,然后继续划分,知道子问题可以直接解决,然后合并子问题得到的结果,推得原问题的答案,分治提高了算法的效率,减少了操作数量。
在C++语言中,递归的实现方式通常会占用更多的栈空间,可能导致栈溢出。
递归用占用栈空间,而栈空间往往不是很大,递归层数过多的时候,可能会导致栈溢出。
对于已经定义好的标准数学函数 sin(x) ,应用程序中的语句 y=sin(sin(x)); 是一种递归调用。
递归是指的函数不断的调用自身,直到当前传参可以得到结果,并返回结果,递归应该是一个从大问题到小问题的分解,然后小问题有了结果并返回,解决大问题,而这个写法只能算是函数嵌套使用。
如果将双向链表的最后一个结点的下一项指针指向第一个结点,第一个结点的前一项指针指向最后一个结点,则该双向链表构成循环链表。
如果将双向链表的最后一个节点的next 指针指向第一个节点,同时第一个节点的prev 指针指向最后一个节点,那么这个双向链表就形成了一个循环链表
数组和链表都是线性表,链表的优点是插入删除不需要移动元素,并且能随机查找。
链表只能顺序访问。为了找到某个节点,需要从头节点开始遍历直到找到目标节点
链表的存储空间物理上可以连续,也可以不连续。
链表中的每个节点包含两部分信息:数据域(存储数据的部分)和指针域(指向下一个节点的指针)。这种指针连接方式使得链表的节点可以在内存中分布不连续,链表的节点可以根据内存管理系统的分配方式,分布在内存中的任何位置。每个节点的指针用于指向下一个节点,这种指针关系决定了链表的逻辑结构。因此,链表在物理存储上可以是连续的,也可以是不连续的,这取决于节点之间的指针关系,而不是在内存中的实际布局方式。
找出自然数n以内的所有质数,常用算法有埃拉托斯特尼(埃氏)筛法和线性筛法,其中埃氏筛法效率更高。
埃氏筛法是一种简单直观的质数筛选算法,适用于较小范围内的质数查找,随着 n 的增大,其效率会下降,因为需要标记的倍数越多。线性筛法是在埃氏筛法基础上的改进,效率更高。
唯一分解定理表明任何一个大于1的整数都可以唯一地表示为一系列质数的乘积,即质因数分解是唯一的。
一个整数可以有多种因数分解的方式(比如顺序不同),但其包含的质数因子及其指数是唯一确定的。
贪心算法通过每一步选择局部最优解来获得全局最优解,但并不一定能找到最优解。
它通常在每一步做出局部最优选择,并希望通过这种方式最终达到全局最优解。然而,并不是所有问题都适合使用贪心算法,并且即使某些问题可以使用贪心算法,它也不能保证一定能找到全局最优解。
归并排序和快速排序都采用递归实现,也都是不稳定排序。( )(2024.6-5)
归并排序是一种稳定的排序算法,快速排序是一种不稳定的排序算法
插入排序有时比快速排序时间复杂度更低。
插入排序在处理少量元素或部分有序数组时,由于其较低的时间复杂度可能比快速排序效率更高,而快速排序通常在处理大规模随机数据时表现更佳
在进行全国人口普查时,将其分解为对每个省市县乡来进行普查和统计。这是典型的分治策略。
分治策略的基本思想是将一个大问题分解为若干个小问题,然后分别解决这些小问题,最后将它们的解合并起来得到整体的解。在人口普查中,各个地区的普查可以看作是对小问题的解决,最后将各地的数据统计合并,得到全国的人口统计数据
在下面C++代码中,由于删除了变量 ptr ,因此 ptr 所对应的数据也随之删除,故执行下述代码时,将报错。
删除指针ptr并不会删除数据本身,只是释放了指针指向的动态内存